3 ms·

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 qu

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.
- knuthsat 5y ago
  What about smol?
  - ModernMech 5y ago
    smol is in the same category as Tokio - it's a runtime for the async capabilities in Rust.
kprotty 5y ago
I don't think tokio's slowness here is "to be expected". There isn't much reason for tokio tasks to have that much overhead over normal thread pools. The I/O driver shouldn't be called in such a benchmark given there's no I/O work happening. Waker's only add a reference count inc/dec + an atomic cas for wake() which should only happen on the JoinHandle `awaits` [4] compared to just an atomic swap for the Zig case on the join handle. Golang doesn't poll for I/O under such cases [0] and tokio should be using the `ParkThread` parker for putting threads to sleep [1] given `net` features aren't enabled (not sure if this is the actually the case) which you can force with a custom Runtime initialization instead of `#[tokio::main]` as an exercise. `crossbeam-deque` requires heap allocation for the run queues, heap allocates on growth, and garbage collects said memory. This is an overhead I wished to avoid and is something tokio has been improvements with avoiding as well [2]. `rayon` isn't a good comparison here given `rayon::join` is optimized to hook directly into the scheduler and run the caller only until the other forked-section completes [3]. This isn't general purpose and it takes advantage of unbounded stack allocation which can technically cause a stack overflow. Zig could do this and also take advantage of batch scheduling, but it complicates the code and is unfair here given `async` usage. Tokio, golang, and the Zig benchmarks require heap allocation on spawn so I believe it makes it a fairer comparison. This is also why I used rayon scopes instead of join(): less specialization and reintroduced the heap allocation from the unbounded concurrency. The `unsafe` there is from me copying the benchmark code from the tokio version to the rayon version and forgetting to remove the hack. In tokio, ownership of the array needed to be passed into the function given the lifetime was no longer linear from the spawn() I assume (correct me if i'm wrong here, but this is what the compile error hinted at). So I needed to recreate the array after the function, hence unsafe. If there's a better way for the tokio version, please send a PR. I see you've done so for the rayon version and I gladly merged it. [0]: See `atomic.Load(&netpollWaiters) > 0` in https://golang.org/src/runtime/proc.go https://golang.org/src/runtime/proc.go [1]: https://github.com/tokio-rs/tokio/blob/master/tokio/src/runtime/driver.rs#L30p https://github.com/tokio-rs/tokio/blob/master/tokio/src/runt... [2]: https://tokio.rs/blog/2019-10-scheduler#a-better-run-queue https://tokio.rs/blog/2019-10-scheduler#a-better-run-queue [3]: https://docs.rs/rayon-core/1.9.1/src/rayon_core/join/mod.rs.html#152 https://docs.rs/rayon-core/1.9.1/src/rayon_core/join/mod.rs.... [4]: https://github.com/tokio-rs/tokio/blob/98578a6f4a494e709f00018b1cd5b0e3dd9a0f72/tokio/src/runtime/task/harness.rs#L226-L241 https://github.com/tokio-rs/tokio/blob/98578a6f4a494e709f000...

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.
knuthsat 5y ago
What about smol?
- ModernMech 5y ago
  smol is in the same category as Tokio - it's a runtime for the async capabilities in Rust.

kprotty 5y ago

I don't think tokio's slowness here is "to be expected". There isn't much reason for tokio tasks to have that much overhead over normal thread pools. The I/O driver shouldn't be called in such a benchmark given there's no I/O work happening. Waker's only add a reference count inc/dec + an atomic cas for wake() which should only happen on the JoinHandle `awaits` [4] compared to just an atomic swap for the Zig case on the join handle. Golang doesn't poll for I/O under such cases [0] and tokio should be using the `ParkThread` parker for putting threads to sleep [1] given `net` features aren't enabled (not sure if this is the actually the case) which you can force with a custom Runtime initialization instead of `#[tokio::main]` as an exercise. `crossbeam-deque` requires heap allocation for the run queues, heap allocates on growth, and garbage collects said memory. This is an overhead I wished to avoid and is something tokio has been improvements with avoiding as well [2]. `rayon` isn't a good comparison here given `rayon::join` is optimized to hook directly into the scheduler and run the caller only until the other forked-section completes [3]. This isn't general purpose and it takes advantage of unbounded stack allocation which can technically cause a stack overflow. Zig could do this and also take advantage of batch scheduling, but it complicates the code and is unfair here given `async` usage. Tokio, golang, and the Zig benchmarks require heap allocation on spawn so I believe it makes it a fairer comparison. This is also why I used rayon scopes instead of join(): less specialization and reintroduced the heap allocation from the unbounded concurrency. The `unsafe` there is from me copying the benchmark code from the tokio version to the rayon version and forgetting to remove the hack. In tokio, ownership of the array needed to be passed into the function given the lifetime was no longer linear from the spawn() I assume (correct me if i'm wrong here, but this is what the compile error hinted at). So I needed to recreate the array after the function, hence unsafe. If there's a better way for the tokio version, please send a PR. I see you've done so for the rayon version and I gladly merged it. [0]: See `atomic.Load(&netpollWaiters) > 0` in https://golang.org/src/runtime/proc.go https://golang.org/src/runtime/proc.go [1]: https://github.com/tokio-rs/tokio/blob/master/tokio/src/runtime/driver.rs#L30p https://github.com/tokio-rs/tokio/blob/master/tokio/src/runt... [2]: https://tokio.rs/blog/2019-10-scheduler#a-better-run-queue https://tokio.rs/blog/2019-10-scheduler#a-better-run-queue [3]: https://docs.rs/rayon-core/1.9.1/src/rayon_core/join/mod.rs.html#152 https://docs.rs/rayon-core/1.9.1/src/rayon_core/join/mod.rs.... [4]: https://github.com/tokio-rs/tokio/blob/98578a6f4a494e709f00018b1cd5b0e3dd9a0f72/tokio/src/runtime/task/harness.rs#L226-L241 https://github.com/tokio-rs/tokio/blob/98578a6f4a494e709f000...