make SegmentedList thread-safe and lock-free by allocating all segments statically #20491
Labels
breaking
Implementing this issue could cause existing code to no longer compile or have different behavior.
proposal
This issue suggests modifications. If it also has the "accepted" label then it is planned.
standard library
This issue involves writing Zig code for the standard library.
Milestone
Motivation
SegmentedList
has turned out to be a useful abstraction when trying to mix Data-Oriented Design with multi-threading. It provides contiguous arrays which is useful for serialization, cache coherency, and ability to use indexes as alternative to pointers, while preserving stable element pointers so that multiple threads can independently do work on different elements within this list, even when more elements are added concurrently.However, it has a big flaw currently: reallocation of the dynamic segments is not thread-safe. In particular, accessing any element by index races with insertions to the data structure, because a resize my cause the dynamic segments to be invalid while being read.
Proposed Changes
Always allocate all the segments statically:
This idea allows specifying the upper bound number of elements via providing the length type. For example, when
Elem
is a pointer andLen
isu32
, it will resolve to this:Smoke test:
On 64-bit systems, the size of this struct is 232 bytes. Compared to ArrayListUnmanaged (24 bytes) and ArrayHashMapUnmanaged (32 bytes), this proposed memory layout requires about 7x more overhead.
In exchange, we get a thread-safe data structure that can be freely accessed and appended to in a lock-free manner. For instance, allocating a new dynamic segment (which is rare) can work like this:
These changes are safe to perform while accessing any previous elements of the data structure by index because the segments are never resized.
Real-World Use Case
There is a direct need for this in the compiler, which uses a thread pool for AstGen work. Worker threads need to be able to create File instances and operate on File pointers.
Currently File instances are allocated individually with GeneralPurposeAllocator. This means that serializing File instances for incremental compilation purposes requires a lot of pointer chasing. On the other hand, if the data were stored in a SegmentedList, then an array of one iovec per segment could be passed to
writev
in order to serialize this data.The text was updated successfully, but these errors were encountered: