C ++性能挑战：整数到std :: string的转换
任何人都可以击败我的整数到std ::字符串代码的性能，下面链接？
已经有几个问题解释了如何在C ++中将整数转换为std::string ，比如这个，但是没有一个提供的解决方案是有效的。
以下是一些编译就绪代码，用于与一些常见方法进行竞争：
与流行的观点相反， boost::lexical_cast有它自己的实现（白皮书），并且不使用stringstream和numeric插入操作符。 我真的很想看看它的表现，因为这个问题表明它很糟糕。
和我自己的贡献一样，它在桌面计算机上具有竞争力，并且演示了一种在嵌入式系统上全速运行的方法，与依赖于整数模的算法不同：
如果您想要使用该代码，我将使用简化的BSD许可证（允许使用商业用途，请求归属地）提供该代码。 请问。
最后，函数ltoa是非标准的，但广泛可用。
我会很快发布我的表现评估作为答案。
算法规则
std::string 。 INT_MIN上的代码。 stringstream的标准C ++版本（http://ideone.com/jh3Sa）的character-for-character相同，但任何显然可以理解的都是正确的数字。 希望讨论
除了更好的算法，我还想在几个不同的平台和编译器上获得一些基准（让我们使用MB / s吞吐量作为我们的标准测量单位）。 我相信我的算法的代码（我知道sprintf基准测试使用了一些快捷方式 - 现在已经修复）是标准定义明确的行为，至少在ASCII假设下是这样，但是如果您看到任何未定义的行为或输入，输出无效，请指出。
结论：
对于g ++和VC2010，不同的算法会执行，可能是由于std::string的不同实现。 VC2010显然在NRVO方面做得更好，摆脱了仅靠gcc的价值回报。
代码被发现超过sprintf一个数量级。 ostringstream落后了50倍甚至更多。
挑战的胜利者是user434507，他的代码运行速度是我自己在gcc上速度的350％。 由于SO社区的突发事件，更多条目将被关闭。
目前的（最终？）速度冠军是：
sprintf快8倍：http：//ideone.com/0uhhX sprintf快15倍：http：//ideone.com/VpKO3 #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;
}
这将在不允许未对齐的内存访问的系统上爆发（在这种情况下，通过*(short*)的第一个未对齐的赋值会导致段错误），但应该非常好地工作。
一个重要的事情是尽量减少使用std::string 。 （讽刺的，我知道。）例如，在Visual Studio中，即使在编译器选项中指定/ Ob2，大多数对std :: string方法的调用也不会内联。 因此，即使像调用std::string::clear()这样微不足道的东西，你可能希望它的速度非常快，但在将CRT作为静态库链接时可能需要100个时钟，而在链接时可能需要多达300个时钟DLL。
出于同样的原因，通过引用返回更好，因为它避免了赋值，构造函数和析构函数。
啊，真棒挑战的方式...我有很多的乐趣。
我有两种算法需要提交（代码在底部，如果你想跳过它）。 在我的比较中，我要求该函数返回一个字符串，并且它可以处理int和unsigned int。 比较那些不构成字符串的东西和那些没有意义的东西。
第一个是有趣的实现，它不使用任何预先计算的查找表或明确的分割/模数。 这个与其他的gcc以及除了Timo之外的其他所有人都有竞争（这是我在下面解释的一个很好的理由）。 第二种算法是我最高性能的实际提交。 在我的测试中，它击败了gcc和msvc上的所有其他人。
我想我知道为什么MSVC的一些结果非常好。 std :: string有两个相关的构造函数std::string(char* str, size_t n)
和
std::string(ForwardIterator b, ForwardIterator e)
gcc对它们都做同样的事情......那就是使用第二个来实现第一个。 第一个构造函数可以比MSVC更有效地实现，MSVC也是如此。 这样做的副作用是，在某些情况下（比如我的快速代码和Timo的代码），可以内联字符串构造函数。 实际上，在MSVC中这些构造函数之间的切换几乎是我的代码的两倍差异。
我的表现测试结果：
代码来源：
- Voigt
- 蒂莫
- ergosys
- user434507
- user-voigt-timo
- 嘻哈乐趣
- 跳蚤快
Ubuntu 10.10 64位Core i5上的gcc 4.4.5 -O2
hopman_fun: 124.688 MB/sec --- 8.020 s hopman_fast: 137.552 MB/sec --- 7.270 s voigt: 120.192 MB/sec --- 8.320 s user_voigt_timo: 97.9432 MB/sec --- 10.210 s timo: 120.482 MB/sec --- 8.300 s user: 97.7517 MB/sec --- 10.230 s ergosys: 101.42 MB/sec --- 9.860 s
Windows 7 64位Core i5上的MSVC 2010 64位/ Ox
hopman_fun: 127 MB/sec --- 7.874 s hopman_fast: 259 MB/sec --- 3.861 s voigt: 221.435 MB/sec --- 4.516 s user_voigt_timo: 195.695 MB/sec --- 5.110 s timo: 253.165 MB/sec --- 3.950 s user: 212.63 MB/sec --- 4.703 s ergosys: 78.0518 MB/sec --- 12.812 s
以下是关于ideone的一些结果和测试/时间框架
http://ideone.com/XZRqp
请注意，ideone是一个32位环境。 我的两个算法都受到这种影响，但hopman_fast至少仍然具有竞争力。
请注意，对于那些不构造字符串的那两个，我添加了以下函数模板：
template <typename T>
std::string itostr(T t) {
std::string ret;
itostr(t, ret);
return ret;
}
现在我的代码...首先是有趣的一个：
// hopman_fun
template <typename T>
T reduce2(T v) {
T k = ((v * 410) >> 12) & 0x000F000F000F000Full;
return (((v - k * 10) << 8) + k);
}
template <typename T>
T reduce4(T v) {
T k = ((v * 10486) >> 20) & 0xFF000000FFull;
return reduce2(((v - k * 100) << 16) + (k));
}
typedef unsigned long long ull;
inline ull reduce8(ull v) {
ull k = ((v * 3518437209u) >> 45);
return reduce4(((v - k * 10000) << 32) + (k));
}
template <typename T>
std::string itostr(T o) {
union {
char str[16];
unsigned short u2[8];
unsigned u4[4];
unsigned long long u8[2];
};
unsigned v = o < 0 ? ~o + 1 : o;
u8[0] = (ull(v) * 3518437209u) >> 45;
u8[0] = (u8[0] * 28147497672ull);
u8[1] = v - u2[3] * 100000000;
u8[1] = reduce8(u8[1]);
char* f;
if (u2[3]) {
u2[3] = reduce2(u2[3]);
f = str + 6;
} else {
unsigned short* k = u4[2] ? u2 + 4 : u2 + 6;
f = *k ? (char*)k : (char*)(k + 1);
}
if (!*f) f++;
u4[1] |= 0x30303030;
u4[2] |= 0x30303030;
u4[3] |= 0x30303030;
if (o < 0) *--f = '-';
return std::string(f, (str + 16) - f);
}
然后是快速的：
// hopman_fast
struct itostr_helper {
static unsigned out[10000];
itostr_helper() {
for (int i = 0; i < 10000; i++) {
unsigned v = i;
char * o = (char*)(out + i);
o[3] = v % 10 + '0';
o[2] = (v % 100) / 10 + '0';
o[1] = (v % 1000) / 100 + '0';
o[0] = (v % 10000) / 1000;
if (o[0]) o[0] |= 0x30;
else if (o[1] != '0') o[0] |= 0x20;
else if (o[2] != '0') o[0] |= 0x10;
else o[0] |= 0x00;
}
}
};
unsigned itostr_helper::out[10000];
itostr_helper hlp_init;
template <typename T>
std::string itostr(T o) {
typedef itostr_helper hlp;
unsigned blocks[3], *b = blocks + 2;
blocks[0] = o < 0 ? ~o + 1 : o;
blocks[2] = blocks[0] % 10000; blocks[0] /= 10000;
blocks[2] = hlp::out[blocks[2]];
if (blocks[0]) {
blocks[1] = blocks[0] % 10000; blocks[0] /= 10000;
blocks[1] = hlp::out[blocks[1]];
blocks[2] |= 0x30303030;
b--;
}
if (blocks[0]) {
blocks[0] = hlp::out[blocks[0] % 10000];
blocks[1] |= 0x30303030;
b--;
}
char* f = ((char*)b);
f += 3 - (*f >> 4);
char* str = (char*)blocks;
if (o < 0) *--f = '-';
return std::string(f, (str + 12) - f);
}
问题中提供的代码的基准数据：
关于ideone（gcc 4.3.4）：
Core i7，Windows 7 64位，8 GB RAM，Visual C ++ 2010 32位：
cl /Ox /EHsc
Core i7，Windows 7 64位，8 GB RAM，Visual C ++ 2010 64位：
cl /Ox /EHsc
Core i7，Windows 7 64位，8 GB RAM，cygwin gcc 4.3.4：
g++ -O3
编辑 ：我要添加我自己的答案，但问题是关闭的，所以我在这里添加它。 :)我写了自己的算法，并设法对Ben的代码进行了很好的改进，尽管我只在MSVC 2010中进行了测试。我还使用与Ben原始版本相同的测试设置对所有实现进行了基准测试码。 - 蒂莫
Intel Q9450，Win XP 32bit，MSVC 2010
cl /O2 /EHsc
-
const char digit_pairs[201] = {
"00010203040506070809"
"10111213141516171819"
"20212223242526272829"
"30313233343536373839"
"40414243444546474849"
"50515253545556575859"
"60616263646566676869"
"70717273747576777879"
"80818283848586878889"
"90919293949596979899"
};
static const int BUFFER_SIZE = 11;
std::string itostr(int val)
{
char buf[BUFFER_SIZE];
char *it = &buf[BUFFER_SIZE-2];
if(val>=0) {
int div = val/100;
while(div) {
memcpy(it,&digit_pairs[2*(val-div*100)],2);
val = div;
it-=2;
div = val/100;
}
memcpy(it,&digit_pairs[2*val],2);
if(val<10)
it++;
} else {
int div = val/100;
while(div) {
memcpy(it,&digit_pairs[-2*(val-div*100)],2);
val = div;
it-=2;
div = val/100;
}
memcpy(it,&digit_pairs[-2*val],2);
if(val<=-10)
it--;
*it = '-';
}
return std::string(it,&buf[BUFFER_SIZE]-it);
}
std::string itostr(unsigned int val)
{
char buf[BUFFER_SIZE];
char *it = (char*)&buf[BUFFER_SIZE-2];
int div = val/100;
while(div) {
memcpy(it,&digit_pairs[2*(val-div*100)],2);
val = div;
it-=2;
div = val/100;
}
memcpy(it,&digit_pairs[2*val],2);
if(val<10)
it++;
return std::string((char*)it,(char*)&buf[BUFFER_SIZE]-(char*)it);
}
上一篇: C++ performance challenge: integer to std::string conversion