WIP parallel is_heap

[Syntaf]

Work in progress of parallel is_heap. Currently passing tests.

• is_heap impl will likely change when I add is_heap_until, is_heap can simply call is_heap_until that ensures all partitions return true

Probably not ready to merge yet, but code review is appreciated. Forgot not to commit that annoying cmake_variables file again gah

[hkaiser]

inspect is unhappy: https://circle-artifacts.com/gh/STEllAR-GROUP/hpx/2259/artifacts/0/tmp/circle-artifacts.2qxRX1E/hpx_inspect_report.html

[hkaiser]

Two comments:

• please add a test verifying that the algorithm returns false for something which we know is not a heap (perhaps a random sequence)?
• please add the references to the docs of is_heap here: https://github.com/STEllAR-GROUP/hpx/blob/master/docs/manual/parallel_algorithms.qbk#L117

[Syntaf]

Update, writing a parallel is_heap is much more difficult than expected. This comment is just me working out my thought process

---

Say you have the heap: 9 8 6 7 4 5 2 0 3 1 , which when visualized looks like

Now say you call parallelized is_heap, and your heap is split into 4 separate partitions. These become

9 8 6 7 4 5 2 0 3 1

The problem is that 2 0 3 is not a max heap, but the algorithm will call std::is_heap on that range. the partitions are treating the beginning part as the head node, which is wrong in this case. The first two partitions got lucky because they chose a node which happened to have children, but in the case of a non-complete heap tree this algorithm would fail.

[Syntaf]

@hkaiser how can I access the inspection report for the recent build?

[hkaiser]

@Syntaf It's under 'Artifacts' on the cirleci webpage associated with the build (you need to be logged in to see it):

[hendrx]

Hey Grant , Have you thought about changing the way you partition the heap?

Since you already know its a binary tree you could maybe just build subtrees from it ( using arithmetics on the Array indices of The Elements )and use those subtrees to Call std::is_heap on.

Then it would obviously Depend on how efficient and fast that subpartitioning would go thru ...

but if the heap was big enough the overhead of onetime subpartitioning might still be outweight by the benefit of the parallel Execution Afterwards.

Cheers, Arne

[hkaiser]

@Syntaf Here is a paper outlining what they did for the gcc parallel stl: http://drobilla.net/papers/Parallel_C++_STL_Heap_Building.pdf

[Syntaf]

@hkaiser Awesome article! thanks for the link. I read through it am working on developing a level parallelism based algorithm. I've got a very simple version of parallel make_heap working(albeit a bit ugly) and am working on improving it so I can move it into an hpx::parallel:: algorithm

[Syntaf]

superseded by #1914