std::list<>::size()method runs in linear time, not in constant time. It was explicitly designed that way for a reason, described in STL faq, but what matters to an ordinary programmer is that testing lists for emptyness should be done with the
emptymethod, not by comparing size to zero, otherwise it's easy to kill performance.
Today, I run into another case where non-const-time
size() matters. I was testing KDevelop on some testcase, and noticed that getting list of stack frames from gdb takes a lot of time. I've added some profiling code, and found that a one command takes 200ms to execute. Adding profiling code to gdb revealed that gdb itself takes some 70ms. Of course, that's not ideal, but even larger fraction of time was apparently spend in KDevelop, ehm, parsing the response.
So I've quickly put up a testcase that repeatedly parses a specific response, and ran it under callgrind. Ten minutes later I've got a profile with
strlen on top. It turned out that the parsing code was using
QCString and calling it's
length method at least one for each token, and for certain tokens -- once for each character. The
length, in turn, just calls
strlen. Since the input string was 20K in size, most of runtime was spend measuring the size of that string.
Another unexpected behaviour was found in the
QCString::mid function. Internally, it also calls
mid was called once for each token.
After uses of non-const-time methods were reduced to minimum, the parsing time my test case decreased 40x. No so bad, I think. The only problem is that time spend in gdb is still to high for a GUI, and that won't be that easy to fix.