10 ms·

Spice: Fine-grained parallelism with sub-nanosecond overhead in Zig

394 points by dsp_person 2y ago

dsp_person 2y ago
see also readme under bench https://github.com/judofyr/spice/blob/main/bench/README.md https://github.com/judofyr/spice/blob/main/bench/README.md
shoggouth 2y ago
List of limitations of the project: https://github.com/judofyr/spice?tab=readme-ov-file#limitations https://github.com/judofyr/spice?tab=readme-ov-file#limitati...
- jd3 2y ago
  Want to state off the bat this this project is awesome and huge kudos to the author for spending their time, attention, and energy 1) working diligently to get this working at all and 2) sharing it with the broader HN community, who are generally known to by hyper-critical to a pedantic degree and/or overly pessimistic (cough the initial Docker project Show HN thread cough) 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. [0]: https://www.sqlite.org/testing.html https://www.sqlite.org/testing.html
  - pverghese 2y ago
    You are welcome to add it. This is a proof of concept
    - jd3 2y ago
      > Spice is primarily a research project. Read along to learn more about it, but if you're considering using it in production you should be aware of its many limitations. Ah, I missed that upon first read. In that case, that caveat/limitation is definitely justified.
  - dsp_person 2y ago
    > sharing it with the broader HN community Note that I posted this, but I am not the author
  - stareatgoats 2y ago
    > (cough the initial Docker project Show HN thread cough) Docker was largely met with enthusiasm here when it was launched. I believe you must refer to how Dropbox was received — famously negatively, initially.
    - WaffleIronMaker 2y ago
      Yeah, that seems right: April 5, 2007: "Show HN, Dropbox" https://news.ycombinator.com/item?id=8863 https://news.ycombinator.com/item?id=8863
      - Dylan16807 2y ago
        Looks positive to me!
    - jd3 2y ago
      Yes, I meant to say dropbox
  - dagw 2y ago
    HN community, who are generally known to by hyper-critical to a pedantic degree and/or overly pessimistic (cough the initial Docker project Show HN thread cough) So you made me dig up the announcement, and contrary to how you recall, it is almost universally positive. https://news.ycombinator.com/item?id=5408002 https://news.ycombinator.com/item?id=5408002
nirushiv 2y ago
I haven’t read through the code in detail but I can tell you “sub-nanosecond overhead” is misleading and marketing fluff. On first look, the measure seems to be some convoluted “time per thing” where the number of threads is far far smaller than the number of “thing”s
- mananaysiempre 2y ago
  That is the ecological niche of Rayon (cited) as well, isn’t it? You need to process a lot of things (thousands to millions), you want to parallelize that processing as much as possible (couple dozen of cores tops), you want to not get killed by scheduling overhead. So you account for the per-thing overhead.
  - CyberDildonics 2y ago
    Anything can have its overhead amortized, but claiming that amortization as your actual overhead is just a lie.
    - hansvm 2y ago
      Most engineers aren't precise with throughput vs latency. Ideally you should report both figures (and anything else salient in performance-sensitive spaces), but it's less a lie and more an extremely commonplace mode of thinking and speaking. 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.
      - CyberDildonics 2y ago
        Most engineers aren't precise with throughput vs latency. 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.
raggi 2y ago
cooperative scheduling is the basis for so many patterns with great metrics :)
- nine_k 2y ago
  But it's not very cooperative, as in tasks yielding to each other. They mostly cooperate by letting some tasks to be given to other threads, and not all the time, but once in a heartbeat. The scheduling happens rarely, so its amortized cost is low.
  - raggi 2y ago
    sure, but that's all details, and there are other cooperative scheduling models which aren't excessively eager. this isn't to be a downer on this implementation, or other implementations, but just generally pointing at cooperative advantages, of which there are many, with one particular implicit and major downside, which is starvation when the cooperation contract is not adhered to.
akovaski 2y ago
I'm not terribly familiar with this space, but I do like the concurrency model presented here. 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.
- akovaski 2y ago
  One thing I noticed was that when I build in Debug mode `zig build`, I got: Baseline,3.92809172 Spice 1 thread,19.1012624 When I built with ReleaseSafe mode `zig build --release=safe`, I got: Baseline,3.264224280000001 Spice 1 thread,3.78043278 So Spice does have a notable degradation of performance if not built for release. The baseline implementation does not share the same degree of degradation when built with the Debug zig build mode. (zig 0.13.0)
gyrovagueGeist 2y ago
This is neat and links to some great papers. I wish the comparison was with OpenMP tasks though; I’ve heard Rayon has a reputation for being a bit slow
rojroy 2y ago
[dead]
rojroy 2y ago
[dead]
assafe 2y ago
This is great!
lcof 2y ago
Interesting research work! Besides the code itself, there is some good reasoning and the documentation is well written The 2018 paper on heartbeat scheduling is also an interesting read https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf
pgt 2y ago
Not to be confused with SpiceDB by AuthZed: https://authzed.com/spicedb https://authzed.com/spicedb
shwestrick 2y ago
For those curious, this implementation is based on a recent line of research called "heartbeat scheduling" which amortizes the overheads of creating parallelism, essentially accomplishing a kind of dynamic automatic granularity control. Related papers: (2018) Heartbeat Scheduling: Provable Efficiency for Nested Parallelism. https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf 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/papers/HELIX_PLDI_2021.pdf 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/papers/HELIX_ASPLOS_2024.pdf https://users.cs.northwestern.edu/~simonec/files/Research/pa... (2024) Automatic Parallelism Management. https://www.cs.cmu.edu/~swestric/24/popl24-par-manage.pdf https://www.cs.cmu.edu/~swestric/24/popl24-par-manage.pdf
- judofyr 2y ago
  Oh this is super interesting. I was only aware of the two first while writing Spice. I’ll definitely look into the two last as well. Thanks for sharing!
geertj 2y ago
Per the description this uses busy waiting in the workers to get to nanosecond level latencies. I wonder if anyone has a perspective on how realistic busy waiting is in large applications with tens of thousands of tasks? Maybe it works if the tasks are async (i.e. not thread based) so that you only have N waiters where N is the size of the executor’s thread pool? In any case energy consumption of such an architecture would be higher. 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).

394 points by dsp_person 2y ago

see also readme under bench https://github.com/judofyr/spice/blob/main/bench/README.md https://github.com/judofyr/spice/blob/main/bench/README.md

shoggouth 2y ago

List of limitations of the project: https://github.com/judofyr/spice?tab=readme-ov-file#limitations https://github.com/judofyr/spice?tab=readme-ov-file#limitati...

jd3 2y ago
Want to state off the bat this this project is awesome and huge kudos to the author for spending their time, attention, and energy 1) working diligently to get this working at all and 2) sharing it with the broader HN community, who are generally known to by hyper-critical to a pedantic degree and/or overly pessimistic (cough the initial Docker project Show HN thread cough) 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. [0]: https://www.sqlite.org/testing.html https://www.sqlite.org/testing.html
- pverghese 2y ago
  You are welcome to add it. This is a proof of concept
  - jd3 2y ago
    > Spice is primarily a research project. Read along to learn more about it, but if you're considering using it in production you should be aware of its many limitations. Ah, I missed that upon first read. In that case, that caveat/limitation is definitely justified.
- dsp_person 2y ago
  > sharing it with the broader HN community Note that I posted this, but I am not the author
- stareatgoats 2y ago
  > (cough the initial Docker project Show HN thread cough) Docker was largely met with enthusiasm here when it was launched. I believe you must refer to how Dropbox was received — famously negatively, initially.
  - WaffleIronMaker 2y ago
    Yeah, that seems right: April 5, 2007: "Show HN, Dropbox" https://news.ycombinator.com/item?id=8863 https://news.ycombinator.com/item?id=8863
    - Dylan16807 2y ago
      Looks positive to me!
  - jd3 2y ago
    Yes, I meant to say dropbox
- dagw 2y ago
  HN community, who are generally known to by hyper-critical to a pedantic degree and/or overly pessimistic (cough the initial Docker project Show HN thread cough) So you made me dig up the announcement, and contrary to how you recall, it is almost universally positive. https://news.ycombinator.com/item?id=5408002 https://news.ycombinator.com/item?id=5408002

nirushiv 2y ago

I haven’t read through the code in detail but I can tell you “sub-nanosecond overhead” is misleading and marketing fluff. On first look, the measure seems to be some convoluted “time per thing” where the number of threads is far far smaller than the number of “thing”s

mananaysiempre 2y ago
That is the ecological niche of Rayon (cited) as well, isn’t it? You need to process a lot of things (thousands to millions), you want to parallelize that processing as much as possible (couple dozen of cores tops), you want to not get killed by scheduling overhead. So you account for the per-thing overhead.
- CyberDildonics 2y ago
  Anything can have its overhead amortized, but claiming that amortization as your actual overhead is just a lie.
  - hansvm 2y ago
    Most engineers aren't precise with throughput vs latency. Ideally you should report both figures (and anything else salient in performance-sensitive spaces), but it's less a lie and more an extremely commonplace mode of thinking and speaking. 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.
    - CyberDildonics 2y ago
      Most engineers aren't precise with throughput vs latency. 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.

raggi 2y ago

cooperative scheduling is the basis for so many patterns with great metrics :)

nine_k 2y ago
But it's not very cooperative, as in tasks yielding to each other. They mostly cooperate by letting some tasks to be given to other threads, and not all the time, but once in a heartbeat. The scheduling happens rarely, so its amortized cost is low.
- raggi 2y ago
  sure, but that's all details, and there are other cooperative scheduling models which aren't excessively eager. this isn't to be a downer on this implementation, or other implementations, but just generally pointing at cooperative advantages, of which there are many, with one particular implicit and major downside, which is starvation when the cooperation contract is not adhered to.

akovaski 2y ago

I'm not terribly familiar with this space, but I do like the concurrency model presented here. 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.

akovaski 2y ago
One thing I noticed was that when I build in Debug mode `zig build`, I got: Baseline,3.92809172 Spice 1 thread,19.1012624 When I built with ReleaseSafe mode `zig build --release=safe`, I got: Baseline,3.264224280000001 Spice 1 thread,3.78043278 So Spice does have a notable degradation of performance if not built for release. The baseline implementation does not share the same degree of degradation when built with the Debug zig build mode. (zig 0.13.0)

gyrovagueGeist 2y ago

This is neat and links to some great papers. I wish the comparison was with OpenMP tasks though; I’ve heard Rayon has a reputation for being a bit slow

rojroy 2y ago

[dead]

rojroy 2y ago

[dead]

assafe 2y ago

This is great!

lcof 2y ago

Interesting research work! Besides the code itself, there is some good reasoning and the documentation is well written The 2018 paper on heartbeat scheduling is also an interesting read https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf

pgt 2y ago

Not to be confused with SpiceDB by AuthZed: https://authzed.com/spicedb https://authzed.com/spicedb

shwestrick 2y ago

For those curious, this implementation is based on a recent line of research called "heartbeat scheduling" which amortizes the overheads of creating parallelism, essentially accomplishing a kind of dynamic automatic granularity control. Related papers: (2018) Heartbeat Scheduling: Provable Efficiency for Nested Parallelism. https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf 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/papers/HELIX_PLDI_2021.pdf 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/papers/HELIX_ASPLOS_2024.pdf https://users.cs.northwestern.edu/~simonec/files/Research/pa... (2024) Automatic Parallelism Management. https://www.cs.cmu.edu/~swestric/24/popl24-par-manage.pdf https://www.cs.cmu.edu/~swestric/24/popl24-par-manage.pdf

judofyr 2y ago
Oh this is super interesting. I was only aware of the two first while writing Spice. I’ll definitely look into the two last as well. Thanks for sharing!

geertj 2y ago

Per the description this uses busy waiting in the workers to get to nanosecond level latencies. I wonder if anyone has a perspective on how realistic busy waiting is in large applications with tens of thousands of tasks? Maybe it works if the tasks are async (i.e. not thread based) so that you only have N waiters where N is the size of the executor’s thread pool? In any case energy consumption of such an architecture would be higher. 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).