`kth_smallest_copy` recurses until stack overflow?

[charlieCoalition]

kth_smallest_copy can recurse until stack overflow when comparator equivalence differs from operator!=

Summary

parlay::kth_smallest_copy appears to recurse until stack overflow when many values are equivalent under the provided comparator, but not equal according to operator!=.

I reproduced this on the current master branch of cmuparlay/parlaylib using a minimal test case. The same issue also appears in a vendored copy of Parlay used in my project.

Minimal Reproducer

#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <utility>

#include <parlay/primitives.h>

using Row = std::pair<uint32_t, uint64_t>;

int main(int argc, char ** argv) {
    const size_t n = argc > 1 ? std::strtoull(argv[1], nullptr, 10) : 50000;
    const size_t k = 0;

    // Every row has the same comparator key, but a different full value.
    // This is equivalent to selecting by loss from rows shaped like
    // (trial_id, loss), where many trials can share the same loss.
    auto rows = parlay::tabulate(n, [](size_t i) -> Row {
        return Row{static_cast<uint32_t>(i), 42};
    });

    std::cerr << "n=" << n << " k=" << k << "\n";

    auto result = parlay::kth_smallest_copy(
        rows,
        k,
        [](const Row & a, const Row & b) -> bool {
            return a.second > b.second;
        }
    );

    std::cout << result.first << " " << result.second << "\n";
    return 0;
}

Build And Run

c++ -std=c++20 -O0 -g -fno-omit-frame-pointer \
  -fsanitize=address,undefined \
  -fno-sanitize-recover=undefined \
  -I /path/to/parlaylib/include \
  repro.cpp \
  -o repro

ulimit -s 1024 && ./repro 50000

Observed Result

n=50000 k=0
AddressSanitizer:DEADLYSIGNAL
=================================================================
ERROR: AddressSanitizer: stack-overflow
...
#253 parlay::kth_smallest_copy(...)
#254 parlay::kth_smallest_copy(...)

SUMMARY: AddressSanitizer: stack-overflow
ABORTING

Without sanitizers, the program exits with a segmentation fault / stack overflow. In my local run, the exit code was 139.

Expected Result

kth_smallest_copy should either return one of the comparator-minimal rows or document that the comparator's equivalence relation must be consistent with operator== / operator!= on the value type.

For the reproducer above, all rows are equivalent under the comparator, so any row with .second == 42 would be acceptable.

Suspected Cause

The implementation filters pivot duplicates with operator!= on the full value:

auto filtered_bucket = parlay::pack(in, parlay::tabulate(n, [&] (size_t i) -> bool {
  return ids[i] == id && (ids[i] == sample_size || it[i] != pivots[ids[i]]);
}));

In the reproducer, the comparator only compares Row::second:

[](const Row & a, const Row & b) -> bool {
    return a.second > b.second;
}

So these rows are comparator-equivalent:

Row{0, 42}
Row{1, 42}

but they are not equal according to std::pair::operator!=, because their .first values differ.

This means the "duplicates of the pivot" filter does not remove values that are duplicate/equivalent with respect to the comparator. When many values fall into that case, the recursive bucket may not shrink, and kth_smallest_copy repeatedly recurses at the same line until stack overflow.

Workarounds

Both of the following avoid the stack overflow:

1. Select on scalar keys directly.

auto result = parlay::kth_smallest_copy(
    parlay::delayed_map(rows, [](const Row & row) -> uint64_t {
        return row.second;
    }),
    k,
    [](const uint64_t & a, const uint64_t & b) -> bool {
        return a > b;
    }
);

2. Use a total comparator over the whole value so comparator equivalence agrees with pair equality.

auto result = parlay::kth_smallest_copy(
    rows,
    k,
    [](const Row & a, const Row & b) -> bool {
        if (a.second != b.second) return a.second > b.second;
        return a.first < b.first;
    }
);

Possible Fix

Would it be appropriate for kth_smallest_copy to filter pivot duplicates using comparator equivalence rather than operator!=?

For example, two values could be treated as equivalent when:

!less(a, b) && !less(b, a)

That would align the duplicate-pivot filtering with the ordering supplied to kth_smallest_copy.

[gblelloch]

Agreed that is a bug. The code should never be using != when a comparator is supplied. As you point out it should be using less(a, b) || less(b,a). We will fix when we have a chance.

Thanks for pointing this out.