我正在尝试将解析字符串优化为 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
对于整数长度未知的情况,是否有任何技巧可以使整数解析更快?
谢谢
测试了三种不同的实现:
手动展开比 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
作为第一步,您可以将
*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;
}