Thursday, December 6, 2007

STL strings vs C strings for parsing

I'm working on a project where I need to build custom high performance HTTP server. One piece of this server is a parser for URLs in incoming requests. It is very simple and on the first glance it shouldn't be that slow compared with other parts of the server. Yet it was taking quite a lot of CPU according to the profiler. The parser is using STL and basically does several string::find() calls to find parts of URL. So I thought maybe string::find() is too slow and decided to benchmark it against strchr(). This is my benchmark code:


#include <string.h>
#include <string>
#include <time.h>
#include <iostream>

using std::string;
using std::cout;

int main() {
const char* str1 = " a ";
const string& str2 = str1;

const unsigned long iterations = 500000000l;

{
clock_t start = clock();

for (unsigned long i = 0; i < iterations; ++i) {
char* pos = strchr(str1, 'a');
}

clock_t end = clock();
double totalTime = ((double) (end - start)) / CLOCKS_PER_SEC;
double iterTime = totalTime / iterations;
double rate = 1 / iterTime;

cout << "Total time: " << totalTime << " sec\n";
cout << "Iterations: " << iterations << " it\n";
cout << "Time per iteration: " << iterTime * 1000 << " msec\n";
cout << "Rate: " << rate << " it/sec\n";
}

{
clock_t start = clock();

for (unsigned long i = 0; i < iterations; ++i) {
string::size_type pos = str2.find('a');
}

clock_t end = clock();
double totalTime = ((double) (end - start)) / CLOCKS_PER_SEC;
double iterTime = totalTime / iterations;
double rate = 1 / iterTime;

cout << "Total time: " << totalTime << " sec\n";
cout << "Iterations: " << iterations << " it\n";
cout << "Time per iteration: " << iterTime * 1000 << " msec\n";
cout << "Rate: " << rate << " it/sec\n";
}
}

Turns out strchr is much faster as long as the benchmark code is compiled with optimizations on:

ilya@denmark:~$ g++ -O3 test.cc && ./a.out
Total time: 0 sec
Iterations: 500000000 it
Time per iteration: 0 msec
Rate: inf it/sec
Total time: 15.5 sec
Iterations: 500000000 it
Time per iteration: 3.1e-05 msec
Rate: 3.22581e+07 it/sec

ilya@denmark:~$ g++ -O2 test.cc && ./a.out
Total time: 0 sec
Iterations: 500000000 it
Time per iteration: 0 msec
Rate: inf it/sec
Total time: 15.76 sec
Iterations: 500000000 it
Time per iteration: 3.152e-05 msec
Rate: 3.17259e+07 it/sec

ilya@denmark:~$ g++ -O1 test.cc && ./a.out
Total time: 0 sec
Iterations: 500000000 it
Time per iteration: 0 msec
Rate: inf it/sec
Total time: 19.23 sec
Iterations: 500000000 it
Time per iteration: 3.846e-05 msec
Rate: 2.6001e+07 it/sec

ilya@denmark:~$ g++ -O0 test.cc && ./a.out
Total time: 18.64 sec
Iterations: 500000000 it
Time per iteration: 3.728e-05 msec
Rate: 2.6824e+07 it/sec
Total time: 16.89 sec
Iterations: 500000000 it
Time per iteration: 3.378e-05 msec
Rate: 2.96033e+07 it/sec

I checked the same code with callgrind and from call graph it looks like strchr() call was inlined while string::find() wasn't. It could be the reason for the difference in the performance. Maybe compiler is even smarter and optimized whole cycle with strchr() out. I'm not sure that the benchmark is completly fair. Anyway one thing is certain: I'll should try to rewrite my URL parser using strchr() and see if the real code is faster.

Update: As anonymous commented it looks as though GCC is replacing the call to strchr() with a compiler builtin, and noticing that str1 points to a literal and doing the search at compile-time. The make the benchmark fair str1 should by supplied at runtime to prevent the optimization. I tried that (passed the string via arvs) and it does change the result. It seems that for short string C strings are faster and for long string STL strings are faster. Not quite sure why yet.

For the reference here the update benchmark code:

#include <string.h>
#include <string>
#include <time.h>
#include <iostream>

using std::string;
using std::cout;

int main(int argc, char** argv) {
const char* str1 = argv[1];
const string& str2 = argv[1];

const unsigned long iterations = 500000000l;

{
clock_t start = clock();

for (unsigned long i = 0; i < iterations; ++i) {
char* pos = strchr(str1, 'a');
}

clock_t end = clock();
double totalTime = ((double) (end - start)) / CLOCKS_PER_SEC;
double iterTime = totalTime / iterations;
double rate = 1 / iterTime;

cout << "Total time: " << totalTime << " sec\n";
cout << "Iterations: " << iterations << " it\n";
cout << "Time per iteration: " << iterTime * 1000 << " msec\n";
cout << "Rate: " << rate << " it/sec\n";
}

{
clock_t start = clock();

for (unsigned long i = 0; i < iterations; ++i) {
string::size_type pos = str2.find('a');
}

clock_t end = clock();
double totalTime = ((double) (end - start)) / CLOCKS_PER_SEC;
double iterTime = totalTime / iterations;
double rate = 1 / iterTime;

cout << "Total time: " << totalTime << " sec\n";
cout << "Iterations: " << iterations << " it\n";
cout << "Time per iteration: " << iterTime * 1000 << " msec\n";
cout << "Rate: " << rate << " it/sec\n";
}
}

Meanwhile I rewrote my URL parser using C strings and it is now 2x times faster. I guess the speedup comes from the fact that with C strings I can minimize number memory allocations for temporary strings. With C string if you want to take substring of another string you can just take pointer in the middle of the original and place '\0' where substring should end if don't mind destroying the original string. With STL (ok, standart) strings you cannot do this and have to make copies.

6 comments:

Anonymous said...

I do wish people would stop saying STL when they mean Standard Library.

Anonymous said...

Looks as though GCC is replacing the call to strchr with a compiler builtin, and noticing that str1 points to a literal and doing the search at compile-time.

Unless all the URLs you're parsing are known at compile-time you should try it with str1 pointing to user-supplied data (e.g. read from stdin or passed in via argv) for a more realistic benchmark.

You might be surprised at the result.

Ilya Martynov said...

You should try it with str1 pointing to user-supplied data (e.g. read from stdin or passed in via argv) for a more realistic benchmark.

Thanks for hint. I just did that (passed the string via arvs) and it does change the result. Though C strings are still faster (~10%) but not as much:

ilya@denmark:~$ g++ -O3 ./test.cc && ./a.out ' a '
Total time: 9.14 sec
Iterations: 500000000 it
Time per iteration: 1.828e-05 msec
Rate: 5.47046e+07 it/sec
Total time: 10.57 sec
Iterations: 500000000 it
Time per iteration: 2.114e-05 msec
Rate: 4.73037e+07 it/sec

Meanwhile I rewrote my URL parser using C strings and it is now 2x times faster. I guess the speedup comes from the fact that with C strings I can minimize number memory allocations for temporary strings. With C string if you want to take substring of another string you can just take pointer in the middle of the original and place '\0' where substring should end if don't mind destroying the original string. With STL (ok, standart) strings you cannot do this and have to make copies.

Anonymous said...

You can do it with std::string, you just have to work with iterator ranges instead of copied substrings.

If you use typical C idioms (e.g. strchr and pointer arithmetic) then the plain C version probably will be faster. However, C++ has its own idioms that might perform better (where that might mean faster, or safer, or both)

Ilya Martynov said...

You can do it with std::string, you just have to work with iterator ranges instead of copied substrings.

I tried do that but while doable it generally makes code more complex as you have to keep two variables to represent the range instead of one for C string. Or am I missing some standard way to represent the range as a single variable? I guess if there was a class with interface similar to string's interface which allows to work on part of other string that would simplify code a lot.

As for safety: my impression that once your are using iterators it is not that much more safer then raw pointers. Standard library doesn't protect you if you ++iterator beyond end() - it is up to programmer to write the code correctly.

jilcov said...

cc &&