如何优化斯特托克+环礁

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 (Xeon系列)

相关主题

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

Answer 1

First off:我发现在信号处理链中优化字符串转换例程大部分时间都是完全徒劳的。系统以字符串形式加载数据的速度(这种情况可能会发生在某些大容量存储中，因为它最初不会选择字符串格式，所以它是由一些不关心性能的东西放置的)，如果您将通过PCIe附加的所有SSD集群的读取速度与atoll的速度进行比较，您会注意到在低效率的转换上损失了微不足道的时间。如果将字符串的部分进行转换，则等待存储的时间甚至不会被转换远远填满，因此即使没有任何算法优化，流水线/多线程也将几乎消除用于转换的所有时间。

我将继续假设包含整数的字符串足够大。数以千万计的整数。否则，考虑到 performance没有什么可抱怨的，所有的优化都可能为时过早。

现在，诀窍是，一旦转换例程的性能达到内存带宽障碍，就无法进行性能优化。为了尽可能地克服这个障碍，优化CPU缓存的使用是至关重要的，因此，尽可能少地进行线性访问和洗牌内存是至关重要的。此外，如果您关心速度，您不希望每次需要转换几位数时调用一个函数--调用开销(保存/还原堆栈，来回跳)将非常重要。因此，如果您追求性能，那么您将立即对整个字符串进行转换，然后只访问生成的整数数组。

因此，在现代的SSE4.2功能的x86处理器上，您可以得到大致类似的东西。

外循环，跳16步：

• 将128位输入字符串加载到128位SIMD寄存器中
• 运行类似于__mm_cmpestri的命令，同时在所有16个字节中查找分隔符和\0终止符的索引。
• 查找索引的内循环
  • 使用SSE复制/移位/即时指令隔离子字符串；用0填充其他子字符串
  • 从前一次迭代中预先保存的“最后字符”(如果有的话--仅适用于每个外循环迭代的第一次内环迭代)
  • 从每一位数字中减去0，再一次使用SSE指令用一条指令(_mm_sub_epi8)执行最多16个减法。
  • 将8个16位子字转换为包含两个64位整数的8个128位字(我认为每16位有一条指令，_mm_cvtepi8_epi64 )
  • 用__mm128初始化一个[10^15 10^14]寄存器，我们称之为powers
  • 循环对双64位字：(每一步应该是一个SSE指令)
    • 先乘powers
    • 用[100 100]划分权力
    • 乘秒与powers
    • 将结果添加到双64位累加器

​

- sum the two values in accumulator
- `store` the result to integer array

​

Answer 2

我宁愿使用类似于std::istringstream的东西

int64_t get_next_int(std::istringstream& line) {
    int64_t token;
    if(!(line >> token))
         exit(0);
    return token;
}


 std::istringstream line(newLine);

 int64_t i = get_next_int(line);

strtok()有着众所周知的drawbacks，您根本不想使用它。

Answer 3

关于

int n= 0;

// Find the token
for ( ; *newline == ' '; newline++)
  ;
if (*newline == 0)
  // Not found
  exit(0);

// Scan and convert the token
for ( ; unsigned(*newline - '0') < 10; newline++)
  n= 10 * n + *newline - '0';
return n;