Spice: Fine-grained parallelism with sub-nanosecond overhead in Zig • Hacker News Board

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

#41

Post by audunw » Tue, Aug 13, 2024, 1:43 PM UTC

nirushiv wrote: post #4

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

Did you read the README at all? I thought it was extremely precise about what exactly is meant by the claim in the title. Not much room for misunderstanding.

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.

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

#42

Post by shwestrick » Tue, Aug 13, 2024, 1:43 PM UTC

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.

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

#43

Post by imtringued » Tue, Aug 13, 2024, 2:05 PM UTC

judofyr wrote: post #26

nirushiv wrote: post #4

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

Author here. 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 par…

Adding more cores doesn't change the time per operation. Your graphs are grossly wrong. What you should have done is drop the nanoseconds and just take the total execution time. Whenever you're writing 1.64ns, you should have written 164ms.

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.

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

#44

Post by geertj » Tue, Aug 13, 2024, 2:28 PM UTC

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).

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

#45

Post by judofyr » Tue, Aug 13, 2024, 3:17 PM UTC

shwestrick wrote: post #42

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 (2021) Task Parallel Assembly Lan…

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!

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

#46

Post by aidenn0 » Tue, Aug 13, 2024, 3:37 PM UTC

mgaunard wrote: post #35

judofyr wrote: post #26

Earlier quoted context omitted.

Author here. 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 par…

You can just divide the speed-up by the number of cores, and that gives you the parallelization efficiency. 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.

> You can just divide the speed-up by the number of cores, and that gives you the parallelization efficiency.

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.

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

#47

Post by CyberDildonics » Tue, Aug 13, 2024, 4:18 PM UTC

hansvm wrote: post #25

CyberDildonics wrote: post #18

Earlier quoted context omitted.

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.

It's not "lying" to use the words most likely to correctly get your point across to your target audience. Maybe they could have communicated better (for a seemingly dead project, IMO they put enough time in regardless), but it's not lying. > 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 someon…

The whole point of overhead is that it is a base constant on top of whatever you do. The whole point of overhead is to eventually be amortized in some way. When someone asks what the overhead is, it is a lie to try to factor amortization in because it's implied that it will be done somewhere anyway.

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

#48

Post by littlestymaar » Tue, Aug 13, 2024, 4:22 PM UTC

littlestymaar wrote: post #33

judofyr wrote: post #26

Earlier quoted context omitted.

Author here. 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 par…

Thanks for the answer, this part is particularly interesting indeed: > 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 off…

Too late to edit so I'll put it here:

> 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…

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

#49

Post by Veedrac » Tue, Aug 13, 2024, 8:27 PM UTC

adrian_b wrote: post #30

x-complexity wrote: post #11

Earlier quoted context omitted.

> I can tell you “sub-nanosecond overhead” is misleading and marketing fluff If and only if (1-thread Spice - non-parallelized baseline) > 1ns, which their tests back up their claims. https://github.com/judofyr/spice/tree/main/bench

At your link it also says: "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.

IMO this is the least convincing part of the benchmark though, since it's uninterpretable without an optimal baseline. You don't know how much of this is because of Spice and how much is because of how the task scales. (This is acknowledged as future work.)

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

#50

Post by Dylan16807 » Wed, Aug 14, 2024, 12:08 AM UTC

WaffleIronMaker wrote: post #40

stareatgoats wrote: post #38

Earlier quoted context omitted.

> (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.

Yeah, that seems right: April 5, 2007: "Show HN, Dropbox" https://news.ycombinator.com/item?id=8863

Looks positive to me!