前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >深入探究immutable.js的实现机制(二)

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

作者头像
秋风的笔记
发布2020-10-27 11:39:17
1K0
发布2020-10-27 11:39:17
举报
文章被收录于专栏:秋风的笔记

作者:YGYOO 链接:https://juejin.im/post/5ba4a6b75188255ca1537b19 来源:掘金

本文是深入探究immutable.js系列的第二篇。

深入探究immutable.js的实现机制(一)[1]

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

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

HAMT

[HAMT](https://en.wikipedia.org/wiki/Hash_array_mapped_trie "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](https://en.wikipedia.org/wiki/Bit_array "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](https://en.wikipedia.org/wiki/Hamming_weight "popcount"),具体算法有很多,我了解不多就不展开了,前面点击后是维基的地址,感兴趣的可以研究下。下面我们看一下这部分的源码:

代码语言:javascript
复制
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方法,我把源码也贴出来:

代码语言:javascript
复制
functionpopCount(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](http://facebook.github.io/immutable-js#batching-mutations "withMutations")方法对相应数据结构进行临时的“可变”操作,最后再返回一个不可变的结构,这就是Transient,比如这样:

代码语言:javascript
复制
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的相关源码:

代码语言:javascript
复制
functionOwnerID() {}
代码语言:javascript
复制
functionasMutable() {
    return this.__ownerID ? this : this.__ensureOwner(new OwnerID());
}
代码语言:javascript
复制
functionwithMutations(fn) {
    const mutable = this.asMutable();
    fn(mutable);
    return mutable.wasAltered() ? mutable.__ensureOwner(this.__ownerID) : this;
}

它给了根节点一个ownerID,这个ownerID会在接下来的操作中按照上面的逻辑使用。注意这段代码是用 JS 的对象地址去作为 ID ,因为每次 new 之后的对象的地址肯定与之前的对象不同,所以用这种方法可以很简便高效地构造一套 ID 体系。下面再看下开启后进行操作时的一段源码( Map 中的set操作就会调用这个update方法):

代码语言:javascript
复制
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;
    returnthis;
    }

    returnnew HashArrayMapNode(ownerID, newCount, newNodes);
}

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

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数组里。大家也可以自己试试,代码如下:

代码语言:javascript
复制
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)

如果文章里有什么问题欢迎指正。

该文章是我正在更新的深入探究immutable.js系列的第二篇,说实话这两篇文章写了挺久,现成的资料很少很散,而且基本都是别的编程语言里的。有时间和精力我会继续更新第三篇甚至第四篇,感觉还是有些内容可以展开。

参考: hypirion.com/musings/und…[2]io-meter.com/2016/11/06/…[3]cdn.oreillystatic.com/en/assets/1…[4]infoscience.epfl.ch/record/1698…[5]lampwww.epfl.ch/papers/idea…[6]github.com/funfish/blo…[7]github.com/facebook/im…[8]

参考资料

[1]

深入探究immutable.js的实现机制(一): https://juejin.im/post/5b9b30a35188255c6418e67c

[2]

hypirion.com/musings/und…: https://hypirion.com/musings/understanding-persistent-vector-pt-1

[3]

io-meter.com/2016/11/06/…: https://io-meter.com/2016/11/06/functional-go-intro-to-hamt

[4]

cdn.oreillystatic.com/en/assets/1…: https://cdn.oreillystatic.com/en/assets/1/event/259/Immutable%20data%20structures%20for%20functional%20JavaScript%20Presentation.pdf

[5]

infoscience.epfl.ch/record/1698…: https://infoscience.epfl.ch/record/169879/files/RMTrees.pdf

[6]

lampwww.epfl.ch/papers/idea…: http://lampwww.epfl.ch/papers/idealhashtrees.pdf

[7]

github.com/funfish/blo…: https://github.com/funfish/blog

[8]

github.com/facebook/im…: https://github.com/facebook/immutable-js/blob/e65e5af806ea23a32ccf8f56c6fabf39605bac80/src

❤️ 看完两件小事

如果你觉得这篇内容对你挺有启发,我想邀请你帮我两个小忙:

1.点个「在看」,让更多的人也能看到这篇内容(喜欢不点在看,都是耍流氓 )

2.欢迎关注公众号 「秋风的笔记」,主要记录日常中觉得有意思的工具以及分享开发实践,保持深度和专注度。

你的「点赞在看分享」是对作者最大的支持❤️

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-07-28,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 秋风的笔记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • HAMT
  • 树高压缩
  • 节点内部压缩-Bitmap
  • 为什么是32
  • 回顾
  • Transient
  • hash冲突
    • 参考资料
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档