triple-buffer
ZIO
triple-buffer | ZIO | |
---|---|---|
4 | 59 | |
79 | 3,992 | |
- | 0.3% | |
6.3 | 9.5 | |
2 months ago | 2 days ago | |
Rust | Scala | |
Mozilla Public License 2.0 | Apache License 2.0 |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
triple-buffer
-
A lock-free single element generic queue
Great write up! I believe the colloquial name for this algorithm is a "lock-free triple buffer". Here's an implementation in Rust (I couldn't find any c/c++ examples) that has extremely thorough comments that might help completely wrap your head around the synchronization ordering. Rust uses the same semantics for atomic primitives as C11, so it should be pretty easy to match up with your implementation. I came to the same conclusion as you to solve an issue I had with passing arbitrarily large data between two threads in an RTOS system I was working with at my day job. It was an extremely satisfying moment, realizing the index variable was sufficient to communicate all the needed information between the two threads.
-
Rust Is Hard, Or: The Misery of Mainstream Programming
Rust marks cross-thread shared memory as immutable in the general case, and allows you to define your own shared mutability constructs out of primitives like mutexes, atomics, and UnsafeCell. As a result you don't get rope to hang yourself with by default, but atomic orderings are more than enough rope to devise incorrect synchronizations (especially with more than 2 threads or memory locations). To quote an earlier post of mine:
In terms of shared-memory threading concurrency, Send and Sync, and the distinction between &T and &Mutex and &mut T, were a revelation when I first learned them. It was a principled approach to shared-memory threading, with Send/Sync banning nearly all of the confusing and buggy entangled-state codebases I've seen and continue to see in C++ (much to my frustration and exasperation), and &Mutex providing a cleaner alternative design (there's an excellent article on its design at http://cliffle.com/blog/rust-mutexes/).
My favorite simple concurrent data structure is https://docs.rs/triple_buffer/latest/triple_buffer/struct.Tr.... It beautifully demonstrates how you can achieve principled shared mutability, by defining two "handle" types (living on different threads), each carrying thread-local state (not TLS) and a pointer to shared memory, and only allowing each handle to access shared memory in a particular way. This statically prevents one thread from calling a method intended to run on another thread, or accessing fields local to another thread (since the methods and fields now live on the other handle). It also demonstrates the complexity of reasoning about lock-free algorithms (https://github.com/HadrienG2/triple-buffer/issues/14).
I find that writing C++ code the Rust way eliminates data races practically as effectively as writing Rust code upfront, but C++ makes the Rust way of thread-safe code extra work (no Mutex unless you make one yourself, and you have to simulate &(T: Sync) yourself using T const* coupled with mutable atomic/mutex fields), whereas the happy path of threaded C++ (raw non-Arc pointers to shared mutable memory) leads to pervasive data races caused by missing or incorrect mutex locking or atomic synchronization.
-
Notes on Concurrency Bugs
In terms of shared-memory threading concurrency, Send and Sync, and the distinction between &T and &Mutex and &mut T, were a revelation when I first learned them. It was a principled approach to shared-memory threading, with Send/Sync banning nearly all of the confusing and buggy entangled-state codebases I've seen and continue to see in C++ (much to my frustration and exasperation), and &Mutex providing a cleaner alternative design (there's an excellent article on its design at http://cliffle.com/blog/rust-mutexes/).
My favorite simple concurrent data structure is https://docs.rs/triple_buffer/latest/triple_buffer/struct.Tr.... It beautifully demonstrates how you can achieve principled shared mutability, by defining two "handle" types (living on different threads), each carrying thread-local state (not TLS) and a pointer to shared memory, and only allowing each handle to access shared memory in a particular way. This statically prevents one thread from calling a method intended to run on another thread, or accessing fields local to another thread (since the methods and fields now live on the other handle). It also demonstrates the complexity of reasoning about lock-free algorithms (https://github.com/HadrienG2/triple-buffer/issues/14).
I suppose &/&mut is also a safeguard against event-loop and reentrancy bugs (like https://github.com/quotient-im/Quaternion/issues/702). I don't think Rust solves the general problem of preventing deadlocks within and between processes (which often cross organizational boundaries between projects and distinct codebases, with no clear contract on allowed behavior and which party in a deadlock is at fault), and non-atomicity between processes on a single machine (see my PipeWire criticism at https://news.ycombinator.com/item?id=31519951). File saving is also difficult (https://danluu.com/file-consistency/), though I find that fsync-then-rename works well enough if you don't need to preserve metadata or write through file (not folder) symlinks.
- A bug that doesn’t exist on x86: Exploiting an ARM-only race condition
ZIO
- The golden age of Kotlin and its uncertain future
-
I had a great experience with Scala and hopefully it will get more popular
scala has 2 healthy and pretty complete lib ecosystems : check out typelevel and ZIO. Both are FP oriented, which might not be your cup of tea at first glance but I would encourage you to try em out ! Softest introduction would be to start with the typelevel cats library and build up from there. The excellent Scala with Cats will ease you softly into an FP mindset. It's a bit dated and for scala 2 only but translating to Scala 3 is a very good exercise if you feel so inclined !
-
Is it prudent to use Scala for anything new?
Last but not least, Scala is currently the language with one of the best effect systems in my opinion (https://zio.dev/). Kotlin for example has copied the approach with https://arrow-kt.io/ which I think is great actually. But when comparing Scala and Kotlin here, Scala wins by a large margin, it is a completely different world. It's like building a highly concurrent system in Erlang vs C.
Of course, if you don't want to learn things like union types, traits/typeclasses and effects (similar to async/await but more powerful) you will be annoyed by Scala. But once you learned them, you can never go back.
-
How to get started?
ZIO
-
Reconnecting with Scala. What's new?
Links: - https://dotty.epfl.ch/ - https://scala-native.org/en/stable/ - https://www.scala-js.org/ - https://typelevel.org/ - https://zio.dev/ - https://github.com/scala-native/scala-native/pull/3120 - https://github.com/lampepfl/dotty/pull/16517 - https://dotty.epfl.ch/docs/reference/experimental/index.html - https://scala-cli.virtuslab.org/ - https://scalameta.org/metals/ - https://docs.scala-lang.org/scala3/guides/migration/compatibility-intro.html - https://www.scala-lang.org/blog/2023/04/18/faster-scalajs-development-with-frontend-tooling.html - https://www.scala-lang.org/blog/2022/08/17/long-term-compatibility-plans.html
-
Why actors are a great fit for a data processing pipeline and how we use them for Quickwit's engine
For the Rx approach, The ZIO framework for Scala has a streaming API that can meet those sorts of requirements. e.g.
-
How to build a Scala Zio CRUD Microservice
This tutorial will introduce how to build from scratch, a REST microservice using the ZIO framework, and examples of ZIO dependency injection, ZIO HTTP, JSON, JDBC, and others from the ZIO environment. The source code is available here
- Cuál lenguaje les da de comer, comunidad?
-
Is Parallel Programming Hard, and, If So, What Can You Do About It? [pdf]
I use ZIO (http://zio.dev) for Scala which makes parallel programming trivial.
Wraps different styles of asynchronicity e.g. callbacks, futures, fibers into one coherent model. And has excellent resource management so you can be sure that when you are forking a task that it will always clean up after itself.
Have yet to see anything that comes close whilst still being practical i.e. you can leverage the very large ecosystem of Java libraries.
-
40x Faster! We rewrote our project with Rust!
The one advantage Rust has over Scala is that it detects data races at compile time, and that's a big time saver if you use low level thread synchronization. However, if you write pure FP code with ZIO or Cats Effect that's basically a non-issue anyway.
What are some alternatives?
bbqueue - A SPSC, lockless, no_std, thread safe, queue, based on BipBuffers
cats-effect - The pure asynchronous runtime for Scala
left-right - A lock-free, read-optimized, concurrency primitive.
Monix - Asynchronous, Reactive Programming for Scala and Scala.js.
Ionide-vim - F# Vim plugin based on FsAutoComplete and LSP protocol
Http4s - A minimal, idiomatic Scala interface for HTTP
scrap - 📸 Screen capture made easy!
Vert.x - Vert.x is a tool-kit for building reactive applications on the JVM
jakt - The Jakt Programming Language
cats - Lightweight, modular, and extensible library for functional programming.
mun - Source code for the Mun language and runtime.
fs2-kafka - Functional Kafka Streams for Scala