concurrent_vector.h

Go to the documentation of this file.

/*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * This source code is licensed under the MIT license found in the
 * LICENSE file in the root directory of this source tree.
 */
 
#pragma once
 
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstring>
#include <initializer_list>
#include <iterator>
#include <stdexcept>
#include <utility>
#include <vector>
 
#include <dispenso/detail/math.h>
#include <dispenso/platform.h>
#include <dispenso/tsan_annotations.h>
 
// Whether to use a non-atomic buffer pointer cache for read-hot paths.
// Disabled on ARM where cache-line writes on every growth operation cause store buffer
// pressure that exceeds the read-path benefit (acquire loads are effectively free for
// sequential access patterns on ARM).
#if !defined(DISPENSO_HAS_CACHED_PTRS)
#if !defined(__aarch64__) && !defined(_M_ARM64)
#define DISPENSO_HAS_CACHED_PTRS 1
#else
#define DISPENSO_HAS_CACHED_PTRS 0
#endif
#endif
 
namespace dispenso {
 
enum class ConcurrentVectorReallocStrategy { kFullBufferAhead, kHalfBufferAhead, kAsNeeded };
 
struct ReserveTagS {};
constexpr ReserveTagS ReserveTag;
 
// Textual inclusion.  Includes undocumented implementation details, e.g. iterators.
#include <dispenso/detail/concurrent_vector_impl.h>
 
template <typename T>
struct DefaultConcurrentVectorSizeTraits {
  static constexpr size_t kDefaultCapacity = (sizeof(T) >= 256) ? 2 : 512 / sizeof(T);
 
  static constexpr size_t kMaxVectorSize =
      (size_t{1} << (sizeof(size_t) * CHAR_BIT > 47 ? 47 : sizeof(size_t) * CHAR_BIT - 1)) /
      sizeof(T);
};
 
struct DefaultConcurrentVectorTraits {
  static constexpr bool kPreferBuffersInline = true;
 
  static constexpr ConcurrentVectorReallocStrategy kReallocStrategy =
      ConcurrentVectorReallocStrategy::kAsNeeded;
 
  static constexpr bool kIteratorPreferSpeed = true;
};
 
template <
    typename T,
    typename Traits = DefaultConcurrentVectorTraits,
    typename SizeTraits = DefaultConcurrentVectorSizeTraits<T>>
class ConcurrentVector {
 public:
  using value_type = T;
  using reference = T&;
  using const_reference = const T&;
  using size_type = size_t;
  using difference_type = ssize_t;
  using reference_type = T&;
  using const_reference_type = const T&;
  using pointer = T*;
  using const_pointer = const T*;
  using iterator = std::conditional_t<
      Traits::kIteratorPreferSpeed,
      cv::ConcurrentVectorIterator<ConcurrentVector<T, Traits>, T, false>,
      cv::CompactCVecIterator<ConcurrentVector<T, Traits>, T, false>>;
  using const_iterator = std::conditional_t<
      Traits::kIteratorPreferSpeed,
      cv::ConcurrentVectorIterator<ConcurrentVector<T, Traits>, T, true>,
      cv::CompactCVecIterator<ConcurrentVector<T, Traits>, T, true>>;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 
  ConcurrentVector() : ConcurrentVector(SizeTraits::kDefaultCapacity / 2, ReserveTag) {}
 
  ConcurrentVector(size_t startCapacity, ReserveTagS)
      : firstBucketShift_(
            detail::log2(
                detail::nextPow2(std::max(startCapacity, SizeTraits::kDefaultCapacity / 2)))),
        firstBucketLen_(size_type{1} << firstBucketShift_) {
    T* firstTwo = cv::alloc<T>(2 * firstBucketLen_);
    initCachedPtrs();
    setCachedPtr(0, firstTwo);
    setCachedPtr(1, firstTwo + firstBucketLen_);
    buffers_[0].store(firstTwo, std::memory_order_release);
    buffers_[1].store(firstTwo + firstBucketLen_, std::memory_order_release);
  }
 
  explicit ConcurrentVector(size_t startSize) : ConcurrentVector(startSize, ReserveTag) {
    T* buf = buffers_[0].load(std::memory_order_relaxed);
    SizeOnExit constructed{size_, 0};
    for (; constructed.count < startSize; ++constructed.count) {
      new (buf + constructed.count) T();
    }
  }
 
  ConcurrentVector(size_t startSize, const T& defaultValue)
      : ConcurrentVector(startSize, ReserveTag) {
    T* buf = buffers_[0].load(std::memory_order_relaxed);
    SizeOnExit constructed{size_, 0};
    for (; constructed.count < startSize; ++constructed.count) {
      new (buf + constructed.count) T(defaultValue);
    }
  }
 
  template <typename InIterator, typename = cv::EnableIfInputIterator<InIterator>>
  ConcurrentVector(InIterator start, InIterator end)
      : ConcurrentVector(start, end, cv::IteratorCategory<InIterator>{}) {}
 
  template <typename InIterator, typename = cv::EnableIfInputIterator<InIterator>>
  ConcurrentVector(size_type startSize, InIterator start, InIterator end)
      : ConcurrentVector(startSize, ReserveTag) {
    assert(cv::rangeLengthIs(start, end, startSize, cv::IteratorCategory<InIterator>{}));
    initFromEmpty(start, end);
  }
 
  ConcurrentVector(std::initializer_list<T> l)
      : ConcurrentVector(l.size(), std::begin(l), std::end(l)) {}
 
  ConcurrentVector(const ConcurrentVector& other)
      : ConcurrentVector(other.size(), other.cbegin(), other.cend()) {}
 
  ConcurrentVector(ConcurrentVector&& other)
      : buffers_(std::move(other.buffers_)),
        firstBucketShift_(other.firstBucketShift_),
        firstBucketLen_(other.firstBucketLen_),
        gaps_(other.gaps_.exchange(nullptr, std::memory_order_relaxed)),
        size_(other.size_.load(std::memory_order_relaxed)) {
    moveCachedPtrsFrom(other);
    other.size_.store(0, std::memory_order_relaxed);
    // This is possibly unnecessary overhead, but enables the "other" vector to be in a valid,
    // usable state right away, no empty check or clear required, as it is for std::vector.
    T* firstTwo = cv::alloc<T>(2 * firstBucketLen_);
    other.setCachedPtr(0, firstTwo);
    other.setCachedPtr(1, firstTwo + firstBucketLen_);
    other.buffers_[0].store(firstTwo, std::memory_order_relaxed);
    other.buffers_[1].store(firstTwo + firstBucketLen_, std::memory_order_relaxed);
  }
 
  ConcurrentVector& operator=(const ConcurrentVector& other) {
    if (&other == this) {
      return *this;
    }
 
    clear();
    reserve(other.size());
    initFromEmpty(other.cbegin(), other.cend());
 
    return *this;
  }
 
  ConcurrentVector& operator=(ConcurrentVector&& other) {
    using std::swap;
    if (&other == this) {
      return *this;
    }
 
    clear();
    swap(firstBucketShift_, other.firstBucketShift_);
    swap(firstBucketLen_, other.firstBucketLen_);
    buffers_ = std::move(other.buffers_);
    swapCachedPtrs(other);
    swapGaps(other);
    size_t curLen = size_.load(std::memory_order_relaxed);
    size_.store(other.size_.load(std::memory_order_relaxed), std::memory_order_relaxed);
    other.size_.store(curLen, std::memory_order_relaxed);
 
    return *this;
  }
 
  void assign(size_type count, const T& value) {
    clear();
    reserve(count);
    SizeOnExit constructed{size_, 0};
    for (iterator it = begin(); constructed.count < count; ++it, ++constructed.count) {
      new (&*it) T(value);
    }
  }
 
  template <
      typename It,
      typename = typename std::iterator_traits<It>::difference_type,
      typename = typename std::iterator_traits<It>::pointer,
      typename = typename std::iterator_traits<It>::reference,
      typename = typename std::iterator_traits<It>::value_type,
      typename = typename std::iterator_traits<It>::iterator_category>
  void assign(It start, It end) {
    clear();
    assignRange(start, end, cv::IteratorCategory<It>{});
  }
 
  void reserve(difference_type capacity) {
    auto bend = bucketAndSubIndex(capacity);
    allocateBufferRange({0, 0, firstBucketLen_}, capacity, bend);
  }
 
  void resize(difference_type len) {
    difference_type curLen = static_cast<difference_type>(size_.load(std::memory_order_relaxed));
    if (curLen < len) {
      grow_to_at_least(len);
    } else if (curLen > len) {
      auto it = end();
      auto newEnd = begin() + len;
      do {
        --it;
        it->~T();
      } while (it != newEnd);
      size_.store(len, std::memory_order_relaxed);
    }
  }
 
  void resize(difference_type len, const T& value) {
    difference_type curLen = static_cast<difference_type>(size_.load(std::memory_order_relaxed));
    if (curLen < len) {
      grow_to_at_least(len, value);
    } else if (curLen > len) {
      auto it = end();
      auto newEnd = begin() + len;
      do {
        --it;
        it->~T();
      } while (it != newEnd);
      size_.store(len, std::memory_order_relaxed);
    }
  }
 
  size_type default_capacity() const {
    return 2 * firstBucketLen_;
  }
 
  size_type capacity() const {
    size_t cap = 2 * firstBucketLen_;
    for (size_t b = 2; b < kMaxBuffers; ++b) {
      if (!buffers_[b].load(std::memory_order_relaxed)) {
        break;
      }
      cap *= 2;
    }
    return cap;
  }
 
  void clear() {
#if defined(__cpp_exceptions)
    if (DISPENSO_EXPECT(gaps_.load(std::memory_order_relaxed) != nullptr, false)) {
      clearWithGaps();
      return;
    }
#endif // __cpp_exceptions
    auto binfo = bucketAndSubIndex(size_.load(std::memory_order_relaxed));
    size_t len = binfo.bucketIndex;
    size_t cap = binfo.bucketCapacity;
    size_t b = binfo.bucket;
    do {
      T* buf = buffers_[b].load(std::memory_order_relaxed);
      T* t = buf + len;
 
      while (t != buf) {
        --t;
        t->~T();
      }
      cap >>= int{b > 1};
      len = cap;
    } while (b--);
    size_.store(0, std::memory_order_release);
  }
 
  void shrink_to_fit() {
    constexpr size_t kMaxExtra = 2;
    auto binfo = bucketAndSubIndex(size_.load(std::memory_order_relaxed));
 
    // We need to at least skip the first two buckets, since we have those as a single allocation.
    size_t startBucket = std::max<size_t>(2, binfo.bucket + kMaxExtra);
 
    for (size_t b = startBucket; b < kMaxBuffers; ++b) {
      T* ptr = buffers_[b].load(std::memory_order_relaxed);
      if (!ptr) {
        break;
      }
      if (buffers_.shouldDealloc(b)) {
        cv::dealloc<T>(ptr);
      }
      clearCachedPtr(b);
      buffers_[b].store(nullptr, std::memory_order_release);
    }
  }
 
  ~ConcurrentVector() {
    clear();
    shrink_to_fit();
    cv::dealloc<T>(buffers_[0].load(std::memory_order_acquire));
  }
 
  iterator insert(const_iterator pos, const T& value) {
    auto it = insertPartial(pos);
    // insertPartial leaves a live (moved-from or default-constructed) element at pos; assign over
    // it rather than constructing on top of it, so that element's resources are released.
    *it = value;
    return it;
  }
 
  iterator insert(const_iterator pos, T&& value) {
    auto it = insertPartial(pos);
    *it = std::move(value);
    return it;
  }
 
  iterator insert(const_iterator pos, size_type count, const T& value) {
    auto it = insertPartial(pos, count);
    std::fill_n(it, count, value);
    return it;
  }
 
  template <
      typename InputIt,
      typename = typename std::iterator_traits<InputIt>::difference_type,
      typename = typename std::iterator_traits<InputIt>::pointer,
      typename = typename std::iterator_traits<InputIt>::reference,
      typename = typename std::iterator_traits<InputIt>::value_type,
      typename = typename std::iterator_traits<InputIt>::iterator_category>
  iterator insert(const_iterator pos, InputIt first, InputIt last) {
    return insertRange(pos, first, last, cv::IteratorCategory<InputIt>{});
  }
 
  iterator insert(const_iterator pos, std::initializer_list<T> ilist) {
    return insert(pos, ilist.begin(), ilist.end());
  }
 
  iterator erase(const_iterator pos) {
    auto e = end();
    if (e == pos) {
      return e;
    }
    size_.fetch_sub(1, std::memory_order_relaxed);
    --e;
    if (e == pos) {
      e->~T();
      return e;
    }
    auto it = begin();
    it += (pos - it);
    it = std::move(pos + 1, const_iterator(e + 1), it);
    // The last slot was vacated by the shift; destroy the moved-from object left there.
    e->~T();
    return it;
  }
 
  iterator erase(const_iterator first, const_iterator last) {
    size_t len = std::distance(first, last);
    auto it = begin();
    size_t startIdx = first - it;
    if (len == 0) {
      return it + (startIdx + len);
    }
    it += startIdx;
 
    auto e = end();
    auto e_it = std::move(last, const_iterator(e), it);
 
    // Destroy the vacated tail [e_it, end()): these are either moved-from or, when the tail was
    // shorter than the erased range, erased elements that nothing was moved into.
    while (e != e_it) {
      --e;
      e->~T();
    }
    size_.fetch_sub(len, std::memory_order_relaxed);
    return e_it;
  }
 
  iterator push_back(const T& val) {
    return emplace_back(val);
  }
 
  iterator push_back(T&& val) {
    return emplace_back(std::move(val));
  }
 
  template <typename... Args>
  iterator emplace_back(Args&&... args) {
    auto index = size_.fetch_add(1, std::memory_order_relaxed);
    auto binfo = bucketAndSubIndex(index);
 
    allocateBuffer(binfo);
 
    iterator ret{this, index, binfo};
 
    T* slot = Traits::kIteratorPreferSpeed ? &*ret : buffers_[binfo.bucket] + binfo.bucketIndex;
#if defined(__cpp_exceptions)
    try {
      new (slot) T(std::forward<Args>(args)...);
    } catch (...) {
      finishFailedGrowth(ret, 1);
      throw;
    }
#else
    new (slot) T(std::forward<Args>(args)...);
#endif // __cpp_exceptions
 
    return ret;
  }
 
  template <typename Gen>
  iterator grow_by_generator(size_type delta, Gen gen) {
    iterator ret = growByUninitialized(delta);
    constructGrown(ret, delta, [&gen](T* p) { new (p) T(gen()); });
    return ret;
  }
 
  iterator grow_by(size_type delta, const T& t) {
    iterator ret = growByUninitialized(delta);
    internalFillN(ret, delta, t);
    return ret;
  }
 
  iterator grow_by(size_type delta) {
    iterator ret = growByUninitialized(delta);
    internalFillDefaultN(ret, delta);
    return ret;
  }
 
  template <
      typename It,
      typename = typename std::iterator_traits<It>::difference_type,
      typename = typename std::iterator_traits<It>::pointer,
      typename = typename std::iterator_traits<It>::reference,
      typename = typename std::iterator_traits<It>::value_type,
      typename = typename std::iterator_traits<It>::iterator_category>
  iterator grow_by(It start, It end) {
    return growByRange(start, end, cv::IteratorCategory<It>{});
  }
 
  iterator grow_by(std::initializer_list<T> initList) {
    return grow_by(std::begin(initList), std::end(initList));
  }
 
  iterator grow_to_at_least(size_type n) {
    size_t curSize = size_.load(std::memory_order_relaxed);
    if (curSize < n) {
      return grow_by(n - curSize);
    }
    return {this, n - 1, bucketAndSubIndex(n - 1)};
  }
 
  iterator grow_to_at_least(size_type n, const T& t) {
    size_t curSize = size_.load(std::memory_order_relaxed);
    if (curSize < n) {
      return grow_by(n - curSize, t);
    }
    return {this, n - 1, bucketAndSubIndex(n - 1)};
  }
 
  void pop_back() {
    auto binfo = bucketAndSubIndex(size_.fetch_sub(1, std::memory_order_relaxed) - 1);
    T* elt = buffers_[binfo.bucket].load(std::memory_order_relaxed) + binfo.bucketIndex;
    elt->~T();
  }
 
  const T& operator[](size_type index) const {
    auto binfo = bucketAndSubIndexForIndex(index);
    T* buf = cachedBuffer(binfo.bucket);
    return buf[binfo.bucketIndex];
  }
 
  T& operator[](size_type index) {
    auto binfo = bucketAndSubIndexForIndex(index);
    T* buf = cachedBuffer(binfo.bucket);
    return buf[binfo.bucketIndex];
  }
 
  const T& at(size_type index) const {
#if defined(__cpp_exceptions)
    if (index >= size_.load(std::memory_order_relaxed)) {
      throw std::out_of_range("Index too large");
    }
#endif
    return operator[](index);
  }
 
  T& at(size_type index) {
#if defined(__cpp_exceptions)
    if (index >= size_.load(std::memory_order_relaxed)) {
      throw std::out_of_range("Index too large");
    }
#endif
    return operator[](index);
  }
 
  iterator begin() {
    return {this, 0, {0, 0, firstBucketLen_}};
  }
 
  iterator end() {
    size_t curSize = size_.load(std::memory_order_relaxed);
    auto binfo = bucketAndSubIndex(curSize);
    return {this, curSize, binfo};
  }
 
  const_iterator begin() const {
    return {this, 0, {0, 0, firstBucketLen_}};
  }
 
  const_iterator end() const {
    size_t curSize = size_.load(std::memory_order_relaxed);
    auto binfo = bucketAndSubIndex(curSize);
    return {this, curSize, binfo};
  }
 
  const_iterator cbegin() const {
    return {this, 0, {0, 0, firstBucketLen_}};
  }
 
  const_iterator cend() const {
    size_t curSize = size_.load(std::memory_order_relaxed);
    auto binfo = bucketAndSubIndex(curSize);
    return {this, curSize, binfo};
  }
 
  reverse_iterator rbegin() {
    return reverse_iterator(end());
  }
 
  reverse_iterator rend() {
    return reverse_iterator(begin());
  }
 
  const_reverse_iterator rbegin() const {
    return const_reverse_iterator(cend());
  }
 
  const_reverse_iterator rend() const {
    return const_reverse_iterator(cbegin());
  }
 
  bool empty() const {
    return size_.load(std::memory_order_relaxed) == 0;
  }
 
  constexpr size_type max_size() const noexcept {
    return Traits::kMaxVectorSize;
  }
 
  size_type size() const {
    return size_.load(std::memory_order_relaxed);
  }
 
  T& front() {
    return *buffers_[0].load(std::memory_order_relaxed);
  }
 
  const T& front() const {
    return *buffers_[0].load(std::memory_order_relaxed);
  }
 
  T& back() {
    return *(end() - 1);
  }
 
  const T& back() const {
    return *(end() - 1);
  }
 
  void swap(ConcurrentVector& oth) {
    using std::swap;
    swap(firstBucketShift_, oth.firstBucketShift_);
    swap(firstBucketLen_, oth.firstBucketLen_);
    size_t othlen = oth.size_.load(std::memory_order_relaxed);
    oth.size_.store(size_.load(std::memory_order_relaxed), std::memory_order_relaxed);
    size_.store(othlen, std::memory_order_relaxed);
 
    // okay, this relies on the fact that we're essentially swapping in the move operator.
    buffers_ = std::move(oth.buffers_);
    swapCachedPtrs(oth);
    swapGaps(oth);
  }
 
 private:
  // Range operations dispatch on iterator category, as std::vector does: forward (and stronger)
  // iterators can be measured with std::distance up front, but that would consume a single-pass
  // input range, so those are consumed exactly once, element by element.
  template <typename It>
  ConcurrentVector(It start, It end, std::forward_iterator_tag)
      : ConcurrentVector(static_cast<size_type>(std::distance(start, end)), start, end) {}
 
  template <typename It>
  ConcurrentVector(It start, It end, std::input_iterator_tag) : ConcurrentVector() {
    for (; start != end; ++start) {
      emplace_back(*start);
    }
  }
 
  template <typename It>
  void assignRange(It start, It end, std::forward_iterator_tag) {
    reserve(std::distance(start, end));
    initFromEmpty(start, end);
  }
 
  template <typename It>
  void assignRange(It start, It end, std::input_iterator_tag) {
    for (; start != end; ++start) {
      emplace_back(*start);
    }
  }
 
  template <typename It>
  iterator insertRange(const_iterator pos, It first, It last, std::forward_iterator_tag) {
    size_t len = std::distance(first, last);
    auto it = insertPartial(pos, len);
    std::copy_n(first, len, it);
    return it;
  }
 
  template <typename It>
  iterator insertRange(const_iterator pos, It first, It last, std::input_iterator_tag) {
    // Append, then rotate the new elements into place (as std::vector implementations do).
    const difference_type index = pos - cbegin();
    const difference_type oldSize = static_cast<difference_type>(size());
    for (; first != last; ++first) {
      emplace_back(*first);
    }
    auto b = begin();
    std::rotate(b + index, b + oldSize, end());
    return b + index;
  }
 
  template <typename It>
  iterator growByRange(It start, It end, std::forward_iterator_tag) {
    const size_t len = static_cast<size_t>(std::distance(start, end));
    iterator ret = growByUninitialized(len);
    internalInit(start, ret, len);
    return ret;
  }
 
  template <typename It>
  iterator growByRange(It start, It end, std::input_iterator_tag) {
    // Only single-pass input iterators come here; forward iterators take the overload above, with
    // no copy. grow_by must claim one contiguous block in a single atomic step, so it needs the
    // length first, and a single-pass range can be read only once: buffer it to learn the length,
    // then move the buffered elements in.
    std::vector<T> buffered(start, end);
    return growByRange(
        std::make_move_iterator(buffered.begin()),
        std::make_move_iterator(buffered.end()),
        std::random_access_iterator_tag{});
  }
 
  DISPENSO_INLINE cv::BucketInfo bucketAndSubIndexForIndex(size_t index) const {
#if defined(_MSC_VER) || defined(__aarch64__) || defined(_M_ARM64)
    // Branching fast path — benefits MSVC and ARM where branch prediction handles
    // sequential access patterns well, avoiding log2/division for the common case.
    if (index < firstBucketLen_) {
      return {0, index, firstBucketLen_};
    }
 
    size_t l2idx = detail::log2(index);
    size_t bucket = (l2idx + 1) - firstBucketShift_;
    size_t bucketCapacity = size_t{1} << l2idx;
    size_t bucketIndex = index - bucketCapacity;
 
    return {bucket, bucketIndex, bucketCapacity};
#else
    return bucketAndSubIndex(index);
#endif // _MSC_VER || __aarch64__ || _M_ARM64
  }
 
  DISPENSO_INLINE cv::BucketInfo bucketAndSubIndex(size_t index) const {
    size_t l2idx = detail::log2(index | 1);
    size_t bucket = (l2idx + 1) - firstBucketShift_;
    size_t bucketCapacity = size_t{1} << l2idx;
    size_t bucketIndex = index - bucketCapacity;
 
    bucket = index < firstBucketLen_ ? 0 : bucket;
    bucketIndex = index < firstBucketLen_ ? index : bucketIndex;
    bucketCapacity = index < firstBucketLen_ ? firstBucketLen_ : bucketCapacity;
 
    return {bucket, bucketIndex, bucketCapacity};
  }
 
  // Sets size_ to the number of elements constructed so far when it goes out of scope, including
  // when a T constructor throws. Used where the vector is filled from empty, not concurrently, so
  // that the destructor (or a later clear()) destroys exactly the elements that were constructed.
  struct SizeOnExit {
    std::atomic<size_t>& size;
    size_t count;
    ~SizeOnExit() {
      size.store(count, std::memory_order_relaxed);
    }
  };
 
#if defined(__cpp_exceptions)
  // A range [first, last) of slots that hold no objects. Gaps form a lock-free, push-only list:
  // growth pushes concurrently, and only clear() (not concurrency safe) takes the list down.
  struct Gap {
    size_t first;
    size_t last;
    Gap* next;
  };
 
  void finishFailedGrowth(const iterator& it, size_t count) {
    finishFailedGrowth(it, count, std::is_nothrow_default_constructible<T>{});
  }
 
  void finishFailedGrowth(const iterator& first, size_t count, std::true_type) noexcept {
    for (iterator it = first; count--; ++it) {
      new (&*it) T();
    }
  }
 
  // Called while an exception propagates; if the gap record cannot be allocated, the program
  // terminates.
  void finishFailedGrowth(const iterator& it, size_t count, std::false_type) {
    const size_t first = static_cast<size_t>(it - begin());
    Gap* gap = new Gap{first, first + count, gaps_.load(std::memory_order_relaxed)};
    while (!gaps_.compare_exchange_weak(
        gap->next, gap, std::memory_order_release, std::memory_order_relaxed)) {
    }
  }
 
  // clear() for a vector with gaps: destroys every element outside them, last to first, then
  // frees the gap records. Allocates nothing.
  void clearWithGaps() {
    // Insertion-sort the list by descending start; failed growths are rare, so it is short.
    Gap* sorted = nullptr;
    Gap* gap = gaps_.exchange(nullptr, std::memory_order_acquire);
    while (gap) {
      Gap* next = gap->next;
      Gap** pos = &sorted;
      while (*pos && (*pos)->first > gap->first) {
        pos = &(*pos)->next;
      }
      gap->next = *pos;
      *pos = gap;
      gap = next;
    }
 
    size_t index = size_.load(std::memory_order_relaxed);
    while (index > 0) {
      if (sorted && index == sorted->last) {
        index = sorted->first;
        Gap* done = sorted;
        sorted = sorted->next;
        delete done;
        continue;
      }
      --index;
      auto binfo = bucketAndSubIndex(index);
      (buffers_[binfo.bucket].load(std::memory_order_relaxed) + binfo.bucketIndex)->~T();
    }
    size_.store(0, std::memory_order_release);
  }
#else
  struct Gap;
#endif // __cpp_exceptions
 
  // Constructs the len elements of a range just reserved by growth, starting at it, calling
  // construct(T*) for each. If a constructor throws, size_ already covers the whole range and
  // other threads may have grown past it, so it cannot shrink: the constructed elements are kept,
  // finishFailedGrowth() fills or records the rest, and the exception continues. When construct
  // cannot throw, the compiler drops the handler and this is the plain loop.
  template <typename Construct>
  void constructGrown(iterator it, size_t len, Construct&& construct) {
#if defined(__cpp_exceptions)
    size_t built = 0;
    try {
      for (; built < len; ++built, ++it) {
        construct(&*it);
      }
    } catch (...) {
      finishFailedGrowth(it, len - built);
      throw;
    }
#else
    for (; len--; ++it) {
      construct(&*it);
    }
#endif // __cpp_exceptions
  }
 
  void swapGaps(ConcurrentVector& other) {
#if defined(__cpp_exceptions)
    Gap* mine = gaps_.load(std::memory_order_relaxed);
    gaps_.store(other.gaps_.load(std::memory_order_relaxed), std::memory_order_relaxed);
    other.gaps_.store(mine, std::memory_order_relaxed);
#else
    (void)other;
#endif // __cpp_exceptions
  }
 
  // Copy-construct [start, end) into an empty vector whose capacity is already reserved.
  template <typename InIterator>
  void initFromEmpty(InIterator start, InIterator end) {
    SizeOnExit constructed{size_, 0};
    for (iterator it = begin(); start != end; ++it, ++start, ++constructed.count) {
      new (&*it) T(*start);
    }
  }
 
  // The following construct the elements of a range just reserved by growth; see constructGrown.
  template <typename InIterator>
  void internalInit(InIterator start, iterator it, size_t len) {
    constructGrown(it, len, [&start](T* p) {
      new (p) T(*start);
      ++start;
    });
  }
 
  void internalFillN(iterator it, size_t len, const T& value) {
    constructGrown(it, len, [&value](T* p) { new (p) T(value); });
  }
 
  void internalFillDefaultN(iterator it, size_t len) {
    constructGrown(it, len, [](T* p) { new (p) T(); });
  }
 
  iterator growByUninitialized(size_type delta) {
    auto index = size_.fetch_add(delta, std::memory_order_relaxed);
    auto binfo = bucketAndSubIndex(index);
    auto bend = bucketAndSubIndex(index + delta);
    allocateBufferRange(binfo, delta, bend);
    return {this, index, binfo};
  }
 
  iterator insertPartial(const_iterator pos) {
    auto e = end();
    auto index = size_.fetch_add(1, std::memory_order_relaxed);
    auto binfo = bucketAndSubIndex(index);
    allocateBuffer(binfo);
    internalFillDefaultN(e, 1);
    return std::move_backward(pos, const_iterator(e), e + 1) - 1;
  }
 
  iterator insertPartial(const_iterator pos, size_t len) {
    auto e = end();
    auto index = size_.fetch_add(len, std::memory_order_relaxed);
    auto binfo = bucketAndSubIndex(index);
    auto bend = bucketAndSubIndex(index + len);
    allocateBufferRange(binfo, len, bend);
    internalFillDefaultN(e, len);
    return std::move_backward(pos, const_iterator(e), e + len) - len;
  }
 
  alignas(kCacheLineSize) cv::ConVecBuffer<
      T,
      SizeTraits::kDefaultCapacity / 2,
      SizeTraits::kMaxVectorSize,
      Traits::kPreferBuffersInline,
      Traits::kReallocStrategy> buffers_;
 
  static constexpr size_t kMaxBuffers =
      detail::log2const(SizeTraits::kMaxVectorSize / (SizeTraits::kDefaultCapacity / 2)) + 1;
 
#if DISPENSO_HAS_CACHED_PTRS
  // Non-atomic cache of buffer pointers for read-hot paths. Buffer pointers are write-once
  // (never change after allocation) and are stored here BEFORE the release store to buffers_[],
  // so any thread that acquires from buffers_[] is guaranteed to see the cached value.
  // All concurrent writes to a given slot store the same value.
  // Disabled on ARM where cache-line invalidation pressure exceeds the read-path benefit.
  alignas(kCacheLineSize) mutable T* cachedPtrs_[kMaxBuffers];
#endif
 
  size_t firstBucketShift_;
  size_t firstBucketLen_;
 
  // Head of the list of gaps left by growth whose element constructor threw; null until that
  // happens. Declared in every build so the layout does not depend on whether exceptions are
  // enabled, but only read or written when they are.
  std::atomic<Gap*> gaps_{nullptr};
 
  alignas(kCacheLineSize) std::atomic<size_t> size_{0};
 
  DISPENSO_INLINE T* cachedBuffer(size_t bucket) const {
#if DISPENSO_HAS_CACHED_PTRS
    return cachedPtrs_[bucket];
#else
    // Relaxed is sufficient: callers only access indices that have been fully constructed, which
    // requires an external happens-before with the writing thread. That synchronization
    // transitively carries the buffer pointer visibility (which was release-stored during
    // allocation). This matches the original pre-cache memory ordering and avoids the cost of
    // ldar (load-acquire) on AArch64.
    return buffers_[bucket].load(std::memory_order_relaxed);
#endif
  }
 
  DISPENSO_INLINE void allocateBuffer(const cv::BucketInfo& binfo) {
#if DISPENSO_HAS_CACHED_PTRS
    buffers_.allocAsNecessary(binfo, cachedPtrs_);
#else
    buffers_.allocAsNecessary(binfo);
#endif
  }
 
  DISPENSO_INLINE void
  allocateBufferRange(const cv::BucketInfo& binfo, ssize_t rangeLen, const cv::BucketInfo& bend) {
#if DISPENSO_HAS_CACHED_PTRS
    buffers_.allocAsNecessary(binfo, rangeLen, bend, cachedPtrs_);
#else
    buffers_.allocAsNecessary(binfo, rangeLen, bend);
#endif
  }
 
  DISPENSO_INLINE void initCachedPtrs() {
#if DISPENSO_HAS_CACHED_PTRS
    for (size_t i = 0; i < kMaxBuffers; ++i) {
      cachedPtrs_[i] = nullptr;
    }
#endif
  }
 
  DISPENSO_INLINE void setCachedPtr(size_t bucket, T* ptr) {
#if DISPENSO_HAS_CACHED_PTRS
    cachedPtrs_[bucket] = ptr;
#else
    (void)bucket;
    (void)ptr;
#endif
  }
 
  DISPENSO_INLINE void clearCachedPtr(size_t bucket) {
#if DISPENSO_HAS_CACHED_PTRS
    cachedPtrs_[bucket] = nullptr;
#else
    (void)bucket;
#endif
  }
 
  DISPENSO_INLINE void moveCachedPtrsFrom(ConcurrentVector& other) {
#if DISPENSO_HAS_CACHED_PTRS
    for (size_t i = 0; i < kMaxBuffers; ++i) {
      cachedPtrs_[i] = other.cachedPtrs_[i];
      other.cachedPtrs_[i] = nullptr;
    }
#else
    (void)other;
#endif
  }
 
  DISPENSO_INLINE void swapCachedPtrs(ConcurrentVector& other) {
#if DISPENSO_HAS_CACHED_PTRS
    for (size_t i = 0; i < kMaxBuffers; ++i) {
      T* cur = cachedPtrs_[i];
      cachedPtrs_[i] = other.cachedPtrs_[i];
      other.cachedPtrs_[i] = cur;
    }
#else
    (void)other;
#endif
  }
 
  friend class cv::ConVecIterBase<ConcurrentVector<T, Traits>, T>;
  friend class cv::ConcurrentVectorIterator<ConcurrentVector<T, Traits>, T, false>;
  friend class cv::ConcurrentVectorIterator<ConcurrentVector<T, Traits>, T, true>;
};
 
template <typename T, class Traits1, class Traits2>
inline bool operator==(
    const ConcurrentVector<T, Traits1>& a,
    const ConcurrentVector<T, Traits2>& b) {
  return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
}
 
template <typename T, class Traits1, class Traits2>
inline bool operator!=(
    const ConcurrentVector<T, Traits1>& a,
    const ConcurrentVector<T, Traits2>& b) {
  return !(a == b);
}
 
template <typename T, class Traits1, class Traits2>
inline bool operator<(
    const ConcurrentVector<T, Traits1>& a,
    const ConcurrentVector<T, Traits2>& b) {
  return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
}
 
template <typename T, class Traits1, class Traits2>
inline bool operator>(
    const ConcurrentVector<T, Traits1>& a,
    const ConcurrentVector<T, Traits2>& b) {
  return b < a;
}
 
template <typename T, class Traits1, class Traits2>
inline bool operator<=(
    const ConcurrentVector<T, Traits1>& a,
    const ConcurrentVector<T, Traits2>& b) {
  return !(b < a);
}
 
template <typename T, class Traits1, class Traits2>
inline bool operator>=(
    const ConcurrentVector<T, Traits1>& a,
    const ConcurrentVector<T, Traits2>& b) {
  return !(a < b);
}
 
template <typename T, class Traits>
inline void swap(ConcurrentVector<T, Traits>& a, ConcurrentVector<T, Traits>& b) {
  a.swap(b);
}
 
// Textual inclusion.  Includes undocumented implementation details, e.g. iterators.
#include <dispenso/detail/concurrent_vector_impl2.h>
 
} // namespace dispenso