Mar ’10 09

Tino Didriksin published yet another speed comparison of different ways to convert an integer into a string (see his blog A howl on the Wind…). And again, Karma turns out to be the leader of the pack by being upto 10 times faster than the other tested methods. This nicely supports our own measurements (see here). Thanks Tino!

23 Responses to “Integer to String Conversion: Karma fastest again”

  1. Michael S says:

    So what’s the best method to use to convert integer to std::string? Seems to me a bit clumsy to go around character buffer (as mentioned in the referenced blogpost).

    Can you use the following?

    int n = ...;
    std::string str;
    karma::generate( str, int_, n );
    

    Regards
    /Michael

    • Hartmut Kaiser says:

      Michael,

      that’s not possible when using Karma directly, but it is only a minor effort to write a small wrapper function:

      bool generate_int(std::string& str, int value)
      {
          namespace karma = boost::spirit::karma;
          std::back_insert_iterator<std::string> sink(str);
          return karma::generate(sink, karma::int_, value);
      }
      

      Regards Hartmut

      • OvermindDL1 says:

        Couldn’t you make a templated ‘auto’ version of that too so it can generate just about any compatible sequence that you feed it?

        • Hartmut Kaiser says:

          Sure, here you are:

          template <typename T>
          bool generate(std::string& str, T const& value) 
          { 
            namespace karma = boost::spirit::karma;  
            std::back_insert_iterator<std::string> sink(str);  
            return karma::generate(sink, value);  
          } 
          

          which can be called for any generator having deined an auto-mapping.

          Regards Hartmut

  2. Arash Partow says:

    Here are my results comparing Karma to Strtk using the test mentioned, I’ve tried this on a dual and quad core system and I can’t figure out why karma has such a large stddev – I’ve made sure the system idle no other processes running etc.

    karma (reuse string): [132716880.00,110476998.00,108231426.00,115787133.00,115343046.00,112319019.00] with fastest 108231426.00, average 115812417.00, stddev 8764973.110
    karma (new string) : [112586184.00,107271477.00,108933894.00,106603308.00,104765256.00,108520209.00] with fastest 104765256.00, average 108113388.00, stddev 2647405.560
    strtk (reuse string): [143051544.00,137458215.00,143345754.00,148164336.00,141972543.00,141011658.00] with fastest 137458215.00, average 142500675.00, stddev 3493341.3543944495
    strtk (new string) : [102116232.00, 99954837.00,102348432.00,101817963.00,100126872.00, 97454043.00] with fastest 99954837.00, average 100636396.50, stddev 1863791.3243944495

    Is there something I’m missing with this test?

    • Hartmut Kaiser says:

      That’s interesting. Could you provide the tests you’re using so we could run it as well?

      Regards Hartmut

  3. Michael S says:

    I believe the following links could be useful for others too:

    * the mentioned/referenced mailing list mails can be found at http://old.nabble.com/Question-regarding-Qi-parse-to25020276.html

    * a strtk library article, including performance comparison tables, are found at http://www.codeproject.com/KB/recipes/Tokenizer.aspx

    Regards,
    /Michael

    • Hartmut Kaiser says:

      Michael,

      thanks for the links! Joel and I are in contact with the author of the strtk library and we pointed out to him that he is using the string class in a way explicitly prohibited by the Standard (he is modifying the buffer content returned by string::c_str()), which gives the speed advantage over Karma he is seeing. I believe, if he changes his code not to use undefined behavior it will be a lot slower as he needs to maintain his own buffers instead. The author promised to change his code and to rerun the benchmarks, which has not happened yet.

      Regards Hartmut

    • Arash Partow says:

      Michael S,
      I believe the String Toolkit library as it is now does not contain any of the “undefined behaviours” that Hartmut suggests with regards to the results found on the CodeProject article. I’m currently awaiting on Hartmut to provide an exact comment about the nature of the undefined behaviour as the library stands rather than a general comment or assumption.

      As for the results on the CodeProject article – all tests are rerun and results updated as new changes are made to the library.

  4. David Allen says:

    The result of this test is trivial. These times are dominated by the method of memory allocation and not the method of conversion. The results of these tests are obvious without running them.

    The only comparison that is meaningful is between ltoa and Spirit.Karma int_, because they both use static buffer allocation. This only demonstrates a very small advantage to using Karma.

    • Arash Partow says:

      David,

      Its true that the Tino tests are more than a bit weird, as in timing individual occurrences of very simple events running on a multithreaded OS running atop of a multiple execution pipe-line architecture will continuously add slight errors to the results, however it is does give a general idea of relative performance – which is quite useful.

      One typical suggestion that Tino could have used from stats-101, when attempting to use such timing values to compute an average, its very common to remove the top x% and bottom x% of values, this removes most of the outliers, which in turn should reduce the overall variance of the mean.

  5. Matt Wilson says:

    Hi

    Arash (posted above) indirectly made me aware of this test, by posting a question about integer-to-string conversion speed on the FastFormat website.

    I’ve added two cases to the test program:
    – FastFormat.Format API
    – FastFormat.Write API

    As expected, the Format API does pretty well, in particular against the likes of IOStreams and lexical_cast. But the best performance is to be had from the Write API, which actually out-performs all other options, by ~10%. The results are included at the bottom of this post, if you’re interested.

    Please note that the results are based on the latest FastFormat release (0.6.1-alpha-1), which is released today (not entirely coincidentally). I only did the “reuse string” test, as I couldn’t see anything to be gained by the “new string” test.

    Hope you find it useful. I’d be interested to know whether its omission from the test was because you’d not heard of it, or for another reason. (No drama either way, just interested.)

    Matt

    sprintf char[] (reuse string): [155325390.00,155740365.00,158275995.00,156004305.00,156835455.00,161862225.00] with fastest 155325390.00, average 157340622.50, stddev 2448784.83
    3694488
    sprintf char[] (new string): [160987650.00,160177080.00,159653520.00,156805650.00,157583520.00,161694300.00] with fastest 156805650.00, average 159483620.00, stddev 1920461.84
    3694488
    snprintf char[] (reuse string): [169543320.00,153888420.00,158899305.00,161842875.00,157050060.00,156248355.00] with fastest 153888420.00, average 159578722.50, stddev 5563204.51
    3694488
    sprintf &string[0] (reuse string): [159661440.00,161592990.00,164420925.00,173162430.00,164225145.00,164451465.00] with fastest 159661440.00, average 164585732.50, stddev 4624718.74
    3694488
    snprintf &string[0] (reuse string): [165962190.00,164496630.00,164494245.00,163612740.00,167895450.00,165797925.00] with fastest 163612740.00, average 165376530.00, stddev 1518495.00
    3694488
    stringstream (new stream, reuse string): [1193714250.00,1190577495.00,1209428370.00,1193707230.00,1211390025.00,1204317150.00] with fastest 1190577495.00, average 1200522420.00, stddev 8983543.69
    3694488
    stringstream (new stream, new string): [1226163735.00,1201297275.00,1214607525.00,1190251920.00,1186489350.00,1208366505.00] with fastest 1186489350.00, average 1204529385.00, stddev 14993818.06
    3694488
    stringstream (reuse stream, reuse string): [583118325.00,580263240.00,592005735.00,576352950.00,575631735.00,590709315.00] with fastest 575631735.00, average 583013550.00, stddev 7021597.51
    3694488
    stringstream (reuse stream, new string): [574644255.00,577037670.00,583907850.00,582114765.00,584508885.00,565901805.00] with fastest 574644255.00, average 578019205.00, stddev 7109863.28
    3694488
    strstream (new stream, reuse string): [1444521045.00,1443160845.00,1440073440.00,1446230205.00,1439475075.00,1452498705.00] with fastest 1439475075.00, average 1444326552.50,stddev 4762992.14
    3694488
    strstream (reuse stream, reuse string): [1061660565.00,1061998620.00,1056166770.00,1069181355.00,1059007920.00,1070805930.00] with fastest 1056166770.00, average 1063136860.00, stddev 5735083.12
    3694488
    lexical_cast (reuse string): [190329570.00,189709515.00,190576695.00,189606870.00,193901715.00,192015660.00] with fastest 189606870.00, average 191023337.50, stddev 1654271.66
    3694488
    lexical_cast (new string): [180927345.00,180979335.00,180865440.00,182459280.00,181848840.00,181075725.00] with fastest 180865440.00, average 181359327.50, stddev 648826.08
    3694488
    karma (reuse string): [31486995.00,31442880.00,31781595.00,31588680.00,31948905.00,31438875.00] with fastest 31442880.00, average 31614655.00, stddev 208311.82
    0
    karma (new string): [32334585.00,32100675.00,32017605.00,32160105.00,32116185.00,32129565.00] with fastest 32017605.00, average 32143120.00, stddev 105273.13
    0
    ff::fmt(reuse string): [114945900.00,103449285.00,104955705.00,103789005.00,102475860.00,105196200.00] with fastest 102475860.00, average 105801992.50, stddev 4590092.38
    3694488
    ff::write(reuse string): [29302455.00,29464905.00,29412450.00,29626590.00,29599095.00,29471220.00] with fastest 29302455.00, average 29479452.50, stddev 120050.51
    3694488

    • Hartmut Kaiser says:

      Matt,

      thanks for the numbers. Do you mind posting the full source code of your tests somewhere for use to have a look?

      I don’t know why the original author didn’t compare against your library.
      Regards Hartmut

      • Matt Wilson says:

        Am happy to. I’ll be including it – or an equivalent (as I don’t know what the copyright situation is) – in the next 0.6 alpha, hopefully at the coming weekend. (I’ll also include another test, based on Karma’s test program.)

        For now, I’ll just publish the blocks of code that I added to include the two FastFormat APIs. Please note that this was with VC++ 9 (32-bit) windows, compiled with:

        cl -nologo -c -EHsc -DWIN32 -O2 -Ox -I.. -I%BOOST% -I%FASTFORMAT_ROOT%/include -I%STLSOFT%/include ..\test.performance.int_to_string.cpp ..\implicit_link.cpp
        

        and linked with:

        link -nologo -release test.performance.int_to_string.obj implicit_link.obj -libpath:%FASTFORMAT_ROOT%/lib
        

        (The implicit_link.cpp file just does a #include <fastformat/implicit_link.h>, btw)

        I make no claims to how it might all perform with other compilers and other platforms, but previous research on its performance show a pretty consistent relationship between them (with the singular exception that IOStreams does heaps better on Linux than Windows).

        Also, I should note that there are FF facilities for eeking out better performance, by using different “sinks” (such as the char_buffer_sink and the c_string_sink). But the default sink accepts anything structurally-conformant to std::string (or std::wstring in widestring builds).

        If you need any help with getting set up, or have any other questions about FastFormat, feel free to post questions on the FastFormat Help Forum.

        Here goes with the code (making no promises for how the angle brackets go … ;-) :

        #include <strstream>
        #include <fastformat/ff.hpp>
        #include <stlsoft/conversion/integer_to_string.hpp>
        
          . . .
        
        
         {
          size_t tlen = 0;
          std::vector<double> timings;
          timings.reserve(R);
          for (size_t r=0 ; r<R ; ++r) {
           ticks start = getticks();
           char x[21];
           std::string str;
           for (int i=0-(N/2) ; i<N/2 ; ++i) {
            str.resize(0);
            tlen += ff::fmt(str, "{0}", i).size();
           }
           ticks end = getticks();
           double timed = elapsed(end, start);
           timings.push_back(timed);
          }
        
          std::cout << "ff::fmt(std::string): ";
          PrintStats(timings);
          std::cout << std::endl;
          std::cout << tlen << std::endl;
         }
        
         {
          size_t tlen = 0;
          std::vector<double> timings;
          timings.reserve(R);
          for (size_t r=0 ; r<R ; ++r) {
           ticks start = getticks();
           char x[21];
           std::string str;
           for (int i=0-(N/2) ; i<N/2 ; ++i) {
            str.resize(0);
            tlen += ff::write(str, i).size();
           }
           ticks end = getticks();
           double timed = elapsed(end, start);
           timings.push_back(timed);
          }
        
          std::cout << "ff::write(std::string): ";
          PrintStats(timings);
          std::cout << std::endl;
          std::cout << tlen << std::endl;
         }
        
      • Arash Partow says:

        Hartmut,

        How is your investigation coming along? – I’d like to know as I’m not sure if the results I’m getting are valid or not. it would be nice to know either way.

  6. Matt says:

    Hi! I suppose the thread is a bit old — but how do we go about efficient double to int conversion, given a particular precision threshold?

Leave a Reply

To use RetinaPost you must register at http://www.RetinaPost.com/register