51–60 of 86 posts
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 ?)
In any case lock-free is defined in term of progress guarantees.
You can get embarassingly parallel performance if you split your data by thread and aggregate periodically.
If you need a consistent view of your entire set of data, that is a slow path with sharding.
In my experiments with multithreaded software I simulate a bank where many bankaccounts are randomly withdrawn from and deposited to. https://github.com/samsquire/multiversion-concurrency-contro...
ShardedBank.java
ShardedBank2.java
ShardedBankNonRandom.java
ShardedHashMap.java
ShardedNonRandomBank2.java
ShardedTotalOrder.java
ShardedTotalRandomOrder.java
I am also experimenting with left-right concurrency control which trades memory usage for performance, it basically keeps two copies of data, one that is currently being read and written to and another inactive copy that is not active. You switch the data structures around periodically to "make changes visible" to that thread.
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…
In particular, the "cost of synchronization" is roughly the price of a L3 memory read/write, or ~50 cycles. In contrast, a read/write to L1 cache is like 4 cycles latency and can be done multiple times per clock tick, and you can go faster (IE: register space).
So an unsynchronized "counter++" will be done ~4-billion times a second.
But a "counter++; sync()" will slow you down 50x slower. That is to say, the "sync()" is the "expensive part" to think about.
------------
A lock is two sync() statements. One sync() when you lock, and a 2nd sync() when you unlock. Really, half-sync() since one is an acquire half-sync and the other is a release half-sync.
If your lock-free data structure uses more than two sync() statements, you're _probably_ slower than a dumb lock-based method (!!!). This is because the vast majority of lock()/unlocks() are uncontested in practice.
So the TL;DR is, use locks because they're so much easier to think about. When you need more speed, measure first, because it turns out that locks are really damn fast in practice and kind of hard to beat.
That being said, there's other reasons to go lock-free. On some occasions, you will be forced to use lock-free code because blocking could not be tolerated. (Ex: lock-free interrupts. Its fine if the interrupt takes a bit longer than expected during contention). So in this case, even if lock-free is slower, the guarantee for forward progress is what you're going for, rather than performance.
So the study of lock-free data-structures is still really useful. But don't always think of for performance reasons, because these data-structures very well will be slower than std-library + lock() in many cases.
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…
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…
Pikus has a number of C++ Parallelism performance talks that discusses this issue. In particular, the "cost of synchronization" is roughly the price of a L3 memory read/write, or ~50 cycles. In contrast, a read/write to L1 cache is like 4 cycles latency and can be done multiple times per clock tick, and you can go faster (IE: register space). So an unsynchronized "counter++" will be done ~4-billion times a second. Bu…
Separately fences and atomic RMWs are slower than plain read/writes, but that's because of the (partially) serialising effects they have on a CPU pipleline, and very little todo with L3 (or any memory) latency.
Case in point: A CAS on intel is 20ish cycles, the L3 latency is 30-40 cycles or more. On the other hand you can have multiple L3 misses outstanding, but CAS hardly pipelines.
Earlier quoted context omitted.
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.
That's my understanding too. In Linux mutexes are implemented by futexes (Fast User-Space mutexes). If there is no contention they are guaranteed to not perform a syscall https://en.wikipedia.org/wiki/Futex
Earlier quoted context omitted.
That's my understanding too. In Linux mutexes are implemented by futexes (Fast User-Space mutexes). If there is no contention they are guaranteed to not perform a syscall https://en.wikipedia.org/wiki/Futex
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.
https://github.com/lattera/glibc/blob/master/nptl/pthread_mu...
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 instructions should compare 128 bits and swap 128 bits.
I don't know why 'good' algorithms would use these if they don't need to, because 128 bit operations are slower.
Not only that, 128 bit compare and swap doesn't work if it is not 128 bit aligned while 64 bit compare and swap will work even if they aren't 64 bit aligned.
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…
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…
Computers are shockingly complex. I can't tell you how many times I've reasoned about a system, ran the profiler, and discovered I was completely wrong.
When I was working on an interpreter for a Lisp, I implemented my first cut of scopes (all the variables within a scope and their values) as a naive unsorted list of key/value pairs, thinking I'd optimize later. When I came back to optimize, I reimplemented this as a hashmap, but when I ran my test programs, to my horror, they were all 10x slower. I plugged in a hashmap library used in lots of production systems and got a significant 2x performance gain, which was still slower than looping over an unsorted list of key/value pairs. The fact is, most scopes have Reasoning didn't lead me to the correct answer, observation did.
Returning to parallel data structures, the fact is, I don't know why lock-free structures are faster than mutex-based structures, I just know that they are in every situation where I've profiled them.
Reasoning isn't completely useless--reasoning is how you intuit what you should be profiling. But if you're just reasoning about how two alternatives will perform and not profiling them in real-life production systems you're wasting everyone's time.
Earlier quoted context omitted.
Pikus has a number of C++ Parallelism performance talks that discusses this issue. In particular, the "cost of synchronization" is roughly the price of a L3 memory read/write, or ~50 cycles. In contrast, a read/write to L1 cache is like 4 cycles latency and can be done multiple times per clock tick, and you can go faster (IE: register space). So an unsynchronized "counter++" will be done ~4-billion times a second. Bu…
A sync, assuming it is your typical memory barrier, is not bound by the L3 latency. You pay (in first approximation) the L3 cost when you touch a contended cache line, whether you are doing a plain write or a full atomic CAS. Separately fences and atomic RMWs are slower than plain read/writes, but that's because of the (partially) serialising effects they have on a CPU pipleline, and very little todo with L3 (or any…
So here's what I know. L1 / L2 caches are "inside the core". To talk to other cores, your data must leave L1/L2 cache and talk to a network. It is on _THIS_ network that the L3 cache exists.
Its not really "L3 cache", its just the memory-network that implements the MOESI protocol (or whatever proprietary variant: MOESIF or whatever) that sits between L2 cache, L3 cache, and core-to-core communications. So I don't want to make it sound like "You're waiting on L3 cache", because you're right. Its not really related to L3 cache.
So I don't really know how that network works (I know the high-level details of MOESI, but I also know that's the textbook explanation and the real world is way more complex), aside from "It'd be roughly on the same order-of-magnitude cost" as the L3 cache.
-------
What's really going on, is that Core#1 is talking to all the other cores and basically performing "git pull" and "git push" to the data asynchronously. Core#1 prefers to perform "git checkin" and "git checkout" (aka: talk to L1/L2 cache), because that's faster.
But when Core#1 does a full sync (git push/git pull), it is required to talk on the network that leads to other cores and/or L3 cache.
Those "git push / git pull" messages are MOESI (F and others), meaning Modified/Owned/Exclusive/Shared/Invalid (and Forwarding, and other proprietary states). Which line up to version-control way better than most people expect.