This is the mail archive of the
mailing list for the libstdc++ project.
Debug mode breaks complexity requirements
- From: "Chris Jefferson" <chris at bubblescope dot net>
- To: libstdc++ at gcc dot gnu dot org
- Date: Tue, 27 May 2008 08:50:42 +0100
- Subject: Debug mode breaks complexity requirements
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
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.