Remove algo logic duplication Round 3

[Christopher Jefferson]

On 28 September 2013 23:49, Marc Glisse <marc.glisse@inria.fr> wrote:
> Hello,
>
> using the program below, it seems to me that to sort the array {1,2}, we do
> 9 copies of the comparison functor, and 13 iterator copies (used to be 4 and
> 8). As long as those are empty or pointers, that's free. But if copying has
> even a slight cost for the functor or the iterator, it is quickly going to
> be noticable.
>
> Maybe we could use more references? The user-facing functions have to take
> iterators by value, but I think the inline helpers could use references.

I think this is good idea. It might also be worth force_inlining some
of the internal functions, even it they are large, where we have
introduced a forwarding function (this won't make code bigger, if we
are the only caller of a templated function, with a particular
instansiation of the comparison template parameter).

>
> (we also perform 2 comparisons where one should be enough, but that's a
> different issue)

That is worth looking at (although increasingly, I want to investigate
doing a fresh sort altogether. In my own code I use an implementation
of timsort, which shows much better performance where data is partly
sorted. However, that's a different patch/discussion!)

Chris