Boost C++ Libraries: Ticket #3218: string_algo algorithms are quite slow in some popular compiler/OS/hardware situations

attachment set

Fri, 26 Jun 2009 02:04:14 GMT

attachment → StrUtils.hpp

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

attachment set

Fri, 26 Jun 2009 02:05:46 GMT

attachment → perf.cpp

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().

Fri, 26 Jun 2009 02:23:38 GMT

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 — Fri, 26 Jun 2009 06:43:52 GMT

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

attachment set

yuri_goldfeld@… — Fri, 26 Jun 2009 22:24:26 GMT

attachment → perf.2.cpp

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 — Fri, 26 Jun 2009 22:30:42 GMT

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

Fri, 26 Jun 2009 23:21:38 GMT

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 — Sun, 28 Jun 2009 21:46:48 GMT

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 — Sat, 18 Jul 2009 16:48:41 GMT

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@… — Mon, 20 Jul 2009 17:52:56 GMT

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 — Mon, 20 Jul 2009 19:17:46 GMT

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 — Mon, 20 Jul 2009 19:27:31 GMT

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@… — Mon, 20 Jul 2009 20:04:29 GMT

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 — Mon, 20 Jul 2009 20:15:49 GMT

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.

owner, component changed

Marshall Clow — Wed, 28 Dec 2011 18:51:59 GMT

owner changed from Pavol Droba to Marshall Clow
component string_algo → algorithm

status changed

Marshall Clow — Wed, 04 Jan 2012 06:54:15 GMT

status new → assigned

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.

status changed; resolution set

Marshall Clow — Wed, 04 Jan 2012 16:41:22 GMT

status assigned → closed
resolution → invalid

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"