深入探究immutable.js的实现机制(二)

上一篇我们研究了 Immutable.js 持久化数据结构的基本实现原理,对其核心数据结构Vector Trie进行了介绍,并着重探究了其中的位分区机制。采用位分区的根本原因是为了优化速度,而对于空间的优化, Immutable.js 是怎么做的呢?接下来先探讨下这点。

HAMT

HAMT全称hash array mapped trie,其基本原理与上篇所说的Vector Trie非常相似,不过它会对树进行压缩,以节约一些空间。 Immutable.js 参考了HAMT对树进行了高度和节点内部的压缩。

树高压缩

假设我们有一个 2 叉 Vector Trie,现在存了一个值,key为110,它会被存到0 1 1这条路径下,如下图:

显然,这图里展示的结构已经进行了最简单的优化,因为现在只存了一个值,所以把与110无关的节点去掉了。还能进行什么优化吗?我们发现,中间那两个节点也是可以去掉的,如下图:

获取该值时,我们先从0找下来,发现这直接是一个根节点,那取它存储的值就行了。就是说在不产生混淆的情况下,我们可以用尽可能少的二进制位去标识这个 key 。这样我们就进行了高度上的压缩,既减少了空间,又减少了查找和修改的时间。
如果要添加一个值,它的 key 结尾也是0,该怎么做呢?很简单,如下图:

我们只要在需要的时候增加或减少节点即可。

节点内部压缩-Bitmap

上一篇我们提到, Immutable.js 的 Trie 里,每个节点数组的长度是 32 ,然而在很多情况下,这 32 个位置大部分是用不到的,这么大的数组显然也占用了很大空间。使用Bitmap,我们就可以对数组进行压缩。
我们先拿长度为 8 的数组举例:

我们实际上只是用了数组的下标对 key 进行索引,这样想数组第 5、6、7 位显然目前是毫无作用的,那 0、2、3 呢?我们有必要为了一个下标 4 去维持一个长度为5的数组吗?我们只需要指明“假想数组”中下标为 1 和为 4 的位置有数就可以了。这里就可以用到bitmap,如下:

我们采用了一个数,以其二进制形式表达“假想的长度为8的数组”中的占位情况,1 表示数组里相应下标位置有值,0 则表示相应位置为空。比如这个二进制数第 4 位(从右往左,从 0 开始数)现在是 1 ,就表示数组下标为 4 的位置有值。这样原本的长度为 8 的数组就可以压缩到 2 。
注意这个数组中的元素还是按照“假想数组”中的顺序排列的,这样我们若要取“假想数组”中下标为 i 的元素时,首先是判断该位置有没有值,若有,下一步就是得到在它之前有几个元素,即在二进制数里第 i 位之前有多少位为 1 ,假设数量为 a ,那么该元素在当前压缩后的数组里下标就是 a 。
具体操作中,我们可以通过bitmap & (1 << i - 1),得到一个二进制数,该二进制数中只有第 i 位之前有值的地方为 1 ,其余全为 0 ,下面我们只需统计该二进制数里 1 的数量即可得到下标。计算二进制数中 1 数量的过程被称作popcount,具体算法有很多,我了解不多就不展开了,前面点击后是维基的地址,感兴趣的可以研究下。
下面我们看一下这部分的源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
get(shift, keyHash, key, notSetValue) {
if (keyHash === undefined) {
keyHash = hash(key);
}
const bit = 1 << ((shift === 0 ? keyHash : keyHash >>> shift) & MASK);
const bitmap = this.bitmap;
return (bitmap & bit) === 0
? notSetValue
: this.nodes[popCount(bitmap & (bit - 1))].get(
shift + SHIFT,
keyHash,
key,
notSetValue
);
}

可见它与我们上一篇看到的源码并没有太大不同(Immutable.js 里如果一个数组占用不超过一半( 16 个),就会对其进行压缩,上一篇的源码就是没有压缩下的情况),就是多了一个用 bitmap 计算数组下标的过程,方式也跟上文所讲的一样,对于这个popCount方法,我把源码也贴出来:
1
2
3
4
5
6
7
8
function popCount(x) {
x -= (x >> 1) & 0x55555555;
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0f0f0f0f;
x += x >> 8;
x += x >> 16;
return x & 0x7f;
}

为什么是32

上一篇我们提到了 Immutable.js 的 Vector Trie 采用了 32 作为数组的长度,也解释了由于采用了位分区,该数字只能是2的整数次幂,所以不能是 31、33 等。但8、16、64等等呢?这是通过实际测试得出的,见下图:

图中分别是查找和更新的时间,看上去似乎 8 或 16 更好?考虑到平时的使用中,查找比更新频次高很多,所以 Immutable.js 选择了 32。

回顾

现在,我们就能理解第一篇文章开头的截图了:


我们可以看到, map 里主要有三种类型的节点:

  • HashArrayMapNode,拥有的子节点数量 >16 ,拥有的数组长度为 32
  • BitmapIndexedNode,拥有的子节点数量 ≤16 ,拥有的数组长度与子节点数量一致,经由 bitmap 压缩
  • ValueNode,叶子节点,存储 key 和 value

此外,每个节点似乎都有个ownerID属性,这又是做什么的呢?它涉及到 Immutable.js 中的可变数据结构。

Transient

其实可以说 Immutable.js 中的数据结构有两种形态,“不可变”和“可变”。虽然“不可变”是 Immutable.js 的主要优势,但“可变”形态下的操作当然效率更高。有时对于某一系列操作,我们只需要得到这组操作结束后的状态,若中间的每一个操作都用不可变数据结构去实现显然有些多余。这种情景下,我们就可以使用withMutations方法对相应数据结构进行临时的“可变”操作,最后再返回一个不可变的结构,这就是Transient,比如这样:

1
2
3
4
5
6
7
8
let map = new Immutable.Map({});
map = map.withMutations((m) => {
// 开启Transient
m.set('a', 1); // 我们可以直接在m上进行修改,不需要 m = m.set('a', 1)
m.set('b', 2);
m.set('c', 3);
});
// Transient结束

实际上, Immutable.js 里很多方法都使用了withMutations构造临时的可变数据结构来提高效率,比如 Map 中的mapdeleteAll方法以及 Map 的构造函数。而在一个不可变数据结构中实现临时的可变数据结构的关键(有点拗口XD),就是这个ownerID。下图对比了使用与不使用Transient时的区别:

显然,使用Transient后由于无需每次生成新的节点,效率会提高空间占用会减少。在开启Transient时,根节点会被赋与一个新的ownerID,在Transient完成前的每一步操作只需遵循下面的逻辑即可:

  1. 若要操作的节点的ownerID与父节点的不一致,则生成新的节点,把旧节点上的值拷贝过来,其ownerID更新为父节点的ownerID,然后进行相应操作;
  2. 若要操作的节点的ownerID与父节点的一致,则直接在该节点上操作;
    下面先我们看下 Immutable.js 中开启Transient的相关源码:
    1
    function OwnerID() {}
    1
    2
    3
    function asMutable() {
    return this.__ownerID ? this : this.__ensureOwner(new OwnerID());
    }
    1
    2
    3
    4
    5
    function withMutations(fn) {
    const mutable = this.asMutable();
    fn(mutable);
    return mutable.wasAltered() ? mutable.__ensureOwner(this.__ownerID) : this;
    }
    它给了根节点一个ownerID,这个ownerID会在接下来的操作中按照上面的逻辑使用。这段代码有个“骚操作”,就是用 JS 的对象地址去作为 ID ,因为每次 new 之后的对象的地址肯定与之前的对象不同,所以用这种方法可以很简便高效地构造一套 ID 体系。
    下面再看下开启后进行操作时的一段源码( Map 中的set操作就会调用这个update方法):
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    update(ownerID, shift, keyHash, key, value, didChangeSize, didAlter) {
    // ...省略前面的代码
    const isEditable = ownerID && ownerID === this.ownerID;
    const newNodes = setAt(nodes, idx, newNode, isEditable);

    if (isEditable) {
    this.count = newCount;
    this.nodes = newNodes;
    return this;
    }

    return new HashArrayMapNode(ownerID, newCount, newNodes);
    }
    与前面讲的逻辑一样,先比较该节点ownerID与传进来父节点的是否一致,然后直接在节点上操作或生成新的节点。

hash冲突

这块的内容就没什么新东西了,任何语言或库里对于 hashMap 的实现都需考虑到 hash 冲突的问题。我们主要看一下 Immutable.js 是怎么处理的。
要上一篇我们知道了,在往 Map 里存一对 key、value 时, Immutable.js 会先对 key 进行 hash ,根据 hash 后的值存到树的相应位置里。不同的 key 被 hash 后的结果是可能相同的,即便概率应当很小。
hash 冲突是一个很基本的问题,解决方法有很多,这里最简单适用的方法就是把冲突的节点扩展成一个线性结构,即数组,数组里直接存一组组 key 和 value ,查找到此处时则遍历该数组找到匹配的 key 。虽然这里的时间复杂度会变成线性的,但考虑到发生 hash 冲突的概率很低,所以时间复杂度的增加可以忽略不计。
我发现 Immutable.js 的 hash 函数对abcbCc的 hash 结果都是 96354,在同一个 map 里用这两个 key 就会造成 hash 冲突,我们把这个 map log 出来如下:

Immutable.js 用了一个叫做HashCollisionNode的节点去处理发生冲突的键值,它们被放在entries数组里。
大家也可以自己试试,代码如下:

1
2
3
4
5
6
7
8
9
10
let map = new Immutable.Map({});

for (let i = 0; i < 10; i++) {
map = map.set(Math.random(), i); // 随便塞一点别的数据
}

map = map.set('abc', 'value1');
map = map.set('bCc', 'value2');

console.log(map)

参考:

https://hypirion.com/musings/understanding-persistent-vector-pt-1
https://io-meter.com/2016/11/06/functional-go-intro-to-hamt
https://cdn.oreillystatic.com/en/assets/1/event/259/Immutable%20data%20structures%20for%20functional%20JavaScript%20Presentation.pdf
https://infoscience.epfl.ch/record/169879/files/RMTrees.pdf
http://lampwww.epfl.ch/papers/idealhashtrees.pdf
https://github.com/funfish/blog
https://github.com/facebook/immutable-js/blob/e65e5af806ea23a32ccf8f56c6fabf39605bac80/src