经验啦

  1. 首页 > 生活百科 > >

系统编程( 三 )

生活百科系统编程


那么，取模运算如何帮助我们从hash表转到存储桶呢？这就要讲到有点无聊但是很神奇的2的乘方了！
首先，让我透露答案：我们将强制所有hash表的大小为2的N次方（幂） 。
我们可以利用这个特性用更快的位运算（bit twiddling）来代替除法运算 。另外，这个特性很容易维护，每当我们需要增加hash表的大小以摊销rehashing的成本时，我们都会将hash表的大小增加一倍，因此随着hash表的增长，它的大小将保持为2的幂 。
现在，我们使用除法运算或者取模运算，将hash值映射到hash表中的bucket索引上 。bucket索引必须严格小于hash表的大?。⑶艺飧鲇成涞纳⒘兄涤Ω檬俏扌蜃刺?。
为了不使用除法运算，我们将使用位掩码（bitmask）来“屏蔽”所有的设置位,除了那些严格小于2的幂的设置位之外 。这种方式可以将所有的entropy保持在最低有效位 ， 就像取模运算一样，但它要快得多 。Agner Fog在相同的英特尔 Skylake体系结构中把这种运算放在1周期延迟的指令列表中 。
作为关于位运算（bit twiddling）和解释如何选择位掩码（bitmask）的一个简单回顾，让我们来看看一些位模式（bit patterns） 。
因为数字是用二进制表示的，所以我们知道每一个2的幂（数值N）只有一个位集 。例如：
Decimal | Binary
2 | 00 00 00 10
8 | 00 00 10 00
32 | 00 10 00 00
128 | 10 00 00 00这意味着所有的N-1的值都比log2（N）的有效位低一位 。例如：
Decimal | Binary
1 | 00 00 00 01
7 | 00 00 01 11
31 | 00 01 11 11
127 | 01 11 11 11因此，为了在HASH % N计算中替代我们的取模运算符，我们使用“按位和（bitwise AND）”运算来计算HASH &(N-1)的值 。这将只保留比我们的log_2(N)位低的设置位，将任何HASH值映射到一个[0 ， N]之间的数字 。如果需要，我们甚至可以缓存这个位掩码，这样以后就不必重新计算它了 。
为了展示使用“位掩码”技巧比使用普通的取模运算的速度要快，我编写了一个小基准测试来比较执行一百万次取模运算和一百万次“位掩码”运算的结果 。
Executing tests from //examples:power-of-two
-----------------------------------------------------------------------------
2019-08-13 02:24:03
Run on (4 X 2800 MHz CPU s)
CPU Caches:
L1 Data 32K (x2)
L1 Instruction 32K (x2)
L2 Unified 262K (x2)
L3 Unified 4194K (x1)
--------------------------------------------------------
Benchmark Time CPU Iterations
--------------------------------------------------------
BM_Mod 9261 us 9234 us 75
BM_BitMask 325 us 324 us 1984从上面的测试结果我们可以看到，使用取模操作符执行DIV指令要比使用“位掩码”大约慢28倍 ， 这个结果接近Agner Fog的慢35倍的预测值 。
因为这个技巧很容易做到，并且提供了一个很好的例子 ， 它已经被许多高性能的hash表使用，比如abseil Swiss Tables的flat_hash_set和flat_hash_map，以及ConcurrencyKit’s ck_ht_map 。
寻址空间高位(Top Bit)用途的调整
通常情况下，你想在一个指针上存储一两个额外的信息 。事实上，这种做法非常常见，以至于维基百科有一篇专门关于它的文章 。实现这一点的一种方法是利用许多64位系统（如Linux）上的虚拟内存地址空间只有48位的这个特性，尽管我们使用8个字节来存储它们 。
这意味着 ， 我们可以把任何我们想要的旧东西放在前16位，当我们真正不想引用它时，就可以屏蔽掉它 。下面是一些使用指针的高位(top bit)来存储底层数据是否“脏了”的C++代码示例 。
constexpr uintptr_t kDirtyBit = 0x8000000000000000;
constexpr uintptr_t kPtrMask = 0x7fffffffffffffff;

相关经验推荐


上一篇：葡萄苗6月份能栽活吗视频 葡萄苗6月份能栽活吗

下一篇：分公司需要营业执照吗