id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
3218,string_algo algorithms are quite slow in some popular compiler/OS/hardware situations,Yuri Goldfeld <yuri_goldfeld@…>,Marshall Clow,"(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

}}}
",Bugs,closed,To Be Determined,algorithm,Boost 1.37.0,Problem,invalid,performance string_algo strings,yuri_goldfeld@…