1BRC 中的那些比特位魔法

如果不熟悉各种位运算可以先去看看 reference 1，找找感觉。

我准备了一个 Java 版本的仓库，不过跳过了好几段没有去实现，c 语言看着费劲的话可以看这个，虽然不全。

还是老样子以排名第一的代码为例。

nextNewLine

简单的说这个方法就是利用了 “Determine if a word has a byte equal to n” 的技巧，无非这里的 n 换成了 (byte) '\n'， 也就是我仓库里的 DetermineByteInWord#hasX，核心就是利用 a ^ a = 0 这个特性，先把数据对齐，然后进行 ^，这样如果 word 中包含 n，则对应的 8 位会全部置为0，再利用 DetermineByteInWord#hasZero/hasZero_V2 达到判断 word 中是否包含 n 的目的。

/**
* copy from CalculateAverage_thomaswue#nextNewLine
* 找到下一行的末尾，并返回地址
*  @param prev 是起始地址（文件/数据块/数据块的碎片等）
*  @return 行尾的地址   
*/
private static long nextNewLine(long prev) {
        while (true) {
            // 根据地址从内存中取出 64 位数据。
            long currentWord = Scanner.UNSAFE.getLong(prev);

            // 0x0A0A0A0A0A0A0A0A = 0000 1010 重复并填满 64 位
			      // 这个 0000 1010 = 0x0A = 10，就是 '\n' or 换行符的 ASCII 码

            // 这里隐藏了一个将 byte 对齐的技巧：0x0A0A0A0A0A0A0A0A = (int)'\n' * 0x0101010101010101L;
            // 也就是前文说的，先把数据对齐，然后 ^
            long input = currentWord ^ 0x0A0A0A0A0A0A0A0AL;

            // ^ 完后检查是否有 8bits 0，如果有，那说明 word 中包含 '\n'
            long pos = (input - 0x0101010101010101L) & ~input & 0x8080808080808080L;
            // 如果 pos != 0，说明在这 64 位数据中找到了 '\n'
            if (pos != 0) {// 计算 '\n' 的内存地址并中断循环

                // 一个内存地址对应 8 bits 的内存空间
				        // 如果是 Big Endian，那下一行行尾的内存地址是:
                //  prev = prev + (64 - numberOfTrailingZeros) / 8
                // 如果是 Little Endian，那就是:
                // prev = prev + numberOfTrailingZeros / 8
                // >>> 3 其实就是 / 8
                prev += Long.numberOfTrailingZeros(pos) >>> 3;
                break;
            }
            else {// pos == 0 说明在前 64 bits 中没找到
              // 那么移动 64 bits 继续搜索
				      // 下一个 64 bits 的起始地址就是原地址加 8
              // nextAddress = prevAddress + 64/8
                prev += 8;
            }
        }
        return prev;
    }

• Big/Little Endian

  略微补充说明一下 Big/Little Endian，中文里经常叫大小端。

  Big Endian stores the most significant byte at the smallest memory address.

  most significant byte 要眼熟一下，他叫最高有效位，你可以简单的理解为有效且最高的 8位，缩写为 MSB。

  Little Endian stores the least significant byte at the smallest memory address.

  least significant byte 就是有效且最低的 8 位，LSB。

  要注意随着场景变化，字节顺序(byte order)是会发生改变的，比如大部分机器（depends on cpu）都默认 Little Endian，但是网络传输通常默认 Big Endian。

  具体到 Java 中，ByteBuffer 默认 Big Endian，比如 MappedByteBuffer，但如果使用 UNSAFE，那就用的是 Native Order，通常是 Little Endian。

  详细的示例代码可以参考前面仓库里的EndianDemo，包括大小端检查、如何判断大小端、大小端时读取到的数据有什么区别、大小端时计算地址的验证等等。

findDelimiter

找分号其实也是 find n in word，只不过直接返回 pos， 因为涉及到 name，它把后续处理延迟到了 findResult 中。

(int)';' = 59 = 0x3B

  private static long findDelimiter(long word) {
      // 0x3B3B3B3B3B3B3B3BL = 0x3B * 0x0101010101010101L
      long input = word ^ 0x3B3B3B3B3B3B3B3BL;
      return (input - 0x0101010101010101L) & ~input & 0x8080808080808080L;
  }

温度相关计算

建议直接看作者的版本，CalculateAverage_merykitty。

搜索 parseDataPoint 方法，注释很详细。

referenece

• Bit Twiddling Hacks