C++中将字符串转换为整数的最有效方法（比atoi更快）

Question

正如标题所述，我正在寻找比atoi更高效的解决方案。目前，我所知道的最快速的方法是

atoi(mystring.c_str())

最后，我希望一种不依赖于Boost的解决方案。是否有好的性能技巧来实现这个？

附加信息：整数不会超过20亿，始终为正数，字符串中没有小数位。

- user788171

---

你会很难击败 atoi。 - Joel

这个问题的答案可能会有些取决于你允许的整数范围。你想转换“任何”整数吗，还是你的输入范围更具体？你确定'mystring'只包含没有其他字符的整数吗？它可以是负数吗？ - paddy

我添加了一些额外的信息，常规大小的整数，始终为正，字符串中没有小数。 - user788171

你得到了很好的答案，但我一直在想 - 你是否真正知道 atoi 单独使用会消耗你整体时间的相当比例？人们经常问这样的问题，实际上有其他的事情可以产生更大的加速效果，但他们不知道如何找到这些事情。 - Mike Dunlavey

Answer 1

我尝试使用查找表的解决方案，但发现它们存在很多问题，并且实际上并不快。最快的解决方案竟然是最不富有想象力的：

int fast_atoi( const char * str )
{
    int val = 0;
    while( *str ) {
        val = val*10 + (*str++ - '0');
    }
    return val;
}

使用一百万个随机生成的字符串运行基准测试：

fast_atoi : 0.0097 seconds
atoi      : 0.0414 seconds

公平地说，我也通过强制编译器不将其内联来测试了这个函数。结果仍然很好：

fast_atoi : 0.0104 seconds
atoi      : 0.0426 seconds

只要您的数据符合fast_atoi函数的要求，就可以得到相当不错的性能。这些要求是：

1. 输入字符串仅包含数字字符或为空
2. 输入字符串表示从0到INT_MAX的数字

- paddy

---

太棒了！非常有用。 - undefined

Answer 2

atoi可以在特定的假设下得到显著的改进。这在Andrei Alexandrescu在2012年的C++ and Beyond会议上有力地展示出来。他的替代方案使用了循环展开和ALU并行性来实现性能的数量级提升。我没有他的资料，但是这个链接使用了类似的技术：http://tombarta.wordpress.com/2008/04/23/specializing-atoi/

- Scott Jones

---

我想我也看过那个。这是你所提到的演示文稿吗？虽然它不是关于C++和Beyond的，但我认为它主要是关于int-to-string而不是reverse。但无论如何，从中还是可以学到很多东西的。 - jogojapan

链接的 int atoi(const char *str) 无法检测到所有溢出。 - chux - Reinstate Monica

Answer 3

此页面比较了使用不同编译器的不同string->int函数之间的转换速度。根据所呈现的结果，未提供错误检查的朴素函数提供的速度大约是atoi()速度的两倍。

// Taken from http://tinodidriksen.com/uploads/code/cpp/speed-string-to-int.cpp
int naive(const char *p) {
    int x = 0;
    bool neg = false;
    if (*p == '-') {
        neg = true;
        ++p;
    }
    while (*p >= '0' && *p <= '9') {
        x = (x*10) + (*p - '0');
        ++p;
    }
    if (neg) {
        x = -x;
    }
    return x;
}

它始终是正数

为了进行微小的优化，请删除上述代码中的负数检查。

如果您可以保证字符串除了数字字符之外不会有其他任何内容，那么可以通过更改循环进一步进行微小的优化。

while (*p >= '0' && *p <= '9') {

while (*p != '\0' ) {

这样就只剩下了你

unsigned int naive(const char *p) {
    unsigned int x = 0;
    while (*p != '\0') {
        x = (x*10) + (*p - '0');
        ++p;
    }
    return x;
}

- x-x

---

然而，天真的实现不符合标准：它不会丢弃前导空格。如果您不需要标准的保证.. - dyp

@DyP：'\0'将会中断循环...应该是<'0'。无论如何，链接页面没有列出其他函数，除了这个天真的循环，这些函数是严肃的超越atoi的候选者——它们没有利用上述关于有效字符期望、始终为正、已知最大大小、不需要任何错误检查的洞察力带来的效率。 - Tony Delroy

这基本上是我做的方式，尽管在循环中我倾向于编写 {x *= 10; x += (*p++ - '0');}。它可能会编译成大致相同的东西。 - Mike Dunlavey

(*p++)&15 可能比 *p++ - '0' 更快。 - johnnycrash

@johnnycrash 不确定为什么会这样。按位与和常量减法都是一条指令。 - Eric Pauley

Answer 4

这里的许多代码示例相当复杂并且做了不必要的工作，这意味着代码可以更加简洁和快速。

转换循环通常编写为对每个字符执行三个不同操作：

• 如果它是字符串结束字符，则退出循环
• 如果它不是数字，则退出循环
• 将其从其代码点转换为实际数字值

第一个观察结果：没有必要单独检查字符串结束字符，因为它不是数字。 因此，“数字性”检查隐含地涵盖了EOS条件。

第二个观察结果：范围测试的双重条件，例如(c >= '0' && c <= '9')，可以通过使用无符号类型并将范围锚定在零来转换为单个测试条件。 这样，范围开始以下的所有不需要的值都被映射到上限以上的范围内，所有不需要的值都被映射到上限以上的范围内：(uint8_t(c-'0') <= 9)

这里需要计算c - '0'...

因此，内部转换循环可以变得更加简洁：

uint64_t n = digit_value(*p);
unsigned d;

while ((d = digit_value(*++p)) <= 9)
{
   n = n * 10 + d;
}

这里的代码被调用的前提条件是 p 指向一个数字，这就是为什么第一个数字可以直接提取出来（这也避免了一次不必要的 MUL）。

这个前提条件并不像乍看起来那么奇怪，因为 p 指向数字正是解析器首先调用这段代码的原因。在我的代码中，整个过程看起来像这样（省略了断言和其他产品质量相关的噪声）：

unsigned digit_value (char c)
{
   return unsigned(c - '0');
}

bool is_digit (char c)
{
   return digit_value(c) <= 9;
}

uint64_t extract_uint64 (char const **read_ptr)
{
   char const *p = *read_ptr;
   uint64_t n = digit_value(*p);
   unsigned d;

   while ((d = digit_value(*++p)) <= 9)
   {
      n = n * 10 + d;
   }

   *read_ptr = p;

   return n;
}

digit_value() 的第一个调用通常会被编译器省略，如果代码被内联并且调用代码已经通过调用 is_digit() 计算出该值。

n * 10 比手动移位（例如 n = (n << 3) + (n << 1) + d）要快，至少在我的机器上使用 gcc 4.8.1 和 VC++ 2013 是如此。我猜两个编译器都使用带有索引缩放的 LEA 来一次性添加三个值，并将其中一个乘以2、4或8。

无论如何，这正是应该的：我们在单独的函数中编写漂亮干净的代码，并表达所需的逻辑（n * 10、x％CHAR_BIT等），而编译器则将其转换为移位、掩码、LEA 等，在大循环中内联所有内容，并处理所有必需的混乱，以使事情变快。我们甚至不必再在所有东西前面加上inline。如果有任何问题，我们只需要在编译器过度热衷时谨慎使用 __declspec(noinline)。

我正在使用上述代码在程序中从文本文件和管道中读取数十亿个数字；如果长度为9..10位，则每秒可以转换115百万个 uints，长度为19..20位时每秒可以转换60百万个 uints（使用gcc 4.8.1）。那比 strtoull() 快十倍以上（刚好足够我的目的，但我走题了……）。这是转换包含 10 百万个数字的文本块的时间（100..200 MB），这意味着内存计时使得这些数字看起来比从缓存运行的合成基准测试中更糟。

- DarthGizka

---

我喜欢在Swift比较中使用“unsigned”。当“p [0] =='\ 0'”时，我不喜欢UB。 - chux - Reinstate Monica

Answer 5

帕迪的实现方式 fast_atoi 比 atoi 快得多 - 毫无疑问 - 但它仅适用于 无符号整数。

下面，我提供了经过评估的帕迪快速转换函数的版本，它仅允许使用无符号整数，但通过将昂贵的操作*替换为+，加快了转换速度。

unsigned int fast_atou(const char *str)
{
    unsigned int val = 0;
    while(*str) {
        val = (val << 1) + (val << 3) + *(str++) - 48;
    }
    return val;
}

这里，我放置了一个完整版本的 fast_atoi()，它可以将带符号的整数转换为数字：

int fast_atoi(const char *buff)
{
    int c = 0, sign = 0, x = 0;
    const char *p = buff;

    for(c = *(p++); (c < 48 || c > 57); c = *(p++)) {if (c == 45) {sign = 1; c = *(p++); break;}}; // eat whitespaces and check sign
    for(; c > 47 && c < 58; c = *(p++)) x = (x << 1) + (x << 3) + c - 48;

    return sign ? -x : x;
} 

- soerium

---

不确定位移解决方案是否实际上更快，因为x86截断乘法是一条指令，而gcc将知道顶部位不重要。 - Eric Pauley

实际上，我在MSVC上使用* 10和位移算法进行了基准测试，并且我始终能够获得更快的速度。 - Octo Poulos

任何现代的编译器都知道在最适合目标 CPU 的情况下，将某些常量的乘法自动转换为移位或其他操作，如果您打开了优化选项（并且必要时提供有关您正在优化的确切 CPU 型号的足够信息）。通常，如果您只是通过查看表达式就能知道可以将其优化为不同的表达式，那么一个好的现代编译器几乎肯定也知道。 （仍然对这个答案加一，因为这是很好的信息需要知道。） - mtraceur

Answer 6

一种更快的转换函数，仅适用于正整数，无需错误检查。

乘法始终比求和和移位慢，因此将乘法替换为移位。

int fast_atoi( const char * str )
{
    int val = 0;
    while( *str ) {
        val = (val << 3) + (val << 1) + (*str++ - '0');
    }
    return val;
}

- hamSh

---

虽然你可以将数字 10 分解为 16 - 4 - 2，但更简单的分解方式是 8 + 2。 - Ben Voigt

不是_总是_，乘法比加法和移位慢。 - chux - Reinstate Monica

你能给一个例子吗？ - hamSh

@hamSh 我使用 fast_atoi 和 fast_atoi2（它将数字乘以10）进行了基准测试，平均而言，fast_atoi2 比 MSVC 上的 fast_atoi 快约1.7％...。 - Octo Poulos

Answer 7

以下是gcc中atoi函数的全部内容：

long atoi(const char *str)
{
    long num = 0;
    int neg = 0;
    while (isspace(*str)) str++;
    if (*str == '-')
    {
        neg=1;
        str++;
    }
    while (isdigit(*str))
    {
        num = 10*num + (*str - '0');
        str++;
    }
    if (neg)
        num = -num;
    return num;
 }

在你的情况下，空格和负数检查是多余的，但只使用纳秒。

isdigit几乎肯定是内联的，因此不会浪费你任何时间。

我真的看不到这里有改进的空间。

- Joel

---

我能够使用这个来创建不同整数类型的函数模板，并在AVR上运行它。 - Caleb Reister

我真的不觉得这里有改进的余地。当最终结果应为 LONG_MIN 时，10*num + (*str - '0') 是UB的。isspace（*str），isdigit（*str）在*str <0时是UB的-虽然这可能不会引起OP的关注。 - chux - Reinstate Monica

Answer 8

我对这里提供的不同函数进行了快速基准测试，还加入了一些额外的内容，并默认将它们转换为int64_t。编译器为MSVC。

以下是结果（左侧为正常时间，右侧为扣除开销后的时间）：

atoi            : 153283912 ns => 1.000x : 106745800 ns => 1.000x
atoll           : 174446125 ns => 0.879x : 127908013 ns => 0.835x
std::stoll      : 358193237 ns => 0.428x : 311655125 ns => 0.343x
std::stoull     : 354171912 ns => 0.433x : 307633800 ns => 0.347x
-----------------------------------------------------------------
fast_null       :  46538112 ns => 3.294x :         0 ns => infx   (overhead estimation)
fast_atou       :  92299625 ns => 1.661x :  45761513 ns => 2.333x (@soerium)
FastAtoiBitShift:  93275637 ns => 1.643x :  46737525 ns => 2.284x (@hamSh)
FastAtoiMul10   :  93260987 ns => 1.644x :  46722875 ns => 2.285x (@hamSh but with *10)
FastAtoiCompare :  86691962 ns => 1.768x :  40153850 ns => 2.658x (@DarthGizka)
FastAtoiCompareu:  86960900 ns => 1.763x :  40422788 ns => 2.641x (@DarthGizka + uint)
-----------------------------------------------------------------
FastAtoi32      :  92779375 ns => 1.652x :  46241263 ns => 2.308x (handle the - sign)
FastAtoi32u     :  86577312 ns => 1.770x :  40039200 ns => 2.666x (no sign)
FastAtoi32uu    :  87298600 ns => 1.756x :  40760488 ns => 2.619x (no sign + uint)
FastAtoi64      :  93693575 ns => 1.636x :  47155463 ns => 2.264x
FastAtoi64u     :  86846912 ns => 1.765x :  40308800 ns => 2.648x
FastAtoi64uu    :  86890537 ns => 1.764x :  40352425 ns => 2.645x
FastAtoiDouble  :  90126762 ns => 1.701x :  43588650 ns => 2.449x (only handle int)
FastAtoiFloat   :  92062775 ns => 1.665x :  45524663 ns => 2.345x (same)

DarthGizka的代码是最快的，而且有停止非数字字符的优点。

此外，位移“优化”比仅使用* 10略慢一点。

基准测试在伪随机字符串上对每个算法进行1000万次迭代，以尽可能限制分支预测，然后再重新运行15次。对于每个算法，丢弃4个最慢和4个最快的时间，并给出8个中位数时间的平均值作为结果。这提供了很多稳定性。另外，我运行fast_null来估计基准测试中的开销（循环+字符串更改+函数调用），然后在第二个数字中扣除该值。

以下是函数的代码：

int64_t fast_null(const char* str) { return (str[0] - '0') + (str[1] - '0'); }

int64_t fast_atou(const char* str)
{
    int64_t val = 0;
    while (*str) val = (val << 1) + (val << 3) + *(str++) - 48;
    return val;
}

int64_t FastAtoiBitShift(const char* str)
{
    int64_t val = 0;
    while (*str) val = (val << 3) + (val << 1) + (*str++ - '0');
    return val;
}

int64_t FastAtoiMul10(const char* str)
{
    int64_t val = 0;
    while (*str) val = val * 10 + (*str++ - '0');
    return val;
}

int64_t FastAtoiCompare(const char* str)
{
    int64_t val = 0;
    uint8_t x;
    while ((x = uint8_t(*str++ - '0')) <= 9) val = val * 10 + x;
    return val;
}

uint64_t FastAtoiCompareu(const char* str)
{
    uint64_t val = 0;
    uint8_t  x;
    while ((x = uint8_t(*str++ - '0')) <= 9) val = val * 10 + x;
    return val;
}

int32_t FastAtoi32(const char* str)
{
    int32_t val  = 0;
    int     sign = 0;
    if (*str == '-')
    {
        sign = 1;
        ++str;
    }
    uint8_t digit;
    while ((digit = uint8_t(*str++ - '0')) <= 9) val = val * 10 + digit;
    return sign ? -val : val;
}

int32_t FastAtoi32u(const char* str)
{
    int32_t val = 0;
    uint8_t digit;
    while ((digit = uint8_t(*str++ - '0')) <= 9) val = val * 10 + digit;
    return val;
}

uint32_t FastAtoi32uu(const char* str)
{
    uint32_t val = 0;
    uint8_t  digit;
    while ((digit = uint8_t(*str++ - '0')) <= 9) val = val * 10u + digit;
    return val;
}

int64_t FastAtoi64(const char* str)
{
    int64_t val  = 0;
    int     sign = 0;
    if (*str == '-')
    {
        sign = 1;
        ++str;
    }
    uint8_t digit;
    while ((digit = uint8_t(*str++ - '0')) <= 9) val = val * 10 + digit;
    return sign ? -val : val;
}

int64_t FastAtoi64u(const char* str)
{
    int64_t val = 0;
    uint8_t digit;
    while ((digit = uint8_t(*str++ - '0')) <= 9) val = val * 10 + digit;
    return val;
}

uint64_t FastAtoi64uu(const char* str)
{
    uint64_t val = 0;
    uint8_t  digit;
    while ((digit = uint8_t(*str++ - '0')) <= 9) val = val * 10u + digit;
    return val;
}

float FastAtoiFloat(const char* str)
{
    float   val = 0;
    uint8_t x;
    while ((x = uint8_t(*str++ - '0')) <= 9) val = val * 10.0f + x;
    return val;
}

double FastAtoiDouble(const char* str)
{
    double  val = 0;
    uint8_t x;
    while ((x = uint8_t(*str++ - '0')) <= 9) val = val * 10.0 + x;
    return val;
}

以下是我使用的基准测试代码，以防万一...

void Benchmark()
{
    std::map<std::string, std::vector<int64_t>> funcTimes;
    std::map<std::string, std::vector<int64_t>> funcTotals;
    std::map<std::string, int64_t>              funcFinals;

#define BENCH_ATOI(func)                     \
    do                                       \
    {                                        \
        auto    start    = NowNs();          \
        int64_t z        = 0;                \
        char    string[] = "000001987";      \
        for (int i = 1e7; i >= 0; --i)       \
        {                                    \
            string[0] = '0' + (i + 0) % 10;  \
            string[1] = '0' + (i + 1) % 10;  \
            string[2] = '0' + (i + 3) % 10;  \
            string[3] = '0' + (i + 5) % 10;  \
            string[4] = '0' + (i + 9) % 10;  \
            z += func(string);               \
        }                                    \
        auto elapsed = NowNs() - start;      \
        funcTimes[#func].push_back(elapsed); \
        funcTotals[#func].push_back(z);      \
    }                                        \
    while (0)

    for (int i = 0; i < 16; ++i)
    {
        BENCH_ATOI(atoi);
        BENCH_ATOI(atoll);
        BENCH_ATOI(std::stoll);
        BENCH_ATOI(std::stoull);
        //
        BENCH_ATOI(fast_null);
        BENCH_ATOI(fast_atou);
        BENCH_ATOI(FastAtoiBitShift);
        BENCH_ATOI(FastAtoiMul10);
        BENCH_ATOI(FastAtoiCompare);
        BENCH_ATOI(FastAtoiCompareu);
        //
        BENCH_ATOI(FastAtoi32);
        BENCH_ATOI(FastAtoi32u);
        BENCH_ATOI(FastAtoi32uu);
        BENCH_ATOI(FastAtoi64);
        BENCH_ATOI(FastAtoi64u);
        BENCH_ATOI(FastAtoi64uu);
        BENCH_ATOI(FastAtoiFloat);
        BENCH_ATOI(FastAtoiDouble);
    }

    for (auto& [func, times] : funcTimes)
    {
        std::sort(times.begin(), times.end(), [](const auto& a, const auto& b) { return a < b; });
        fmt::print("{:<16}: {}\n", func, funcTotals[func][0]);
        int64_t total = 0;
        for (int i = 4; i <= 11; ++i) total += times[i];
        total /= 8;
        funcFinals[func] = total;
    }

    const auto base     = funcFinals["atoi"];
    const auto overhead = funcFinals["fast_null"];
    for (const auto& [func, final] : funcFinals)
        fmt::print("{:<16}: {:>9} ns => {:.3f}x : {:>9} ns => {:.3f}x\n", func, final, base * 1.0 / final, final - overhead, (base - overhead) * 1.0 / (final - overhead));
}

- Octo Poulos

Answer 9

为什么不使用stringstream？我不确定它的特定开销，但你可以定义：

int myInt; 
string myString = "1561";
stringstream ss;
ss(myString);
ss >> myInt;

当然，你需要

#include <stringstream> 

- Rome_Leader

---

这是C++的典型写法，但速度比精简的“朴素”转换循环慢几个数量级。 - DarthGizka

你进行了基准测试吗？ - undefined

Answer 10

唯一明确的答案是检查你的编译器和真实数据。

我会尝试一些东西（即使它使用内存访问，所以根据缓存可能会很慢），例如：

int value = t1[s[n-1]];
if (n > 1) value += t10[s[n-2]]; else return value;
if (n > 2) value += t100[s[n-3]]; else return value;
if (n > 3) value += t1000[s[n-4]]; else return value;
... continuing for how many digits you need to handle ...

如果t1，t10等都是静态分配和常量，编译器就不必担心任何别名问题，生成的机器代码应该相当不错。

- 6502