C语言 尽可能快地解析整数

xkrw2x1b  于 2023-03-01  发布在  其他
关注(0)|答案(3)|浏览(115)

我试图在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
有什么技巧可以让整数解析在整数长度未知的情况下也更快吗?
谢谢

hpcdzsge

hpcdzsge1#

测试了三种不同的实现:
手动展开比OP的循环版本稍快。

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

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)          \
      result *= 10;switch(c)                            \
   {                                    \
        case '0' ... '9':               \
            result += (c) - '0';        \
            break;                      \
        case 0:                         \
        default:                        \
            return result;              \
   }                                    

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次迭代-20个字符长的数字):

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

l7wslrjt2#

第一步,可以将*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

mzillmmw

mzillmmw3#

下面是OP函数的一个小小的改进。它不需要源代码至少是20字节,不像展开的版本。

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>

// gcc intparse.c -o intparse.bin -O3

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;
}

uint64_t myparse(const unsigned char *source)
{
   uint64_t res = 0;
   unsigned char digit = *source - 48;
   while (digit < 10) {
       res = res * 10 + digit;
       ++source;
       digit = *source - 48;
   }
   return res;
}


uint64_t  get_cycles () {
  uint32_t lo,hi;
  asm  volatile("rdtsc":"=a"(lo),"=d"(hi));
  return  (( uint64_t)hi<<32 | lo);
}

int main(int argc, char *argv[]) {
    char*needle_in_string;    
    uint64_t cycleno1, cycleno2, reslong;
    cycleno1 = get_cycles ();
    reslong = myparse(argv[1]);
    cycleno2 = get_cycles ();
    printf("%lu (%li cycles)\n", reslong, cycleno2 - cycleno1);
    cycleno1 = get_cycles ();
    reslong = parse(argv[1]);
    cycleno2 = get_cycles ();
    printf("%lu (%li cycles)\n", reslong, cycleno2 - cycleno1);
}

我有结果了...

1234567890123456789 (280 cycles)
1234567890123456789 (552 cycles)

以及

55 (120 cycles)
55 (400 cycles)

相关问题