Spice: Fine-grained parallelism with sub-nanosecond overhead in Zig
github.com
github.com
Related papers:
(2018) Heartbeat Scheduling: Provable Efficiency for Nested Parallelism. https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf
(2021) Task Parallel Assembly Language for Uncompromising Parallelism. https://users.cs.northwestern.edu/~simonec/files/Research/pa...
(2024) Compiling Loop-Based Nested Parallelism for Irregular Workloads. https://users.cs.northwestern.edu/~simonec/files/Research/pa...
(2024) Automatic Parallelism Management. https://www.cs.cmu.edu/~swestric/24/popl24-par-manage.pdf
Moreover, I think that mode of thought comes from the fact that most programming problems don't have hard latency bounds, so throughput dominates the conversation. If I'm spending 10us on average while handling a 10ms soft deadline, every single component can easily be occasionally 100x more expensive (latency) without me caring, and if it buys me another 1us on average (throughput) then I'll save gobs of money in compute.
Anyone making claims about performance should know the difference.
This isn't even about either, it's lying about overhead by not counting it correctly.
If someone asks what your cable bill is and you say it's only $2.50 a month because you have 32 TVs, no one is going to say that makes sense.
> Anyone making claims about performance should know the difference.
They probably do know the difference. Knowing the difference isn't the thing you're quibbling with.
> If someone asks what your cable bill is and you say it's only $2.50 a month because you have 32 TVs, no one is going to say that makes sense.
Sure...because when asking about your cable bill it's unambiguous that you want the total number of dollars. The whole reason there's any issue at all here is that some of their language is ambiguous if you don't consider the target audience and don't analyze their charts or read the descriptions of those charts. Picking an analogy which resonates precisely because of the lack of ambiguity doesn't say a whole lot about the actual problem at hand.
I think something is a lie when somebody intentionally tries to mislead (even when communicating "facts" if the intent is to maliciously shape the recipient mind). I think when they intentionally try to convey the "right" ideas (as I think this author is doing -- again, using words the way you think most of your peers use them is usually a good thing), that's not a lie. There are gray areas in between. I don't think this is a gray area, except insofar as I don't know all the facts perfectly.
You still seem to disagree with me though. I'd really like to understand why. I have a couple theories, which I'll list, but I'm interested in any insights you have:
1. You disagree with my description of what "lying" is.
2. You think the author is less deserving of trust than I do (since they seem to be profiting almost nothing other than a tiny bit of publicity, since they did outline in their README exactly what they meant, with photos, and since the title didn't stoop to clickbait, my default position is that they likely weren't too malicious, but you might have different priors and might also disagree with my opinions of those conflicts of interest).
> the whole point of overhead ...
That's perhaps the last pertinent thing we disagree about. I'll throw out my opinion, and I sincerely want to know your thoughts on the matter:
An extremely commonplace occurrence is that something is slow and you want to speed it up (measuring perceived latency). If you can magically do that by adding parallelism then it's a good day at work. Unfortunately, parallelism can easily add "overhead" -- parallelizing small or finely grained problems usually increases wall-clock timing, usually substantially.
In that mode of operation, the whole problem you're trying to solve is reducing a certain latency measurement, making it clear from context what "overhead" means. Other definitions don't even enter into the equation.
Zooming out a bit, I've heard that phrasing a ton of times in many different companies. Sure, it's better if people know to speak more precisely (and I think we're in agreement that a few more performance characteristics would be nice to know here), but it's hard for me to imagine a world were my default perception of somebody is that they're lying when they're using the exact same words and meanings as scores of other good engineers. _Maybe_ they are, but that's by no means my default assumption.
From a slightly different perspective, one thing the library does on top of handling small workloads well is handling _finely grained_ workloads. That's super important from a usability point of view, since you can express the parallelism in the most natural way and let the library handle the fact that it's hard to schedule that task (e.g., most schedulers suck as soon as you're talking about work items on the order of a single cache line). Just being able to have a convenient abstraction when writing a long-running job is also a fantastic feature. In that case, we would still care about throughput, not latency.
Separately, though definitely more rarely, there are jobs which are sub-second but where it's hard to batch many of them at once. If you're forced to execute many and care about the time till completion (latency, again at a much longer timescale), being able to make each one much faster is a big deal.
I really think that first paragraph is a commonplace occurrence though. Something important is slow (measured in "human" blinking timescales), so you slap a better scheduler and some parallelism at it and start work on the next ticket. Ripgrep, at some level (it has lots of other technical accomplishments; I don't want to let this comment give the mistaken impression that I'm demeaning the project) is useful precisely because it throws parallelism at sub-second problems.
If and only if (1-thread Spice - non-parallelized baseline) > 1ns, which their tests back up their claims.
"Spice shows subpar scalability: The speed-up of using 16 threads was merely ~11x"
If that is true, then "Spice" is suitable only for small tasks, which can be completed at most in milliseconds, which can benefit from its low overhead, while for any bigger tasks something better must be used.
I’d maybe phrase it as “Spice is not optimal” instead of “Spice is not suited for”, but yes, that’s the conclusion for this benchmark.
I’m hoping/assuming that for a more typical case (more CPU work being done) Spice will scale better, but I haven’t done the benchmark yet.
Each extra thread adds more overhead from lock contention. At 16 threads overhead is up to 3.6 ns (so 10 times more). I'm guessing, but that would mean the 0.36 ns of overhead included an uncontested lock? That's not possible. There's some other weirdness going on in the benchmark data too. So either I'm not understanding what he's actually timing or maybe there is a bug in the benchmark code.
Also, if you multiply all the values out, I think he's timing in milliseconds (when runtime is calculated and converted to millis, they come out as whole numbers). Don't most benchmarkers have better precision than that? Maybe he's just using `time prog` and the data is just really dirty. Or maybe he's just choosing really, really bad metrics that totally useless for this (this is probably correct, just not sure if there are more issues).
AFAICT this is just a really cool and really practical algorithm for microthreads with near zero cost per semantic thread.
What? The threadpool has a shared mutex accessed by each worker thread, which is used for pushing work on heartbeat and for dequeuing work. https://github.com/judofyr/spice/blob/167deba6e4d319f96d9d67...
"Adding more threads to the system will not make your program any slower" is an insane claim to be making for any lightweight task scheduling system, and trivially not true looking at this: if you have 1000 threads as workers and degenerate tree program than each worker will take turns serializing themselves through the mutex. Things like these are massive red flags to anyone reading the README.
Actually, if you did have a 32k core machine somehow with magical sufficiently-uniform memory for microthreading to be sensible for it, I think it's not even hard to extend the algorithm to work with that. Just put the workers on a 3D torus and only share orthogonally. It means you don't have perfect work sharing, but I'm also pretty sure it doesn't matter.
I knew that some people would react negatively to the term, but I can assure the intention is for you to have a better understanding of exactly how and when you should use Spice and Rayon. I would recommend reading the benchmark document: https://github.com/judofyr/spice/blob/main/bench/README.md.
What people typically do when comparing parallel code is to only compare the sequential/baseline with a parallel version running at all threads (16). Let's use the numbers for Rayon that I got for the 100M case:
- Sequential version: 7.48 ns.
- Rayon: 1.64 ns.
Then they go "For this problem Rayon showed a 4.5x speed-up, but uses 16 threads. Oh no, this is a bad fit." That's very true, but you don't learn anything from that. How can I use apply this knowledge to other types of problems?
However, if you run the same benchmark on varying number of threads you learn something more interesting: The scheduler in Rayon is actually pretty good at giving work to separate threads, but the overall work execution mechanism has a ~15 ns overhead. Despite this being an utterly useless program we've learnt something that we can apply later on: Our smallest unit of work should probably be a bit bigger than ~7 ns before we reach for Rayon. (Unless it's more important for use to reduce overall latency at the cost of the throughput of the whole system.)
In comparison, if you read the Rayon documentation they will not attempt to give you any number. They just say "Conceptually, calling join() is similar to spawning two threads, one executing each of the two closures. However, the implementation is quite different and incurs very low overhead": https://docs.rs/rayon/latest/rayon/fn.join.html.
(Also: If I wanted to be misleading I would say "Spice is twice as fast as Rayon since it gets 10x speed-up compared to 4.5x speed-up")
> Despite this being an utterly useless program we've learnt something that we can apply later on: Our smallest unit of work should probably be a bit bigger than ~7 ns before we reach for Rayon.
That's a very interesting project.
The big limitation I see with the current approach is that the usability of the library is much worth than what Rayon offers.
The true magic of Rayon is that you just replace `iter()` with `par_iter()` in you code and voilà! now you have a parallel execution. But yes it has some overhead, so maybe Rayon could try and implement this kind of scheduling as an alternative so that people pick what works best for their use-case.
> the usability of the library is much worse than what Rayon
I'm a little bit ashamed to see that this fairly upvoted comment of mine has such an stupid English mistake in it…
I've seen systems that can achieve 99% efficiency on thousands on nodes for real useful applications that involve non-trivial synchronization. Now that is an impressive feat.
Sure, there is probably some extra latency to get everything running, but for a sufficiently long program run, that is all irrelevant.
The linked benchmark document does this. 82% for 4 cores on Spice with a small workload, and 69% for 16 cores on Spice with a large workload. Compared to about 25% for Rayon on 4 cores with a small workload and 88% for Rayon on 16 cores with a large workload.
> Sure, there is probably some extra latency to get everything running, but for a sufficiently long program run, that is all irrelevant.
The entire point of the linked benchmark README.md is to deal with insufficiently long program runs. Spice is an attempt to allow parallelization of very small amounts of work by decreasing fixed overhead. Perhaps such a thing is not useful but that doesn't prevent it from being interesting.
The overhead should be measured as a percentage versus a theoretical base line such as perfect linear speedup. You haven't shown the ideal scenario for each core count, so how are we supposed to know how much overhead there really is?
The single core scenario is 363ms and linear speedup for 32 cores gives us 11.3ms. Your benchmark says you needed 38ms. This means you achieved 31% of the theoretical performance of the CPU, which mind you is pretty good, especially since nobody has benchmarked what is actually possible while loading all cores by running 32 single threaded copies of the original program, but you're advertising a meaningless "sub nanosecond" measure here.
The title is totally fine. There is no title with zero room for misinterpretation. All I took from it is that it's a library with extreme low latency by some kind of measure.. and then I went to the readme to see exactly what that measure was. Very straightforward.
I think the README here is very well written, and I have a good idea of what's going on just from reading it, but there are a few areas where I'm left scratching my head. Thankfully the code is fairly easy to read.
Baseline,3.92809172
Spice 1 thread,19.1012624
Baseline,3.264224280000001
Spice 1 thread,3.78043278
(zig 0.13.0)
The 2018 paper on heartbeat scheduling is also an interesting read https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf
I also really appreciate that the author recognizes the limits of their own project, which preemptively addresses most of the usual snark.
> Lack of tests: Spice contains a lot of gnarly concurrent code, but has zero testing coverage. This would have be improved before Spice can be responsibly used for critical tasks.
Testing correctness of execution for critical tasks is one thing, but I would expect a library which implements "gnarly concurrent code" to at least have regression tests — what guarantee is there to an end-user that functionality which exists in a working state today might not break tomorrow due to a subtle yet nefarious regression?
sqlite has 590 times as much test code and test scripts as it does raw c source code [0]; this fact, along with its stability and portability, is one of the numerous reasons why it has proliferated to become the defacto embedded database used across the planet. While we're comparing apples to oranges in this contrived example, the general point still stands — regression tests beget stability and confidence in a project.
In epics where I work, if we _must_ defer baseline regression tests, we usually create a follow-up ticket inside of the same epic to at least write them before feature/epic launch, usually.
Ah, I missed that upon first read. In that case, that caveat/limitation is definitely justified.
Note that I posted this, but I am not the author
Docker was largely met with enthusiasm here when it was launched. I believe you must refer to how Dropbox was received — famously negatively, initially.
April 5, 2007: "Show HN, Dropbox"
So you made me dig up the announcement, and contrary to how you recall, it is almost universally positive.
Related, I’ve been interested a while whether there’s a faster way for a producer of work to have a consumer wake up without resorting to busy waiting, possibly by running the consumer in the producer time slice.
Also related, I’ve wondered if it’s possible to have a user space FUTEX_WAKE operation that would halve the typical penalty of waking up a consumer (to just the consumer).