C++ performance challenge: integer to std::string conversion

by 
#include <string>

const char digit_pairs[201] = {
  "00010203040506070809"
  "10111213141516171819"
  "20212223242526272829"
  "30313233343536373839"
  "40414243444546474849"
  "50515253545556575859"
  "60616263646566676869"
  "70717273747576777879"
  "80818283848586878889"
  "90919293949596979899"
};


std::string& itostr(int n, std::string& s)
{
    if(n==0)
    {
        s="0";
        return s;
    }

    int sign = -(n<0);
    unsigned int val = (n^sign)-sign;

    int size;
    if(val>=10000)
    {
        if(val>=10000000)
        {
            if(val>=1000000000)
                size=10;
            else if(val>=100000000)
                size=9;
            else 
                size=8;
        }
        else
        {
            if(val>=1000000)
                size=7;
            else if(val>=100000)
                size=6;
            else
                size=5;
        }
    }
    else 
    {
        if(val>=100)
        {
            if(val>=1000)
                size=4;
            else
                size=3;
        }
        else
        {
            if(val>=10)
                size=2;
            else
                size=1;
        }
    }
    size -= sign;
    s.resize(size);
    char* c = &s[0];
    if(sign)
        *c="-";

    c += size-1;
    while(val>=100)
    {
       int pos = val % 100;
       val /= 100;
       *(short*)(c-1)=*(short*)(digit_pairs+2*pos); 
       c-=2;
    }
    while(val>0)
    {
        *c--='0' + (val % 10);
        val /= 10;
    }
    return s;
}

std::string& itostr(unsigned val, std::string& s)
{
    if(val==0)
    {
        s="0";
        return s;
    }

    int size;
    if(val>=10000)
    {
        if(val>=10000000)
        {
            if(val>=1000000000)
                size=10;
            else if(val>=100000000)
                size=9;
            else 
                size=8;
        }
        else
        {
            if(val>=1000000)
                size=7;
            else if(val>=100000)
                size=6;
            else
                size=5;
        }
    }
    else 
    {
        if(val>=100)
        {
            if(val>=1000)
                size=4;
            else
                size=3;
        }
        else
        {
            if(val>=10)
                size=2;
            else
                size=1;
        }
    }

    s.resize(size);
    char* c = &s[size-1];
    while(val>=100)
    {
       int pos = val % 100;
       val /= 100;
       *(short*)(c-1)=*(short*)(digit_pairs+2*pos); 
       c-=2;
    }
    while(val>0)
    {
        *c--='0' + (val % 10);
        val /= 10;
    }
    return s;
}

This will blow up on systems that disallow unaligned memory accesses (in which case, the first unaligned assignment via *(short*) would cause a segfault), but should work very nicely otherwise.

One important thing to do is to minimize the use of std::string. (Ironic, I know.) In Visual Studio, for example, most calls to methods of std::string are not inlined, even if you specify /Ob2 in compiler options. So even something as trivial as a call to std::string::clear(), which you might expect to be very fast, can take 100 clockticks when linking CRT as a static library, and as much as 300 clockticks when linking as a DLL.

For the same reason, returning by reference is better because it avoids an assignment, a constructor and a destructor.

More Related Contents:

  1. How can I convert a std::string to int?
  2. Efficient string concatenation in C++
  3. Convert String containing several numbers into integers
  4. Memory-efficient C++ strings (interning, ropes, copy-on-write, etc) [closed]
  5. convert string to integer in c++
  6. How to convert int to string in C++
  7. C++ most efficient way to convert string to int (faster than atoi)
  8. Read whole ASCII file into C++ std::string [duplicate]
  9. std::string formatting like sprintf
  10. Why does changing 0.1f to 0 slow down performance by 10x?
  11. Legality of COW std::string implementation in C++11
  12. Is std::vector so much slower than plain arrays?
  13. Why is transposing a matrix of 512×512 much slower than transposing a matrix of 513×513?
  14. Is it better to use std::memcpy() or std::copy() in terms to performance?
  15. Differences between C++ string == and compare()?
  16. Split a string into words by multiple delimiters [duplicate]
  17. Read file-contents into a string in C++ [duplicate]
  18. What’s faster, iterating an STL vector with vector::iterator or with at()?
  19. Fast Cross-Platform C/C++ Image Processing Libraries
  20. Set precision of std::to_string when converting floating point values [duplicate]
  21. Why is std::unordered_map slow, and can I use it more effectively to alleviate that?
  22. Why does the most negative int value cause an error about ambiguous function overloads?
  23. Similar String algorithm
  24. Why is std::fill(0) slower than std::fill(1)?
  25. Performance of qsort vs std::sort?
  26. Is Python faster and lighter than C++? [closed]
  27. When did C++ compilers start considering more than two hex digits in string literal character escapes?
  28. equivalent of Console.ReadLine() in c++
  29. converting narrow string to wide string
  30. What’s the difference between istringstream, ostringstream and stringstream? / Why not use stringstream in every case?

Leave a Comment