|
The fastest to_string in town.
December 01, 2002
URL:http://www.drdobbs.com/flexible-c-1-efficient-integer-to-string/184401596
/* /////////////////////////////////////////////////////////////
*
* ...
*
* Extract from stlsoft_integer_to_string.h
*
* www: http://www.synesis.com.au/stlsoft
* http://www.stlsoft.org/
*
* Copyright (C) 2002, Synesis Software Pty Ltd.
* (Licensed under the Synesis Software Standard Source License:
* http://www.synesis.com.au/licenses/ssssl.html)
*
* ...
*
* ////////////////////////////////////////////////////////// */
...
template <class C, class I>
inline const C *unsigned_integer_to_string( C *buf,
size_t cchBuf,
I i)
{
C *psz = buf + cchBuf - 1; // Set psz to last char
*psz = 0; // Set terminating null
do
{
unsigned lsd = i % 10; // Get least significant
// digit
i /= 10; // Prepare for next most
// significant digit
--psz; // Move back
*psz = get_digit_character<C>()[lsd]; // Place the digit
} while(i != 0);
return psz;
}
— End of Listing —
/* /////////////////////////////////////////////////////////////
*
* ...
*
* Extract from stlsoft_integer_to_string.h
*
* www: http://www.synesis.com.au/stlsoft
* http://www.stlsoft.org/
*
* Copyright (C) 2002, Synesis Software Pty Ltd.
* (Licensed under the Synesis Software Standard Source License:
* http://www.synesis.com.au/licenses/ssssl.html)
*
* ...
*
* ////////////////////////////////////////////////////////// */
...
template <class C, class I>
inline const C *signed_integer_to_string( C *buf,
size_t cchBuf,
I i)
{
C *psz = buf + cchBuf - 1; // Set psz to last char
*psz = 0; // Set terminating null
if(i < 0)
{
do
{
signed lsd = i % 10; // Determine least
// significant digit
i /= 10; // Deal with next most
// significant digit
--psz; // Move back
*psz = get_digit_character<C>()[lsd]; // Place digit
} while(i != 0);
*(--psz) = C('-'); // Prepend minus sign
}
else
{
do
{
signed lsd = i % 10; // Determine least
// significant digit.
i /= 10; // Deal with next most
// significant digit
--psz; // Move back
*psz = get_digit_character<C>()[lsd]; // Place digit
} while(i != 0);
}
return psz;
}
— End of Listing —
/* /////////////////////////////////////////////////////////////
*
* ...
*
* Extract from stlsoft_integer_to_string.h
*
* www: http://www.synesis.com.au/stlsoft
* http://www.stlsoft.org/
*
* Copyright (C) 2002, Synesis Software Pty Ltd.
* (Licensed under the Synesis Software Standard Source License:
* http://www.synesis.com.au/licenses/ssssl.html)
*
* ...
*
* ////////////////////////////////////////////////////////// */
...
template <ss_typename_param_k C>
inline const C *get_digit_character()
{
static const C s_characters[19] =
{
'9'
, '8'
, '7'
, '6'
, '5'
, '4'
, '3'
, '2'
, '1'
, '0'
, '1'
, '2'
, '3'
, '4'
, '5'
, '6'
, '7'
, '8'
, '9'
};
static const C *s_mid = s_characters + 9;
return s_mid;
}
— End of Listing —
Introduction
sprintf is probably the most common way to convert integers to string form, whether you call it directly or indirectly (e.g., within iostream insertion manipulators). However, the very powerful sprintf function is overkill for many simple conversions, and there is a performance penalty for using it.
This article describes a simple template-based technique, applicable on all platforms and compatible with multithreaded processes, for efficiently converting 8-, 16-, 32-, and 64-bit signed and unsigned integers to strings.
The article will also present performance results quantifying the advantages in different scenarios, and for different compilers/runtime libraries, on both Win32 and Linux platforms. The results show that the conversion functions can perform at as little as 13% of the call cost of sprintf.
Implementation
The implementation [1] is template-based, providing a function for unsigned-integer conversion (which is more efficient, there being no sign) and one for signed-integer conversions (which needs to account for processing negative numbers and prepending the minus sign). Abridged implementations of the unsigned and signed versions are shown in Listings 1 and 2 respectively [2].
The functions work by writing backwards into a caller-supplied character buffer and returning a pointer to the converted form within the buffer. The least significant digit is calculated and written to the current endpoint within the buffer. The digit is converted into its equivalent character value via the lookup table contained within get_digit_character [3] (see Listing 3). The convertee value is then divided by 10, the endpoint moved backwards, the cycle repeated until 0 is reached, and the current endpoint is returned as a pointer to the converted string. For signed integers with a negative value, a minus sign is first prepended, and the function returns a pointer to that character.
Performance
I’ll discuss two performance scenarios. The first scenario is a simple conversion, returning a pointer to a converted value. The second scenario involves the sprintf statement:
sprintf("string0:%dstring1:%dstring2:%dstring3:%dstring4:%d", ...);
and its equivalent combination of strcpy and integer_to_string calls. The scenarios were tested on Win32 (Borland 5.51, GCC MinGW, and Visual C++ 6.0) and Linux (GCC). Tables 1 and 2 and show the results [4], which are expressed as a percentage of the sprintf time.
As the results show, simple conversions can be as low as 15% of the cost of using sprintf. For the complex conversion, the efficiency gain is less significant for all compilers/platforms other than Visual C++.
Also notable is that the gains are much less for 64-bit integers than for 8, 16, or 32 and in some cases can actually be more expensive.
Conclusion
The use of these functions avoids the higher call cost of sprintf and also lends simple code construction by virtue of returning a pointer to the converted string. An additional advantage is that it can help in avoiding linking to the C runtime library in circumstances where this is desirable [5].
They are thread-safe, since they do not use a static internal buffer. The original (non-thread-safe) version did so, and tests showed that it was somewhat better performing, but thread-safety was deemed more important.
For 64-bit conversions it may be better to stick with sprintf on performance grounds (at least on non-64-bit platforms). This is presumably because the sprintf implementations have been optimized to deal with 64-bit integers on 32-bit systems [6].
The current implementation does not provide any zero padding, but the intention is merely to provide an efficient alternative to the common default conversion. Formatting should still be carried out in sprintf, which has a long history and is no doubt well optimized for such sophisticated operations.
Another criticism is that this solution is limited to base 10. I am currently working on adding an additional template parameter for the base, which I expect to be no less efficient. The implementations will have the same algorithm(s), but will use an expanded lookup table and use the parameterized base rather than the hard-coded 10 in the implementations.(In further research conducted after this article was written, Digital Mars C/C++ 8.29 shows a creditable best performance range of 46% (worst is 97%), and Metrowerks’ CodeWarrior 8.0 shows a very impressive 9% (worst 117%). The full results for these two compilers are included in the online archive [2], along with all the source code and project files for Visual C++ 5.0/6.0, Digital Mars 8.29, and Metrowerks CodeWarrior 8.0.)
Potential Applications
You could use these functions in the implementation of serialization libraries, since the functions convert much quicker than sprintf for single variables. Furthermore, they are also useful in any situation where a function needs a pointer to char containing the (decimal) string form of an integer (e.g., when setting the text of a window in a UI), or when you want to avoid linking in the C runtime library [5].
Notes and References
[1] These functions form part of the STLSoft Conversion Library, available at <http://stlsoft.org/libraries/conversion_library.html>. STLSoft is an open-source organization for the development of robust, lightweight, cross-platform STL software.
[2] The full implementation, along with the test program and supporting headers, is available for download from <www.cuj.com/code> or [1].
[3] As well as providing flexibility beyond the decimal digits (in anticipation of supporting the planned non-base 10 implementations), this implementation will also work with character encoding schemes that do not have contiguous ordering of the characters “0” and “1” through “9.”
[4] The results were insignificantly affected by targeting particular (versions of Intel) processors.
[5] There are various reasons why one might wish to avoid linking to the C runtime library, such as reliability (e.g., Win32 with Visual C++), executable size (e.g., creating very small executables, usually on Win32), and providing one’s own chopped-down version, though discussion of such is outside the scope of this article.
[6] I am currently working on a custom implementation for 64-bit conversions on Intel 32-bit platforms.
Matthew Wilson holds a degree in Information Technology and a Phd in Electrical Engineering and is a software development consultant for Synesis Software. Matthew’s work interests are in writing bullet-proof real-time, GUI, and software-analysis software in C, C++, and Java. He has been working with C++ for over 10 years and is currently bringing STLSoft.org and its offshoots into the public domain. Matthew can be contacted via [email protected] or at <http://stlsoft.org>.
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.