set_intersection/set_difference fails when run with execution::par

[isidorostsa]

Expected Behavior

The function should return the same result independent of the # of threads it uses. It should return an iterator to the end of the range with the common elements. This happens with set_difference as well.

Actual Behavior

Running the algorithm with hpx::execution::par gives out different results depending on how many threads it is run with.

For input std::vectors:
{-1, 1, 2, 3, 4, 5} and
{0, 1, 2, 3, 8, 10}

it gives 3 common elements with 1-3 threads, 2 for 4 threads, 1 for 5 threads, 3 again for 6 threads, and 2, 1, 0, -1 (?!), -2, -3 for 7...12 threads. (negatives are result of pointer distance, not something explicitly returned by the algorithm)

For input:
int v1[30] = {0, 1 ... 29},
int v2[29] = {15, 16 ... 43}

it gives 14 common elements for 7, 9, 11 threads, 13 common elements for 12 threads,

For input: (according to the documentation this is well defined)
{ 1, 1, 1, 4, 5 }
{ 1, 1, 1 }
It crashes with a double free error when run with 5 or more threads

Steps to Reproduce the Problem

Here is the code i used:

  std::vector<int> v = { 1, 2, 3, 4, 5 };
  std::vector<int> w = { 3, 4, 5 };
  std::vector<int> x(v.size() + w.size());

  auto s = hpx::set_intersection(hpx::execution::par, v.begin(), v.end(), w.begin(), w.end(), x.begin());

  std::cout << "Common elements amount: " << std::distance(x.begin(), s) << std::endl;

Specifications

I am using

HPX: V1.9.0-trunk (AGAS: V3.0), Git: 248a14c
Boost: V1.81.0
Hwloc: V2.8.0

Build:
Type: release
Date: Mar 3 2023 17:15:21
Platform: linux
Compiler: GNU C++ version 11.3.0
Standard Library: GNU libstdc++ version 20220421
Allocator: system

[isidorostsa]

This was sort of mentioned here: #3442

[hkaiser]

@isidorostsa would you have any ideas on how to fix this?

[isidorostsa]

Certainly, I have some ideas. Each time a new thread is added, an element goes missing, indicating a potential off-by-one error in the process of dividing the sets into different chunks for each thread.

The issue likely lies within the more general hpx/parallel/algorithms/detail/set_operation.hpp function. This is further supported by the fact that we encounter similar problems when running the same tests using set_difference.