c++ - 如何优化strtok + atoll

Question

在执行时间上有什么好的方法可以优化这个函数吗？我的最终目标是解析一个由几个整数组成的长字符串(每行几千个整数，上千行)。这是我最初的解决方案。

int64_t get_next_int(char *newLine) {
    char *token=strtok(newLine, " ");
    if( token == NULL ) {
        exit(0);
    }
    return atoll(token);
}

更多细节:我需要基于“状态”的 strtok 实现，因此 strtok 实现的填充应该存在于最终字符串中。环礁不需要任何类型的验证。

目标系统:Intel x86_64(至强系列)

相关主题:

• atoi 优化:C++ most efficient way to convert string to int (faster than atoi)

Answer 1

首先:我发现在大多数情况下优化信号处理链中的字符串转换例程完全是徒劳的。您的系统以字符串形式加载数据的速度(这可能会发生在一些大容量存储中，它是由不关心性能的东西放置的，因为它首先不会选择字符串格式，否则)，并且如果您将通过 PCIe 连接的 SSD 集群以外的所有读取速度与 atoll 的读取速度进行比较，您会发现您在低效转换上损失的时间可以忽略不计。如果通过转换流水线加载该字符串的部分内容，等待存储所花费的时间甚至不会被转换远程填满，因此即使没有任何算法优化，流水线/多线程也将消除几乎所有花在转换上的时间。

我将继续并假设您的包含整数的字符串足够大。就像，数千万个整数。否则，考虑到没有什么可提示的 std::iostream performance，所有的优化都可能还为时过早。 .

现在，诀窍是一旦转换例程的性能达到内存带宽障碍，就无法进行任何性能优化。为了尽可能地突破这一障碍，优化 CPU 缓存的使用至关重要——因此，尽可能少地进行线性访问和混洗内存在这里至关重要。此外，如果您关心速度，则不希望每次需要转换几位数字时都调用一个函数——调用开销(保存/恢复堆栈、来回跳转)将是显着的。因此，如果您追求性能，您将立即转换整个字符串，然后访问生成的整数数组。

因此，在现代的、支持 SSE4.2 的 x86 处理器上，您将拥有大致类似的东西

外层循环，16步跳转:

• 将 128 位输入字符串加载到 128 位 SIMD 寄存器
• 运行类似于__mm_cmpestri的程序一次在所有这 16 个字节中查找 分隔符和 \0 终止符的索引
• 对找到的索引进行内部循环
  • 使用 SSE copy/shift/immediate 指令隔 ionic 串；用0
  填充其他的
  • 预先保存上一次迭代的“最后一个字符”(如果有的话——应该只适用于每次外循环迭代的第一次内循环迭代)
  • 从每个数字中减去 0，再次使用 SSE 指令通过一条指令 ( _mm_sub_epi8 ) 执行最多 16 次减法
  • 将八个 16 位子字转换为八个 128 位字，每个字包含两个打包的 64 位整数(我认为每 16 位一条指令，_mm_cvtepi8_epi64)
  • 用[10^15 10^14]初始化一个__mm128寄存器，我们称它为powers
  • 循环对双 64 位字:(每一步应该是一个 SSE 指令)
    • 先乘以幂
    • 按[100 100]划分权力
    • 将秒乘以幂
    • 将结果添加到双 64 位累加器
  • 将累加器中的两个值相加
  • 将结果存储到整数数组