[Bug libstdc++/89120] std::minmax_element 2.5 times slower than hand written loop

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89120

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
First there is the issue of iterator vs value, as in your other PR.

The performance of minmax depends a lot on the element type and the
distribution. The standard requires that we perform only 3n/2 comparisons (not
2n like your version), which essentially prescribes the implementation.
However, minmax is probably the most classical example shown in classes on
branch prediction. For a uniform choice of a permutation, the 2n comparisons
can be well predicted (O(log n) are mispredicted) while if you only do 3n/2
comparisons, n/2 of those are unpredictable, so n/4 are badly predicted, and
that costs a lot.