Flexible C++ #4: Efficient Integer To String Conversions

This is the final installment in the integer-to-string series [1, 2, 3]. The previous two installments [2, 3] and the original article [1] described different approaches to the efficient conversion of integers into strings. This time arround, I continue with the "Flexible C++" philosophy, and consider one last variation.

Solutions 1 - 4

Solution 1 [1] is the STLSoft [4] integer_to_string<> template, and it is used as follows:

int i = . . .;
char buffer[21];
puts(stlsoft::integer_to_string(buffer, 21, i));

Solution 2 [2] is the WinSTL [5] int_to_string<> template, and its use would look like:

int i = . . .;
puts(winstl::int_to_string<char>(i));

Solution 3 [3] looks the same as Solution 2, but employs thread-specific circular buffering to try to cheat the possibility of overwriting the internal buffer as a result of intrathread reentrancy. Solution 3 is rejected since it is a purveyor of dangerous false hopes.

Solution 4 [3] uses modern compilers' abilities to deduce the sizes of arrays, which means that the first form can be succinctly, and safely, expressed as

int i = . . .;
char buffer[21];
puts(stlsoft::integer_to_string(buffer, i));

All four solutions perform significantly better than sprintf() ([3]). I suggested in the previous column [3] that Solution 4 is the best solution. However, I've not exhausted the possibilities, and there's one more implementation strategy to consider.

Solution 5

The last solution is a departure from the previous four. Rather than returning a C-string pointer (char/wchar_t const*) into a buffer passed to the function or one provided by the library on a per-thread basis, this version returns an instance of a proxy object. The proxy class–int2str_proxy<>–contains its own buffer as a member variable, and provides an implicit conversion to a C-string pointer. Integer-to-string conversion is, of course, carried out by stlsoft::integer_to_string<>(), as is the case with all the solutions. The implementations of the class and the assistor function, int2str<>(), are in Listing 1.

To use it, you simply call int2str<>(), stipulating the appropriate character types, as in int2str<wchar_t>(101) int2str<>() returns an instance of int2str_proxy<>, and is therefore a Conversion Shim [6]. If you aren't familiar with Shims, they are a simple but powerful generalizing mechanism. (See [6] for a detailed description of the concept, and the various Shim types.)

The advantage of this technique is that the return-value lifetime problem inherent in Solution 2, and incompletely addressed in Solution 3, is not a feature of this approach. Hence an expression such as the following will yield correct results.

void dump_2_ints(char const *s1, char const *s2);
int i = . . . ;
int j = . . . ;
dump_2_ints(int2str<char>(i), int2str<char>(j));

However, in common with Conversion Shims [6], this one exposes another return-value lifetime problem, just in a slightly different form. Consider the following code:

int         i = . . . ;
char const  *s = int2str<char>(i);
 
puts(s); // Eeek!

This code is bad. Although it may work, it will only be as an artifact of your compiler and the precise layout of your program. In principle, the behavior of the aforementioned code is undefined, and therefore it is broken. This is one of the caveats of Conversion Shims [6]: the returned converted values must not be retained if they are pointers, but used immediately, or deep copies taken.

The efficiency we're buying is, in part, derived from the fact that we're trading in pointers, specifically C-string pointers. It's been demonstrated that the cost of such pointer-derived efficiencies are that the code is, if not dangerous, at least accompanied with a health warning. The way around this is to return something that is a value-type, such as a string instance, as in:

inline std::string integer_to_string_instance(int i)
{
  char  buffer[21];
  return std::string(integer_to_string(buffer, stlsoft_num_elements(buffer), i));
}

Naturally, the safety would be bought at the cost of a loss in efficiency.

Performance

All the previous solutions have been performance tested, and now's no time to go soft, so this final installment describes a performance test of Solutions 1, 2, 4, and 5, along with sprintf(), itoa(), and integer_to_string_instance(). These seven conversion mechanisms were tested for nine popular Win32 compilers, all optimized for speed [7]. The test program, the full results in an Excel spreadsheet, and the various STLSoft headers [8] are included in the online archive. Data points are missing where the compilers do not support a particular solution.

Figure 1 shows the performances of these seven conversion schemes. Since the various compilers' runtime libraries show marked differences in the performances of their sprintf() implementations, these results are not necessarily indicative of the relative efficacy of the compilers' code generation. We'll do that shortly, with some absolute figures.

The results show that considerable gains are to be had in using Solutions 1-4 over the other schemes for most compilers. GCC and Intel show the best performance; using the custom solutions is around an eighth the cost of sprintf(). Second, at around 20 percent the sprintf() cost, comes Digital Mars 8.38, which has undergone significant improvements in the optimization of template code over previous versions. CodeWarrior, Comeau, and both versions of Visual C++ also show a significant performance benefit, at around 25 percent the cost of sprintf(). Borland and Watcom have about 50 percent the cost of sprintf(). But bear in mind what I said about drawing conclusions between the absolute speeds of the compilers from this relative table; Digital Mars and Watcom all have absolute sprintf() times that are about 50-60 percent those of the other compilers, so it's not appropriate to judge the relative performances of the compilers at this point.

I've included itoa() (or _itoa() for Intel and Visual C++) in this month's assessment. For the compilers that do above average in the template optimization, the custom solutions outperform itoa(). Only Borland and Visual C++ 7.1 have an itoa() that outperforms the custom solutions, and neither of these is especially good at optimizing templates. As newer, and better, versions of these compilers come out we can expect the custom solutions to out perform itoa() (which will probably always bear a performance cost due to its separate compilation and support for different bases).

In terms of the four custom solutions, the results show that there's virtually no difference between any of them, which is quite pleasing. This means that you can take whichever approach best suits your needs, without having to worry about performance differences between them.

Figure 2 shows the absolute performance times for sprintf(), atoi(), the four custom solutions, and the integer_to_string_instance() function. The results clearly show what we've learned in previous installments of the column: that Intel and GCC are the masters of template optimization. It is only with these two compilers, and the custom solutions, that the scenario time falls under the 1000ms barrier. However, with release 8.38, Digital Mars comes very close to matching them. (Previous releases of Digital Mars do not perform with anywhere near the alacrity, so you should make sure you upgrade.) Also giving a very creditable account of itself is CodeWarrior. The next tier are Comeau, Visual C++ 6.0, and Visual C++ 7.1 (It's worth nothing, and somewhat concerning, that although Visual C++ 7.1 is faster than its 5-year-old predecessor in library related measures, in the optimization of the custom solutions, for which we may expect the pure code generation efficiency to be more clearly represented, it is slower in some cases by up to 15 percent.) Watcom produces the next best results for the custom solutions, and then Borland brings up the rear.

Conclusion

It's fair to draw some cautious conclusions regarding the relative efficiency of the different compilers' abilities in optimizing template code, since the integer_to_string<>() technique relies only on other, simple template functions resident in the same header file, rather than any standard (C or C++) library facilities. Since much of modern C++ coding involves a lot of templates, this is a pretty important issue.

The inclusion of itoa() (or _itoa() for Visual C++) into the tests is interesting. For those compilers that are not up to par on template optimization, you can save yourself a degree of complexity and just use this widely available, albeit nonstandard, library function. I would hope, though, as compilers continue to improve, that the custom solutions would represent the more portably efficient option.

GCC, Intel, and, to a slightly lesser extent, Digital Mars are the cream of the crop when it comes to the optimization of the templates, and set a mark that all other compilers should be working towards with some eagerness. But that's enough soapbox; I don't want to distract you from the primary conclusion that you should be using the STLSoft conversion components.

Finally, there's one last thing I should point out, though it may cost me some stars on my C++ good behavior chart. The performance for the value (std::string) returning option doesn't exactly set the world alight. In several cases it outperforms sprintf(), but this is with compilers that do comparatively well on the custom solutions, so I think it's safe to attribute the performance to stlsoft::integer_to_string<>(). But despite this helping hand, the cost of the single memory allocation ([9]) and strcpy() involved in creating the return value means that this option does not fair well with respect to the custom solutions. The relative performances are 222 percent, 509 percent, 199 percent, 335 percent, 238 percent, 367 percent, and 149 percent, so I would say that if you need speed, you should opt for the custom solutions, and be mindful of the pitfalls (not that Solution 4 holds any real dangers for a competent programmer).

Summary

I hope you've enjoyed this little series into integer-to-string conversions, and that it's given you food for thought. In general, I think it's wise to profile the libraries you're using, even the standard libraries, and not just accept what you're given; it's interesting that some of the very best compilers are linked to lacklustre libraries.

Second, I hope you've had a chance to think outside the box on the subjects of number string representation, return value lifetime, threading, and reentrancy.

Finally, I would like to think that you've all gained a little vicarious empowerment through my industry, and will be less willing to accept the restrictions of your libraries, compilers, or of any "one true way" of accepted best practice. There's never going to be a substitute for understanding your tools and making informed choices.

Acknowledgments

Thanks to Eelis van der Weegen and John Torjo, who suggested similar approaches to Solution 5. Thanks also to Massimiliano Alberti for suggesting that I include itoa() into the study, even if it does make the integer_to_string<> template look less impressive.

Notes and References

[1] Efficient Integer To String Conversions", Matthew Wilson, C/C++ User's Journal, December 2002.

[4] Efficient Integer To String Conversions, part 2", Matthew Wilson, C/C++ User's Journal Experts Forum, September 2003.

[3] Efficient Integer To String Conversions, part 3", Matthew Wilson, C/C++ User's Journal Experts Forum, September 2003.

[4] STLSoft is an open-source organization whose focus is the development of robust, lightweight, cross-platform template software, and is located at http://stlsoft.org/.

[5] WinSTL is the Win32-specific subproject of STLSoft, and is located at http://winstl.org/. There's also a UNIXSTL, which lives at http://unixstl.org/.

[6] Generalized String Manipulation: Access Shims and Type Tunnelling", Matthew Wilson, CUJ, August 2003. There are a number of Shim types, and Attribute and Control Shims appear in several popular libraries, including Boost (http://boost.org/).

[7] All the compilations were set to maximum speed optimization, and targeted (as much as is possible) at the host system processor, a Pentium IV. The settings for the compilers were as follows:

Note: To pass optimization options through to Comeau, you need to use a forward slash, rather than a hyphen. Comeau attempts to pass all forward slash options to the back end compiler, although there's no guarantee that it can/will do so for all.

[8] The updated stlsoft_integer_to_string.h is included in the archive for this article, and will appear in the STLSoft libraries from v1.7.1 onwards, which should be out early in 2004. v1.7.1-beta versions are available online now.

[9] This assumes that all the compilers tested apply RVO in the integer_to_string_instance() function. They do, but the story behind that is for another instalment of "Flexible C++."

About the Author

Matthew Wilson is a software development consultant for Synesis Software, specializing in robustness and performance in C, C++, Java and .NET. Matthew is the author of the STLSoft libraries, and the forthcoming book Imperfect C++ (to be published by Addison-Wesley, 2004). He can be contacted via [email protected] or at http://stlsoft.org/.