string_algo algorithms are quite slow in some popular compiler/OS/hardware situations

[Yuri Goldfeld <yuri_goldfeld@…>]

(This was reproduced with Boost 1.37.0, which was the latest version available a couple of months ago.)

We recently tried to use string_algo for some string processing-heavy software at my company. It is a lovely library, very general and elegant. So, we tried to put it into our (eventually intended for production) code. We were surprised to find that, while in our Linux environment everything was okay, the same code in Windows ran very noticeably slower. Therefore, I tried to measure the performance of string_algo algorithms themselves with some crude techniques. Here is what I found.

We have 3 platforms. First is a Debian-based Linux with 2.6 kernel and libc 2.4, with gcc 4.1. Second is Mac OS X 10.5 Leopard, with gcc 4.0. Third is Windows XP Pro (latest updates), with MS Visual Studio/C++ 2008. I turned on -O2 for gcc, and default Release optimization mode for VC++. All 3 are fairly modern situations. I wrote a simple string library, a part of which is attached here. It is templated but quite basic, mostly operating on basic_string<T> or, in some cases where it's convenient, const T*. The goal was to compare the speed of doing some basic operations (like starts_with or to_upper) with string_algo vs. my library.

The results are listed below. The performance in Linux, as you can see, is pretty good. Sure, it's a little slower than my library, but it's not by too much, and the added elegance and flexibility is well worth it. On Mac, the performance is a bit worse but not by much. On Windows, it is really bad, in certain cases 10 or even 30 times slower than the hand-made version. In particular, it seems anything involving lower-vs.-upper case conversions or comparisons makes it especially slow (although case-sensitive ops are also slow, but less so). In my opinion, this could prevent the library from being useful in many real-world applications, such as ours.

Before I attach the code and detailed instructions on how to build it (should be fairly easy), here are the results:

Debian-based Linux (Dual AMD Opteron 2.4GHz, 1MB cache), gcc-4.1:

ygoldfel@yurik2:~/boost-work$ ./a.out 
string("abcdefgh") == string("abcdefgh")| 1047 msec.
equals(string("abcdefgh"), string("abcdefgh"))| 1301 msec.
Boost/hand ratio = 1.2426

StartsWith(string("abcdefghi"), "abcd")| 601 msec.
starts_with(string("abcdefghi"), "abcd")| 696 msec.
Boost/hand ratio = 1.15807

StartsWithI(string("abcdefghi"), "aBcD")| 844 msec.
istarts_with(string("abcdefghi"), "aBcD")| 1375 msec.
Boost/hand ratio = 1.62915

EqualsI("abcdefghi", "aBcDeFgHi")| 613 msec.
iequals("abcdefghi", "aBcDeFgHi")| 1445 msec.
Boost/hand ratio = 2.35726

ToUpperCopy(string("aBcDeFgHi"))| 1560 msec.
to_upper_copy(string("aBcDeFgHi"))| 1935 msec.
Boost/hand ratio = 1.24038

ToLowerCopy(string("aBcDeFgHi"))| 1619 msec.
to_lower_copy(string("aBcDeFgHi"))| 1670 msec.
Boost/hand ratio = 1.0315

ToLower(str)| 416 msec.
to_lower(str)| 1353 msec.
Boost/hand ratio = 3.2524

ToUpper(str)| 416 msec.
to_upper(str)| 1326 msec.
Boost/hand ratio = 3.1875

Mac OS X 10.5 (2008 Apple MacBook, Intel Core 2 Duo 2GHz), gcc 4.0:

ygoldfel@MAC:~/boost-work$ ./a.out 
string("abcdefgh") == string("abcdefgh")| 1709 msec.
equals(string("abcdefgh"), string("abcdefgh"))| 2357 msec.
Boost/hand ratio = 1.37917

StartsWith(string("abcdefghi"), "abcd")| 670 msec.
starts_with(string("abcdefghi"), "abcd")| 1008 msec.
Boost/hand ratio = 1.50448

StartsWithI(string("abcdefghi"), "aBcD")| 1011 msec.
istarts_with(string("abcdefghi"), "aBcD")| 2490 msec.
Boost/hand ratio = 2.46291

EqualsI("abcdefghi", "aBcDeFgHi")| 798 msec.
iequals("abcdefghi", "aBcDeFgHi")| 2497 msec.
Boost/hand ratio = 3.12907

ToUpperCopy(string("aBcDeFgHi"))| 2395 msec.
to_upper_copy(string("aBcDeFgHi"))| 3076 msec.
Boost/hand ratio = 1.28434

ToLowerCopy(string("aBcDeFgHi"))| 2439 msec.
to_lower_copy(string("aBcDeFgHi"))| 3176 msec.
Boost/hand ratio = 1.30217

ToLower(str)| 514 msec.
to_lower(str)| 2185 msec.
Boost/hand ratio = 4.25097

ToUpper(str)| 459 msec.
to_upper(str)| 2108 msec.
Boost/hand ratio = 4.59259

Windows XP Pro (Intel Quad Core 2 Q6600 2.40GHz), MS VC++ 2008:

C:\projects\boost_perf\Release>boost_perf.exe
string("abcdefgh") == string("abcdefgh")| 605 msec.
equals(string("abcdefgh"), string("abcdefgh"))| 1413 msec.
Boost/hand ratio = 2.33554

StartsWith(string("abcdefghi"), "abcd")| 323 msec.
starts_with(string("abcdefghi"), "abcd")| 666 msec.
Boost/hand ratio = 2.06192

StartsWithI(string("abcdefghi"), "aBcD")| 352 msec.
istarts_with(string("abcdefghi"), "aBcD")| 3238 msec.
Boost/hand ratio = 9.19886

EqualsI("abcdefghi", "aBcDeFgHi")| 171 msec.
iequals("abcdefghi", "aBcDeFgHi")| 5212 msec.
Boost/hand ratio = 30.4795

ToUpperCopy(string("aBcDeFgHi"))| 704 msec.
to_upper_copy(string("aBcDeFgHi"))| 3445 msec.
Boost/hand ratio = 4.89347

ToLowerCopy(string("aBcDeFgHi"))| 621 msec.
to_lower_copy(string("aBcDeFgHi"))| 3429 msec.
Boost/hand ratio = 5.52174

ToLower(str)| 211 msec.
to_lower(str)| 2867 msec.
Boost/hand ratio = 13.5877

ToUpper(str)| 210 msec.
to_upper(str)| 2800 msec.
Boost/hand ratio = 13.3333

Windows XP Pro (AMD Athlon 64 X2 5600+ 2.91GHz), same executable:

C:\Documents and Settings\yurik\My Documents>boost_perf.exe
string("abcdefgh") == string("abcdefgh")| 596 msec.
equals(string("abcdefgh"), string("abcdefgh"))| 1538 msec.
Boost/hand ratio = 2.58054

StartsWith(string("abcdefghi"), "abcd")| 338 msec.
starts_with(string("abcdefghi"), "abcd")| 716 msec.
Boost/hand ratio = 2.11834

StartsWithI(string("abcdefghi"), "aBcD")| 387 msec.
istarts_with(string("abcdefghi"), "aBcD")| 2418 msec.
Boost/hand ratio = 6.24806

EqualsI("abcdefghi", "aBcDeFgHi")| 237 msec.
iequals("abcdefghi", "aBcDeFgHi")| 3373 msec.
Boost/hand ratio = 14.2321

ToUpperCopy(string("aBcDeFgHi"))| 733 msec.
to_upper_copy(string("aBcDeFgHi"))| 2781 msec.
Boost/hand ratio = 3.794

ToLowerCopy(string("aBcDeFgHi"))| 728 msec.
to_lower_copy(string("aBcDeFgHi"))| 2813 msec.
Boost/hand ratio = 3.86401

ToLower(str)| 211 msec.
to_lower(str)| 2081 msec.
Boost/hand ratio = 9.86256

ToUpper(str)| 237 msec.
to_upper(str)| 1976 msec.
Boost/hand ratio = 8.33755

[Yuri Goldfeld <yuri_goldfeld@…>]

Part of a hand-made string library, used to compare against Boost performance-wise.

[Yuri Goldfeld <yuri_goldfeld@…>]

The driver program that includes Boost string_algo and the attached StrUtils.hpp. It has a crude timer mechanism and a few performance tests in main().

[Yuri Goldfeld <yuri_goldfeld@…>]

For all 3 platforms, the only common requirement is the availability of Boost headers in some directory. Platform-specific requirements for running my simple test program:

Linux: gcc (probably version 3.3 or higher).

Mac OS X: none (comes with gcc 4.0 or higher).

Windows: Visual Studio (2008 or higher, though I'm sure an older version will work).

Steps to build and run my simple test program:

Linux Create a directory and put attached files StrUtils.hpp and perf.cpp there. Go to that directory and do, from command line:

g++ -I $BOOST_DIR -DUNIX32 -O2 perf.cpp -o perf_test

where $BOOST_DIR is the path to your Boost headers. Now, run the program:

./perf_test

Mac

Exactly the same steps as for Linux.

Windows

I can provide you with a Visual Studio project file, but it might be easier to just do it yourself. Open MS Visual Studio and create a new project/solution; make it a Win32 Console Application that is empty, with no precompiled headers. Add the two attached files, StrUtils.hpp and perf.cpp, into the project. Click Project / Properties. In the Configuration: dropdown, select Release (or something that contains that word). Click Configuration Properties / C++ / General, and in Additional Include Directories browse to where you Boost headers are located on the disk. Now, click Configuration Properties / C++ / Preprocessor, and for Preprocessor Definitions, add ";WIN32" to the end of whatever is there already. Now, in the Configuration: dropdown, select Debug. Repeat the Add'l Include Dirs and Preprocessor Defs steps. Finally, click OK.

Select Release configuration in the main dropdown in the toolbar and press F7 to build program. Now, you can run it from the command line (cd to <path to your project>\Release, and run "boost_perf" or whatever you named your project).

The above is how I do it as a VC++ noob, but if you're a VC++ wizard, go right ahead.

[Pavol Droba]

Just curious, VC++2008 employs quite rigorous run-time checking, which is sometimes enabled even in the Release mode. This checks significantly reduce the performance. To get a serious reading I suggest to disable all checks and compile in Relaase mode with maximum optimization possible. One example is SCL to disable it use #define _SECURE_SCL=0 or add _SECURE_SCL=0 into C++/Preprocessor in the project settings.

Can you please re-run the tests using this settings?

More info here: ​http://msdn.microsoft.com/en-us/library/aa985965(VS.80).aspx

[yuri_goldfeld@…]

The driver program that includes Boost string_algo and the attached StrUtils?.hpp. It has a crude timer mechanism and a few performance tests in main(). In Windows, now prints whether VC++ checked iterators are being used.

[anonymous]

Good guess, especially since it seems like in-place-modifying functions like to_lower() are much slower than intuitively slower copying ones like to_lower_copy(). Unfortunately, disabling SCL did not fix it. The 2nd perf.cpp I attached prints whether _SECURE_SCL is enabled in Windows. I disabled it in Project Properties like you said (_SECURE_SCL=0). I also turned up every optimization setting to maximum, with the resulting command line:

/Ox /Ob2 /Oi /Ot /Oy /GL /I "C:\workspaces\client-1.4.7\akamai\boost" /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_SECURE_SCL=0" /D "_UNICODE" /D "UNICODE" /FD /EHsc /MD /Gy /Fo"Release\\" /Fd"Release\vc90.pdb" /W3 /WX /nologo /c /Zi /TP /errorReport:prompt

This was the output:

C:\projects\boost_perf\Release>boost_perf.exe
Windows build: _SECURE_SCL = 0
string("abcdefgh") == string("abcdefgh")| 612 msec.
equals(string("abcdefgh"), string("abcdefgh"))| 1046 msec.
Boost/hand ratio = 1.70915

StartsWith(string("abcdefghi"), "abcd")| 266 msec.
starts_with(string("abcdefghi"), "abcd")| 553 msec.
Boost/hand ratio = 2.07895

StartsWithI(string("abcdefghi"), "aBcD")| 337 msec.
istarts_with(string("abcdefghi"), "aBcD")| 3320 msec.
Boost/hand ratio = 9.85163

EqualsI("abcdefghi", "aBcDeFgHi")| 170 msec.
iequals("abcdefghi", "aBcDeFgHi")| 5248 msec.
Boost/hand ratio = 30.8706

ToUpperCopy(string("aBcDeFgHi"))| 590 msec.
to_upper_copy(string("aBcDeFgHi"))| 3445 msec.
Boost/hand ratio = 5.83898

ToLowerCopy(string("aBcDeFgHi"))| 591 msec.
to_lower_copy(string("aBcDeFgHi"))| 3385 msec.
Boost/hand ratio = 5.72758

ToLower(str)| 160 msec.
to_lower(str)| 2847 msec.
Boost/hand ratio = 17.7938

ToUpper(str)| 160 msec.
to_upper(str)| 2841 msec.
Boost/hand ratio = 17.7563

Note the first line, which prints the value of _SECURE_SCL. The docs you gave were for VS 2005, but it's all the same for VS 2008: ​http://msdn.microsoft.com/en-us/library/aa985965.aspx

If there's anything else to try, let me know.

Replying to pavol_droba:

Just curious, VC++2008 employs quite rigorous run-time checking, which is sometimes enabled even in the Release mode. This checks significantly reduce the performance. To get a serious reading I suggest to disable all checks and compile in Relaase mode with maximum optimization possible. One example is SCL to disable it use #define _SECURE_SCL=0 or add _SECURE_SCL=0 into C++/Preprocessor in the project settings.

Can you please re-run the tests using this settings?

More info here: ​http://msdn.microsoft.com/en-us/library/aa985965(VS.80).aspx

[Yuri Goldfeld <yuri_goldfeld@…>]

Replying to anonymous:

since it seems like in-place-modifying functions like to_lower() are much slower than intuitively slower copying ones like to_lower_copy().

Ignore that... I misread the data. Although it's true that in the StrUtils implementation, doing stuff in place is much more beneficial performance-wise than in string_algo.

[Pavol Droba]

Second guess are locales. As you said, performance problem is shown when case sensitivity takes place. You might want to try to modify is_iequal (in compare.hpp) to use hardcoded strupr instead of locale specific toupper.

[Steven Watanabe]

I just ran a few tests using a custom case insensitive comparison predicate.

struct iequal_pred {
    bool operator()(char c1, char c2) const {
        return(std::tolower(c1) == std::tolower(c2));
    }
};

The results look a lot better.

StartsWithI(string("abcdefghi"), "aBcD")| 349 msec.
starts_with(string("abcdefghi"), "aBcD", iequal_pred())| 706 msec.
Boost/hand ratio = 2.02292

EqualsI("abcdefghi", "aBcDeFgHi")| 188 msec.
equals("abcdefghi", "aBcDeFgHi", iequal_pred())| 262 msec.
Boost/hand ratio = 1.39362

[yuri_goldfeld@…]

Thank you for your updates, Pavol and Steven. Unfortunately I do not have the time right now to experiment with it, but I may revisit it in the future. If either one of you will be doing further development on this library, all of this bears looking into. It's a really clean library, but this can be a stumbling block for practical development. Which is a shame, as I understand the library (or part thereof) is in consideration for a future C++ library standard?

It is interesting that the case-insensitivity performance is so much better with a custom predicate, given that the predicate is still relying on the locale mechanism, which I'd assumed is the source of slowness. I am assuming when you ran my original code (without the custom predicate), the results were equally as bad as mine?

Also, it seems that even with case-sensitive algorithms the performance can be quite a bit worse than my dumber library (see results for starts_with() and equals()).

[anonymous]

Replying to steven_watanabe:

I just ran a few tests using a custom case insensitive comparison predicate.

struct iequal_pred {
    bool operator()(char c1, char c2) const {
        return(std::tolower(c1) == std::tolower(c2));
    }
};

The results look a lot better.

StartsWithI(string("abcdefghi"), "aBcD")| 349 msec.
starts_with(string("abcdefghi"), "aBcD", iequal_pred())| 706 msec.
Boost/hand ratio = 2.02292

EqualsI("abcdefghi", "aBcDeFgHi")| 188 msec.
equals("abcdefghi", "aBcDeFgHi", iequal_pred())| 262 msec.
Boost/hand ratio = 1.39362

Hello, thanks for the testing. It seems that MS locates implementation is realy the cause of problems. In your test, you have used C-locales which are probably much faster

[anonymous]

Replying to yuri_goldfeld@…:

Also, it seems that even with case-sensitive algorithms the performance can be quite a bit worse than my dumber library (see results for starts_with() and equals()).

Hello,

Tests showed that the bottleneck lies in the MS implementation of locales. It is a possible problem, but I don't consider it critical. There are two reasons for it: 1) The problem is not on the side of the library. Following the boost spirit, the implementation is targeted for a generic C++ conforming compiler. As such you can see that it performs rather well on GCC. It does not try to workaround deficiencies in specific platforms/compilers like MS. The effect of these might be counterproductive. Right now it the well know library performs badly and show an obvious problem in the compiler, the developments team might be more inclined to fix the issue. Otherwise it would stay happy, not knowing that there's any problem at all. Let them do their job ;)

2) Secondly, since the StringAlgo library is written in very generic way, you can easily overcome this shortcoming by using your optimized is_iequal predicate. The boost version is not hardwired in to algorithms. It is merely provided as a generic default. All case-insensitive algorithms have a generic variant that accepts an arbitrary character comparison predicate. Please consult the documentation for the library to find out the details.

Under these conditions I consider this issue to be resolved.

Best Regards, Pavol

[yuri_goldfeld@…]

Hmm. Well, I did my best by providing data, which you may or may not act upon; certainly I'm not suggesting it's easy. The arguments above you put forth are sound in their own way, however from a practical (as opposed to theoretical) standpoint these are still serious issues. Simply put, if an implementation is 2-30 times slower than expected on one of the most popular compiler/hardware combinations out there, this is a problem. Of course, it sucks for you to have to figure out what the compiler is doing wrong in its optimizations or whatever... but the practical result remains the practical result and is really all that matters to the user.

I'm not saying there is a design flaw or anything or that the Boost spirit is violated, just that there is a usability problem in some very popular environments.

Also, while you say "the" bottleneck is locales, I reiterate that this is only true for case-insensitive things I ran; you can see that the case-sensitive algorithms (at least some of them) are also significantly slower (2+ times in my runs above), just not to the same extreme extent. It would be fairly easy to try out more, if desired.

At least, I would personally recommend you add a Performance section to the StringAlgo documentation referring to some of these potential pitfalls. This may help people in practical terms.

[anonymous]

I didn't mean to sound unthankful. I sure appreciate your effort very much. I simply don't see a reasonable time frame when I would be able to apply the results of your analysis. So I suggested a ready-to use scenario.

If you would like to participate and suggest some improvements to the implementation (ideally in form of patch) of would gladly review them and possibly integrate them into the library.

[Marshall Clow]

I tried Stephen's test on my Mac (gcc 4.2), both with and without his comparison predicate

StartsWithI(string("abcdefghi"), "aBcD")| 471 msec.
istarts_with(string("abcdefghi"), "aBcD")| 1060 msec.
Boost/hand ratio = 2.25053

EqualsI("abcdefghi", "aBcDeFgHi")| 274 msec.
iequals("abcdefghi", "aBcDeFgHi")| 989 msec.
Boost/hand ratio = 3.60949

----
StartsWithI(string("abcdefghi"), "aBcD")| 450 msec.
starts_with(string("abcdefghi"), "aBcD", iequal_pred ())| 575 msec.
Boost/hand ratio = 1.27778

EqualsI("abcdefghi", "aBcDeFgHi")| 253 msec.
equals("abcdefghi", "aBcDeFgHi", iequal_pred ())| 262 msec.
Boost/hand ratio = 1.03557

I will try on a Windows machine (well, VM) as well, but it looks like when you compare apples to apples, Boost.StringAlgo is not substantially slower than the hand-rolled code; rather, the performance difference was that the two routines were doing different kinds of comparisons - one was using std::tolower, while the other was using the locale system.

if I find the same thing on Windows, I will close this bug, especially since there's a simple way to use std::tolower for the conversions where speed is a priority.

[Marshall Clow]

Same thing on Windows; the bulk of the time is spent doing the locale-aware uppercasing.

If you want the kind of performance that you get with the other library, you should use the same kind of uppercasing as that library (std::tolower, for example)

Closing as "not a bug"