parallel merge is not stable

[jefftrull]

merge_testcase.zip
The documentation for the merge algorithm states For equivalent elements in the original two ranges, the elements from the first range precede the elements from the second range. I find that this is sometimes not the case when the parallel execution policy is chosen.

The attached testcase merges two ranges of <int, char> pairs, ordered by the first value. For my compiler (gcc 6.3.0) I find that the resulting merged sequence interleaves equivalent elements from the input ranges, instead of using all of the equivalent elements from the first range first. Specifically, when merging (3,a), (3,b) with (3,c) the result is (3,a), (3,c), (3,b).

Due to the high threshold (65536) for using the parallel version of the algorithm, reproducing this requires modifying this line so the threshold is something low (I used 10).

[hkaiser]

@taeguk: any comments?

[taeguk]

@jefftrull Thanks for your bug report! I'll take a look in this weekend.

[hkaiser]

@taeguk: I added the test on a branch here: https://github.com/STEllAR-GROUP/hpx/tree/fixing_2964

@jefftrull: the problem is not reproducible for me (at least not with the test case you provided). This might become interesting ... ;-)

[jefftrull]

Hi @hkaiser ! Did you try that threshold hack...

[hkaiser]

@jefftrull Ahh no. Will try, thanks.

[hkaiser]

@taeguk: we need to find a way to modify this value without editing the code. Executor parameters for the win! Something like:

merge(execution::par.with(threshold([]() { return 10; })), ...)

or

merge(execution::par.with(threshold(10)), ...)

or somesuch...

[taeguk]

@jefftrull In PR #2967, I fixed the problem which you reported! Really thanks for your bug reporting! :)

[taeguk]

@hkaiser I agree that we need to find a way to modify the thredhold. The things you suggested seem good to me. execution::par.with(...) can be possible in now? Or we need to design and implement that to execution policy?

[sithhell]

Reopening as the tests fail. See for example here:
http://rostam.cct.lsu.edu/builders/hpx_clang_4_boost_1_63_centos_x86_64_debug/builds/102/steps/run_unit_tests/logs/tests.unit.parallel.inplace_merge%20%2818.97%20sec%29

[hkaiser]

@taeguk would you be able to look into this error, please?

[taeguk]

@hkaiser I will look that in this weekend.

[taeguk]

@hkaiser @sithhell I looked into this error.
It seems the bug of libc++, not of our code.
https://git.codingcafe.org/Mirrors/llvm-mirror/libcxx/commit/25a78dcd773ce509469a2b892adbeac0c230cdb9

[hkaiser]

Ahh, thanks for investigating this more closely. Is it possible to disable the failing tests for the platforms we know are broken?

[taeguk]

@hkaiser For doing what you said, we may be able to use conditional build with checking HPX_CLANG_VERSION. We should search that bug was fixed since exactly what version of libc++.

[sithhell]

You shouldn't check the clang version, but the stdlib version. This is a bug in libc++, you could also use libstdc++ with clang

[taeguk]

@sithhell Oops. Yes, you're right. I was strange...

[jefftrull]

Thanks all!