15 ms·

A single line of code made a 24-core server slower than a laptop

617 points by Ygg2 5y ago

PhileinSophia 5y ago
physicsgraph 5y ago
This article is a well-written deep dive on parallel performance debugging that ends up identifying the difference being due to how caching is handled on multi-CPU vs single-CPU systems. Thanks to the author for taking time to write up their troubleshooting process description.
- bhauer 5y ago
  Agreed. I appreciate the author adding the small effort to briefly describe the idiosyncratic pieces (e.g., Rune) in their unique problem space. So often, writers believe their readers all play in a similar problem space. So they elect to leave understanding such idiosyncrasies for the reader to either dig deeper on their own, or self-select out of reading altogether.
chrisaycock 5y ago
The culprit was a shared atomic reference counter (Arc). The cache invalidation across cores eliminated any kind of scaling via multiple threads. The solution is to stop sharing. The author had to make changes specific to this codebase for each thread to have its own copy of the offending dataset.
- denysvitali 5y ago
  Awesome TL;DR! I read the full article but this summarizes it well. The article is anyways worth a full read
- divs1210 5y ago
  Immutable collections save the day!
  - Thiez 5y ago
    Immutable collections wouldn't really help here since Rust does not have a garbage collector, so they would still be wrapped in an `Arc<T>`, or use one internally. Unless you're giving each thread their own copy of the immutable collection, in which case the immutability doesn't really add much.
    - ericbarrett 5y ago
      You're right if they're wrapped in an Arc<T>. But it's a lot easier to confidently clone an immutable data structure to threads/async functions because you know they won't be mutated by other cores. If you're cloning mutable data, you'll have to collect each "shard" at the end of whatever runtime loop your program has, and merge them back into the authoritative model. (Or drop the changes, but then why make the data mutable?) Gets hairy.
- amelius 5y ago
  Or use a language with a good concurrent garbage collector.
  - dagmx 5y ago
    What language wouldn't hit this issue? The second you have an atomic write across multiple numa clusters you'll hit this. Edit: it appears they're talking specifically about the ref counting whereas I was considering the entirety of a shared context. That clarification helps me understand where their statement was coming from
    - amelius 5y ago
      The problem was caused by a memory management primitive. This wouldn't be an issue in a runtime with a GC designed for concurrent loads.
      - dagmx 5y ago
        How would the GC avoid the atomic lock and cache invalidation across numa boundaries? What language has a sufficiently lock less rw capable GC? Edit: to clarify I was thinking about a mutable context share as shown in the code example, not solely about the ref counting.
        amelius 5y ago
        GoLang. It was designed for highly concurrent loads. For an overview of history and technology involved, read e.g.: https://blog.twitch.tv/en/2016/07/05/gos-march-to-low-latency-gc-a6fa96f06eb7/ https://blog.twitch.tv/en/2016/07/05/gos-march-to-low-latenc...
        dagmx 5y ago
        Edit: another comment explains that you're likely talking about just the ref counting aspect rather than the entire context sharing used by the rune code shown, in which case, yes I see why a concurrent GC would avoid the issue in that scenario. ---------- I'm familiar with Go's GC. Your linked post doesn't explain how it would avoid the hit mentioned by the cache invalidation across multiple clusters. It'll either try and put multiple go routines on a single cluster (as listed in the link) or it'll need to copy the necessary stack per thread. Which is effectively what the original article ends up doing. But if you encounter anything that needs to run concurrently across threads while using a single r/w object, you'll hit the same cliff surely?
- klabb3 5y ago
  The issue is that Rust doesn't allow static borrowing across thread boundaries (except for globals), which necessitates cloning the arc. This is why they chose to instead copy the contents and use thread locals (may be wrong - skimmed the article). I've had this complaint for over a year, and nobody is addressing it. Arcs are absolutely ubiquitous, it can come back and bite anytime, it's just very hard to know upfront where a bottleneck is and most people will never profile to this extent. I really wish Rust would reconsider the decision to throw its hands up at non-lexical destruction guarantees. This is related to the thread::scoped removal from 2015 (IIRC), after which mem::forget was added. Anyway, I'm rambling. There's tons to read for the curious. The simplest mitigation right now is to clone arcs only when necessary, and instead use static references of those arcs whenever possible (especially hot paths). It's a mess for refactors and easy to miss, but better than nothing.
  - Thiez 5y ago
    > I really wish Rust would reconsider the decision to throw its hands up at non-lexical destruction guarantees. This is related to the thread::scoped removal from 2015 (IIRC), after which mem::forget was added. Anyway, I'm rambling. There's tons to read for the curious. I think the original argument that leaking memory using safe code by building a reference cycle is still valid. The language would have to change significantly to prevent that, so either reference counting must be unsafe, or we accept that destruction cannot be guaranteed just because something goes out of scope. That is why `forget` is safe.
    - lilyball 5y ago
      The general solution here is to use scopes instead of RAII to ensure destruction. Rust lost its thread::scoped libstd API because that was based on RAII, but there are multiple crates in the ecosystem that provide the lexical scope-based solution
    - klabb3 5y ago
      This is indeed the reason often cited, but it's more nuanced than that. If cycle forming ref types had a lifetime param, you could guarantee destruction at a lifetime level, a weaker but highly useful guarantee. In fact one proposal at the time was to add a lifetime param to Arc and Rc, but it was rejected because it had such big impact and the team was stressed about the 1.0 release. If you look at the various crates that offer static borrowing across threads today, they use lexical scope and they are perfectly safe and guarantee destruction IFF the inner scopes terminate (which is exactly the guarantee you want). However, they are too restrictive to be useful.
twoodfin 5y ago
In situations like this, it’s valuable to know about all the event types perf can sample beyond CPU cycles, including cache misses at various levels and branch mis-predictions. These can go right into flamegraphs as well.
deleted 5y ago
[deleted]
bob1029 5y ago
> The fact that our reference counters are atomic is an additional problem that makes things even more complex for the processor. Although using atomic instructions is often referred to as “lockless programming”, this is slightly misleading – in fact, atomic operations require some locking to happen at the hardware level. This locking is very fine-grained and cheap as long as there is no congestion, but as usual with locking, you may expect very poor performance if many things try to fight for the same lock at the same time. And it is of course much worse if those “things” are whole CPUs and not just single cores that are close to each other. Contention is the devil and you can never hide from it if you bring it into your life. The fastest "contention avoidance hack" would be the CAS operation as mentioned above, which still performs approximately 2 orders of magnitude slower than a single threaded operation would in the most adverse scenarios. If you aren't sure of which problems actually "fit" on a modern x86 thread these days, rest assured that many developers in fintech have been able to squeeze entire financial exchanges onto one: https://lmax-exchange.github.io/disruptor/disruptor.html https://lmax-exchange.github.io/disruptor/disruptor.html For most scenarios, you really don't need all those damn cores. They are almost certainly getting in the way of you solving your problems.
- cecilpl2 5y ago
  Games are a prime example of systems which must take advantage of all possible hardware resources.
  - bob1029 5y ago
    The fact that we believe this is probably part of the problem with game development today.
  - dagmx 5y ago
    Games similarly struggle with multi core/ccx designed chips. Battlefield 4 was famously terrible on Ryzen when AMD first released it.
    - littlecranky67 5y ago
vlovich123 5y ago
Is there any tooling that can demonstrate cache coherency hotspots like cache line bouncing or inter-core communication?
- maxwell86 5y ago
  Yes. Linux perf has a c2c hit modify “mode”/“option” that will report precisely this issue.
  - loeg 5y ago
    What is c2c? Thanks.
    - eptcyka 5y ago
      Cache to cents? Kernels 2 cents on how your code is utilizing the cache? I have 0 clue too.
      - masklinn 5y ago
        Cache to Cache, It tracks a bunch of cache-related counters, and HITM (hit modify) tracks loads of data modified by either an other core of the same node ("local hitm") or by an other node entirely ("remote hitm"). Here, the contention would have shown up as extreme amounts of both, as each core would almost certainly try atomically updating a value which had just been updated by an other core, with higher than even chances the value had been updated by a core of the other socket (= node).
    - tkhattra 5y ago
      c2c stands for cache-2-cache. perf-c2c allows you to measure cacheline contention - see https://man7.org/linux/man-pages/man1/perf-c2c.1.html https://man7.org/linux/man-pages/man1/perf-c2c.1.html and https://joemario.github.io/blog/2016/09/01/c2c-blog/ https://joemario.github.io/blog/2016/09/01/c2c-blog/.
      - 5y ago
cheschire 5y ago
There are only two hard things in Computer Science: cache invalidation and naming things. - Phil Karlton
- hnaccount_rng 5y ago
  You missed the off-by-one errors
  - cheschire 5y ago
    So you mean I was off by one?
- Pet_Ant 5y ago
  Better version: There are only two hard things in Computer Science: cache invalidation, naming things, and off-by-one errors.
  - jahnu 5y ago
    There are only two hard things in Computer Science: cache invalidation, naming things, and off-by-oly two hard things in Computer Scivetëm� dy gjëra të vështira në Shkencën Komp��jute
    - jacquesm 5y ago
      Hehe. Ok. That is very funny :)
      - gavinray 5y ago
        I don't get it -- am I slow?
        jacquesm 5y ago
        Buffer overflow :)
        5y ago
Thiez 5y ago
Is this the kind of situation where assigning a core affinity to the various threads would have made a difference (to make sure they all run on the same physical processor), or is the mere presence of another processor enough to trigger the behavior shown in the article?
- deleted 5y ago
  [deleted]
- loeg 5y ago
  No, that would not make a significant difference here. The problem is that the same line has to bounce around all of the threads that share it; pinning doesn’t reduce that very much on this time-scale. Thread migrations will be very infrequent relative to atomic operations, especially when the number of runnable threads is lower than number of physical cores.
- hermitdev 5y ago
  I don't think core affinity would have helped in this situation. They had one instance that was being shared across all cores, necessitating the reference count to be sync'd between sockets at L3 cache level. They may have seen some benefit if you had, say, 2 instances, one per CPU socket, and dedicated an instance per socket to avoid L3 cache interactions. But, in this case, it is far simpler, cleaner and better performing to not share the instance and avoid the reference counting entirely.
- dagmx 5y ago
  Core affinity would only help if he didn't have more threads than clusters. Otherwise he'd either hit the wall his laptop did, or cross the cluster and hit the cache issues
cletus 5y ago
The mantra I live by is that multi-threaded programming is so potentially complex and it's so easy to screw up (eg erasing all your supposed performance gains as was the case in this article) or by introducing subtle bugs or (worse) security flaws that you should do absolutely everything you can to avoid it. IME C++ programmers seem to put an unreasonable amount of faith on RAII to "solve" these problems eg: std::mutex m; ... { std::lock_guard<std::mutex> lg(m); // do stuff with a mutex lock } // lock_guard destructor releases mutex If you're just updating a (private) map or something, this is fine. But as soon as this gets complex (eg by calling a function and you lose control over what thread is executing because some deep code creates a new thread) then this all turns to crap. So whenever anyone tells you "just start a thread" without any hesitation, it's reasonably safe to assume they have no idea what they're talking about. This is one reason I love the async code model used in a number of languages. I have the most experience with Hack [1] but it's not unique to that. What I tend to think of as "product" code (which is a real Facebook-ism) has no need to every create a thread and dealing with any concurrency issues. Now if you're programming an HTTP server or an RDMBS or other infrastructure then sure, you have a valid need. But if you're just serving HTTP requests, just avoid it entirely if you can because any performance gain is probably imaginary but the complexity increase isn't. [1]: https://docs.hhvm.com/hack/asynchronous-operations/introduction https://docs.hhvm.com/hack/asynchronous-operations/introduct...
- Thiez 5y ago
  Isn't that mantra a bit too pessimistic? After fixing the performance issue, a speedup that was almost linear in the number of cores was achieved using multithreading. In addition, async code can bring much of the same challenges as multithreading. For example, in C# tasks may run on the current thread, but they may also run on a thread-pool, and this is mostly transparent to the programmer. When you don't immediately await all asynchronous operations your tasks may end up running at the same time.
  - cletus 5y ago
    Like anything you weigh up the upside against the downside. The downside is more complex code, code that's harder to reason about, the possibility of concurrency bugs, slower development times, the possibility of security flaws and you may just be shifting your performance bottleneck (eg creating a hot mutex). The upside is lower latency, more throughput and higher QPS. My argument is quite simply YAGNI. A lot of these benefits are for many people purely imaginary. They're the very definition of premature optimization. Code that is less complex, faster to develop in and likely "good enough" is probably going to help you way more than that. If you get to the scale where heavy multithreading actually matters, that's a good problem to have. My argument is that many people aren't there and I would hazard a guess that a contributing factor to not getting there is worrying about this level of performance before they need to.
w_t_payne 5y ago
Shared-nothing dataflow models are an interesting way to engineer (some types of) parallelism.
dathinab 5y ago
Has anyone any idea where the `` format strings come from?? As far as I know rust doesn't have them. And as far as I know if rust gets format strings it most likely get them in form of a `f` prefix (like raw strings have an `r` prefix and binary strings have a `b` prefix). Is it just a thing to make the code more readable/shorter on the web?
- michalhosna 5y ago
  If you are talking about "Here is an example of a complete workload that measures performance of selecting rows by random keys", then you are looking at Rune code rather than Rust code. See https://rune-rs.github.io/book/template_literals.html https://rune-rs.github.io/book/template_literals.html
- metabagel 5y ago
  Markdown uses backticks around code. https://docs.github.com/en/github/writing-on-github/getting-started-with-writing-and-formatting-on-github/basic-writing-and-formatting-syntax#quoting-code https://docs.github.com/en/github/writing-on-github/getting-...
  - mkl 5y ago
    HN doesn't use Markdown.
- cdirkx 5y ago
  The code shown in the article isn't Rust, but Rune [0], which has similar syntax, but is a dynamic scripting language. It has template literals [1]. [0] https://rune-rs.github.io/ https://rune-rs.github.io/ [1] https://rune-rs.github.io/book/template_literals.html https://rune-rs.github.io/book/template_literals.html
  - dathinab 5y ago
    Oh, that makes sense.
kentonv 5y ago
An aside: > L3 cache is shared by all cores of a CPU. I recently learned this is no longer true! AMD EPYC processors (and maybe other recent AMDs?) divide cores into groups called "core complexes" (CCX), each of which has a separate L3 cache. My particular processor is 32-core where each set of 4 cores is a CCX. I discovered this when trying to figure out why a benchmark was performing wildly differently from one run to the next with a bimodal distribution -- it turned out to depend on whether Linux has scheduled the two processes in my benchmark to run on the same CCX vs. different CCXs. https://en.wikipedia.org/wiki/Epyc https://en.wikipedia.org/wiki/Epyc shows the "core config" of each model, which is (number of CCX) x (cores per CCX).
- masklinn 5y ago
  > I recently learned this is no longer true! AMD EPYC processors (and maybe other recent AMDs?) divide cores into groups called "core complexes" (CCX), each of which has a separate L3 cache. It's still kinda true, just that "a CPU" in that context is a CCX. Cross CCX communications has shown up a fair bit in reviews and benches, and really in all chips at that scale (e.g. Ampere's Altras and Intel's Xeons): https://www.anandtech.com/show/16529/amd-epyc-milan-review/4 https://www.anandtech.com/show/16529/amd-epyc-milan-review/4 and one of the "improvements" in Zen 3 is the CCX are much larger (there's one CCX per CCD, rather than 2) so there's less crosstalk. And it could already be untrue previously e.g. the Pentium D were rushed out by sticking two P4 dies on the same PCB, I think they even had to go through the northbridge to communicate, so they were dual socket in all but physical conformation (hence being absolute turds). I don't think they had L3 at all though, so that wasn't really a factor, but still...
  - IronWolve 5y ago
    Yup, and why overclocking on AMD tests each of your ccx/cores, marks gold cores that can reach 5ghz+, and slower cores that dont overclock. Also why AMD tests each ccx, and moves worse ones to lower end products, and higher ones to the 5950x. Then you can OC tweak each core and try to milk out performance, PBO tends to be pretty good on detecting which cores with slight performance boost. With a few bios options, all that adds up without effort. And then finally get a better (advanced) scheduler in windows/linux that can move workloads around per core depending on workload. Windows released multiple fixes for the scheduler on AMD starting with win10 1903. I find scheduler mods and modest bios tweaks to increase performance without much effort, very detectable performance. Linux I use xanmod (and pf-kernel before that) Windows I use project lasso and AMD PBO. Slow/fast cores and scheduler tweaks is how win11/arm mac/android, makes things appear faster too. Amusing, scheduler/core tweaks been around for linux for a decade+, making the desktop super smooth, but its now mainstream in win11/arm osx.
jv22222 5y ago
Yes! Finally, HN removed the rule to strip thew word "How" from the title.
- hinkley 5y ago
  A few hours later...
amichal 5y ago
Would this tool have have scaled as well as 24 separate OS processes? I remember hitting this same issue many years ago. Some primitive in the library (c++) didn’t on the surface appear to involve shared state and cache write lock but of course it did if you thought about it. Since I switched over to more application level coding I don’t work that low level very much and tend to scale with processes now (typically not needing that much parallelism anyway) so i don’t often have to think these things through anymore.
- loeg 5y ago
  Probably yes, unless the author went to great lengths to contend on shared memory segments.
- 10000truths 5y ago
  The problem outlined in the article is not with process vs thread, the problem is with multiple parallel execution contexts reading and writing the same cache line. This issue would have manifested in the same way if your separate processes touched the same offset in a shared memory mapping. Of course, designing with multiple processes in mind helps to design a shared-nothing architecture, as the costs of shared state between processes are much more explicit. But any kind of state that needs to be shared will run into the same bottleneck, because all forms of shared IPC fundamentally have to use some form of locking somewhere in the stack to serialize incoming inputs.
  - lmeyerov 5y ago
    I think the intuition on processes vs threads was right: 1. The Arc use is a case (I believe! Am not a Rust'er!) of true sharing of references. The cacheline will be contention across cores. Doing processes would have eliminated true sharing. Tracking logical core affinity for references via a modal type system could have flagged this at compile time, but I suspect that's not a thing in Rust land. 2. Even if it was false sharing at the cacheline level, process abstractions in shared memory systems are generally aligned to avoid false sharing at cacheline granularity (and misaligned ops at smaller granularities). Of course, in the extreme, a 10X hero programmer may have tried to do amazing levels of bit packing and syscall hackery and thus break all those niceties, but that's the cleanup that everyone else in a team has to make the hero a 10Xer.
nikkinana 5y ago
wabain 5y ago
This is an excellent writeup, but I'm curious about how dependent the microbenchmark is on the scripting engine doing no real work. My off-the-cuff guess is that the unshared version might still perform better with other workloads (it would have higher throughput and avoid variance caused by fluctuating degrees of cache contention) but it might be that the observable overhead from hammering a single cache line would disappear if each thread had more varied work to do. And of course if the scripting engine benefits substantially from caching internal state across invocations (things like incrementally optimized JIT code) then having 24 instances can incur substantial extra work.
deleted 5y ago
[deleted]
Pxtl 5y ago
That actually makes me appreciate that the single-threadedness of Python might a good thing since Python uses refcounting.
reilly3000 5y ago
FWIW this is the kind of content I originally came to HN for and what keeps me coming back.
johnisgood 5y ago
Can anyone TL;DR it? A single line, in Rust, can make a 24-core server slower than a laptop? What line is that?
- jkelleyrtp 5y ago
  In a multithreaded context, shared data was shared via atomic reference counting. The atomic operation acted as a single bottleneck for every operation. The solution was to derive deep cloning for the shared data (a 1 line fix) to reduce atomic contention.
game_the0ry 5y ago
Relevant video - Scott Meyers: Cpu Caches and Why You Care https://www.youtube.com/watch?v=WDIkqP4JbkE https://www.youtube.com/watch?v=WDIkqP4JbkE Remember, boys and girls, small mistakes can have big consequences. Keep those data in immutable data structures when mutli-threading. Actor model also helps.
pengaru 5y ago
TL;DR: serializing your parallel work dispatch on an atomic global counter is bad for scaling across many cores. Or, per-cpu counters exist for a reason.
ncmncm 5y ago
The notion of "lock-free" is fundamentally misleading. It trips up everybody who hopes "lock-free" will be a magic bullet freeing them from resource contention bottlenecks. When you have explicit locks, aka mutexes (condition variables, semaphores, what-have-you), the interaction between your threads is visible on the surface. Replacing that with "lock-free" interaction, you have essentially the same set of operations as when taking a mutex. On the up side, overhead cost may be lower. On the down side, mistakes show up as subtly wrong results instead of deadlocks. And, you get less control, so when you have a problem, it is at best harder to see why, and harder to fix. Because the lock-free operations involve similar hardware bus interactions under the covers, they cannot fix contention problems. You have no choice but to fix contention problems at a higher, architectural design level, by reducing actual contention. Having solved the problems there, the extra cost of explicit mutex operations often does not matter, and the extra control you get may be worth any extra cost. What is lock-free good for, then? Lock-free components reduce overhead when there is no contention. Given any actual contention, performance is abandoned in favor of correctness. So, if you have mutexes and performance is good, moving to lock-free operations might make performance a little better. If performance is bad, mutexes and lock-free operations will be about equally as bad.
- duped 5y ago
  Unfortunately I think this comment does is muddy the waters even more. All "lock free" means is that one process(+) may not cause any other process to block during execution. "Contention" is not very meaningful to a lock-free algorithm, since lock-free algorithms typically do not permit shared data access semantics. Rather they describe how data is sent between processes, which is why a lock-free solution looks very different than something behind mutexes. But to the heart of your point, I do wish people spent more time understanding that lock-free vs lock-ful is a distinction in semantics and doesn't imply anything about performance. There are subtle trade offs. (+) I'm using "process" with a lot of hand waving, assume it means whatever your atom of parallelism is
  - ncmncm 5y ago
    You are confusing two fundamentally different topics. Anywhere there is no possibility of contention for access to a resource, "lock-free" is trivially meaningless.
dan-robertson 5y ago
It seems to me that one solution would be to be able to shard an Arc into separate counts for each thread, so that the synchronisation wouldn’t be required (?) but I don’t know how it would be done without making most Arcs unnecessarily expensive. Perhaps another problem is that libraries can’t be (or just aren’t) generic about the kind of smart-pointers that are used but the kind of smart-pointers used can matter a lot (e.g. libraries often have to use Arc for some of their clients even though Rc would often suffice). But maybe I’m just totally wrong about this?
- Kranar 5y ago
  It's a great idea and in fact a variation of it is being explored by Python to eliminate the use of the GIL without introducing performance regressions. The variation is instead of one count per thread, have two reference counts where one is atomic and the other is not atomic. The heuristic is that at any given time, the majority of writes are performed within a single thread and so that thread has exclusive read/write access to the non-atomic reference count, all other threads share the atomic reference count. There is some work needed to coordinate the atomic and non-atomic reference count so as to test when an object can be deleted, but the overhead of this work is less than the cost of always using an atomic. http://iacoma.cs.uiuc.edu/iacoma-papers/pact18.pdf http://iacoma.cs.uiuc.edu/iacoma-papers/pact18.pdf
  - dan-robertson 5y ago
    In the case of the original article, the reference count was being updated by all the threads so having an Arc-with-Rc-for-one-thread wouldn’t actually change things, I think. But maybe you just mean for ‘cheaper smart-pointers in general’? The python thing is interesting. I thought there were other reasons for the GIL than ref counts but I guess everything must be addressed.
    - Kranar 5y ago
      Yep in this case it might not have helped, but all this to say that some exploration of having multiple reference counts is a great idea. The balance becomes the overhead of coordinating multiple reference counts versus the gains from reduced atomic operations.
teen 5y ago
That code? Thread.sleep(5000)
errcorrectcode 5y ago
My laptop (i7-8650U) has slightly faster single-core performance than my 96-thread dual 7402 EPYC Milan home server. I'm fine with that. I'm not fine with undue inefficiencies, i.e., excessive cache misses, branch mis-predictions, and unparallelization due to sloppy or unfortunate code.
pc86 5y ago
> Because there are 4 cores, the throughput increases linearly up to 4 threads. Then it increases slightly more up to 8 threads, thanks to hyper-threading that squeezes a bit more performance out of each core. Obviously there is no performance improvement beyond 8 threads, because all CPU resources are saturated at this point. [emphasis mine] Can someone more knowledgeable than I please explain the obvious part of this? Why is the performance identical for 8-12 threads? What is it that is saturated at 8 threads even though there are 4 more threads hanging around?
- bunnythefifth 5y ago
  Note that it is a 4-core CPU which employs simultaneous multithreading[1] (hyper-threading in this case) to achieve a higher throughput while executing independent instruction streams. This technique can provide multiple hardware threads to the OS to schedule its processes on (typically 2 per physical core), and the CPU takes care of executing them as concurrently as possible on a single core (typically by employing a few hardware enhancements within the core so that it can work with multiple instruction streams in a since clock cycle). At first, the throughput up to 4 cores increases linearly because 4 OS threads can utilize 4 hardware threads independently, making the greatest possible use of available hardware resources. Beyond 4 OS threads, simultaneous multithreading comes into play and up to 8 OS threads get scheduled on 8 "simultaneously multithreaded" hardware threads, which offers increased throughput, but not as drastic (see how the author uses the word "slightly"). Beyond 8 OS threads, the throughput will not increase as you are out of hardware threads which actually execute your instruction streams independently. The OS can spawn an arbitrary number of threads beyond 8, but they will take turns executing on your 8 available hardware threads - no gain in net throughput. You get limited by the hardware. [1] https://en.wikipedia.org/wiki/Simultaneous_multithreading https://en.wikipedia.org/wiki/Simultaneous_multithreading
- davidgtl 5y ago
  The simplest explanation I've heard is that hyperthreading is like using two hands to keep the mouth always full(whereas with only one sometimes it remains idle). Once you can keep it always full, there's no use adding more hands.
jbkkd 5y ago
CQL is a very confusing term to pronounce.
lilyball 5y ago
If I understand this correctly, the problem is strictly contention on the cache lines containing the reference counts for the shared data. The fact that the data itself was shared is fine, it's just the reference counts that are a problem, yes? Instead of unsharing the whole thing, I wonder if it would make more sense for Rune's Vm type to just re-wrap the Arcs in a new reference-counted type. I don't know if Rune spawns new threads internally, if not then it could store these as Rc<Arc<…>>, but if so then it could use Arc<Arc<…>>. This may look odd but it would ensure that every Vm gets its own independent reference count to use for all of its internal cloning. Or it could redesign its internals to avoid doing so much cloning of the pointers, instead using borrows, though I don't know anything about the Rune API so I don't know how viable that is. In any case, the basic takeaway here should be that using Arc is still potentially expensive if you end up cloning it often (and it looks like Rune does; in a quick skim it's cloning the runtime context and unit quite often). Arc should be used just to deal with data lifetime issues, but cloning of Arc should be avoided as much as possible.
Too 5y ago
Interesting when you start to compare with C++ stdlib which only has shared_ptr, being the equivalent to Arc, but no single-threaded equivalent Rc. Usually the argument you hear is that the performance difference is negligible. One could also argue that you shouldn't use any kind of refcounter in a tight loop where it can affect performance as much as it did there. Refactoring the code a bit to allow passing by reference there would likely help even more. Still cool to see that just changing to Rc gave that much gain.
Matthias247 5y ago
This one is quite surprising. Typical multithreaded/async Rust code contains lots of atomically reference counted variables. And while it’s somewhat common sense that it’s not perfect from a performance point of view (and shared nothing frameworks like seastar/glommio try to avoid it) I’ve never seen a report about such a massive degradation before. Wondering in what kind of pathological case this is running here.

617 points by Ygg2 5y ago

This article is a well-written deep dive on parallel performance debugging that ends up identifying the difference being due to how caching is handled on multi-CPU vs single-CPU systems. Thanks to the author for taking time to write up their troubleshooting process description.

bhauer 5y ago
Agreed. I appreciate the author adding the small effort to briefly describe the idiosyncratic pieces (e.g., Rune) in their unique problem space. So often, writers believe their readers all play in a similar problem space. So they elect to leave understanding such idiosyncrasies for the reader to either dig deeper on their own, or self-select out of reading altogether.

chrisaycock 5y ago

The culprit was a shared atomic reference counter (Arc). The cache invalidation across cores eliminated any kind of scaling via multiple threads. The solution is to stop sharing. The author had to make changes specific to this codebase for each thread to have its own copy of the offending dataset.

denysvitali 5y ago
Awesome TL;DR! I read the full article but this summarizes it well. The article is anyways worth a full read
divs1210 5y ago
Immutable collections save the day!
- Thiez 5y ago
  Immutable collections wouldn't really help here since Rust does not have a garbage collector, so they would still be wrapped in an `Arc<T>`, or use one internally. Unless you're giving each thread their own copy of the immutable collection, in which case the immutability doesn't really add much.
  - ericbarrett 5y ago
    You're right if they're wrapped in an Arc<T>. But it's a lot easier to confidently clone an immutable data structure to threads/async functions because you know they won't be mutated by other cores. If you're cloning mutable data, you'll have to collect each "shard" at the end of whatever runtime loop your program has, and merge them back into the authoritative model. (Or drop the changes, but then why make the data mutable?) Gets hairy.
amelius 5y ago
Or use a language with a good concurrent garbage collector.
- dagmx 5y ago
  What language wouldn't hit this issue? The second you have an atomic write across multiple numa clusters you'll hit this. Edit: it appears they're talking specifically about the ref counting whereas I was considering the entirety of a shared context. That clarification helps me understand where their statement was coming from
  - amelius 5y ago
    The problem was caused by a memory management primitive. This wouldn't be an issue in a runtime with a GC designed for concurrent loads.
    - dagmx 5y ago
      How would the GC avoid the atomic lock and cache invalidation across numa boundaries? What language has a sufficiently lock less rw capable GC? Edit: to clarify I was thinking about a mutable context share as shown in the code example, not solely about the ref counting.
      - amelius 5y ago
        GoLang. It was designed for highly concurrent loads. For an overview of history and technology involved, read e.g.: https://blog.twitch.tv/en/2016/07/05/gos-march-to-low-latency-gc-a6fa96f06eb7/ https://blog.twitch.tv/en/2016/07/05/gos-march-to-low-latenc...
        dagmx 5y ago
        Edit: another comment explains that you're likely talking about just the ref counting aspect rather than the entire context sharing used by the rune code shown, in which case, yes I see why a concurrent GC would avoid the issue in that scenario. ---------- I'm familiar with Go's GC. Your linked post doesn't explain how it would avoid the hit mentioned by the cache invalidation across multiple clusters. It'll either try and put multiple go routines on a single cluster (as listed in the link) or it'll need to copy the necessary stack per thread. Which is effectively what the original article ends up doing. But if you encounter anything that needs to run concurrently across threads while using a single r/w object, you'll hit the same cliff surely?
klabb3 5y ago
The issue is that Rust doesn't allow static borrowing across thread boundaries (except for globals), which necessitates cloning the arc. This is why they chose to instead copy the contents and use thread locals (may be wrong - skimmed the article). I've had this complaint for over a year, and nobody is addressing it. Arcs are absolutely ubiquitous, it can come back and bite anytime, it's just very hard to know upfront where a bottleneck is and most people will never profile to this extent. I really wish Rust would reconsider the decision to throw its hands up at non-lexical destruction guarantees. This is related to the thread::scoped removal from 2015 (IIRC), after which mem::forget was added. Anyway, I'm rambling. There's tons to read for the curious. The simplest mitigation right now is to clone arcs only when necessary, and instead use static references of those arcs whenever possible (especially hot paths). It's a mess for refactors and easy to miss, but better than nothing.
- Thiez 5y ago
  > I really wish Rust would reconsider the decision to throw its hands up at non-lexical destruction guarantees. This is related to the thread::scoped removal from 2015 (IIRC), after which mem::forget was added. Anyway, I'm rambling. There's tons to read for the curious. I think the original argument that leaking memory using safe code by building a reference cycle is still valid. The language would have to change significantly to prevent that, so either reference counting must be unsafe, or we accept that destruction cannot be guaranteed just because something goes out of scope. That is why `forget` is safe.
  - lilyball 5y ago
    The general solution here is to use scopes instead of RAII to ensure destruction. Rust lost its thread::scoped libstd API because that was based on RAII, but there are multiple crates in the ecosystem that provide the lexical scope-based solution
  - klabb3 5y ago
    This is indeed the reason often cited, but it's more nuanced than that. If cycle forming ref types had a lifetime param, you could guarantee destruction at a lifetime level, a weaker but highly useful guarantee. In fact one proposal at the time was to add a lifetime param to Arc and Rc, but it was rejected because it had such big impact and the team was stressed about the 1.0 release. If you look at the various crates that offer static borrowing across threads today, they use lexical scope and they are perfectly safe and guarantee destruction IFF the inner scopes terminate (which is exactly the guarantee you want). However, they are too restrictive to be useful.

twoodfin 5y ago

In situations like this, it’s valuable to know about all the event types perf can sample beyond CPU cycles, including cache misses at various levels and branch mis-predictions. These can go right into flamegraphs as well.

deleted 5y ago

[deleted]

bob1029 5y ago

> The fact that our reference counters are atomic is an additional problem that makes things even more complex for the processor. Although using atomic instructions is often referred to as “lockless programming”, this is slightly misleading – in fact, atomic operations require some locking to happen at the hardware level. This locking is very fine-grained and cheap as long as there is no congestion, but as usual with locking, you may expect very poor performance if many things try to fight for the same lock at the same time. And it is of course much worse if those “things” are whole CPUs and not just single cores that are close to each other. Contention is the devil and you can never hide from it if you bring it into your life. The fastest "contention avoidance hack" would be the CAS operation as mentioned above, which still performs approximately 2 orders of magnitude slower than a single threaded operation would in the most adverse scenarios. If you aren't sure of which problems actually "fit" on a modern x86 thread these days, rest assured that many developers in fintech have been able to squeeze entire financial exchanges onto one: https://lmax-exchange.github.io/disruptor/disruptor.html https://lmax-exchange.github.io/disruptor/disruptor.html For most scenarios, you really don't need all those damn cores. They are almost certainly getting in the way of you solving your problems.

cecilpl2 5y ago
Games are a prime example of systems which must take advantage of all possible hardware resources.
- bob1029 5y ago
  The fact that we believe this is probably part of the problem with game development today.
- dagmx 5y ago
  Games similarly struggle with multi core/ccx designed chips. Battlefield 4 was famously terrible on Ryzen when AMD first released it.
  - littlecranky67 5y ago

vlovich123 5y ago

Is there any tooling that can demonstrate cache coherency hotspots like cache line bouncing or inter-core communication?

maxwell86 5y ago
Yes. Linux perf has a c2c hit modify “mode”/“option” that will report precisely this issue.
- loeg 5y ago
  What is c2c? Thanks.
  - eptcyka 5y ago
    Cache to cents? Kernels 2 cents on how your code is utilizing the cache? I have 0 clue too.
    - masklinn 5y ago
      Cache to Cache, It tracks a bunch of cache-related counters, and HITM (hit modify) tracks loads of data modified by either an other core of the same node ("local hitm") or by an other node entirely ("remote hitm"). Here, the contention would have shown up as extreme amounts of both, as each core would almost certainly try atomically updating a value which had just been updated by an other core, with higher than even chances the value had been updated by a core of the other socket (= node).
  - tkhattra 5y ago
    c2c stands for cache-2-cache. perf-c2c allows you to measure cacheline contention - see https://man7.org/linux/man-pages/man1/perf-c2c.1.html https://man7.org/linux/man-pages/man1/perf-c2c.1.html and https://joemario.github.io/blog/2016/09/01/c2c-blog/ https://joemario.github.io/blog/2016/09/01/c2c-blog/.
    - 5y ago

cheschire 5y ago

There are only two hard things in Computer Science: cache invalidation and naming things. - Phil Karlton

hnaccount_rng 5y ago
You missed the off-by-one errors
- cheschire 5y ago
  So you mean I was off by one?
Pet_Ant 5y ago
Better version: There are only two hard things in Computer Science: cache invalidation, naming things, and off-by-one errors.
- jahnu 5y ago
  There are only two hard things in Computer Science: cache invalidation, naming things, and off-by-oly two hard things in Computer Scivetëm� dy gjëra të vështira në Shkencën Komp��jute
  - jacquesm 5y ago
    Hehe. Ok. That is very funny :)
    - gavinray 5y ago
      I don't get it -- am I slow?
      - jacquesm 5y ago
        Buffer overflow :)
      - 5y ago

Thiez 5y ago

Is this the kind of situation where assigning a core affinity to the various threads would have made a difference (to make sure they all run on the same physical processor), or is the mere presence of another processor enough to trigger the behavior shown in the article?

deleted 5y ago
[deleted]
loeg 5y ago
No, that would not make a significant difference here. The problem is that the same line has to bounce around all of the threads that share it; pinning doesn’t reduce that very much on this time-scale. Thread migrations will be very infrequent relative to atomic operations, especially when the number of runnable threads is lower than number of physical cores.
hermitdev 5y ago
I don't think core affinity would have helped in this situation. They had one instance that was being shared across all cores, necessitating the reference count to be sync'd between sockets at L3 cache level. They may have seen some benefit if you had, say, 2 instances, one per CPU socket, and dedicated an instance per socket to avoid L3 cache interactions. But, in this case, it is far simpler, cleaner and better performing to not share the instance and avoid the reference counting entirely.
dagmx 5y ago
Core affinity would only help if he didn't have more threads than clusters. Otherwise he'd either hit the wall his laptop did, or cross the cluster and hit the cache issues

cletus 5y ago

The mantra I live by is that multi-threaded programming is so potentially complex and it's so easy to screw up (eg erasing all your supposed performance gains as was the case in this article) or by introducing subtle bugs or (worse) security flaws that you should do absolutely everything you can to avoid it. IME C++ programmers seem to put an unreasonable amount of faith on RAII to "solve" these problems eg: std::mutex m; ... { std::lock_guard<std::mutex> lg(m); // do stuff with a mutex lock } // lock_guard destructor releases mutex If you're just updating a (private) map or something, this is fine. But as soon as this gets complex (eg by calling a function and you lose control over what thread is executing because some deep code creates a new thread) then this all turns to crap. So whenever anyone tells you "just start a thread" without any hesitation, it's reasonably safe to assume they have no idea what they're talking about. This is one reason I love the async code model used in a number of languages. I have the most experience with Hack [1] but it's not unique to that. What I tend to think of as "product" code (which is a real Facebook-ism) has no need to every create a thread and dealing with any concurrency issues. Now if you're programming an HTTP server or an RDMBS or other infrastructure then sure, you have a valid need. But if you're just serving HTTP requests, just avoid it entirely if you can because any performance gain is probably imaginary but the complexity increase isn't. [1]: https://docs.hhvm.com/hack/asynchronous-operations/introduction https://docs.hhvm.com/hack/asynchronous-operations/introduct...

Thiez 5y ago
Isn't that mantra a bit too pessimistic? After fixing the performance issue, a speedup that was almost linear in the number of cores was achieved using multithreading. In addition, async code can bring much of the same challenges as multithreading. For example, in C# tasks may run on the current thread, but they may also run on a thread-pool, and this is mostly transparent to the programmer. When you don't immediately await all asynchronous operations your tasks may end up running at the same time.
- cletus 5y ago
  Like anything you weigh up the upside against the downside. The downside is more complex code, code that's harder to reason about, the possibility of concurrency bugs, slower development times, the possibility of security flaws and you may just be shifting your performance bottleneck (eg creating a hot mutex). The upside is lower latency, more throughput and higher QPS. My argument is quite simply YAGNI. A lot of these benefits are for many people purely imaginary. They're the very definition of premature optimization. Code that is less complex, faster to develop in and likely "good enough" is probably going to help you way more than that. If you get to the scale where heavy multithreading actually matters, that's a good problem to have. My argument is that many people aren't there and I would hazard a guess that a contributing factor to not getting there is worrying about this level of performance before they need to.

w_t_payne 5y ago

Shared-nothing dataflow models are an interesting way to engineer (some types of) parallelism.

dathinab 5y ago

Has anyone any idea where the `` format strings come from?? As far as I know rust doesn't have them. And as far as I know if rust gets format strings it most likely get them in form of a `f` prefix (like raw strings have an `r` prefix and binary strings have a `b` prefix). Is it just a thing to make the code more readable/shorter on the web?

michalhosna 5y ago
If you are talking about "Here is an example of a complete workload that measures performance of selecting rows by random keys", then you are looking at Rune code rather than Rust code. See https://rune-rs.github.io/book/template_literals.html https://rune-rs.github.io/book/template_literals.html
metabagel 5y ago
Markdown uses backticks around code. https://docs.github.com/en/github/writing-on-github/getting-started-with-writing-and-formatting-on-github/basic-writing-and-formatting-syntax#quoting-code https://docs.github.com/en/github/writing-on-github/getting-...
- mkl 5y ago
  HN doesn't use Markdown.
cdirkx 5y ago
The code shown in the article isn't Rust, but Rune [0], which has similar syntax, but is a dynamic scripting language. It has template literals [1]. [0] https://rune-rs.github.io/ https://rune-rs.github.io/ [1] https://rune-rs.github.io/book/template_literals.html https://rune-rs.github.io/book/template_literals.html
- dathinab 5y ago
  Oh, that makes sense.

kentonv 5y ago

An aside: > L3 cache is shared by all cores of a CPU. I recently learned this is no longer true! AMD EPYC processors (and maybe other recent AMDs?) divide cores into groups called "core complexes" (CCX), each of which has a separate L3 cache. My particular processor is 32-core where each set of 4 cores is a CCX. I discovered this when trying to figure out why a benchmark was performing wildly differently from one run to the next with a bimodal distribution -- it turned out to depend on whether Linux has scheduled the two processes in my benchmark to run on the same CCX vs. different CCXs. https://en.wikipedia.org/wiki/Epyc https://en.wikipedia.org/wiki/Epyc shows the "core config" of each model, which is (number of CCX) x (cores per CCX).

masklinn 5y ago
> I recently learned this is no longer true! AMD EPYC processors (and maybe other recent AMDs?) divide cores into groups called "core complexes" (CCX), each of which has a separate L3 cache. It's still kinda true, just that "a CPU" in that context is a CCX. Cross CCX communications has shown up a fair bit in reviews and benches, and really in all chips at that scale (e.g. Ampere's Altras and Intel's Xeons): https://www.anandtech.com/show/16529/amd-epyc-milan-review/4 https://www.anandtech.com/show/16529/amd-epyc-milan-review/4 and one of the "improvements" in Zen 3 is the CCX are much larger (there's one CCX per CCD, rather than 2) so there's less crosstalk. And it could already be untrue previously e.g. the Pentium D were rushed out by sticking two P4 dies on the same PCB, I think they even had to go through the northbridge to communicate, so they were dual socket in all but physical conformation (hence being absolute turds). I don't think they had L3 at all though, so that wasn't really a factor, but still...
- IronWolve 5y ago
  Yup, and why overclocking on AMD tests each of your ccx/cores, marks gold cores that can reach 5ghz+, and slower cores that dont overclock. Also why AMD tests each ccx, and moves worse ones to lower end products, and higher ones to the 5950x. Then you can OC tweak each core and try to milk out performance, PBO tends to be pretty good on detecting which cores with slight performance boost. With a few bios options, all that adds up without effort. And then finally get a better (advanced) scheduler in windows/linux that can move workloads around per core depending on workload. Windows released multiple fixes for the scheduler on AMD starting with win10 1903. I find scheduler mods and modest bios tweaks to increase performance without much effort, very detectable performance. Linux I use xanmod (and pf-kernel before that) Windows I use project lasso and AMD PBO. Slow/fast cores and scheduler tweaks is how win11/arm mac/android, makes things appear faster too. Amusing, scheduler/core tweaks been around for linux for a decade+, making the desktop super smooth, but its now mainstream in win11/arm osx.

jv22222 5y ago

Yes! Finally, HN removed the rule to strip thew word "How" from the title.

hinkley 5y ago
A few hours later...

amichal 5y ago

Would this tool have have scaled as well as 24 separate OS processes? I remember hitting this same issue many years ago. Some primitive in the library (c++) didn’t on the surface appear to involve shared state and cache write lock but of course it did if you thought about it. Since I switched over to more application level coding I don’t work that low level very much and tend to scale with processes now (typically not needing that much parallelism anyway) so i don’t often have to think these things through anymore.

loeg 5y ago
Probably yes, unless the author went to great lengths to contend on shared memory segments.
10000truths 5y ago
The problem outlined in the article is not with process vs thread, the problem is with multiple parallel execution contexts reading and writing the same cache line. This issue would have manifested in the same way if your separate processes touched the same offset in a shared memory mapping. Of course, designing with multiple processes in mind helps to design a shared-nothing architecture, as the costs of shared state between processes are much more explicit. But any kind of state that needs to be shared will run into the same bottleneck, because all forms of shared IPC fundamentally have to use some form of locking somewhere in the stack to serialize incoming inputs.
- lmeyerov 5y ago
  I think the intuition on processes vs threads was right: 1. The Arc use is a case (I believe! Am not a Rust'er!) of true sharing of references. The cacheline will be contention across cores. Doing processes would have eliminated true sharing. Tracking logical core affinity for references via a modal type system could have flagged this at compile time, but I suspect that's not a thing in Rust land. 2. Even if it was false sharing at the cacheline level, process abstractions in shared memory systems are generally aligned to avoid false sharing at cacheline granularity (and misaligned ops at smaller granularities). Of course, in the extreme, a 10X hero programmer may have tried to do amazing levels of bit packing and syscall hackery and thus break all those niceties, but that's the cleanup that everyone else in a team has to make the hero a 10Xer.

nikkinana 5y ago

wabain 5y ago

This is an excellent writeup, but I'm curious about how dependent the microbenchmark is on the scripting engine doing no real work. My off-the-cuff guess is that the unshared version might still perform better with other workloads (it would have higher throughput and avoid variance caused by fluctuating degrees of cache contention) but it might be that the observable overhead from hammering a single cache line would disappear if each thread had more varied work to do. And of course if the scripting engine benefits substantially from caching internal state across invocations (things like incrementally optimized JIT code) then having 24 instances can incur substantial extra work.

deleted 5y ago

[deleted]

Pxtl 5y ago

That actually makes me appreciate that the single-threadedness of Python might a good thing since Python uses refcounting.

reilly3000 5y ago

FWIW this is the kind of content I originally came to HN for and what keeps me coming back.

johnisgood 5y ago

Can anyone TL;DR it? A single line, in Rust, can make a 24-core server slower than a laptop? What line is that?

jkelleyrtp 5y ago
In a multithreaded context, shared data was shared via atomic reference counting. The atomic operation acted as a single bottleneck for every operation. The solution was to derive deep cloning for the shared data (a 1 line fix) to reduce atomic contention.

game_the0ry 5y ago

Relevant video - Scott Meyers: Cpu Caches and Why You Care https://www.youtube.com/watch?v=WDIkqP4JbkE https://www.youtube.com/watch?v=WDIkqP4JbkE Remember, boys and girls, small mistakes can have big consequences. Keep those data in immutable data structures when mutli-threading. Actor model also helps.

pengaru 5y ago

TL;DR: serializing your parallel work dispatch on an atomic global counter is bad for scaling across many cores. Or, per-cpu counters exist for a reason.

ncmncm 5y ago

The notion of "lock-free" is fundamentally misleading. It trips up everybody who hopes "lock-free" will be a magic bullet freeing them from resource contention bottlenecks. When you have explicit locks, aka mutexes (condition variables, semaphores, what-have-you), the interaction between your threads is visible on the surface. Replacing that with "lock-free" interaction, you have essentially the same set of operations as when taking a mutex. On the up side, overhead cost may be lower. On the down side, mistakes show up as subtly wrong results instead of deadlocks. And, you get less control, so when you have a problem, it is at best harder to see why, and harder to fix. Because the lock-free operations involve similar hardware bus interactions under the covers, they cannot fix contention problems. You have no choice but to fix contention problems at a higher, architectural design level, by reducing actual contention. Having solved the problems there, the extra cost of explicit mutex operations often does not matter, and the extra control you get may be worth any extra cost. What is lock-free good for, then? Lock-free components reduce overhead when there is no contention. Given any actual contention, performance is abandoned in favor of correctness. So, if you have mutexes and performance is good, moving to lock-free operations might make performance a little better. If performance is bad, mutexes and lock-free operations will be about equally as bad.

duped 5y ago
Unfortunately I think this comment does is muddy the waters even more. All "lock free" means is that one process(+) may not cause any other process to block during execution. "Contention" is not very meaningful to a lock-free algorithm, since lock-free algorithms typically do not permit shared data access semantics. Rather they describe how data is sent between processes, which is why a lock-free solution looks very different than something behind mutexes. But to the heart of your point, I do wish people spent more time understanding that lock-free vs lock-ful is a distinction in semantics and doesn't imply anything about performance. There are subtle trade offs. (+) I'm using "process" with a lot of hand waving, assume it means whatever your atom of parallelism is
- ncmncm 5y ago
  You are confusing two fundamentally different topics. Anywhere there is no possibility of contention for access to a resource, "lock-free" is trivially meaningless.

dan-robertson 5y ago

It seems to me that one solution would be to be able to shard an Arc into separate counts for each thread, so that the synchronisation wouldn’t be required (?) but I don’t know how it would be done without making most Arcs unnecessarily expensive. Perhaps another problem is that libraries can’t be (or just aren’t) generic about the kind of smart-pointers that are used but the kind of smart-pointers used can matter a lot (e.g. libraries often have to use Arc for some of their clients even though Rc would often suffice). But maybe I’m just totally wrong about this?

Kranar 5y ago
It's a great idea and in fact a variation of it is being explored by Python to eliminate the use of the GIL without introducing performance regressions. The variation is instead of one count per thread, have two reference counts where one is atomic and the other is not atomic. The heuristic is that at any given time, the majority of writes are performed within a single thread and so that thread has exclusive read/write access to the non-atomic reference count, all other threads share the atomic reference count. There is some work needed to coordinate the atomic and non-atomic reference count so as to test when an object can be deleted, but the overhead of this work is less than the cost of always using an atomic. http://iacoma.cs.uiuc.edu/iacoma-papers/pact18.pdf http://iacoma.cs.uiuc.edu/iacoma-papers/pact18.pdf
- dan-robertson 5y ago
  In the case of the original article, the reference count was being updated by all the threads so having an Arc-with-Rc-for-one-thread wouldn’t actually change things, I think. But maybe you just mean for ‘cheaper smart-pointers in general’? The python thing is interesting. I thought there were other reasons for the GIL than ref counts but I guess everything must be addressed.
  - Kranar 5y ago
    Yep in this case it might not have helped, but all this to say that some exploration of having multiple reference counts is a great idea. The balance becomes the overhead of coordinating multiple reference counts versus the gains from reduced atomic operations.

teen 5y ago

That code? Thread.sleep(5000)

errcorrectcode 5y ago

My laptop (i7-8650U) has slightly faster single-core performance than my 96-thread dual 7402 EPYC Milan home server. I'm fine with that. I'm not fine with undue inefficiencies, i.e., excessive cache misses, branch mis-predictions, and unparallelization due to sloppy or unfortunate code.

pc86 5y ago

> Because there are 4 cores, the throughput increases linearly up to 4 threads. Then it increases slightly more up to 8 threads, thanks to hyper-threading that squeezes a bit more performance out of each core. Obviously there is no performance improvement beyond 8 threads, because all CPU resources are saturated at this point. [emphasis mine] Can someone more knowledgeable than I please explain the obvious part of this? Why is the performance identical for 8-12 threads? What is it that is saturated at 8 threads even though there are 4 more threads hanging around?

bunnythefifth 5y ago
Note that it is a 4-core CPU which employs simultaneous multithreading[1] (hyper-threading in this case) to achieve a higher throughput while executing independent instruction streams. This technique can provide multiple hardware threads to the OS to schedule its processes on (typically 2 per physical core), and the CPU takes care of executing them as concurrently as possible on a single core (typically by employing a few hardware enhancements within the core so that it can work with multiple instruction streams in a since clock cycle). At first, the throughput up to 4 cores increases linearly because 4 OS threads can utilize 4 hardware threads independently, making the greatest possible use of available hardware resources. Beyond 4 OS threads, simultaneous multithreading comes into play and up to 8 OS threads get scheduled on 8 "simultaneously multithreaded" hardware threads, which offers increased throughput, but not as drastic (see how the author uses the word "slightly"). Beyond 8 OS threads, the throughput will not increase as you are out of hardware threads which actually execute your instruction streams independently. The OS can spawn an arbitrary number of threads beyond 8, but they will take turns executing on your 8 available hardware threads - no gain in net throughput. You get limited by the hardware. [1] https://en.wikipedia.org/wiki/Simultaneous_multithreading https://en.wikipedia.org/wiki/Simultaneous_multithreading
davidgtl 5y ago
The simplest explanation I've heard is that hyperthreading is like using two hands to keep the mouth always full(whereas with only one sometimes it remains idle). Once you can keep it always full, there's no use adding more hands.

jbkkd 5y ago

CQL is a very confusing term to pronounce.

lilyball 5y ago

If I understand this correctly, the problem is strictly contention on the cache lines containing the reference counts for the shared data. The fact that the data itself was shared is fine, it's just the reference counts that are a problem, yes? Instead of unsharing the whole thing, I wonder if it would make more sense for Rune's Vm type to just re-wrap the Arcs in a new reference-counted type. I don't know if Rune spawns new threads internally, if not then it could store these as Rc<Arc<…>>, but if so then it could use Arc<Arc<…>>. This may look odd but it would ensure that every Vm gets its own independent reference count to use for all of its internal cloning. Or it could redesign its internals to avoid doing so much cloning of the pointers, instead using borrows, though I don't know anything about the Rune API so I don't know how viable that is. In any case, the basic takeaway here should be that using Arc is still potentially expensive if you end up cloning it often (and it looks like Rune does; in a quick skim it's cloning the runtime context and unit quite often). Arc should be used just to deal with data lifetime issues, but cloning of Arc should be avoided as much as possible.

Too 5y ago

Interesting when you start to compare with C++ stdlib which only has shared_ptr, being the equivalent to Arc, but no single-threaded equivalent Rc. Usually the argument you hear is that the performance difference is negligible. One could also argue that you shouldn't use any kind of refcounter in a tight loop where it can affect performance as much as it did there. Refactoring the code a bit to allow passing by reference there would likely help even more. Still cool to see that just changing to Rc gave that much gain.

Matthias247 5y ago

This one is quite surprising. Typical multithreaded/async Rust code contains lots of atomically reference counted variables. And while it’s somewhat common sense that it’s not perfect from a performance point of view (and shared nothing frameworks like seastar/glommio try to avoid it) I’ve never seen a report about such a massive degradation before. Wondering in what kind of pathological case this is running here.