1. 原文

Optimizing hash tables: hiding the hash code

2. 摘要翻译

ECMAScript 2015引入了几种新的数据结构，如：Map、Set、WeakSet、WeakMap，它们的底层实现都是hash table。本文会详细介绍通过最近的几项性能优化在V8 v6.3+里是如何存储hash table的key的。

Hash code

一个hash function是用来将一个key映射到hash table中某个位置上的。而_hash code_则是hash function根据某个key运算后得到的结果。

在V8中，hash code是一个随机数字（random number），与object value无关。因此，我们无法重新计算它，就意味着一定要存储它。

因为在JS中，对象是可以作为key来使用的。因此之前是将hash code作为一个private symbol存储在key对象里的。private symbol在V8里类似Symbol，除了几点：它不可被枚举，也不会被暴露到JS的用户空间内。

function GetObjectHash(key) {
  const hash = key[hashCodeSymbol];
  if (IS_UNDEFINED(hash)) {
    hash = (MathRandom() * 0x40000000) | 0;
    if (hash === 0) hash = 1;
    key[hashCodeSymbol] = hash;
  }
  return hash;
}

这种方案工作得很好，因为在对象被加到hash table之前我们不需要为hash code字段预留内存。直到加入到hash table的时间点，private symbol才会被存储到对象内。

V8可以优化hash code symbol查找，通过使用和其他属性查找相同的IC System方案来提供非常快的hash code查找。这套方案在monomorphic IC查找上工作的很好，前提条件是当所有的key都拥有相同的hidden class。然而真实世界的JS代码一般不按这套方式编写，且key经常都拥有不同的hidden class导致如果使用monomorphic IC查找来查找hash code会非常慢。

使用private symbol方案的另一个问题是它导致存储hash code的对象发生了hidden class transition。这导致了低效的多态代码，不单单只是反应在hash code查找上，还反应在key对象的其他属性查找上，而且还导致了优化代码的deoptimization。

JavaScript object backing stores

每个JS对象（JSObject）在V8中除了头部之外还使用了两个word，一个用来存储指向elements backing store的指针，另一个用来存储指向properties backing store的指针。

elements backing store用来存储类似array indices的属性，而backing store则是存储key是字符串和symbol的属性。查看这篇博客来进一步了解backing stores。

const x = {};
x[1] = 'bar';      // ← stored in elements
x['foo'] = 'bar';  // ← stored in properties

Hiding the hash code

最简单存储hash code的解决方案就是再在JS对象上拓展一个word的空间，将hash code直接存储在对象里。然而这样做会导致那些未被加入hash table的对象里的内存空间被浪费。作为替代方案，我们尝试将hash code存储在elements store或properties store内。

elements backing store是一个包含了长度和所有elements的数组。在这里我们没有什么能做的，因为将hash code存储在reserved slot（类似the 0th index）仍旧会在未将对象作为hash table的key使用的时候浪费内存。

因此我们将视线转到properties backing store。properties backing store的数据结构有两种：数组和字典。

不像elements backing store使用的数组没有长度限制（upper limit），properties backing store中的数组有1022个值的长度限制（upper limit）。V8将长度超限的情况转而使用字典，为了性能考虑。（这里我稍微简化了下 —— 在其他某些场景下V8也是可以使用字典的）

因此，properties backing store有三种可能的状态：

• 空（没有属性）
• 数组（最多可以存储1022个值）
• 字典

The properties backing store is empty

当空的情况，我们可以直接把hash code存储在JS对象的这个offset里：

The properties backing store is an array

在32位机器上，V8中的整型是长度小于2³¹的unboxed数字，这被称为Smi。在一个Smi中，最小的一位（the least significant bit）是用来区分和指针之间差异的tag，其他的31位（31 bits）用来存储整型的值。

通常情况下，数组将它们的长度存储成Smi。因为我们知道这里的数组的容量上限是1022，我们只需要10位（10 bits）来存储这个长度。我们就可以使用剩下的21位（21 bits）来存储hash code！

The properties backing store is a dictionary

字典的情况，我们为存储hash code增加了字典一个word的长度，在字典的开头专门辟出了一个slot专门用来存储hash code。这种解决方案默认会浪费一个word长度的内存空间，因为按比例来看这个尺寸的空间增长的影响并不像内存的情况那样大。

使用这些解决方案之后，hash code的查找就不再需要通过复杂的JS对象属性查找机制了。

Performance improvements

通过SixSpeed benchmark跟踪的Map和Set性能变化反应性能提升了大约500%（a ~500% improvement）。

这项改进也提升了基准benchmark ARES6的性能5%（a 5% improvement）。

在使用Emberperf benchmark套件中的一个benchmark测试Ember.js的时候也反馈了18%的性能提升（an 18% improvement）。

3. 注

翻译Smi的时候查看上文提到的链接中的内容辅助理解了下，这里放一下链接里的原文，方便以后查看：

来源：value representation in javascript implementations

引用：

Google’s V8 JavaScript engine still does it this way. This yields 31-bit immediate signed integers; you can just do a signed right-shift to get the value. They call them “smi” values, for “small integers”; they are more commonly called “fixnums”. There are other fun tricks you can do to avoid shifts for some common operations, like addition. Note that they also take advantage of the four-byte alignment (in their case) to encode another immediate value, “failure objects”, using the other low bit.

The size of a tagged pointer is the size of a pointer, so 32 bits on a 32-bit machine, and 64 on a 64-bit machine. V8 doesn’t actually use 63-bit smi values on 64-bit machines, AFAIK.

EOF