Vladimir Prus


Thursday, April 27, 2006

Non-constant size

Quite some time ago, when I was learning STL, all information sources stressed the importance of learning complexity guarantees that methods of various containters make. One specific subtle thing is that the 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 empty method, 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 length, and 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.


Anonymous said...

I want to recommend this site to you https://essays-writers.com/law-research-paper.html. Many writers work there. I often buy already written essays or articles on various topics. It helps me be a good student.

Anonymous said...

Hurry up! get your vision direct coupon now

best assignment help said...

This is a fantastic article that is both educational and fun. I'm not sure why other experts in this field haven't thought of this. You must continue with your writing. I'm a student who wants to be a good writer, which I feel I can attain by prioritising assignments and taking use of online learning tools.

oguzhadaway said...

Pune Hotel & Casino - MapYRO
Pune 속초 출장마사지 Casino, Casino & Hotel. Pune is a 진주 출장안마 vibrant, bustling city, with 평택 출장안마 lots of attractions 여주 출장마사지 including many famous and popular. A very short walk 부천 출장안마 from