Lock free non-allocating collection

0
votes

I am looking for a collection data structure that is:

  1. thread safe
  2. lock free
  3. non-allocating (amortized or pre-allocated is fine)
  4. non-intrusive
  5. not using exotic intrinsics

Element order does not matter. Stack, queue, bag, anything is fine. I have found plenty of examples that fulfill four of these five requirements, for example:

  • .NET's List is not thread safe.
  • If I put a mutex on it, then it's not lock free.
  • .NET's ConcurrentStack is thread safe, lock free, uses a simple CompareExchange, but allocates a new Node for each element.
  • If I move the next pointer from the Node to the element itself, then it's intrusive.
  • Array based lock free data structures tend to require multi-word intrinsics.

I feel like I'm missing something super obvious. This should be a solved problem.

1
collectionspoolintrinsicslock-free

1 Answers

0
votes
  • .NET's ConcurrentQueue fulfills all five requirements. It does allocate when the backing storage runs out of space, similar to List<T>, but as long as there is extra capacity, no allocations occur. Unfortunately the only way to reserve extra capacity upfront, is to initialize it with a collection of same size and then dequeuing all the elements.
  • same is true for .NET's ConcurrentBag