concurrency

Bilingual

Concurrency, interactivity, mutability, choose two
2 months ago
- Concurrency, interactivity, and mutability are three desirable features in programming, but it is impossible to have all three simultaneously without trade-offs.
- Dropping interactivity (as in C, Rust, Go) ensures safety and performance but removes the ability to inspect or modify programs at runtime.
- Dropping concurrency via a Global Interpreter Lock (GIL) in languages like Python and Ruby allows safe interactivity and mutability but introduces performance overhead from locking all data accesses.
- Dropping mutability (as in Erlang) uses message passing with copied values for safe concurrency and interactivity, but copying data is slow and incurs performance costs.
- Common Lisp allows all three but requires careful management to avoid data corruption when interacting with concurrent threads via the REPL.
On Async Rust
2 months ago
- The author began using Rust in 2017 and views async Rust as complex due to its combination with Rust's unique constraints, not poor design.
- Many applications may not need N:M threading (like async) because modern computers are fast enough for OS threads, but developers still want it for Rust to compete with Go and C++.
- Rust's zero-cost abstraction goal prevents adopting Go-like async models that require a heavy runtime, as seen with the removal of green threads.
- Issues with Arc and Mutex in async Rust are actually general concurrency problems, not unique to async, and stem from poor design thinking rather than async itself.
- Async Rust faces 'crate coloring' where most IO-related crates are async, forcing sync programs to pull in async dependencies, and Tokio dominates the ecosystem, limiting executor choice.
- The language lacks async support for traits, Drop, and closures, making async a second-class citizen, though effect system extensions are being explored.
- The sans-IO pattern inverts control by separating IO from logic, allowing code sharing across sync and async implementations and reducing dependency bloat.
Shuttle
2 months ago
- The Shuttle library is a concurrency verification tool developed by former AWS engineers, designed to make testing concurrent code easier.
- It addresses the difficulty of reproducing and catching concurrency bugs by using controlled thread scheduling with random exploration.
- The tool provides drop-in replacements for standard library concurrency primitives and runs tests in a harness that manipulates scheduling.
- Exhaustive exploration (as in Loom) is not always feasible due to factorial growth in permutations; random exploration handles complex cases and is parallelizable.
- A worked example demonstrates catching a classic concurrency error (race condition in semaphore) and fixing it with optimistic concurrency and compare-and-swap.
- Integration involves conditional compilation and re-exports to replace std::sync primitives with shuttle::sync.
- The library has been used successfully at AWS S3 for critical software and won Best Paper at SOSP '21.
async() => { await }
2 months ago
- The internet primarily consists of websites, with Cloudflare's service handling over 300,000 requests per second.
- Serving clients one at a time doesn't scale, so concurrency is needed to handle multiple clients simultaneously.
- JavaScript lacks native threads, leading to callback-based concurrency known as 'callback hell' before async/await was introduced.
- Async/await simplifies asynchronous code, making it more readable and manageable, as shown by converting callback-heavy code to a cleaner async structure.
Taking OCaml and Eio for a Spin
2 months ago
- The author chose to learn OCaml due to its recent renaissance with multicore support, effects, and the OxCaml spin from Jane Street, focusing on the Eio concurrency framework.
- They started with Real World OCaml (RWO) but found it lacked exercises, so switched to CS3110 which provided better practice and then returned to RWO for advanced topics.
- OCaml offers a mix of functional and imperative programming, with named arguments, but the syntax can be wordy (e.g., let..in, match..with) and the compiler stops at the first error, slowing iteration.
- Eio is an effects-based I/O library with features like io_uring and deterministic concurrency, suitable for building a Raft consensus algorithm.
- The author implemented a simple RPC protocol using Eio flows, buffered readers/writers, streams, promises, and fibers to handle concurrent requests safely.
- The client uses a write queue and promises to manage concurrent invocations, and the server handles connections with a loop that reads and responds to procedure calls.
- Overall, OCaml is fun and easy to use, but has a small userbase, making it harder to find code examples and best practices.
Notes on structured concurrency, or: Go statement considered harmful
2 months ago
- Concurrency APIs have traditionally used go statements (thread spawning, callbacks, futures) that allow background tasks to run independently, similar to goto statements in control flow.
- Go statements break abstraction by making functions non-black-box (they may spawn tasks without caller knowledge), disrupt automatic resource cleanup, and hinder proper error propagation.
- Trio introduces nurseries as a structured alternative, where tasks are started within a nursery block and the parent task waits for all child tasks to finish before exiting, ensuring control flow follows the 'black box' rule.
- Nurseries preserve function abstraction, support dynamic task spawning, allow explicit passing of nursery objects for flexibility, enable custom nursery-like types, and integrate automatic error propagation and cancellation.
- Removing go statements enables new features like reliable cancellation and proper control-C handling in Python, and nurseries encourage clearer, more robust concurrent programming, as demonstrated by simplified implementations like Happy Eyeballs in Trio.
The Tokio/Rayon Trap and Why Async/Await Fails Concurrency
2 months ago
- Async/await simplifies writing asynchronous code by making it look synchronous, but hides complexity in scheduling and control flow, shifting burden to developers.
- The conflation of asynchrony and concurrency in async/await can cause production issues, such as latency spikes from CPU-bound tasks blocking cooperative runtimes.
- Developers must manually separate I/O and compute tasks into different runtimes like Tokio and Rayon, acting as 'human schedulers' and undermining the abstraction's promise.
- Async/await runtimes often default to unbounded capacity, leading to out-of-memory crashes during traffic spikes due to unchecked task spawning and queuing.
- Work-stealing schedulers aimed at fairness can reduce throughput by destroying CPU cache locality and causing contention, as seen in large-scale systems like Erlang BEAM.
- Project Tina is introduced as an alternative concurrency framework based on state machines, featuring thread-per-core design, strict bounds, and deterministic simulation testing for predictability.
Concurrent JavaScript: It can work (2017)
2 months ago
- SharedArrayBuffer enables concurrent access in JavaScript, allowing for multi-threaded programming.
- A strawman API proposes adding threads, locks, condition variables, and thread-local variables to JavaScript for full concurrency.
- Implementation in WebKit involves segmented butterflies for wait-free operations and transition-thread-locality inference to minimize overhead.
- Performance goals include no regressions for non-concurrent code, linear scalability, and sensible memory model semantics.
- Concurrency interacts with the DOM by restricting access to main-thread-only objects but allowing limited concurrent accesses to global properties.
- The proposed scheme relies on 64-bit systems and aims to keep overhead minimal for most property accesses.
Solving Santa Claus Puzzle
2 months ago
- The article explores solving the Santa Claus concurrency puzzle using the SPIN model checker and Promela.
- Key constraints include: Santa cannot marshal groups; reindeer have priority over elves when both wait; and full groups (9 reindeer or 3 elves) must participate together.
- Three failure scenarios are analyzed: delivering without all reindeer ready, simultaneous delivery and consultation, and consulting elves despite waiting reindeer.
- A correct model introduces rooms (separate processes) for marshalling, with Santa waiting for 'group ready' signals to ensure proper synchronization and priority.
- Safety and liveness properties (e.g., mutual exclusion, full group participation, progress) are validated using Linear Temporal Logic (LTL) in SPIN.
- The solution is translated into a Go implementation, highlighting the educational value of model checking for uncovering subtle concurrency bugs.
Go-Flavored Concurrency in C
2 months ago
- Go's concurrency model is popular for its lightweight goroutines, channels, and efficient runtime scheduler, but replicating it in C using only POSIX threads presents trade-offs.
- Solod (So) implements a concurrency stack based on pthread primitives: sync.Mutex and sync.Cond wrap pthread_mutex_t and pthread_cond_t, providing basic synchronization.
- Atomic operations in So map directly to C's __atomic built-ins, matching Go's performance for load, store, and compare-and-swap operations without pthread overhead.
- So's conc.Pool uses a fixed number of worker threads with a shared task queue, built with mutexes and condition variables, suitable for coarse-grained workloads but not for thousands of blocked tasks like goroutines.
- Channels in So (conc.Chan[T]) support buffered and unbuffered modes, using mutexes and condition variables for synchronization, with performance close to Go for pooled tasks but slower for fine-grained hand-offs due to kernel wakeup costs.
- Benchmarks show So's pthread-based concurrency is competitive for uncontended locks and atomic operations, but condition variables and channels are significantly slower when threads block, with up to 23x slower unbuffered channel transfers.
- Design decisions include using pthreads instead of fibers for simplicity, keeping concurrency in the standard library for explicit allocations and flexibility, and providing timeouts instead of select for channel operations.
- The approach offers simplicity and performance close to Go for coarse-grained workloads but cannot match Go's efficiency for fine-grained concurrency due to the overhead of kernel thread management.
C++ Details of Asymmetric Fences
3 months ago
- Asymmetric thread fences optimize concurrency by shifting heavy synchronization costs from a common path to an infrequent slow path, using lightweight compiler barriers on the fast path and stronger fences on the slow path.
- The lightweight fence (asymmetric_thread_fence_light) is implemented as a compiler barrier (e.g., asm volatile("" : : : "memory")), preventing compiler reordering but not hardware reordering.
- The heavy fence (asymmetric_thread_fence_heavy) on Linux uses the membarrier() system call, which issues inter-processor interrupts (IPIs) to enforce memory ordering across cores, involving smp_mb() barriers before and after IPI sending.
- The C++ standard formalizes asymmetric fences (P1202R5) by integrating them into the memory model, with rules affecting the single total order S for memory_order_seq_cst operations and requiring careful handling to avoid transitivity issues.
- Implementation details include fast-path optimizations in membarrier() for single-core or single-mm scenarios, architecture-specific smp_mb() implementations, and considerations for data races and happens-before relationships.
FoundationDB's Flow – Bringing Actor-Based Concurrency to C++11
3 months ago
- Flow is a programming language that brings actor-based concurrency to C++11, developed for FoundationDB to meet high performance, scalability, and reliability goals.
- It uses actors, futures, promises, and keywords like wait(), ACTOR, state, and choose...when to enable asynchronous message-passing and deterministic simulation.
- Flow code is preprocessed into C++11, with caveats such as local variables not surviving wait() calls and special handling for state variables and IDE support.
Lunatic: An Erlang-inspired runtime for WebAssembly
3 months ago
- Lunatic is an open-source WebAssembly runtime inspired by Erlang.
- It provides isolated, lightweight processes for high concurrency and fault tolerance.
- Features include performance through JIT-compiled Wasm, security via capability limits, and distributed clustering.
- Applications are portable across architectures and OSes, compiled once to WebAssembly.
- Supervision trees enable monitoring and recovery of failing processes.

concurrency

Concurrency, interactivity, mutability, choose two

On Async Rust

Shuttle

async() => { await }

Taking OCaml and Eio for a Spin

Notes on structured concurrency, or: Go statement considered harmful

The Tokio/Rayon Trap and Why Async/Await Fails Concurrency

Concurrent JavaScript: It can work (2017)

Solving Santa Claus Puzzle

Go-Flavored Concurrency in C

C++ Details of Asymmetric Fences

FoundationDB's Flow – Bringing Actor-Based Concurrency to C++11

Lunatic: An Erlang-inspired runtime for WebAssembly