I don't know whether it's really important here, but first and last are not perfectly forwarded to is_heap_until.

Yah, we do it inconsistently throughout the algorithm implementations. Most of the time iterators are passed by value, sometimes not. The Standard prescribes for the algorithms to take iterators by value (on the outermost layer), everything else is up to the implementation I guess.

Iterators are usually cheap to copy. So, pass-by-value is faster than pass-by-reference.
And when using pass-by-reference, there is a dangerous thing like below:

iterator func(iterator& first, iterator& last, int val) { 
    while(first != last) {
        if(*fisrt == val) return first;
        ++first;
    } 
}
func(first, first);

So, I think pass-by-value is better than perfect forwarding.

Iterators are usually cheap to copy. So, pass-by-value is faster than pass-by-reference.

While I agree with the first statement (even if the keyword here is usually), I don't see how pass-by-value can be faster than pass-by-reference. Could you elaborate, please?

@hkaiser By compiler, pass-by-reference is implemented using pointer in compiled assembly codes. So, when accessing element through reference, there is a dereferencing cost. So, pass-by-value is more faster than pass-by-reference.

Can zip_iterator<iterator1, iterator2, ...> be used with parallel algorithms?

@Naios @hkaiser I agree about size of iterator can be larger than a pointer. I want to hear your thoughts about what we use for parallel algorithm function interfaces. Which one is better choice as you think?

As I said above, the Standard mandates for the algorithms to take the iterators by value (at the outermost level). So that's what we should do. Otherwise we have not applied a uniform policy. I think almost everywhere we pass iterators by value, but I'm not sure. In the end we shouldn't be able to measure any difference, so I think you can leave things the way you have it right now.

Once you have resolved the merge conflict with master we can go ahead and merge this PR.

To be honest, my personal opinion is that one should avoid additional copies in API internal code, since you don't know how huge the object will be the users passes to it. Also @hkaiser has shown that compound iterators can have a significantly larger size (:eyes: ranges). Hence, call by value can have a performance drawback when a copy operation can't be optimized out (type erased objects).

Can zip_iterator<iterator1, iterator2, ...> be used with parallel algorithms?

Yes, and we do so in the implementation of some of the algorithms.

Formally, zip_iterator can be only an input iterator at best as the type returned by dereferencing it is not a true reference. However, we applied a somewhat illegal trick allowing to pretend that zip_iterator is more than an input iterator. We know that dereferencing our zip_iterator returns a tuple of stable references, which allows for it to be used in most contexts normally requiring better iterators. The only exception to this is sort_by_key which relies on swapping elements dereferenced by the underlying iterator. For this reason we have added this overload for swapping tuples of references: https://github.com/STEllAR-GROUP/hpx/blob/master/hpx/util/tuple.hpp#L985-L1001 which allows us to implement sort_by_key on top of sort using a zip_iterator.

Just a minor improvement: maybe you could use std::next over + 1?

is_heap requires random access iterators, so this should be fine.

Same for first and second as above

👍

missing newline at eof

It's far out of scope for this PR, but it would be nice if there would be something like a HPX_TEST_FAIL(); macro, like GTest provides one.
Just checked it and something like this doesn't seem to exist in the current codebase.

@Naios feel free to add it, we'd be happy to accept such a PR. Thanks!

What is a 'max heap' ?

@hkaiser in standard, is_heap check whether the given range is max heap.
http://en.cppreference.com/w/cpp/algorithm/is_heap

You might want to add a link to cppreference.com as this has an explanation for a max heap (see also: 47e122e). BTW, the actual Standard does not talk about max heaps, see: http://eel.is/c++draft/alg.heap.operations.

Hmm.. But, I think using word "max heap' is right. With std::less as a predicate, biggest element is root of heap.

Sure, just please add a link to cppreference.com like I did for the other algorithms, please (47e122e).

Is there a benefit of explicitly implementing is_heap instead of simply relying on is_heap_until:

 bool is_heap(first, last) { return is_heap_until(first, last) == last; }

?

There is a overhead in that way.
is_heap : https://github.com/taeguk/hpx/blob/176f86e11388b38dcc6afe9516b099246a7b6505/hpx/parallel/algorithms/is_heap.hpp#L77
is_heap_until : https://github.com/taeguk/hpx/blob/176f86e11388b38dcc6afe9516b099246a7b6505/hpx/parallel/algorithms/is_heap.hpp#L227
In case of is_heap, it can be canceled early than is_heap_until.

Surely, there are many duplications of codes.
I had a try to have a one helper with no overhead, not two helpers(is_heap_helper and is_heap_until_helper).
But, I was failed to that. Because util::partitioner returns algorithm_result<ExPolicy, R>, I can't determine whether using just result or result.get().
https://github.com/taeguk/hpx/blob/176f86e11388b38dcc6afe9516b099246a7b6505/hpx/parallel/algorithms/is_heap.hpp#L216
Surely, I can do that using template meta programming and enable_if. But, this is complex. And I think it seems not good.

In case of is_heap , it can be canceled early than is_heap_until .

You should be able to break early for is_heap_until as well.

In case of is_heap_until, I can't break the partition checking lower index than an index of element which breaks the heap. I can only break the partition checking higher index than it.
But in case of is_heap, when in any partition I find an element which breaks the heap, I can break all partitions.

Right, makes sense.

This does not make any sense.

I'll fix it.

I'd suggest to use bool here instead of auto. Same amount of typing, better readability...

I'll fix it.

Same here. Let's make those return types explicit.

I'll fix it.

@hkaiser @Naios How do you think about this overhead to dereferencing comp.
In line 73, comp is passed by reference. This dereferencing is executed many times. So, I think this is an issue to think about.
I think passing comp by value is better. How do you think about it?
This issue is related to find_if, too. (https://github.com/STEllAR-GROUP/hpx/blob/master/hpx/parallel/algorithms/find.hpp#L208)

Since the comparison function is a function object, passing by reference here is fine. Passing by value requires a copy operation on the FO which will be more costly - in cases like this, where a lambda captures the FO (by reference) the compiler only has to call the function at the address supplied - it does not have to 'dereference' the pointer every time, so this is a zero cost reference capture in effect.

Am I obsessed with too small thing which just one memory access per loop iteration?

Possibly. Ultimately, you should time the algorithm, use a profiler if possible, and then make changes and do it again. If the dereferencing is a problem, you'll see a difference, if not, don't worry about it and move on to bigger things. Usually in cases like this, the algorithm itself can be order N, O(N^2), O(logN) etc etc and tweaking the way the algorithm works will make a much bigger impact than the micro-optimizations.

There will be cases where passing by reference/copy makes a difference and it's good to keep an eye open for them though, so don't stop looking (but time things if you can to confirm your hypotheses)

it does not have to 'dereference' the pointer every time, so this is a zero cost reference capture in effect.

@biddisco Did you mean that the compiler optimizes such dereferencings?

If the function object has no 'state', the only thing that matters is the call operator - which is just a function pointer. - an address. So when you pass the function object by reference, all the compiler has to do is call the function at the address. So yes, I suspect that when you have a function object with no member data, then the compiler really ought to be smart enough to know that there is no need to pass a reference to the object itself, but rather the function. However, as I write this down, I realize that it probably isn't true and there might well be a dereference going on ...
I think I need to try a small example with an assembler to be sure ....

But passing a function object by value, won't be any better, because you'll have to create a copy on the stack and then call the function call operator - which will be the same pointer (after all, the call operator will be a static function stored somewhere).

Maybe the call operator will be inlined anyway for a simple lambda ..... I need to research what's going on before I write more!

Hold on. the call operator is a just a function address. and when it is caled, it requires the args and a 'this' pointer (to the lambda in this case), so passing by refernce just requires the this pointer (the reference) and the function call. Passing by value, requires a copy, and then a call. So reference wins (even if the copy is made only once at the start of a loop for example because they both require a function call and a this pointer - and if the object has no state, the this pointer isn't even needed, so the compile will probably drop it)

@biddisco I've got it! That was my wrong thought.
The dereferencing will not occur even if FO is passed by reference because a function call needs a pointer anyway.
Obviously, pass-by-reference is better than pass-by-value in this case.