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

Question

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

atoi(mystring.c_str())

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

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

原文由 user788171 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

我对此处给出的不同功能 + 一些附加功能进行了快速基准测试，默认情况下我将它们转换为 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 发布，翻译遵循 CC BY-SA 4.0 许可协议