mgeier / rtrb

A realtime-safe single-producer single-consumer (SPSC) ring buffer
Apache License 2.0
202 stars 14 forks source link

Comparison against alternative crates? #39

Open TheButlah opened 3 years ago

TheButlah commented 3 years ago

Hi, I'm considering using this crate but am unsure whether the performance is any better than the other SPSPC wait free ringbuffers. A comparison to crossbeam_channel might also be merited, since I could see using their bounded queues in a very similar way to the ringbuffer.

mgeier commented 3 years ago

Thanks for bringing this up! This is an interesting but complicated topic ...


First, the simple thing: SPSC is always faster than MPSC/SPMC/MPMC. If not, the SPSC implementation sucks (or the other one is incorrect). SPSC is just a much simpler problem with a much simpler solution. Not only is it less complex, it also needs much less code and is typically easier to understand. On the flip side, it's also much more limted.

All crossbeam queues are slower than this SPSC (and any reasonable other SPSC implementation). That's why https://github.com/crossbeam-rs/crossbeam/pull/338 was started, which also includes a few benchmarks. The rtrb implementation is based on that PR, which was never merged.


When it comes to comparing SPSC implementations, you should consider multiple aspects:

Correctness is very hard to check, because all SPSC implementations use a fair amount of unsafe code. It's basically impossible to test, you'll have to analyze the code to convince yourself that it is correct.

I think that rtrb is correct, but who am I to say?

I think the most important difference between the existing SPSC crates is their API. Many crates only work for u8 values, some work with arbitrary T. The simplest API is to push() and pop() single items. Some crates (e.g. rtrb and https://github.com/agerasev/ringbuf) allow to handle multiple items at once, which is more efficient than repeated push() and/or pop(). The most efficient way to write multiple items will involve an unsafe API (because of uninitialized memory). IMHO the API of rtrb is nicer than ringbuf, but I'm of course very biased.

What kind of operations are you planning to use? Which of the provided APIs do you prefer?

If there is something missing in the API of rtrb, please let me know!

Finally, performance ...

It's very hard to create meaningful benchmarks. I've created some in the benches directory, which can be run with cargo bench. The single-threaded benchmarks are quite reliable and reproducible, but also mostly useless. The more interesting part is the behavior when two threads are involved, but the benchmarks are potentially less reproducible due to unpredictable OS thread scheduling.

If you want to compare rtrb to other crates, you can copy the benchmarking code and adapt it accordingly. Some time ago, I've started working on a comparison between crates (https://github.com/mgeier-forks/rtrb/tree/performance-comparison), but I haven't finished it. If you want, you can try it anyway, by running cargo bench in the performance-comparison subdirectory.

All this is probably meaningless, because the benchmark code will most likely not reflect your actual usage pattern, and the real-life performance differences between SPSC implementations are probably negligibly small anyway.

mgeier commented 3 years ago

Keeping in mind that all benchmarks are wrong, here is one result from running the two-threads benchmark from the https://github.com/mgeier-forks/rtrb/tree/performance-comparison branch on my laptop:

violin

You should of course not trust the good result for rtrb, because I created the benchmark (and I selected the result from a few runs).

Changes of about 10% are common between runs, sometimes there are even 20% changes.

If you have any ideas how to make the results more stable (or more meaningful in general), please let me know!

ghost commented 3 years ago

image my test result.

ghost commented 3 years ago

with

[profile.bench]
lto = true
opt-level = 3
codegen-units = 1

and tweaked my kernel, resulting in a very amazing speed. image

mgeier commented 3 years ago

I've just tried it with the suggested [profile.bench] settings:

violin

The differences are not that big, but it looks like the pop() timings improve in most crates.

Could that mean that maybe an #[inline] is missing in one of the functions in the pop() code path?

tweaked my kernel, resulting in a very amazing speed.

Are you talking about changes to the Linux scheduler?

This might have an influence on how the secondary thread (the one that generates contention on the atomic variables) is scheduled and therefore distort the measurements.

ghost commented 3 years ago

I followed the red hat low latency tuning guide, https://access.redhat.com/sites/default/files/attachments/201501-perf-brief-low-latency-tuning-rhel7-v1.1.pdf, I disable the hyperthreading and turned all the kernel commands mentioned in doc. And use the low latency tuned-adm profile setting. I also use cpuset clear the core I use for benchmark.

mgeier commented 3 years ago

Thanks @zhenpingfeng for the information about latency tuning. This looks very promising and I'll have a closer look when I have more time.

In the meantime, I've modified the benchmark code a bit: #42. I hope this makes it more reproducible and also more meaningful.

I also modified the performance comparison and created a new branch: https://github.com/mgeier-forks/rtrb/tree/performance-comparison2

violin

mgeier commented 3 years ago

@TheButlah Coming back to your original question about crossbeam-channel ...

I tried my latest benchmark with crossbeam-queue and concurrent-queue:

violin

I must say I'm quite surprised how fast they are!

In the uncontended case they are quite a bit slower than most SPSC implementations but faster than ringbuf!

In the contended case it's much closer. crossbeam-queue is only a little bit slower than the SPSC implementations, and concurrent-queue is even faster than ringbuf.

ghost commented 3 years ago

image my benchmark2 result.

ghost commented 3 years ago
use rtrb::RingBuffer;
use std::thread;
use std::time::Instant;

fn main() {
    let (mut producer, mut consumer) = RingBuffer::<Instant>::new(2).split();

    thread::spawn(move || {
        loop {
            match consumer.pop().ok() {
                Some(now) => {
                    println!("{:?}", now.elapsed());
                }
                None => { continue; }
            }
        }
    });

    loop {
        let now = Instant::now();
        let _ = producer.push(now).is_ok();
    }
}

I have some questions. The elapsed time I get by using the above code is about 4us (FIFO scheduler). Is my method of using this library wrong? Or sending an Instant structure does take this amount of time? How can I reduce the latency to the nanosecond level?

New update:

fn main() {

    let num_msg: usize = 1_000_000;

    let (mut producer, mut consumer) = RingBuffer::<Instant>::new(2).split();

    thread::spawn(move || {
        let mut n = 0;
        loop {
            match consumer.pop().ok() {
                Some(now) => {
                    let _ = now.elapsed();
                    if n != num_msg {
                        n += 1;
                    } else {
                        break
                    }
                }
                None => { continue; }
            }
        }
    });

    let now = Instant::now();
    for n in 0..num_msg {
        while !producer.push(now).is_ok() {};
    }

    println!("avg {:?}", now.elapsed() / num_msg as u32);
}

After removing the println! marco, it now only cost around 120ns per send. problem solved.

mgeier commented 3 years ago

Thanks @zhenpingfeng for running the benchmarks again, the results seem pretty much consistent with mine, which is good!

The idea of sending an Instant through the ring buffer is brilliant! However, in your updated code, this isn't really used anymore, right? You might as well send any other payload since you are ignoring the value obtained from pop().

BTW, I think you could replace your match statement with if let, and the continue statement is superfluous since it is the last statement in the loop anyway.

ghost commented 3 years ago

Actually, the elapsed function call is worked, if I remove it, each sends only cost around 100ns.

mgeier commented 3 years ago

Actually, the elapsed function call is worked, if I remove it, each sends only cost around 100ns.

Yes, sure, the elapsed() method is called, but the result is ignored, so you might as well remove it.

We are not interested in benchmarking the elapsed() method, right?

If it takes 100ns without the elapsed() call, this perfectly matches your result from above (https://github.com/mgeier/rtrb/issues/39#issuecomment-823770692), doesn't it?

ghost commented 2 years ago

An Update for rtrb 0.2.2 and rustc 1.65.0-nightly under 5.15.0-46-generic Ubuntu image

mgeier commented 2 years ago

Thanks @zhenpingfeng for the updated measurement!

It's interesting that npnc seems to have gotten slightly worse in the contended case. But maybe that's just measurement inaccuracy.

BTW, there is a new branch with additional crates for performance comparison: https://github.com/mgeier-forks/rtrb/tree/performance-comparison3. And I've removed spsc-bounded-queue because it has been yanked from crates.io.

ghost commented 2 years ago

image the performance-comparison3 result

mgeier commented 2 years ago

Here's the result on my laptop (Intel(R) Core(TM) i5-7Y54)

violin

jmakov commented 1 year ago

Can we get this kind of pics in the README on the landing page? Super interesting.

mgeier commented 11 months ago

Thanks for the suggestion @jmakov! I'm hesitant to provide "official" plots in the README, because all benchmarks are wrong. But I'm adding a few sentences with a link to this issue here, where everyone can comment on their flaws and can provide opposing results.

See #107.

kasparthommen commented 6 months ago

Hi @mgeier , have you ever tried including Disruptor-inspired crates into your benchmarks, like any of the following?

mgeier commented 6 months ago

Thanks for the hint @kasparthommen, I have never heard of it!

I didn't quite understand the API though ... I have added the performance comparison to the codebase (see #123), would you like to add a PR adding the crates you suggested?

Speaking of which, I have updated the benchmarks recently, so I think it's time to share some plots again. I did those on Linux, with an Intel(R) Core(TM) i5-7Y54 CPU.

I split the benchmarks in two parts. One uses a very small buffer size (only 2 elements!), which means there is a lot of contention and many of the attempted read and write operations will fail:

benchmark results for small buffer

The other benchmark uses a very large buffer size, and therefore no contention at all, so that every single intended read and write operation will succeed:

benchmark results for large buffer

I think those are the worst-case and best-case scenarios, respectively, and any real use case will be somewhere in between.

Note that npnc is best in the uncontended case (likely because it uses the power-of-2 index wrapping trick), but it is significantly worse in the contended case.

On the other hand, omango is the best in the contended case, but it takes more than twice as long as the leaders in the uncontended case.

If anyone else wants to share their results (especially on other CPU architectures), please go ahead!

boranby commented 5 months ago

large small

I ran two-threads-large without magnetic to see the others in more detail. large-no-magnetic