hadrieng2 / spmc-buffer Goto Github PK
View Code? Open in Web Editor NEWAn extension of triple-buffering to multiple-consumer scenarios
License: Mozilla Public License 2.0
An extension of triple-buffering to multiple-consumer scenarios
License: Mozilla Public License 2.0
Same issue as HadrienG2/triple-buffer#4, except that I would be even more reluctant to give consumers the ability to write to their buffer, as from an implementation point of view it means that multiple consumers could not safely share a single version of the buffer anymore.
In spmc_buffer, multiple readers can be accessing a buffer's inner data concurrently. Therefore, the inner type should be Sync in order to avoid data races with types exposing inner mutability such as Cell.
This mirrors HadrienG2/triple-buffer#5 . Given that I only need the inner type to be clonable at buffer creation time, imposing a Clone requirement is actually a bit too strong, and I would be fine with a Default type as well for example.
Use simpler struct names, as in TripleBuffer v1, and clean up the code a bit along the way to make it easier to understand and prepare for #4.
Unlike TripleBuffer, SPMCBuffer is not always wait-free for the producer. There are situations where the producer will block for an unbounded amount of time, the simplest scenario being when the producer attempts a buffer swap and all other buffers are currently held by consumers who do not want to move to the latest buffer version yet.
We currently handle this by with a spin loop. But that can be a waste of CPU time. Instead, we should use the OS facilities for blocking the thread. Rust provides two different accesses to them, one being thread::park/unpark and the other being Condvars. Since the identity of the producer thread can change over time, I think it's best to use a Condvar.
There is a catch, however. When the producer looks for spare buffers, it does not lock a mutex, and allows consumers to liberate buffers concurrently. That's a feature, because SPMCBuffer is designed to be efficient in the wait-free regime, where producer blocking is rare, and having consumers lock a mutex on every read buffer switch comes with a scalability tax. But it means that at the time where the producer does decide to go to sleep due to storage exhaustion, storage may actually already have been concurrently liberated by consumers, which means that a producer should not solely count on consumers to wake it up on storage liberation, but also check again from time to time.
Here is how I propose to handle this. On the data structure side, I would add the following:
The producer's slow "no buffer found" path would be modified as follows:
The consumer's buffer liberation path would be extended with the following procedure:
It would be tempting to also unset the flag along the way. But wakeups may be lost since there is a delay between the moment where a producer sets the "going to sleep" flag and actually goes to sleep. As the producer will clear the flag right after waking up, I think that optimizing the optimization like this would just be an unnecessary increase of the lost wakeup risk for the sake of hypothetical CPU performance in an overall rare event.
Just like triple-buffer ( HadrienG2/triple-buffer#3 ), the current version of spmc-buffer does not align buffers sufficiently far apart in memory to prevent false sharing. Once some facilities for this land in stable Rust, I should correct this.
Same issue as HadrienG2/triple-buffer#2 .
Same issue as HadrienG2/triple-buffer#1 , except that due to reference counting, we should probably rather go for at least 16-bit unsigned integers.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.