120 lines
4.3 KiB
Markdown
120 lines
4.3 KiB
Markdown
# 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](#threadweaver---lock-free-multi-thread-communication-templates)
|
||
- [Requirements](#requirements)
|
||
- [Quick Start](#quick-start)
|
||
- [Explicitness](#explicitness)
|
||
- [Important Messages](#important-messages)
|
||
- [External Synchronization](#external-synchronization)
|
||
- [Variations](#variations)
|
||
- [Common Verbs](#common-verbs)
|
||
- [`[sync] init`](#sync-init)
|
||
- [`[sync] flush`](#sync-flush)
|
||
- [`send`](#send)
|
||
- [`recv`](#recv)
|
||
- [Design and Inspiration](#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](include/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](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](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.
|