尽可能快地解析整数

问题描述 投票:0回答:2

我正在尝试将解析字符串优化为 C 中的 uint64 值。目前我使用一个天真的解决方案:

uint64_t parse(const char *source)
{
   uint64_t res = 0;
   while (source[0] >= '0' && source[0] <= '9') {
       res = res * 10 + (source[0] - '0');
       ++source;
   }
   return res;
}

然而,这并没有那么快。我的第一个优化实际上是通过一个简单的比较来替换

isdigit(c)
(由于
isdigit
的实施,这要快得多)。不幸的是,那也是我最后一次优化。

有些帖子描述了一些小魔术,但它们似乎总是假定固定大小的整数: https://kholdstare.github.io/technical/2020/05/26/faster-integer-parsing.html

对于整数长度未知的情况,是否有任何技巧可以使整数解析更快?

谢谢

c optimization integer
2个回答
0
投票

测试了三种不同的实现:

手动展开比 OP 的循环版本稍快

#define GET1(result, c) do {if((c) >= '0' && (c) <= '9') result += (c) - '0'; else return result;} while(0) ;       \
   result *= 10


uint64_t parse2(const char *source)
{
    uint64_t result = 0;
    GET1(result, source[0 ]);
    GET1(result, source[1 ]);
    GET1(result, source[2 ]);
    GET1(result, source[3 ]);
    GET1(result, source[4 ]);
    GET1(result, source[5 ]);
    GET1(result, source[6 ]);
    GET1(result, source[7 ]);
    GET1(result, source[8 ]);
    GET1(result, source[9 ]);
    GET1(result, source[10]);
    GET1(result, source[11]);
    GET1(result, source[12]);
    GET1(result, source[13]);
    GET1(result, source[14]);
    GET1(result, source[15]);
    GET1(result, source[16]);
    GET1(result, source[17]);
    GET1(result, source[18]);
    GET1(result, source[19]);
    return result;
}


#define GET(result, c)          \
   switch(c)                            \
   {                                    \
        case '0' ... '9':               \
            result += (c) - '0';        \
            break;                      \
        case 0:                         \
        default:                        \
            return result;              \
   }                                    \
   result *= 10;


uint64_t parse1(const char *source)
{
    uint64_t result = 0;
    GET(result, source[0 ]);
    GET(result, source[1 ]);
    GET(result, source[2 ]);
    GET(result, source[3 ]);
    GET(result, source[4 ]);
    GET(result, source[5 ]);
    GET(result, source[6 ]);
    GET(result, source[7 ]);
    GET(result, source[8 ]);
    GET(result, source[9 ]);
    GET(result, source[10]);
    GET(result, source[11]);
    GET(result, source[12]);
    GET(result, source[13]);
    GET(result, source[14]);
    GET(result, source[15]);
    GET(result, source[16]);
    GET(result, source[17]);
    GET(result, source[18]);
    GET(result, source[19]);
    return result;
}

结果(1000000000 次迭代 - 20char 长数字):

OPs parse: 14.26654600 seconds 
parse2   : 13.39631300 seconds 
parse1   : 12.98047100 seconds

0
投票

作为第一步,您可以将

*source
转换为
unsigned char
。减去 '0' 后,您只需要执行一次比较。

如果可以的话,您也可以使用

[[likely]]
影响分支预测(在这种情况下没有任何效果

如果你事先知道字符串的长度,那么一次获取和处理一个以上的字节是可能的。

#include <iostream>
#include <cstdint>

uint64_t parse(const char *source) {
    uint64_t res = 0;
    while(true) {
        unsigned char digit = (unsigned char)(*source++ - '0');
        if (digit > 9) [[unlikely]] {
            break;
        }
        res = res * 10 + digit;
   }
   return res;
}

int main() {
    auto num = parse("1234567890");
    std::cout << num << "\n";    
    return 0;
}

演示 - https://godbolt.org/z/5q15P5611

© www.soinside.com 2019 - 2024. All rights reserved.