http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49717
Summary: Debug version checking algorithmic preconditions may have different complexity Product: gcc Version: 4.5.1 Status: UNCONFIRMED Severity: normal Priority: P3 Component: libstdc++ AssignedTo: unassig...@gcc.gnu.org ReportedBy: bange...@gmail.com This is essentially just a request to state something more explicitly on the website: We've started using the libstdc++ debug mode for running our testsuite (and found a dozen or so bugs with it -- yay) but I've come to realize that a bunch of tests now time out: they've become orders of magnitude slower. The reason I found for this is that many of the algorithms in libstdc++ (rightfully) check preconditions. For example, std::lower_bound checks whether indeed the given element partitions the sequence. The problem here is that these checks violate the complexity guarantees of the algorithms: std::lower_bound is supposed to be O(log(N)) but with the check for partitioning, it is now O(N). In our case, we call this function for each element of a sequence, and so we get O(N**2) instead of O(N log(N)) and the result is the increase in compute time. There is little one can do about this -- the debug mode is meant to check these things and it can't be done in O(log(N)). But it would be good to state this prominently somewhere in the corresponding web sites. Thanks W.