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

Subject: [Boost-bugs] [Boost C++ Libraries] #3218: string_algo algorithms are quite slow in some popular compiler/OS/hardware situations
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2009-06-26 02:01:32

#3218: string_algo algorithms are quite slow in some popular compiler/OS/hardware
situations
------------------------------------------------------+---------------------
 Reporter:  Yuri Goldfeld <yuri_goldfeld@…>           |       Owner:  pavol_droba
     Type:  Bugs                                      |      Status:  new        
Milestone:  To Be Determined                          |   Component:  string_algo
  Version:  Boost 1.37.0                              |    Severity:  Problem    
 Keywords:  performance string_algo strings           |  
------------------------------------------------------+---------------------
 (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_at_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_at_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

 }}}

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/3218>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.