Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A collection of lock-free data structures written in standard C++11

github.com

Post reply on HN
Print view View original

41–50 of 86 posts

Re: A collection of lock-free data structures written in standard C++11

#41

Post by cjensen »

An issue in C++ is that it only supports atomic changes to the builtin types. For example, you can only CAS a 64-bit value if your largest integer/pointer type is 64-bits.

Good lock free algorithms use double-width instructions like cmpxchg16b which compare 64-bits but swap 128-bits. You can then use the compared 64-bits as a kind of version number to prevent the a-b-a problem.

Using only the built-in atomics is working with a hand tied behind your back. With the wider version, it's trivial to write multi-producer multi-consumer stacks with no limits to the number of objects stored. It's also pretty easy (if you copy the published algorithm) to do the same with queues.

Re: A collection of lock-free data structures written in standard C++11

#42

Post by dnedic »

cjensen wrote: post #41

An issue in C++ is that it only supports atomic changes to the builtin types. For example, you can only CAS a 64-bit value if your largest integer/pointer type is 64-bits. Good lock free algorithms use double-width instructions like cmpxchg16b which compare 64-bits but swap 128-bits. You can then use the compared 64-bits as a kind of version number to prevent the a-b-a problem. Using only the built-in atomics is work…

True, that would help immensely in creating MPMC data structures, but as these are SPSC there is no problem. Also to clarify, this is only for the indexes, the data members can be anything.

Using these intrinsics or inline assembly would break portability or create situations where platforms have different feature levels, which is not something I intend to do. I want the library to be compatible with everything from a tiny MCU to x86.

Re: A collection of lock-free data structures written in standard C++11

#43

Post by maldev »

planede wrote: post #4
bluGill wrote: post #2

From the FAQ: > The biggest reason you would want to use a lockfree data structure in such a scenario would be performance. Locking has a non-neglegible runtime cost on hosted systems as every lock requires a syscall. This is misleading. While a lock does have a runtime cost, in some cases that cost is less than all the force CPU cache synchronization calls that lock free needs to do. With a lock you only have to syn…

Moreover, is "every lock requires a syscall" accurate? Probably depends on target platform and standard library, but my impression was that at low contention it doesn't really require syscalls, at least on Linux and glibc's pthread.

You can literally just do an atomic swap on some memory location. Three lines of assembly, like.

    mov rax, 1  ; load the value to exchange into rax
   acquire_lock:
    ; attempt to acquire the lock
    xchg byte [ADDR_LOCK], al  ; atomically swap the lock value with rax
    test al, al  ; test if the original lock value was 0 (unlocked)
    jnz acquire_lock  ; if it was not, loop until we can acquire the lock
The downside is you want a backoff to sleep the thread so it doesn't go into a loop. But the actual lock code is simple. You can easily have this be your function "AcquireLock()" and then do

while(!AcquireLock()) { //pause thread execution. }

And I think this is where they get the syscall being needed, since this will normally require a syscall to pause the thread from the scheduler.

Re: A collection of lock-free data structures written in standard C++11

#44

Post by jcelerier »

andersced wrote: post #7

Should be benchmarked against -> https://github.com/Deaod/spsc_queue If proven faster OK.. If not.. Well.. back to the drawing board. I gave it a try -> https://github.com/andersc/fastqueue Deaod is the kingpin.

https://max0x7ba.github.io/atomic_queue/html/benchmarks.html for an existing set of benchmarks where this could be added

Re: A collection of lock-free data structures written in standard C++11

#45

Post by gpderetta »

cjensen wrote: post #41

An issue in C++ is that it only supports atomic changes to the builtin types. For example, you can only CAS a 64-bit value if your largest integer/pointer type is 64-bits. Good lock free algorithms use double-width instructions like cmpxchg16b which compare 64-bits but swap 128-bits. You can then use the compared 64-bits as a kind of version number to prevent the a-b-a problem. Using only the built-in atomics is work…

Actually C++ only requires TriviallyComparable for std::atomic. The issue with 2CAS is that intel until very recently only provided cmpxchg16b[1] but no 128 atomic load and stores: SSE 128 bit memory operations were not guaranteed to be atomic (and in fact were observed not to be on some AMDs).

So a 128 bit std::atomic on intel was not only suboptimal as the compiler had to use 2cas for load and stores as well, but actually wrong as an atomic load from readonly memory would fault. So at some point the ABI was changed to use the spinlock pool. Not sure if it has changed since.

If you do it "by hand", when you only need a 2cas, a 128 bit load that is not atomic is fine as any tearing will be detected by the CAS and 'fixed', but it is hard for the compiler to optimize generic code.

[1] which actually does full 128bit compare and swap, you are probably confusing it with the Itanium variant.

Re: A collection of lock-free data structures written in standard C++11

#46

Post by aseipp »

cjensen wrote: post #41

An issue in C++ is that it only supports atomic changes to the builtin types. For example, you can only CAS a 64-bit value if your largest integer/pointer type is 64-bits. Good lock free algorithms use double-width instructions like cmpxchg16b which compare 64-bits but swap 128-bits. You can then use the compared 64-bits as a kind of version number to prevent the a-b-a problem. Using only the built-in atomics is work…

The lack of DWCAS as a primitive in general is really annoying, C++ aside. RISC-V's -A extension has no form of it, either; you only get XLEN-sized AMO + LL/SC (no 2*XLEN LL/SC either!)

It's one of those features that when you want it, you really really really want it, and the substitutions are all pretty bad in comparison.

Re: A collection of lock-free data structures written in standard C++11

#47

Post by kilotaras »

- A lot of code won't work for types with no default constructors, but that is at least compile error

- Using memcpy[0] for arbitrary types is just wrong, see [1]

[0] https://github.com/DNedic/lockfree/blob/main/lockfree/inc/bi...

[1] https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p11...

Re: A collection of lock-free data structures written in standard C++11

#48

Post by dnedic »

kilotaras wrote: post #47

- A lot of code won't work for types with no default constructors, but that is at least compile error - Using memcpy[0] for arbitrary types is just wrong, see [1] [0] https://github.com/DNedic/lockfree/blob/main/lockfree/inc/bi... [1] https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p11...

This is already noted in the Queue readme, only the Queue constructs the type, the other 2 data structures are meant for PODs only.

I will take a look at adding support for constructing in-place for the other 2 data structures, but at the moment, they are just for PODs.

Re: A collection of lock-free data structures written in standard C++11

#49

Post by bluGill »

josephg wrote: post #29
ot wrote: post #9

Earlier quoted context omitted.

This is true in principle and it is good calling it out, but in practice I've never seen a mutex-based data structure beat an equivalent lock-free data structure, even at low contention, unless the latter is extremely contrived. A mutex transaction generally requires 2 fences, one on lock and one on unlock. The one on unlock would not be strictly necessary in principle (on x86 archs the implicit acquire-release seman…

Are there any good benchmarks which demonstrate the performance characteristics you’re talking about? Or case studies where an application moved from mutexes to lock free data structures, and compared the resulting performance?

This is impossible to do in a useful way for publication. You can do case studies, but minor changes in various factors that seem minor can make a massive difference in benchmarks. As such you need to find real world data, used in a real world scenario, for your application: then benchmark it. Even then you have a benchmark useful for your application only, and not worth publishing.

Re: A collection of lock-free data structures written in standard C++11

#50

Post by jylam »

Maybe I don't understand the concept, but aren't lock-free structures "just" delegating the locking mechanism to the CPU via atomic operations ? (although even if that's the case I can understand the speedup) (and if so, why aren't all those lockfree structures the default, instead of using mutexes ?)
Post reply on HN