12 ms·

This is similar to how java.util.concurrent.atomic.LongAdder works: https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/concurrent

This is similar to how java.util.concurrent.atomic.LongAdder works: https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/concurrent/atomic/LongAdder.java https://github.com/openjdk/jdk/blob/master/src/java.base/sha...

BeeOnRope 2y ago
Yeah exactly, and this is a commonly used trick in concurrent data structures in general. The Java implemenation has the additional twist that they don't use a fixed number of "slots" but rather start at 1 and use CAS failures as a mechanism to detect contention and then grow the number of slots until there are no longer CAS failures.
o11c 2y ago
Huh, that's ... still quite inefficient. Since a multiple variables in a cache line is fine if all will be accessed from the same cpu, you ideally want a separate allocator for that, then you can avoid all the spooky dynamic growth. And most CPUs offer a direct "atomic add" instruction which is much faster than a CAS loop. For pure stat counters you generally want `relaxed` memory ordering on that; for other cases acquire and/or release may be desired (this is tricky to get performance-optimal given that some platforms upgrade to a stronger memory ordering for free so it's best to require it in your algorithm, whereas others are best with an explicit fence in the edge case). I've never found a real-world use for `seq_cst`. It's unfortunate that per-cpu variable are difficult in userland, but there are at least 2 ways to fully emulate them - rseq and pinning - and you can also just revert to full-blown thread-locals (which have much better tooling support) if you aren't constructing a gratuitously large number of threads, or shared thread-locals if you do have a lot of threads. If you make the wrong choice here, correctness never suffers, only performance.
- BeeOnRope 2y ago
  Uncontended CAS without carried dependendies on the result (almost always the case in this use case) are similar in performace to atomic add on most platforms. The CAS is the price they pay for contention detection, though it would be interesting to consider solutions which usually use unconditional atomics with only the occasional CAS in order to check contention, or which relied on some other contention detection approach (e.g., doing a second read to detect when the value incremented by more than your own increment). The solution looks reasonable to me given the constraints.
  - o11c 2y ago
    Part of my point was that "check for contention" is often a silly thing to do in the first place, when you can just avoid it entirely (and with simpler code too). Admittedly, Java is fundamentally incapable of half of the solutions, but making a simple bump allocator (called once per statistic at startup) over per-thread arrays is still possible.

BeeOnRope 2y ago

Yeah exactly, and this is a commonly used trick in concurrent data structures in general. The Java implemenation has the additional twist that they don't use a fixed number of "slots" but rather start at 1 and use CAS failures as a mechanism to detect contention and then grow the number of slots until there are no longer CAS failures.

o11c 2y ago

Huh, that's ... still quite inefficient. Since a multiple variables in a cache line is fine if all will be accessed from the same cpu, you ideally want a separate allocator for that, then you can avoid all the spooky dynamic growth. And most CPUs offer a direct "atomic add" instruction which is much faster than a CAS loop. For pure stat counters you generally want `relaxed` memory ordering on that; for other cases acquire and/or release may be desired (this is tricky to get performance-optimal given that some platforms upgrade to a stronger memory ordering for free so it's best to require it in your algorithm, whereas others are best with an explicit fence in the edge case). I've never found a real-world use for `seq_cst`. It's unfortunate that per-cpu variable are difficult in userland, but there are at least 2 ways to fully emulate them - rseq and pinning - and you can also just revert to full-blown thread-locals (which have much better tooling support) if you aren't constructing a gratuitously large number of threads, or shared thread-locals if you do have a lot of threads. If you make the wrong choice here, correctness never suffers, only performance.

BeeOnRope 2y ago
Uncontended CAS without carried dependendies on the result (almost always the case in this use case) are similar in performace to atomic add on most platforms. The CAS is the price they pay for contention detection, though it would be interesting to consider solutions which usually use unconditional atomics with only the occasional CAS in order to check contention, or which relied on some other contention detection approach (e.g., doing a second read to detect when the value incremented by more than your own increment). The solution looks reasonable to me given the constraints.
- o11c 2y ago
  Part of my point was that "check for contention" is often a silly thing to do in the first place, when you can just avoid it entirely (and with simpler code too). Admittedly, Java is fundamentally incapable of half of the solutions, but making a simple bump allocator (called once per statistic at startup) over per-thread arrays is still possible.