StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POC++ performance challenge: integer to std::string conversion
text
Body
copied!<p><strong>Can anyone beat the performance of my integer to std::string code, linked below?</strong></p> <p>There are already several questions that explain how to convert an integer into a <code>std::string</code> in C++, such as <a href="https://stackoverflow.com/questions/228005/alternative-to-itoa-for-converting-integer-to-string-c">this one</a>, but none of the solutions provided are efficient.</p> <p>Here is compile-ready code for some common methods to compete against:</p> <ul> <li>The "C++ way", using stringstream: <a href="http://ideone.com/jh3Sa" rel="noreferrer">http://ideone.com/jh3Sa</a></li> <li>sprintf, which SO-ers usually recommend to the performance conscious: <a href="http://ideone.com/82kwR" rel="noreferrer">http://ideone.com/82kwR</a></li> </ul> <p>Contrary to <a href="https://stackoverflow.com/questions/228005/alternative-to-itoa-for-converting-integer-to-string-c/228041#228041">popular belief</a>, <code>boost::lexical_cast</code> has its own implementation (<a href="http://www.accu.org/var/uploads/journals/overload74.pdf" rel="noreferrer">white paper</a>) and does not use <code>stringstream</code> and numeric insertion operators. I'd really like to see its performance compared, because <a href="https://stackoverflow.com/questions/1250795/very-poor-boostlexical-cast-performance">this other question suggests that it's miserable</a>.</p> <p>And my own contribution, which is competitive on desktop computers, and demonstrates an approach that runs at full speed on embedded systems as well, unlike algorithms dependent on integer modulo:</p> <ul> <li>Ben's algorithms: <a href="http://ideone.com/SsEUW" rel="noreferrer">http://ideone.com/SsEUW</a></li> </ul> <p>If you want to use that code, I'll make it available under a simplified BSD license (commercial use allowed, attribution required). Just ask.</p> <p>Finally, the function <code>ltoa</code> is non-standard but widely available.</p> <ul> <li>ltoa version, for anyone who has a compiler that provides it (ideone doesn't): <a href="http://ideone.com/T5Wim" rel="noreferrer">http://ideone.com/T5Wim</a></li> </ul> <p>I'll post my performance measurements as an answer shortly.</p> <h2>Rules for algorithms</h2> <ul> <li>Provide code for a conversion of at least 32-bit signed and unsigned integers into decimal.</li> <li>Produce output as a <code>std::string</code>.</li> <li>No tricks that are incompatible with threading and signals (for example, static buffers).</li> <li>You may assume an ASCII character set.</li> <li>Make sure to test your code on <code>INT_MIN</code> on a two's complement machine where the absolute value is not representable.</li> <li>Ideally, the output should be character-for-character identical with the canonical C++ version using <code>stringstream</code>, <a href="http://ideone.com/jh3Sa" rel="noreferrer">http://ideone.com/jh3Sa</a>, but anything that is clearly understandable as the correct number is ok, too.</li> <li><strong>NEW</strong>: Although you can use whatever compiler and optimizer options (except completely disabled) you want for the comparison, the code needs to also compile and give correct results under at least VC++ 2010 and g++.</li> </ul> <h2>Hoped-for Discussion</h2> <p>Besides better algorithms, I'd also like to get some benchmarks on several different platforms and compilers (let's use MB/s throughput as our standard unit of measure). I believe that the code for my algorithm (I know the <code>sprintf</code> benchmark takes some shortcuts -- now fixed) is well-defined behavior by the standard, at least under the ASCII assumption, but if you see any undefined behavior or inputs for which the output is invalid, please point that out.</p> <h2>Conclusions:</h2> <p>Different algorithms perform for g++ and VC2010, likely due to the different implementations of <code>std::string</code> on each. VC2010 clearly does a better job with NRVO, getting rid of return-by-value helped only on gcc.</p> <p>Code was found that outperforms <code>sprintf</code> by an order of magnitude. <code>ostringstream</code> falls behind by a factor of 50 and more.</p> <p>The winner of the challenge is user434507 who produces code that runs 350% of the speed of my own on gcc. Further entries are closed due to the whims of the SO community.</p> <p>The current (final?) speed champions are:</p> <ul> <li>For gcc: user434507, at 8 times faster than <code>sprintf</code>: <a href="http://ideone.com/0uhhX" rel="noreferrer">http://ideone.com/0uhhX</a></li> <li>For Visual C++: Timo, at 15 times faster than <code>sprintf</code>: <a href="http://ideone.com/VpKO3" rel="noreferrer">http://ideone.com/VpKO3</a></li> </ul>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload