71–80 of 86 posts
Earlier quoted context omitted.
The code isn't the easiest to read but in glibc it seems that the syscall is only performed if waiters are detected in userspace during an unlock operation https://github.com/lattera/glibc/blob/master/nptl/pthread_mu...
Indeed You only need to FUTEX_WAKE if you know there are waiters (or of you lost track of the number of waiters).
Earlier quoted context omitted.
If you are going to do batch operations, your data structure should be optimized to support them, so you're back to one CAS. The same would apply to the locked scenario, where you probably don't want to copy 1000 elements in the critical section. About the sufficiently smart optimizations, sure, everything is easy to imagine, but in my experience this never happened, and I'd be curious to hear practical examples if y…
Here's one I had: I was trying to build a Bloom filter in parallel. Each thread had large-ish batches of hashes it wanted to insert into the filter. Naively, you'd just have each thread iterate through the batches and do __sync_fetch_and_or for each of the hashes (this was a register-blocked Bloom filter so we only needed to perform one 8-byte or operation per hash). What ended up being MUCH faster was to partition t…
Earlier quoted context omitted.
Indeed You only need to FUTEX_WAKE if you know there are waiters (or of you lost track of the number of waiters).
What can cause the mutex to lose track of the number of waiters?
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 a…
It hasn't, Clang/GCC emit a cmpxchg16b only if you opt-in with `-mcx16`, which changes the ABI.
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 a…
Earlier quoted context omitted.
Maybe this has changed, but last time I looked at futexes there was no syscall for locking (assuming no contention), but unlocking always made a syscall. This was many years ago so it could be different now.
The code isn't the easiest to read but in glibc it seems that the syscall is only performed if waiters are detected in userspace during an unlock operation https://github.com/lattera/glibc/blob/master/nptl/pthread_mu...
https://doc.rust-lang.org/src/std/sys/unix/locks/futex_mutex...
Unlock is just:: self.futex.swap(0, Release) -- if the value we get back is 2 then we know at least one thread is asleep waiting on this futex, so we need a system call to wake them, but in the uncontended case we're done immediately.
Every datastructure is lock free. Locks are required when you have multiple writers. The article states the usefull only for certain circumstance: for single consumer single producer scenarios. So yea within these assumptions you can make something work.
Earlier quoted context omitted.
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?
https://youtu.be/_qaKkHuHYE0 (CppCon) A senior software engineer at Google tried to optimize tcmalloc by replacing a mutex with lockless MPMC queue. After many bugs and tears, the result is not statistically significant in production systems.
But I guess this was only one part and malloc wouldn't be fully lockfree.
In any case the lockfree mallocs designs I have seen use NxN queues to shuffle buffers around, but I guess it would be unsuitable for a generic malloc.
Earlier quoted context omitted.
Here's one I had: I was trying to build a Bloom filter in parallel. Each thread had large-ish batches of hashes it wanted to insert into the filter. Naively, you'd just have each thread iterate through the batches and do __sync_fetch_and_or for each of the hashes (this was a register-blocked Bloom filter so we only needed to perform one 8-byte or operation per hash). What ended up being MUCH faster was to partition t…
This seems to me like a parallel accumulation problem, why not have each thread accumulate a filter on a subset of the data (so no locking involved), and then reduce the results (which is just an OR of all the local accumulations)?
The locking strategy very rarely had any reduction in parallelism due to the randomized lock-taking.
There were also other reasons, such as not wanting to replicate the filter per-thread.
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…