6 ms·

The culprit was a shared atomic reference counter (Arc). The cache invalidation across cores eliminated any kind of scaling via multiple threads. The solution

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.

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.