segfault in parlay::sort, possibly related to size

[jespiron]

EDIT: I found the fix, will make pull request soon

Hello, hope your day is going great! parlay::sort seems to segfault for certain sized inputs. What puzzles me is that when I step through the program, I don’t see any invalid address accesses. It would be helpful if I could see the source.

I was wondering where parlay::sort is implemented in this library so that we can further investigate? Thank you!

Code that isolates the crash: range.zip

Observations:

• Removing any one of the points in rand40Pts causes the crash to go away
• 24 seems to be the magic array size. < 24 ok, >= 24 crash. Example: magic24.zip

Why I think the cause is in parlay::sort: Consider the below program that initializes rand40Pts to contain the points from (1,1) to (24, 24). At some point, the sorting function outputs (0,0), a point that was not originally in rand40Pts.

#include <parlay/primitives.h>
#include <iostream>
#include <string>
#include <vector>

using namespace std;
using point = array<int, 2>;

struct weighted_point {
  point p;
  int w;
};

ostream& operator<<(ostream& s, const weighted_point& p) {
  s << '(' << p.p[0] << ',' << p.p[1] << ')';
  return s;
}

// **************************************************************
// Driver code
// **************************************************************

int main(int argc, char* argv[]) {
  std::vector<weighted_point> rand40Pts;
  for(int i = 1; i <= 24; i++) {
    rand40Pts.emplace_back(weighted_point{{i, i}, i});
  }
  auto sortedS = parlay::sort(rand40Pts, [](const weighted_point& p1, const weighted_point& p2) {
      cout << "p1=" << p1 << ", p2" << p2 << endl;
      if (p1.p[1] == p2.p[1]) return p1.p[0] - p2.p[0];
      return p1.p[1] - p2.p[1];
    });

  return 0;
}

Running ./range |head -100 outputs

p1=(8,8), p2(20,20)
p1=(9,9), p2(20,20)
p1=(9,9), p2(8,8)
p1=(15,15), p2(20,20)
p1=(15,15), p2(8,8)
p1=(15,15), p2(9,9)
p1=(2,2), p2(20,20)
p1=(2,2), p2(8,8)
p1=(2,2), p2(9,9)
p1=(2,2), p2(15,15)
p1=(15,15), p2(8,8)
p1=(9,9), p2(15,15)
p1=(2,2), p2(15,15)
p1=(20,20), p2(15,15)
p1=(6,6), p2(15,15)
p1=(7,7), p2(15,15)
p1=(5,5), p2(15,15)
p1=(3,3), p2(15,15)
p1=(10,10), p2(15,15)
p1=(11,11), p2(15,15)
p1=(12,12), p2(15,15)
p1=(13,13), p2(15,15)
p1=(14,14), p2(15,15)
p1=(4,4), p2(15,15)
p1=(16,16), p2(15,15)
p1=(17,17), p2(15,15)
p1=(18,18), p2(15,15)
p1=(19,19), p2(15,15)
p1=(1,1), p2(15,15)
p1=(21,21), p2(15,15)
p1=(22,22), p2(15,15)
p1=(23,23), p2(15,15)
p1=(24,24), p2(15,15)
p1=(0,0), p2(15,15) <== issue starts here