PR 60519: Debug mode should check comparators for irreflexivity (Was: pdqsort - a faster std::sort)

[Jonathan Wakely]

On 11/04/15 10:00 +0200, François Dumont wrote:
>    Note that I also plan to implement PR 60519 thanks to those 
>wrapper as all algos are relying on it. It is a very nice central 
>place to implement additional checks.

Hmm, maybe I've misunderstood your suggestion, but that would mean
checking on every comparison in many cases. e.g.  in std::sort we
have:

  std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));                                                                                                                                                 │

Because this calls the single-argument version of __iter_comp_iter()
we can't just add the check in the constructor of _Iter_to_comp_iter
where we have a dereferencable iterator and the functor:

--- bits/predefined_ops.h.orig  2015-04-11 13:28:30.063009877 +0100
+++ bits/predefined_ops.h       2015-04-11 13:28:33.645013410 +0100
@@ -268,7 +268,13 @@
 
       _Iter_comp_to_iter(_Compare __comp, _Iterator1 __it1)
        : _M_comp(__comp), _M_ref(*__it1)
-      { }
+      {
+#ifdef _GLIBCXX_DEBUG
+       // Comparison must define a Strict Weak Ordering, like "less than",
+       // so must be irreflexive, i.e. x < x must be false.
+       __glibcxx_assert( !_M_cmp(_M_ref, _M_ref) );
+#endif
+      }
 
       template<typename _Iterator2>
        bool

That won't help std::sort, because it doesn't use _Iter_comp_to_iter.
If you add the irreflexivity check to _Iter_comp_iter then it needs to
check in operator(), on every call.  That means we do 2N comparisons
instead of N, but we would get most of the benefit just by doing N+1
checks. (Alternatively _Iter_comp_iter could add a boolean member in
Debug Mode and only do the check once, but I really think this check
can be one of the "Debug Mode Lite" checks that doesn't affect ABI or
cause ODR violations and doesn't cost much in run-time performance.)

So I think we really want the irreflexivity check in std::sort itself,
so it can be done just once on entry to the function, not repeated at
every step. e.g.

#ifdef _GLIBCXX_DEBUG
   // Comparison must define a Strict Weak Ordering, like "less than",
   // so must be irreflexive, i.e. x < x must be false.
   if (__first != __last)
     __glibcxx_assert( !__comp(*__first, *__first));
#endif
  std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));                                                                                                                                                 │