@@ -41,19 +41,22 @@ import stdexec;
4141 *
4242 * BLOCK COUNTER ENCODING:
4343 * ----------------------
44- * Block counters (last_block_, start_block_, and internal counters) are 64-bit values with:
45- * - Bits [63:32]: Round number (32-bit unsigned, wraps on overflow)
46- * - Bits [31:0]: Block index within the circular block array (masked by mask_)
44+ * The queue-level block counters (last_block_, start_block_) count blocks
45+ * linearly: counter = round * num_blocks() + index. Because num_blocks() is a
46+ * power of two, the index is (counter & mask_) and the round is
47+ * (counter >> round_shift_). Moving to the next or previous block is counter + 1
48+ * or counter - 1; the round changes exactly when the index wraps.
4749 *
48- * The round number increments each time the index wraps around from mask_ to 0.
49- * This encoding allows:
50+ * The counters are std::uint64_t regardless of the width of std::size_t, so the
51+ * round always has at least 32 bits and wraps in step with the 32-bit block-level
52+ * rounds below. This encoding allows:
5053 * - Direct comparison of counters to determine relative order
5154 * - ABA problem prevention through round tracking
52- * - Efficient atomic operations on a single 64-bit value
55+ * - Atomic operations on a single 64-bit value
5356 *
5457 * TWO-LEVEL ROUND SYSTEM:
5558 * ----------------------
56- * 1. Queue-level rounds: Tracked in last_block_/start_block_ upper 32 bits
59+ * 1. Queue-level rounds: counter >> round_shift_ of last_block_/start_block_
5760 * - Increments when the owner wraps around the circular block array
5861 * - Passed to blocks during reclaim() to initialize block-level rounds
5962 *
@@ -176,31 +179,38 @@ namespace experimental::execution::bwos
176179 std::vector<Tp, Allocator> ring_buffer_;
177180 };
178181
179- auto advance_get_index (std:: size_t & owner, std:: size_t owner_index) noexcept -> bool;
180- auto advance_steal_index ( std::size_t & thief) noexcept -> bool;
181- auto advance_put_index ( std::size_t & owner) noexcept -> bool ;
182+ // Linear block counter, see BLOCK COUNTER ENCODING. Deliberately not
183+ // std::size_t: the round must keep 32 bits on 32-bit targets.
184+ using block_counter = std::uint64_t ;
182185
183- auto increase_block_counter (std::size_t counter) const noexcept -> std::size_t;
184- auto decrease_block_counter (std::size_t counter) const noexcept -> std::size_t;
186+ auto advance_get_index (block_counter& owner, std::size_t owner_index) noexcept -> bool;
187+ auto advance_steal_index (block_counter& thief) noexcept -> bool;
188+ auto advance_put_index (block_counter& owner) noexcept -> bool;
185189
186- // Block counter (round in upper 32 bits, index in lower bits) for the most
190+ auto index_of (block_counter counter) const noexcept -> std::size_t;
191+ auto round_of (block_counter counter) const noexcept -> std::uint32_t;
192+
193+ // Linear block counter (see BLOCK COUNTER ENCODING) for the most
187194 // recent block owned by push/pop operations. Modified only by the owner
188195 // thread.
189- alignas (hardware_destructive_interference_size) STDEXEC ::__std::atomic<std:: size_t > last_block_{
190- 0 };
196+ alignas (
197+ hardware_destructive_interference_size) STDEXEC ::__std::atomic<block_counter> last_block_{ 0 };
191198
192199 // Block counter for the oldest block available for stealing. Modified only
193200 // by the owner thread when it advances to a new block and needs to reclaim
194201 // the block at start_block_ position.
195202 alignas (
196- hardware_destructive_interference_size) STDEXEC ::__std::atomic<std:: size_t > start_block_{0 };
203+ hardware_destructive_interference_size) STDEXEC ::__std::atomic<block_counter > start_block_{0 };
197204
198205 // Circular array of blocks. Size is always a power of 2 for efficient
199206 // masking.
200207 std::vector<block_type, allocator_of_t <block_type>> blocks_{};
201208
202209 // Bitmask (blocks_.size() - 1) for extracting block index from counters.
203210 std::size_t mask_{};
211+
212+ // log2(blocks_.size()) for extracting the round from counters.
213+ int round_shift_{};
204214 };
205215
206216 // ////////////////////////////////////////////////////////////////////////////
@@ -214,18 +224,19 @@ namespace experimental::execution::bwos
214224 block_type (block_size, allocator),
215225 allocator_of_t<block_type>(allocator))
216226 , mask_(blocks_.size() - 1)
227+ , round_shift_(std::countr_zero(blocks_.size()))
217228 {
218229 blocks_[0 ].reclaim (0 );
219230 }
220231
221232 template <class Tp , class Allocator >
222233 auto lifo_queue<Tp, Allocator>::pop_back() noexcept -> Tp
223234 {
224- std:: size_t owner = last_block_.load (STDEXEC ::__std::memory_order_relaxed);
225- std::size_t owner_index{};
235+ block_counter owner = last_block_.load (STDEXEC ::__std::memory_order_relaxed);
236+ std::size_t owner_index{};
226237 do
227238 {
228- owner_index = owner & mask_ ;
239+ owner_index = index_of ( owner) ;
229240 block_type& current_block = blocks_[owner_index];
230241 auto [ec, value] = current_block.get ();
231242 if (ec == lifo_queue_error_code::success)
@@ -245,11 +256,11 @@ namespace experimental::execution::bwos
245256 template <class Tp , class Allocator >
246257 auto lifo_queue<Tp, Allocator>::steal_front() noexcept -> Tp
247258 {
248- std:: size_t thief = start_block_.load (STDEXEC ::__std::memory_order_relaxed);
259+ block_counter thief = start_block_.load (STDEXEC ::__std::memory_order_relaxed);
249260 do
250261 {
251- auto const thief_round = static_cast <std:: uint32_t > (thief >> 32 );
252- std::size_t const thief_index = thief & mask_ ;
262+ auto const thief_round = round_of (thief);
263+ std::size_t const thief_index = index_of ( thief) ;
253264 block_type& block = blocks_[thief_index];
254265 fetch_result result = block.steal (thief_round);
255266 while (result.status != lifo_queue_error_code::done)
@@ -273,10 +284,10 @@ namespace experimental::execution::bwos
273284 template <class Tp , class Allocator >
274285 auto lifo_queue<Tp, Allocator>::push_back(Tp value) noexcept -> bool
275286 {
276- std:: size_t owner = last_block_.load (STDEXEC ::__std::memory_order_relaxed);
287+ block_counter owner = last_block_.load (STDEXEC ::__std::memory_order_relaxed);
277288 do
278289 {
279- std::size_t owner_index = owner & mask_ ;
290+ std::size_t owner_index = index_of ( owner) ;
280291 block_type& current_block = blocks_[owner_index];
281292 auto ec = current_block.put (value);
282293 if (ec == lifo_queue_error_code::success)
@@ -293,10 +304,10 @@ namespace experimental::execution::bwos
293304 template <class Iterator , class Sentinel >
294305 auto lifo_queue<Tp, Allocator>::push_back(Iterator first, Sentinel last) noexcept -> Iterator
295306 {
296- std:: size_t owner = last_block_.load (STDEXEC ::__std::memory_order_relaxed);
307+ block_counter owner = last_block_.load (STDEXEC ::__std::memory_order_relaxed);
297308 do
298309 {
299- std::size_t owner_index = owner & mask_ ;
310+ std::size_t owner_index = index_of ( owner) ;
300311 block_type& current_block = blocks_[owner_index];
301312 first = current_block.bulk_put (first, last);
302313 }
@@ -317,45 +328,32 @@ namespace experimental::execution::bwos
317328 }
318329
319330 template <class Tp , class Allocator >
320- auto lifo_queue<Tp, Allocator>::increase_block_counter(std::size_t counter) const noexcept
321- -> std::size_t
331+ auto lifo_queue<Tp, Allocator>::index_of(block_counter counter) const noexcept -> std::size_t
322332 {
323- std::uint32_t round = static_cast <std::uint32_t >(counter >> 32 );
324- std::size_t index = counter & mask_;
325- std::size_t next_index = (index + 1 ) & mask_;
326- std::uint32_t next_round = round + static_cast <std::uint32_t >(next_index == 0 );
327- return (static_cast <std::size_t >(next_round) << 32 ) | next_index;
333+ return static_cast <std::size_t >(counter) & mask_;
328334 }
329335
330336 template <class Tp , class Allocator >
331- auto lifo_queue<Tp, Allocator>::decrease_block_counter(std::size_t counter) const noexcept
332- -> std::size_t
337+ auto lifo_queue<Tp, Allocator>::round_of(block_counter counter) const noexcept -> std::uint32_t
333338 {
334- std::uint32_t round = static_cast <std::uint32_t >(counter >> 32 );
335- std::size_t index = counter & mask_;
336- std::size_t prev_index = static_cast <std::size_t >(static_cast <std::ptrdiff_t >(index) - 1 )
337- & mask_;
338- std::uint32_t prev_round = round - static_cast <std::uint32_t >(index == 0 );
339- return (static_cast <std::size_t >(prev_round) << 32 ) | prev_index;
339+ return static_cast <std::uint32_t >(counter >> round_shift_);
340340 }
341341
342342 template <class Tp , class Allocator >
343- auto
344- lifo_queue<Tp, Allocator>::advance_get_index(std::size_t & owner, std::size_t owner_index) noexcept
345- -> bool
343+ auto lifo_queue<Tp, Allocator>::advance_get_index(block_counter& owner,
344+ std::size_t owner_index) noexcept -> bool
346345 {
347- std:: size_t start = start_block_.load (STDEXEC ::__std::memory_order_relaxed);
346+ block_counter start = start_block_.load (STDEXEC ::__std::memory_order_relaxed);
348347 if (start == owner)
349348 {
350349 // Cannot move backward past start_block_ - queue is empty
351350 return false ;
352351 }
353- // Move to predecessor block, properly decrementing round if wrapping
354- // backward
355- std::size_t predecessor = decrease_block_counter (owner);
356- std::size_t predecessor_index = predecessor & mask_;
357- block_type& previous_block = blocks_[predecessor_index];
358- block_type& current_block = blocks_[owner_index];
352+ // Move to predecessor block; the round drops when the index wraps backward
353+ block_counter predecessor = owner - 1 ;
354+ std::size_t predecessor_index = index_of (predecessor);
355+ block_type& previous_block = blocks_[predecessor_index];
356+ block_type& current_block = blocks_[owner_index];
359357 current_block.reduce_round ();
360358 previous_block.takeover ();
361359 last_block_.store (predecessor, STDEXEC ::__std::memory_order_relaxed);
@@ -364,43 +362,43 @@ namespace experimental::execution::bwos
364362 }
365363
366364 template <class Tp , class Allocator >
367- auto lifo_queue<Tp, Allocator>::advance_put_index(std:: size_t & owner) noexcept -> bool
365+ auto lifo_queue<Tp, Allocator>::advance_put_index(block_counter & owner) noexcept -> bool
368366 {
369- std::size_t next_index = (owner + 1ul ) & mask_;
370- std::size_t owner_index = owner & mask_;
367+ block_counter next = owner + 1 ;
368+ std::size_t next_index = index_of (next);
369+ std::size_t owner_index = index_of (owner);
371370 if (next_index == owner_index)
372371 {
373372 // Wrap-around would hit the same block - queue is full
374373 return false ;
375374 }
376- // Calculate next round, incrementing when wrapping to index 0
377- std::uint32_t next_round = static_cast <std::uint32_t >(owner >> 32 )
378- + static_cast <std::uint32_t >(next_index == 0 );
379- block_type& next_block = blocks_[next_index];
375+ // The round increments exactly when next_index wraps to 0
376+ std::uint32_t next_round = round_of (next);
377+ block_type& next_block = blocks_[next_index];
380378 if (!next_block.is_writable (next_round))
381379 {
382380 // Block is not yet safe to reuse (thieves still accessing previous generation)
383381 return false ;
384382 }
385- std:: size_t first = start_block_.load (STDEXEC ::__std::memory_order_relaxed);
386- std::size_t first_index = first & mask_ ;
383+ block_counter first = start_block_.load (STDEXEC ::__std::memory_order_relaxed);
384+ std::size_t first_index = index_of ( first) ;
387385 if (next_index == first_index)
388386 {
389387 // About to reuse the block at start_block_, so advance start_block_ forward
390- start_block_.store (increase_block_counter ( first) , STDEXEC ::__std::memory_order_relaxed);
388+ start_block_.store (first + 1 , STDEXEC ::__std::memory_order_relaxed);
391389 }
392390 block_type& current_block = blocks_[owner_index];
393391 current_block.grant ();
394- owner = ( static_cast <std:: size_t >(next_round) << 32 ) | next_index ;
392+ owner = next ;
395393 next_block.reclaim (next_round);
396394 last_block_.store (owner, STDEXEC ::__std::memory_order_relaxed);
397395 return true ;
398396 }
399397
400398 template <class Tp , class Allocator >
401- auto lifo_queue<Tp, Allocator>::advance_steal_index(std:: size_t & thief) noexcept -> bool
399+ auto lifo_queue<Tp, Allocator>::advance_steal_index(block_counter & thief) noexcept -> bool
402400 {
403- thief = increase_block_counter (thief) ;
401+ ++ thief;
404402 return thief < last_block_.load (STDEXEC ::__std::memory_order_relaxed);
405403 }
406404
0 commit comments