bbbGan

iguana性能优化

2023/08/03 C++ 位运算 共 2657 字，约 8 分钟

前言

iguana对XML的第一版解析依靠 rapidxml 。后面开发移除对rapidxml的依赖时，最初版本的代码性能比较平庸，大概落后rapidxml一倍，经过了一系列的优化之后性能提升了不少，最终解析速度比rapidxml快了一倍，这篇文章简单分享一下提升解析性能的方法。

加速判断

首先XML的结构有类似 < >value < >， 在解析XML中，需要经常跳过一些字符，直到遇到某个字符，常规的写法如下：

template <typename It, char C>
void skip_till(It &&it, It &&end) {
    while (it != end && it != C) {
        ++it;
    }
}

上面的字符串按位比较，直到找到了想要的字符 C。如果需要跳过到 ` <，可以实例化模板： skip_till<’<’>(it, end);`

现代的CPU一般都是64位，也就是8个char的长度，如果每次可以比较8个字符，这样速度无疑会提升不少。

以 < 举例如何判断更快。<的ASCII码是60，二进制为 00111100；要一次性比较8个字符，就需要把8个字符连在一起当作一个uint64类型的数字 chunk 。把 chunk和8个 <的ASCII码进行异或操作，如果出现了某个字节为0，说明出现了字符 <；

inline constexpr auto has_smaller = [](uint64_t chunk) IGUANA__INLINE_LAMBDA {
  return has_zero(
      chunk ^
      0b0011110000111100001111000011110000111100001111000011110000111100);
};

找目标字符的任务就转换成了在 uint64 类型的数字中找到为0的字节。如果有多个为0的字节，只需要找到第一个即可。

判断一个字节是否全为0，可以想到的是加上0xFF，因为除非是0，否则任何数字加上 0xFF 都会产生进位。有以下式子：

 ((c + 0xFF) & ~ c) & 0x80

结论：只有在c为0的情况下，结果为 0x80，否则结果为 0x00

可以使用反推的方法：

  • 要求结果是 0x80，则 ` ((c + 0xFF) & ~ c)的最高位必须是 1，即大于等于 0x80`。
  • ` ((c + 0xFF) & ~ c)最高位是 1，又因为 & ~ c ，则 c的最高位必须是 0，且 (c + 0xFF)`最高位为 1
  • (c + 0xFF)最高位为 1 并且 c 最高位为0，除非 c 是0，否则任何 小于 0x80的数字加上 0xFF，该字节最高位必为0。

上面是判断一个字节，当多个字节的时候情况略微不同，因为需要考虑到低字节产生的进位，因此应该加上0xFE而不是0xFF，而最低位不会有进位，因此依然是0xFF。因此多字节判断的式子如下：

(((chunk + 0xFEFEFEFEFEFEFEFF) & ~chunk) & 0x8080808080808080);

如果低位不产生进位，而chunk的该字节是0x01，0x01 + 0xFE = 0xFF。这种情况下会出现该字节不是0，但是在最终结果中，该字节是 0x80的情况。

但是这种情况并不会影响我们找到第一个该字符出现的位置。因为这种情况是前面的字节为0，从而没有产生进位。前面的第一个为0的字节位置是准确的！

has_zero 最终的代码如下，0xFEFEFEFEFEFEFEFF 和 -0x0101010101010101是一样的。

inline constexpr auto has_zero = [](uint64_t chunk) IGUANA__INLINE_LAMBDA {
  return (((chunk - 0x0101010101010101) & ~chunk) & 0x8080808080808080);
}

当没有目标字符比如 <的时候，结果全为0。当结果不为0，说明这8个字符中出现了目标字符，并且应该找第一个出现的，即最右边是 0x80 的字节。

下面是最终的代码，每次8个字符进行批量判断，当不足8个字符的时候，逐字符判断。

template <typename It> IGUANA_INLINE void skip_till(It &&it, It &&end) {
  if (std::distance(it, end) >= 7) {
      const auto end_m7 = end - 7;
      for (; it < end_m7; it += 8) {
        const auto chunk = *reinterpret_cast<const uint64_t *>(&*it);
        uint64_t test = has_greater(chunk);
        if (test != 0) {
          it += (countr_zero(test) >> 3);
          return;
        }
      }
    }

  while (it < end) {
    if (*it == '<')
      return;
    ++it;
  }
}

其中 has_greater返回的是 0 或者有字节为 0x80的数字。由于需要找到最右边字节为 0x80 的位置，式 countr_zero(test) >> 3，其中 countr_zero 返回最右边的 0 的个数，再除 8，即可得到该字节的位置。

顺序解析

在最初的解析过程中，将所有字段的名称和指针信息存放在哈希表中。每次匹配到一个键（key）时，都会通过哈希表查找相应的指针。然而，在结构体的定义中，字段通常是按顺序定义的，这为我们提供了顺序解析的可能性。因此，我们可以首先尝试进行顺序解析，而不是在哈希表中查找。只有当顺序解析失败时，我们才会转而去哈希表中查找，以实现解析。

这种优化方式充分利用了结构体字段定义的顺序性，从而避免了不必要的哈希表查找，提高了解析效率。

结论

相比于逐字节判断，通过一次判断8个字节可以显著提高处理速度。但是也会出现限制，前面的所有假设是基于小端的情况下，如果是大端的情况下，似乎可以从找最右边的0x80转换成找最左边的0x80来得到大端情况下的解决方案，但是上文说到的不产生进位的特殊情况下，只有找最右边的 0x80是没有问题的，找最左边是有问题的，会误判0x01是目标字符，这意味着会误判和目标字符取反再异或的结果是 0x01，即和目标字符相差 +1或者 -1的字符。

虽然顺序解析带来了性能上的优势，但也会导致代码膨胀的问题。但为了高性能是可以接受的！

Search

    Table of Contents