一亿行挑战(1BRC)top代码精析-使用 SWAR 技术找到分号分隔符

网上对这段代码相关内容介绍非常少,给出下知识背景:

输入文本格式:

Hamburg;12.0
Bulawayo;8.9
Palembang;38.8
St. John's;15.2
Cracow;12.6
Bridgetown;26.9
Istanbul;6.2
Roseau;34.4
Conakry;31.2
Istanbul;23.0

前面是气象站名称,后面是温度(注意是华氏度)

这里关注一个优化点,如何最高效的分离出;所在的位置。

基本思想:

1. 根据mmap,从文本中一次读取一个64位的数据(通过unsafe),按照long类型读出来

2. 从long类型的数据中确定是否存在;

第二步精析:

1. long SEMICOLON_PATTERN = 0X3BL; // ;的accic码

2. 假设读取到的long类型的数据为0x3B00000000000000L

3. long match = i ^ SEMICOLON_PATTERN

4. 异或的结果是如果存在分号,则必然在某一段字节不为0。如果不存在分号,则全部的字节必然全部不为0.按照示例step2中为例,则前两个字节必然为0.

5. 问题划归到如何判断patternMatch中是否有字段为0的问题

该问题解析为:

long mask = ((match - 0x0101010101010101L) & ~match) & 0x8080808080808080L;

如果mask !=0 ,则必然其中包含分号。如果=0,则不包含。原因如下:

1. 先解析第一步match - 0x0101010101010101L 。按照字节进行划分match的段,共有8段。每段减去1.这样得到的结果中,8段中如果有任何一段从左数第一个bit为1的情况有如下两种:

a. 本身match的这段就是00.这样-1以后是负值,负值的第一位bit为1,满足条件

b. 本身match的这段值为>=128,也就是0xff.此时-1的话,第一位bit为1.这种原因是因为本身确实够减1,match本身的值第一位bit就是1导致的。满足条件

c.其他情况下match的值必然>=1.因此-1后是一个正值,第一位bit位0,不会满足条件

2. 解析第二步&~match

先分别对step1中的a,b两种情况进行讨论

a. 情况 本身match的这段就是00.~match 这段是ff。这样(match - 0x0101010101010101L)&~match后,结果该字段就是一个负值和ff做与运算,因此结果是首bit为1.

b.情况 本身match这段第一位bit值为1,取反后为0.(match - 0x0101010101010101L)对应的段是首bit为1的。但是因为~match对应的首bit为0, 进行&后,正好结果就是首bit为0

c.情况。其他情况下,~match的第一个bit位必然为1,而(match - 0x0101010101010101L)的结果根据解析的第一步说明它第一个bit值为0.因此& ~match后第一个bit值必然为0

3. 综上所述,((match - 0x0101010101010101L) & ~match)在分割成的8段字节中,如果有字节为分号,则结果一定从左数第一个bit值为1.如果没有,则该字节从左数第一个bit值为0.

4. & 0x8080808080808080L

        根据第3步的解析,则很自然的。得到每个字节的从左数第一个bit值,如果!=0,说明是存在分号的。等于0,说明是不存在分号的。

扩展问题:

1. 如何获取是第几位是分号:

final int index = Long.numberOfTrailingZeros(mask) >> 3;

其实就是看第几段是非0的值。采用numberOfTrailingZeros获取最右边0的个数,因为一个字节是8个0.因此直接/8,就得到该long型对应的8字节文本快,从右数第几个字节是分号了。

2. 大家思考下能否继续优化呢?

其实是可以的,因为accic字符集的范围是0-127.不存在大于127的情况。因此我们可以修改以上代码为:

long mask = (match - 0x0101010101010101L) & 0x8080808080808080L;

也就是本身match的这段值为>=128这种情况可忽略。

参考网站:SWAR 的理解 | Waaagh!

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-03-25 01:06:06       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-03-25 01:06:06       101 阅读
  3. 在Django里面运行非项目文件

    2024-03-25 01:06:06       82 阅读
  4. Python语言-面向对象

    2024-03-25 01:06:06       91 阅读

热门阅读

  1. 微信小程序图片资源优化实践

    2024-03-25 01:06:06       39 阅读
  2. conda删除虚拟环境

    2024-03-25 01:06:06       38 阅读
  3. 什么是高防服务器?

    2024-03-25 01:06:06       41 阅读
  4. duckdb学习-1

    2024-03-25 01:06:06       38 阅读
  5. 清华镜像介绍

    2024-03-25 01:06:06       47 阅读
  6. 计算机网络(特南鲍姆版) 期末总结

    2024-03-25 01:06:06       41 阅读
  7. 模拟电子技术实验(五)

    2024-03-25 01:06:06       38 阅读
  8. Ubuntu 未能识别较新型号 Nvidia 显卡案例分析

    2024-03-25 01:06:06       41 阅读