Debug mode breaks complexity requirements

[Chris Jefferson]

I've just reported PR36338, which is that debug mode
(-D_GLIBCXX_DEBUG) makes some algorithms takes MUCH longer. In
particular, it turns heap_sort from and O(n log n) algorithm which
sorts 10,000 elements in 0.01s to one which is O(n^2 log n) and sorts
10,000 elements in a minute and a half. This "effectively" hangs my
program, as I do many such sorts.

This is part of a wider issue I believe, which is debug mode features
which break the complexity requirements of the underlying functions.
While it's fine for functions to take a bit longer than they did
before, I'm not sure it's acceptable to make them take *n longer than
they did before.

A quick scan suggests this mainly effects functions which take O(log
n) on an array but have a debug mode check on the whole array
including:

pop_heap, push_heap, lower/upper_bound and friends.

It is easy to construct programs which use these functions which are
over 10,000 times slower in debug mode.

I'm tempted to suggest introducing a new mode, say _GLIBCXX_DEBUG_SLOW
and moving these checks there, or adding _GLIBCXX_DEBUG_FAST to let
users skip these checks. However, it's possible (I haven't checked
carefully) that strictly the 'iterator checks' are non-conforming.
Personally, they are the things I really want, and find help me.

Regardless of which way this goes, it is fortunately possible in the
case of PR36338 to fix heap_sort and keep all the checks in place, so
maybe is no-one else has ever complained, this isn't a major issue.

Chris