30

正如标题中提到的，我正在寻找比 atoi 可以给我更多性能的东西。目前，我知道的最快的方法是

atoi(mystring.c_str())

最后，我更喜欢不依赖 Boost 的解决方案。有没有人有很好的性能技巧来做到这一点？

附加信息：int 不会超过 20 亿，它总是正数，字符串中没有小数位。

4

10 回答 10

36

我使用查找表尝试了解决方案，但发现它们充满了问题，而且实际上速度不是很快。最快的解决方案被证明是最没有想象力的：

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
于 2013-05-30T02:15:23.250 回答
16

atoi给定某些假设，可以显着改进。Andrei Alexandrescu 在 C++ and Beyond 2012 会议上的演讲有力地证明了这一点。Hi 的替代品使用循环展开和 ALU 并行性来实现性能改进的数量级。我没有他的资料，但这个链接使用了类似的技术：http ://tombarta.wordpress.com/2008/04/23/specializing-atoi/

于 2013-05-30T01:31:20.023 回答
15

本页比较了使用不同编译器的不同 string->int 函数之间的转换速度。根据给出的结果，naive 函数不提供错误检查，其速度大约是 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;
}
于 2013-05-30T01:34:51.053 回答
12

这里有相当多的代码示例非常复杂并且做了不必要的工作，这意味着代码可以更精简、更快。

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

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

第一个观察：不需要单独检查字符串结尾字符，因为它不是数字。因此，对“数字”的检查隐含地涵盖了 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指向一个数字是解析器首先调用这段代码的原因。在我的代码中，整个 shebang 看起来像这样（断言和其他生产质量的噪音被消除了）：

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 位，它每秒转换 1.15 亿个 uint，长度为 19..20 位（gcc 4.8.1）的每秒转换 6000 万个单位。这比我的目的快十倍以上strtoull()（对于我的目的来说还不够，但我离题了......）。这是转换每个包含 1000 万个数字 (100..200 MB) 的文本 blob 的时间，这意味着内存时间使这些数字看起来比在从缓存运行的合成基准测试中要差一些。

于 2014-11-14T21:38:03.977 回答
6

Paddy 的fast_atoi 实现比atoi快- 毫无疑问 - 但它仅适用于无符号整数。

下面，我放置了 Paddy 的 fast_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;
}
于 2014-09-14T18:20:52.607 回答
2

这是 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 几乎可以肯定是内联的，因此不会花费您任何时间。

我真的看不出这里有改进的余地。

于 2013-05-30T04:13:09.363 回答
2

一个更快的转换函数，仅用于正整数，没有错误检查。

乘法总是比求和和移位慢，因此用移位改变乘法。

int fast_atoi( const char * str )
{
    int val = 0;
    while( *str ) {
        val = (val << 3) + (val << 1) + (*str++ - '0');
    }
    return val;
}
于 2018-07-18T04:23:45.923 回答
1

为什么不使用字符串流？我不确定它的特殊开销，但您可以定义：

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

当然，你需要

#include <stringstream>
于 2013-05-30T02:02:30.450 回答
0

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

我会尝试的东西（即使它正在使用内存访问，所以它可能会很慢取决于缓存）是

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 ...

ift1等t10是静态分配的并且是常量，编译器不应该担心任何别名，并且生成的机器代码应该相当不错。

于 2013-05-30T08:07:49.567 回答
-1

这是我的。Atoi 是我能想到的最快的。我使用 msvc 2010 编译，因此可以将两个模板结合起来。在 msvc 2010 中，当我组合模板时，它会使您提供 cb 参数的情况变慢。

Atoi 处理几乎所有特殊的 atoi 情况，并且比这更快或更快：

int val = 0;
while( *str ) 
    val = val*10 + (*str++ - '0');

这是代码：

#define EQ1(a,a1) (BYTE(a) == BYTE(a1))
#define EQ1(a,a1,a2) (BYTE(a) == BYTE(a1) && EQ1(a,a2))
#define EQ1(a,a1,a2,a3) (BYTE(a) == BYTE(a1) && EQ1(a,a2,a3))

// Atoi is 4x faster than atoi.  There is also an overload that takes a cb argument.
template <typename T> 
T Atoi(LPCSTR sz) {
    T n = 0;
    bool fNeg = false;  // for unsigned T, this is removed by optimizer
    const BYTE* p = (const BYTE*)sz;
    BYTE ch;
    // test for most exceptions in the leading chars.  Most of the time
    // this test is skipped.  Note we skip over leading zeros to avoid the 
    // useless math in the second loop.  We expect leading 0 to be the most 
    // likely case, so we test it first, however the cpu might reorder that.
    for ( ; (ch=*p-'1') >= 9 ; ++p) { // unsigned trick for range compare
      // ignore leading 0's, spaces, and '+'
      if (EQ1(ch, '0'-'1', ' '-'1', '+'-'1'))
        continue;
      // for unsigned T this is removed by optimizer
      if (!((T)-1 > 0) && ch==BYTE('-'-'1')) {
        fNeg = !fNeg;
        continue;
      }
      // atoi ignores these.  Remove this code for a small perf increase.
      if (BYTE(*p-9) > 4)  // \t, \n, 11, 12, \r. unsigned trick for range compare
        break;
    }
    // deal with rest of digits, stop loop on non digit.
    for ( ; (ch=*p-'0') <= 9 ; ++p) // unsigned trick for range compare
      n = n*10 + ch; 
    // for unsigned T, (fNeg) test is removed by optimizer
    return (fNeg) ? -n : n;
}

// you could go with a single template that took a cb argument, but I could not
// get the optimizer to create good code when both the cb and !cb case were combined.
// above code contains the comments.
template <typename T>
T Atoi(LPCSTR sz, BYTE cb) {
    T n = 0;
    bool fNeg = false; 
    const BYTE* p = (const BYTE*)sz;
    const BYTE* p1 = p + cb;
    BYTE ch;
    for ( ; p<p1 && (ch=*p-'1') >= 9 ; ++p) {
      if (EQ1(ch,BYTE('0'-'1'),BYTE(' '-'1'),BYTE('+'-'1')))
        continue;
      if (!((T)-1 > 0) && ch == BYTE('-'-'1')) {
        fNeg = !fNeg;
        continue;
      }
      if (BYTE(*p-9) > 4)  // \t, \n, 11, 12, \r
        break;
    }
    for ( ; p<p1 && (ch=*p-'0') <= 9 ; ++p)
      n = n*10 + ch; 
    return (fNeg) ? -n : n;
}
于 2014-05-19T17:37:17.113 回答