Ali Cheraghi 57ca3512e4 std.sort.pdq: fix stack overflow on 32-bit targets ...

our pdq implementation uses an explicit stack of `Range` entries to avoid recursion.
The size of this stack was set to `log2(maxInt(usize) + 1)`. on 32-bit
targets like `wasm32-freestanding`, this would hit the maximum size,
causing OOB. there were two issues:

- `max_limit`, which controls how many imbalanced partitions are allowed
  before the algorithm falls back to heapsort, was computed as
  `floorPowerOfTwo(n) + 1` instead of `log2(n)` as in the original c++
  reference implementation. e.g. for `n = 1_000_000`, this allowed 524289
  bad partitions before heapsort would kick in, instead of 19.
  this meant deeply imbalanced partitions could accumulate stack pushes
  essentially without limit. However, i didn't observe any meaningful
  difference in benchmarks.

- the worst-case stack depth is bounded by `log2(n) + max_limit`,
  which approaches `2 * log2(n)`. The reference c++ and go implementation
  doesn't have this problem because they don't use explicit stack buffer.

2026-06-11 05:40:50 +02:00

..

block.zig

lib: correct unnecessary uses of 'var'

2023-11-19 09:55:07 +00:00

pdq.zig

std.sort.pdq: fix stack overflow on 32-bit targets

2026-06-11 05:40:50 +02:00