16 ms·

Running the benchmarks locally (zig is fastest, but that's probably expected) zig (~1 week older than HEAD): ./zig-out/bin/qsort filling shuffling

by Jarred 5y ago

Running the benchmarks locally (zig is fastest, but that's probably expected) zig (~1 week older than HEAD): ./zig-out/bin/qsort filling shuffling running took 177.46ms rust nightly: cargo run --release --bin qsort warning: the cargo feature `edition2021` has been stabilized in the 1.56 release and is no longer necessary to be listed in the manifest See https://doc.rust-lang.org/nightly/cargo/reference/manifest.html#the-edition-field for more information about using this feature. Finished release [optimized] target(s) in 0.02s Running `target/release/qsort` filling shuffling running took 896.91656ms cargo run --release --bin rsort warning: the cargo feature `edition2021` has been stabilized in the 1.56 release and is no longer necessary to be listed in the manifest See https://doc.rust-lang.org/nightly/cargo/reference/manifest.html#the-edition-field for more information about using this feature. Finished release [optimized] target(s) in 0.02s Running `target/release/rsort` filling shuffling running took 212.190694ms go 1.16.3: go run qsort.go filling shuffling running took 222.90356ms on macOS 11.5.2 with a 2.4 GHz 8-Core Intel Core i9

komuW 5y ago
When you do `go run qsort.go` you are also timing the time taken by Golang to build/compile the code. I suspect the same applies to `cargo run` You should do something like; `go build . && time ./qsort`
- masklinn 5y ago
  The same occurs with Rust, we can even see that the no-op recompilation takes about 20ms. It’s obviously just a rough estimate / comparison otherwise it’d be using hyperfine or something along those lines.
  - nessex 5y ago
    This is not the case, it measures the time between two points in the code at runtime and prints that[1]. [1] https://github.com/kprotty/zap/blob/blog/benchmarks/rust/rayon_qsort.rs#L14-L17 https://github.com/kprotty/zap/blob/blog/benchmarks/rust/ray...
- Arnavion 5y ago
  The "took #ms" line is output of the program. It does not include compilation time.
Arnavion 5y ago
The fact that the Rust tokio version (the one that uses tokio tasks instead of threads) is slow is to be expected. tokio tasks aren't appropriate for running quicksort; they will have overhead compared to a regular threadpool because of I/O reactor, waker etc code that will never get used. rayon or crossbeam are more appropriate since they are actually designed for general-purpose thread work. Using rayon's scopes will also get rid of the `unsafe` that's being (ab)used to create the fake `&'static mut` slices. Though for some reason, the rayon version (rayon_qsort.rs) uses scopes, but still uses `unsafe` to create `&'static mut` slices... ( https://github.com/kprotty/zap/pull/3 https://github.com/kprotty/zap/pull/3 )
- gefhfff 5y ago
  Can you explain that Tokio vs crossbeam vs rayon a bit more? Should I default to rayon or crossbeam because of that?
  - YorickPeterse 5y ago
    Crossbeam is a library that provides various concurrency primitives, such as a queue type that allows stealing of work. Rayon is a library for running code in parallel. Typically you'll give it a (parallel) iterator of sorts, and it will distribute the work across a pool of threads. Tokio is a library for async IO operations.
  - nicoburns 5y ago
    Tokio is designed for concurrent io, rayon, or tokio-threadpool for concurrent cpu-bound task.
  - ModernMech 5y ago
    It depends on what you want to do. If you are doing io-bound work, Tokio would be what you want -- you would use it as a runtime for the async capabilities in Rust. If you have cpu-bound work, then rayon is what you want to use. Rayon is a work-stealing parallelism crate -- it will schedule work to be done, and different threads will schedule portions of it as they become available to do work. It's very easy to get 100% CPU utilization across all cores use Rayon if your work is naturally paralellizable, and the interface is dead simple: anywhere you do a .iter(), you can turn it into a .par_iter(), and Rayon will parallelize the work. Note there is some overhead to using Rayon -- you normally will be better off doing your work on a single thread unless you have a large number of elements in your collection... I found for my application I needed more than 1e6 elements before I saw an appreciable performance benefit to using Rayon. As others said, Crossbeam is for sending and receiving messages across threads. I use it alongside of tokio and rayon.
erichdongubler 5y ago
Does this already use `target-cpu=native`? Not sure if that would be apples-to-apples with the Zig implementation (which is what's important here), but I'd be surprised if it didn't yield some interesting wins.
rdsubhas 5y ago
At first glance, this looks great, almost 20% speedup! But genuine question, this looks to be how almost every new tech begins. Initially it's FAST because it keeps things as barebones as possible, and everything else other than the specific module can be ignored. But no feature works in isolation, so as more features get added – scheduling constraints, safety quirks, or random features that cut across the language – the 20% looks like nothing. I did go through the blog, but how can one be sure that this 20% gap is a guaranteed design advantage, and not just a temporary deferral of everything else?
- skohan 5y ago
  fwiw Zig is taking its role as a low-level, bare bones "c replacement" as a core design constraint. For instance zig has eschewed from even fairly tame features like operator overloading because they're not considered in line with Zig's identity as a minimal, explicit language. So feature creep is always a concern, but from what I understand Zig has a better chance at avoiding this than other projects due to the language's guiding philosophy.
- kristoff_it 5y ago
  Nobody can predict the future, but one thing that might help is that Protty is in the Zig core dev team and, as the post shows, he really cares about efficiency.
- jorangreef 5y ago
  > this looks to be how almost every new tech begins On second thought, do you think this is true? The level of detail shown in this post is fairly extraordinary for event loops just getting started. > how can one be sure that this 20% gap is a guaranteed design advantage I would say because the design is solid and recognizes principles of mechanical sympathy that are fundamental and unlikely to change for quite some time.
- dnautics 5y ago
  > how can one be sure that this 20% gap is a guaranteed design advantage It's no guarantee, but in my experience, Zig is a language that lends itself very well to composability. I imagine that instead of adding features to stdlib, anyone who needs "extra features" in their threading system will find it quite easy to implement their own as a library outside of stdlib that can easily be swapped in and out in A/B tests for the library consumer. If some feature or another is REALLY wanted in the stdlib for some reason it would probably be easy to drop it behind a comptime-flag as part of a type constructor function, which won't compromise (runtime) performance, teeny tiny hit to comptime performance.
stewbrew 5y ago
Erm, could somebody explain to me why I shouldn't understand this as an argument pro go given that it is about as fast as the fully optimized versions of zig and rust?
- kristoff_it 5y ago
  I think that's a perfectly reasonable way of looking at it.
- jerf 5y ago
  Go's value proposition is that it has good bang-for-the-buck. It's fairly easy to write in. There's easier, but it's fairly easy. It performs fairly well. There are things that perform better, but it's fairly good. It scales fairly well. There's things that scale better, but it's pretty good. If you draw all this out on the programming landscape, I think one of the reasons Go has succeeded as well as it did is that this was a poorly covered part of the landscape. There were languages that were much easier, but performed much worse, and languages that performed much better, but generally required a lot more developer effort. I don't expect Go to ever top the charts on performance on a task like this, but it's often hanging around at only a bit slower, and it does that across a wide variety of tasks and on a wide variety of dimensions. It's not the best at much of anything, but it's pretty darned good for pretty cheap on a lot of measures.
- mamcx 5y ago
  Well, work with several task is THE thing with Go, right? If it were too much worse Go will fail. In situations like this, is important to remember that Rust/Zig are (system)languages to MAKE "Go" but also, million other different things with different goals. So other way to look at this is "If I wanna designa language with a runtime like Go, this both have it that close!"
pizza234 5y ago
I get inconsistent results, both in terms of platform and language. The benchmark may be flawed, and no conclusions should be drawn, to be prudent. Running on Linux (zig -Dc), rounded average of 3 runs. 8-thread Intel laptop machine: zip 0.9.0-dev.958: 945 rust 1.5.0-nightly 21-09-12/qsort: 545 rust 1.5.0-nightly 21-09-12/rsort: 255 go 1.16.8: 355 32-thread AMD workstation: zip 0.9.0-dev.958: 410 rust 1.5.0-nightly 21-09-12/qsort: 780 rust 1.5.0-nightly 21-09-12/rsort: 135 go 1.16.8: 135 Additionally, I haven't done a thorough review, but enabling the commented code: // Optimized version (hooks directly into the scheduler) // rayon::join( // || quick_sort(low), // || quick_sort(high) // ); yields a 110ms run on the faster machine.
- kprotty 5y ago
  I'm not sure how this implies it is flawed. It benchmarks thread pools so on a system which allowed more parallel concurrent tasks (i.e. 32t amd cpu) the throughput is expected to scale somewhat, and you see this in your results. Also, `zig -Dc` links to libc (`-Dc`) but builds in debug mode by default, similar to Rust and C/C++ compilers. The readme contains instructions to compile it with optimizations (`-Drelease-fast`), the rust versions do so as well (`--release`) so you should re-evaluate your results. See one of my other comments in this post on why I didn't use rayon::join() by default.
  - pizza234 5y ago
    > Also, `zig -Dc` links to libc (`-Dc`) but builds in debug mode by default, similar to Rust and C/C++ compilers Right! This was a misunderstanding of mine. Updated results: 8-thread Intel laptop machine: zip 0.9.0-dev.958: 230 rust 1.5.0-nightly 21-09-12/qsort: 545 rust 1.5.0-nightly 21-09-12/rsort: 255 go 1.16.8: 355 32-thread AMD workstation: zip 0.9.0-dev.958: 125 rust 1.5.0-nightly 21-09-12/qsort: 780 rust 1.5.0-nightly 21-09-12/rsort: 135 go 1.16.8: 135 The reason why I think that conclusions should not be drawn due to the excessive variability between systems. On the parent poster's system, zig is faster by a much larger margin than the two systems I've tried. And there's a ~45% difference in Go's performance compared to the fastest runner for the respective system.
deleted 5y ago
[deleted]
adenozine 5y ago
Rust is such a bloated, insane design-by-committee language. It's actually still surprising to me that corporations are defending it and using it. I sure won't. It's also just so dang ugly to read. If Perl and C++ had a mutant offspring, I think it'd be Rust. And that's just not respectful to Perl! I'm really happy that Zig is doing so well. I'm planning on contributing a little chunk of money to the ZSF whenever they get a 1.0 landed. I do think there are some lessons to learn from Rust about formal methods as foundational building blocks in a language. I'm eager to see Zig mature more around the memory-safety side of things.
- pcwalton 5y ago
  There was no "design committee" for Rust. I'm increasingly skeptical that any language with lifetimes can be anything other than "ugly to read". People complain about syntax, but what they're really complaining about is semantics.
  - fiddlerwoaroof 5y ago
    The thing that really surprised me about Rust is the significance of a semicolon at the end of a function body. E.g.: fn foo { 1; } Returns unit while fn foo { 1 } Returns 1. This reminds me of nothing so much as the infamous JavaScript ASI footgun where this returns undefined: function foo() { return 2; }
    - c-cube 5y ago
      It's not just the function's body, it's any block. Blocks in rust are expressions and return their last statement's value. It's nothing like Javascript's ASI where it's just inserting ; implicitly and only `return` can return a value.
    - burntsushi 5y ago
      It's also nothing like Javascript because Rust is statically typed. If you accidentally insert a semi-colon (or not), you're almost guaranteed to get a compile error.

by Jarred 5y ago

komuW 5y ago

When you do `go run qsort.go` you are also timing the time taken by Golang to build/compile the code. I suspect the same applies to `cargo run` You should do something like; `go build . && time ./qsort`

masklinn 5y ago
The same occurs with Rust, we can even see that the no-op recompilation takes about 20ms. It’s obviously just a rough estimate / comparison otherwise it’d be using hyperfine or something along those lines.
- nessex 5y ago
  This is not the case, it measures the time between two points in the code at runtime and prints that[1]. [1] https://github.com/kprotty/zap/blob/blog/benchmarks/rust/rayon_qsort.rs#L14-L17 https://github.com/kprotty/zap/blob/blog/benchmarks/rust/ray...
Arnavion 5y ago
The "took #ms" line is output of the program. It does not include compilation time.

Arnavion 5y ago

The fact that the Rust tokio version (the one that uses tokio tasks instead of threads) is slow is to be expected. tokio tasks aren't appropriate for running quicksort; they will have overhead compared to a regular threadpool because of I/O reactor, waker etc code that will never get used. rayon or crossbeam are more appropriate since they are actually designed for general-purpose thread work. Using rayon's scopes will also get rid of the `unsafe` that's being (ab)used to create the fake `&'static mut` slices. Though for some reason, the rayon version (rayon_qsort.rs) uses scopes, but still uses `unsafe` to create `&'static mut` slices... ( https://github.com/kprotty/zap/pull/3 https://github.com/kprotty/zap/pull/3 )

gefhfff 5y ago
Can you explain that Tokio vs crossbeam vs rayon a bit more? Should I default to rayon or crossbeam because of that?
- YorickPeterse 5y ago
  Crossbeam is a library that provides various concurrency primitives, such as a queue type that allows stealing of work. Rayon is a library for running code in parallel. Typically you'll give it a (parallel) iterator of sorts, and it will distribute the work across a pool of threads. Tokio is a library for async IO operations.
- nicoburns 5y ago
  Tokio is designed for concurrent io, rayon, or tokio-threadpool for concurrent cpu-bound task.
- ModernMech 5y ago
  It depends on what you want to do. If you are doing io-bound work, Tokio would be what you want -- you would use it as a runtime for the async capabilities in Rust. If you have cpu-bound work, then rayon is what you want to use. Rayon is a work-stealing parallelism crate -- it will schedule work to be done, and different threads will schedule portions of it as they become available to do work. It's very easy to get 100% CPU utilization across all cores use Rayon if your work is naturally paralellizable, and the interface is dead simple: anywhere you do a .iter(), you can turn it into a .par_iter(), and Rayon will parallelize the work. Note there is some overhead to using Rayon -- you normally will be better off doing your work on a single thread unless you have a large number of elements in your collection... I found for my application I needed more than 1e6 elements before I saw an appreciable performance benefit to using Rayon. As others said, Crossbeam is for sending and receiving messages across threads. I use it alongside of tokio and rayon.

erichdongubler 5y ago

Does this already use `target-cpu=native`? Not sure if that would be apples-to-apples with the Zig implementation (which is what's important here), but I'd be surprised if it didn't yield some interesting wins.

rdsubhas 5y ago

At first glance, this looks great, almost 20% speedup! But genuine question, this looks to be how almost every new tech begins. Initially it's FAST because it keeps things as barebones as possible, and everything else other than the specific module can be ignored. But no feature works in isolation, so as more features get added – scheduling constraints, safety quirks, or random features that cut across the language – the 20% looks like nothing. I did go through the blog, but how can one be sure that this 20% gap is a guaranteed design advantage, and not just a temporary deferral of everything else?

skohan 5y ago
fwiw Zig is taking its role as a low-level, bare bones "c replacement" as a core design constraint. For instance zig has eschewed from even fairly tame features like operator overloading because they're not considered in line with Zig's identity as a minimal, explicit language. So feature creep is always a concern, but from what I understand Zig has a better chance at avoiding this than other projects due to the language's guiding philosophy.
kristoff_it 5y ago
Nobody can predict the future, but one thing that might help is that Protty is in the Zig core dev team and, as the post shows, he really cares about efficiency.
jorangreef 5y ago
> this looks to be how almost every new tech begins On second thought, do you think this is true? The level of detail shown in this post is fairly extraordinary for event loops just getting started. > how can one be sure that this 20% gap is a guaranteed design advantage I would say because the design is solid and recognizes principles of mechanical sympathy that are fundamental and unlikely to change for quite some time.
dnautics 5y ago
> how can one be sure that this 20% gap is a guaranteed design advantage It's no guarantee, but in my experience, Zig is a language that lends itself very well to composability. I imagine that instead of adding features to stdlib, anyone who needs "extra features" in their threading system will find it quite easy to implement their own as a library outside of stdlib that can easily be swapped in and out in A/B tests for the library consumer. If some feature or another is REALLY wanted in the stdlib for some reason it would probably be easy to drop it behind a comptime-flag as part of a type constructor function, which won't compromise (runtime) performance, teeny tiny hit to comptime performance.

stewbrew 5y ago

Erm, could somebody explain to me why I shouldn't understand this as an argument pro go given that it is about as fast as the fully optimized versions of zig and rust?

kristoff_it 5y ago
I think that's a perfectly reasonable way of looking at it.
jerf 5y ago
Go's value proposition is that it has good bang-for-the-buck. It's fairly easy to write in. There's easier, but it's fairly easy. It performs fairly well. There are things that perform better, but it's fairly good. It scales fairly well. There's things that scale better, but it's pretty good. If you draw all this out on the programming landscape, I think one of the reasons Go has succeeded as well as it did is that this was a poorly covered part of the landscape. There were languages that were much easier, but performed much worse, and languages that performed much better, but generally required a lot more developer effort. I don't expect Go to ever top the charts on performance on a task like this, but it's often hanging around at only a bit slower, and it does that across a wide variety of tasks and on a wide variety of dimensions. It's not the best at much of anything, but it's pretty darned good for pretty cheap on a lot of measures.
mamcx 5y ago
Well, work with several task is THE thing with Go, right? If it were too much worse Go will fail. In situations like this, is important to remember that Rust/Zig are (system)languages to MAKE "Go" but also, million other different things with different goals. So other way to look at this is "If I wanna designa language with a runtime like Go, this both have it that close!"

pizza234 5y ago

I get inconsistent results, both in terms of platform and language. The benchmark may be flawed, and no conclusions should be drawn, to be prudent. Running on Linux (zig -Dc), rounded average of 3 runs. 8-thread Intel laptop machine: zip 0.9.0-dev.958: 945 rust 1.5.0-nightly 21-09-12/qsort: 545 rust 1.5.0-nightly 21-09-12/rsort: 255 go 1.16.8: 355 32-thread AMD workstation: zip 0.9.0-dev.958: 410 rust 1.5.0-nightly 21-09-12/qsort: 780 rust 1.5.0-nightly 21-09-12/rsort: 135 go 1.16.8: 135 Additionally, I haven't done a thorough review, but enabling the commented code: // Optimized version (hooks directly into the scheduler) // rayon::join( // || quick_sort(low), // || quick_sort(high) // ); yields a 110ms run on the faster machine.

kprotty 5y ago
I'm not sure how this implies it is flawed. It benchmarks thread pools so on a system which allowed more parallel concurrent tasks (i.e. 32t amd cpu) the throughput is expected to scale somewhat, and you see this in your results. Also, `zig -Dc` links to libc (`-Dc`) but builds in debug mode by default, similar to Rust and C/C++ compilers. The readme contains instructions to compile it with optimizations (`-Drelease-fast`), the rust versions do so as well (`--release`) so you should re-evaluate your results. See one of my other comments in this post on why I didn't use rayon::join() by default.
- pizza234 5y ago
  > Also, `zig -Dc` links to libc (`-Dc`) but builds in debug mode by default, similar to Rust and C/C++ compilers Right! This was a misunderstanding of mine. Updated results: 8-thread Intel laptop machine: zip 0.9.0-dev.958: 230 rust 1.5.0-nightly 21-09-12/qsort: 545 rust 1.5.0-nightly 21-09-12/rsort: 255 go 1.16.8: 355 32-thread AMD workstation: zip 0.9.0-dev.958: 125 rust 1.5.0-nightly 21-09-12/qsort: 780 rust 1.5.0-nightly 21-09-12/rsort: 135 go 1.16.8: 135 The reason why I think that conclusions should not be drawn due to the excessive variability between systems. On the parent poster's system, zig is faster by a much larger margin than the two systems I've tried. And there's a ~45% difference in Go's performance compared to the fastest runner for the respective system.

deleted 5y ago

[deleted]

adenozine 5y ago

Rust is such a bloated, insane design-by-committee language. It's actually still surprising to me that corporations are defending it and using it. I sure won't. It's also just so dang ugly to read. If Perl and C++ had a mutant offspring, I think it'd be Rust. And that's just not respectful to Perl! I'm really happy that Zig is doing so well. I'm planning on contributing a little chunk of money to the ZSF whenever they get a 1.0 landed. I do think there are some lessons to learn from Rust about formal methods as foundational building blocks in a language. I'm eager to see Zig mature more around the memory-safety side of things.

pcwalton 5y ago
There was no "design committee" for Rust. I'm increasingly skeptical that any language with lifetimes can be anything other than "ugly to read". People complain about syntax, but what they're really complaining about is semantics.
- fiddlerwoaroof 5y ago
  The thing that really surprised me about Rust is the significance of a semicolon at the end of a function body. E.g.: fn foo { 1; } Returns unit while fn foo { 1 } Returns 1. This reminds me of nothing so much as the infamous JavaScript ASI footgun where this returns undefined: function foo() { return 2; }
  - c-cube 5y ago
    It's not just the function's body, it's any block. Blocks in rust are expressions and return their last statement's value. It's nothing like Javascript's ASI where it's just inserting ; implicitly and only `return` can return a value.
  - burntsushi 5y ago
    It's also nothing like Javascript because Rust is statically typed. If you accidentally insert a semi-colon (or not), you're almost guaranteed to get a compile error.