fork_join_executor silently truncates ranges > 2^32

[arpittkhandelwal]

Summary

fork_join_executor currently truncates iteration ranges to 32-bit
indices. When size > UINT32_MAX (~4.29B), indices wrap silently,
causing incorrect results with no warning or exception.

This affects both static and dynamic scheduling paths.

Root Cause

1. Static scheduling:
   In fork_join_executor.hpp, partition boundaries are cast to
   std::uint32_t:

   auto const part_begin = static_cast<std::uint32_t>(...);
   auto const part_end   = static_cast<std::uint32_t>(...);
   

   If size > UINT32_MAX, part_begin/part_end wrap.

2. Dynamic scheduling:
   contiguous_index_queue is hardcoded to 32-bit indices via:

   static_assert(sizeof(T) <= 4, ...);
   

   It packs two 32-bit indices into a 64-bit atomic, so 64-bit
   ranges are fundamentally unsupported.

Impact

• Silent incorrect results for large ranges
• Affects for_each, transform, reduce, etc.
• Particularly problematic for HPC workloads

Proposed Fix

Immediate (correctness):

1. For loop_schedule::static_:
   Replace std::uint32_t with std::size_t in partition calculations.

2. For loop_schedule::dynamic:
   Add runtime guard:

   if (size > std::numeric_limits<std::uint32_t>::max())
       throw std::overflow_error(
           "fork_join_executor: dynamic scheduling "
           "not supported for ranges > 2^32");
   

Long-term:

• Either implement a 64-bit index queue (128-bit CAS), or
• Provide a lock-based fallback for 64-bit indices.

[arpittkhandelwal]

@hkaiser Sir, while reviewing the fork_join_executor code, I noticed that the partition indices are explicitly cast to std::uint32_t. This means ranges larger than 2^32 will silently truncate and wrap, potentially producing incorrect results without any warning.

I’ve summarized the issue and proposed a possible fix above. Please let me know if I’m interpreting this correctly.

[hkaiser]

Yes, the fork_join_executor relies on the contiguous_index_queue which supports only 32bit indicies. We can support larger indices only if the system has lockfree 128-bit atomics (which most systems don't have, unfortunately). There is an earlier attempt to implement lockfree 128-bit atomics (at least on x86) here: #6521, but the person working on it gave up eventually.

[Sahilll10]

@hkaiser, thank you for the context on contiguous_index_queue and #6521.

After reviewing #6521, I see the core issue: uint128_atomic (derived from std::atomic<uint128_type>) couldn't be used in tagged_ptr_pair.hpp because the code passes the 128-bit value by value, triggering the deleted copy constructor of std::atomic. Fixing that would require major refactoring.

I propose a two-phase fix that avoids 128-bit atomics entirely:

Phase 1(Static):
Replace static_cast<std::uint32_t> with std::size_t in fork_join_executor.hpp boundary calculations. This immediately fixes silent truncation for loop_schedule::static_, with zero risk.

Phase 2 (Dynamic):
Instead of 128-bit atomics, implement segmented dispatch: split ranges > UINT32_MAX into 32-bit segments, dispatch each sequentially via the existing contiguous_index_queue<std::uint32_t>, and reconstruct the full size_t index as segment_offset + local_index. This reuses the proven lock-free queue, avoids atomic refactoring. The only tradeoff is sequential segment processing, which is negligible for large ranges.

Later, we can layer the 128-bit detection from #6521 as an optimization: if lockfree 128-bit atomics are available, switch to a true 64-bit queue; otherwise fall back to segmented dispatch.

I'd like to start with Phase 1 as a standalone PR, then tackle Phase 2 separately.

Would you be open to me working on this? I'd appreciate your guidance.

Thank you and looking forward to contributing.

[hkaiser]

Would you be open to me working on this? I'd appreciate your guidance.

Sure, please go ahead, if you're interested. Thanks! Let's do it step by step and let's have an eye on possible performance impacts.

[Sahilll10]

Hi @hkaiser @arpittkhandelwal

Just a quick update – I've been working on the fix for the uint32_t truncation in fork_join_executor static scheduling (Phase 1). The code changes are ready, but I'm currently hitting a few test errors when trying to run the new regression test. I'm debugging them now and hope to have it sorted out soon.

Apologies for the delay – I'll open the PR as soon as possible.

Thanks for your patience!