ThreadWeaver - Lock-Free Multi-Thread Communication Templates

A collection of lock-free intra-thread message-sending fabrics including SPSC, MPSC and SPMC templates, targeting x64 and ARMv8+ platforms.

The implementation avoids CAS retry loops and ensures a linearly bounded number of operations for fairness, leading to bounded latency for any request to be processed. Fairness here means that no producer or consumer can be perpetually starved under continuous contention.

Some variations of the same actions are provided for fine-tuning performance.

Table of Contents

• ThreadWeaver – Lock-Free Multi-Thread Communication Templates
• Requirements
• Quick Start
  • Explicitness
  • Important Messages
  • External Synchronization
  • Variations
  • Common Verbs
    • [sync] init
    • [sync] flush
    • send
    • recv
• Design and Inspiration

Requirements

The Weaver library requires a compiler supporting C++20 and above standards.

Quick Start

Weaver is contained within one header in weaver.h to accommodate C++ specific template instantiation requirements.

The user must provide the cache line size --param=destructive-interference-size or configure the static THWeaver::CLS parameter in order to compile with the library. This is to ensure correct cache line isolation and avoid false sharing across platforms.

We will use the term "fabric" to refer to instantiated communication objects from the Weaver library.

The included classes are:

1. SPSC: THWeaver::EndpointQueue
2. MPSC: THWeaver::FanInFabric
3. SPMC: THWeaver::FanOutFabric

See docs for more detailed documentation on the classes and result enums.

Explicitness

The Weaver library expects that the user explicitly state the behavior for the fabric and does not rely on automatic constructors and destructors for state initialization and resource management.

Important Messages

Throughout the documentation (including this README), all important messages will have a leading "IMPORTANT".

Violations of important messages may result in undefined behavior.

External Synchronization

Some non-critical Weaver methods may expect external synchronization, oriented towards control-plane usage rather than the actual data-plane pipelines.

Use of these methods without synchronization may result in undefined behaviors.

These operations are marked by [sync].

Variations

All class methods are named by verb[_variation], and different variations of the same action may have different costs.

This document will only contain an overview on the verb (action), please see docs for detailed views on variations

Common Verbs

The verbs listed below are universal to all Weaver classes.

[sync] init

Explicitly initialize the fabric.

IMPORTANT: This method is expected to only be called once during the fabric's lifetime.

[sync] flush

Reset the fabric or part of the fabric.

send

Moves a message into the fabric. The return type will explicitly inform if and how it failed.

recv

Moves a message out of the fabric or initializes a token to the message. The return type will explicitly inform if and how it failed.

Design and Inspiration

Weaver is designed for the current generation and architecture of hardware and does not provide upwards compatibility to future hardware. It assumes multi-level caching and high-cost of memory operations, and aims to reduce memory and cache coherence traffic by respecting the hardware cache architecture.

And to ensure fairness for multiple producer or consumer threads, Weaver includes simple scheduling that degrades into round-robin schemes in the worst case.

It is inspired by networking concepts and hardware clock domain crossing implementations. And for each operation, it tries to keep modifications monotonic and data-flow unidirectional.

Shared states that must be lossless are structured so that operations are causally ordered and monotonic, allowing simpler synchronization and reduced coherence traffic.