性能：Immutable.js Map vs List vs plain JS
Performance: Immutable.js Map vs List vs plain JS
问题
我的基准测试有问题吗？ Immutable.js find() 怎么会比 array.find() 慢 8 倍呢？
好吧，不完全公平，因为我在 Immutable.List 中使用 Immutable.Map。但对我来说，这是一个真实世界的例子。如果我使用 Immutable.js 它是为了保护不变性并在某些方面获得性能（结构共享发挥作用的地方）。仅在对象的根部使用 Immutable.js 是没有意义的。
下面的基准实际上来自 another question（我的也是）。我对结果感到非常惊讶，我不得不单独 post 它才能弄清楚。是我的基准测试有问题，还是性能差异真的有这么大？
背景
我应用中的一些数据可以被视为应用元数据。原始数据存在于服务器的数据库中。不会经常更新元数据。该应用程序将在启动时检查更新的元数据。
我到处都在使用 Immutable.js，但我会返回纯 js 来获取元数据。这种数据不需要花哨的结构共享。
测试是在集合中按键查找值
合集 10 件商品
求值一百万次
Mac 迷你酷睿 i7 2.6
结果：
带强制键的普通 JS 对象：8 毫秒
使用 find() 的普通 JS 数组：127 毫秒
Immutable.Map 带数字键：185 ms
Immutable.List 使用 find()：972 毫秒 !! 我莫名其妙
当我使用 React Native 时，如果我想达到 60 fps，我总是必须注意 16 毫秒的限制。基准值似乎不是线性的。 运行 只有 100 次查找的测试使用 Map 需要 1 ms，使用 List 需要 2 ms。挺贵的。
测试代码
let Immutable = require('immutable');
let mapTest = Immutable.Map()
.set(1, Immutable.Map({value: 'one'}))
.set(2, Immutable.Map({value: 'two'}))
.set(3, Immutable.Map({value: 'three'}))
.set(4, Immutable.Map({value: 'four'}))
.set(5, Immutable.Map({value: 'five'}))
.set(6, Immutable.Map({value: 'six'}))
.set(7, Immutable.Map({value: 'seven'}))
.set(8, Immutable.Map({value: 'eight'}))
.set(9, Immutable.Map({value: 'nine'}))
.set(10, Immutable.Map({value: 'ten'}));
let listTest = Immutable.fromJS([
{key: 1, value: 'one'},
{key: 2, value: 'two'},
{key: 3, value: 'three'},
{key: 4, value: 'four'},
{key: 5, value: 'five'},
{key: 6, value: 'six'},
{key: 7, value: 'seven'},
{key: 8, value: 'eight'},
{key: 9, value: 'nine'},
{key: 10, value: 'ten'}
])
let objTest = {
1: {value: 'one'},
2: {value: 'two'},
3: {value: 'three'},
4: {value: 'four'},
5: {value: 'five'},
6: {value: 'six'},
7: {value: 'seven'},
8: {value: 'eight'},
9: {value: 'nine'},
10: {value: 'ten'}
};
let arrayTest = [
{key: 1, value: 'one'},
{key: 2, value: 'two'},
{key: 3, value: 'three'},
{key: 4, value: 'four'},
{key: 5, value: 'five'},
{key: 6, value: 'six'},
{key: 7, value: 'seven'},
{key: 8, value: 'eight'},
{key: 9, value: 'nine'},
{key: 10, value: 'ten'}
];
const runs = 1e6;
let i;
let key;
let hrStart;
console.log(' ')
console.log('mapTest -----------------------------')
key = 1;
hrstart = process.hrtime();
for(i=0; i<runs; i++) {
let result = mapTest.getIn([key, 'value'] )
key = (key >= 10) ? 1 : key + 1;
}
hrend = process.hrtime(hrstart);
console.info("Execution time (hr): %dms", hrend[0] * 1000 + hrend[1]/1000000);
console.log(' ')
console.log('listTest -----------------------------')
key = 1;
hrstart = process.hrtime();
for(i=0; i<runs; i++) {
let result = listTest
.find(item => item.get('key') === key)
.get('value');
key = (key >= 10) ? 1 : key + 1;
}
hrend = process.hrtime(hrstart);
console.info("Execution time (hr): %dms", hrend[0] * 1000 + hrend[1]/1000000);
console.log(' ')
console.log('arrayTest -----------------------------')
key = 1;
hrstart = process.hrtime();
for(i=0; i<runs; i++) {
let result = arrayTest
.find(item => item.key === key)
.value
key = (key >= 10) ? 1 : key + 1;
}
hrend = process.hrtime(hrstart);
console.info("Execution time (hr): %dms", hrend[0] * 1000 + hrend[1]/1000000);
console.log(' ')
console.log('objTest -----------------------------')
key = 1;
hrstart = process.hrtime();
for(i=0; i<runs; i++) {
let result = objTest[key].value
key = (key >= 10) ? 1 : key + 1;
}
hrend = process.hrtime(hrstart);
console.info("Execution time (hr): %dms", hrend[0] * 1000 + hrend[1]/1000000);
JS 引擎非常擅长优化 'hot' 操作 - 那些重复很多并且尽可能简单的操作（例如 TurboFan in V8). Plain JS objects and array functions are always going to beat a library like Immutable.js, where List calls Collection calls Seq calls Operations （等等），尤其是当操作重复了很多次。
Immutable.js 似乎是为了方便使用而设计的，避免了可变 JS 集合的许多麻烦，而不是纯粹的性能。
如果你有一百万个东西，使用低级 JS 对象或数组（或 Web Assembly，如果性能很关键）。如果你有一千件事并且 需要 确定不丢帧，那么纯 JS 仍然是可行的方法。这些都是特殊情况 - 对于大多数用例来说，Immutable.js 的便利性值得降低速度。
简短的回答是，与原生 JS 数组相比，Immutable.js 使用的数据结构表示需要大量额外开销来遍历 List 的元素。
基准测试 Immutable.List.find 和 Array.find
你的基准测试很好，但我们可以通过去掉嵌套映射来简化问题；考虑实际问题的性能是正确的，但它有助于理解性能差异以尽可能简化问题。在基准测试中考虑性能如何随不同的输入大小变化也通常很有用。例如，在 Immutable.js 中，List.prototype.find 的实现方式可能会导致初始调用和设置需要一段时间，但随后遍历 List 的方式与原生 JS 数组的执行方式类似；在这种情况下，原生 JS 数组和 Immutable.js 列表之间的性能差异会随着输入长度变长而减小（事实并非如此）。
让我们也为原生 JS 数组创建我们自己的查找函数，Array.prototype.ourFind 与原生进行比较 Array.prototype.find 以确定差异是否部分是由于 JS 函数本身的性能 vs . 实现内置功能的性能。
Array.prototype.ourFind = function(predicate) {
for (let i = 0; i < this.length; i++) {
if (predicate(this[i])) return this[i];
}
}
function arrayRange(len) {
return new Array(len).fill(null).map((_, i) => i);
}
function immutListRange(len) {
return Immutable.fromJS(arrayRange(len));
}
function timeFind(coll, find, iters) {
let startTime = performance.now();
for (let i = 0; i < iters; i++) {
let searchVal = i % coll.length,
result = find.call(coll, item => item === searchVal);
}
return Math.floor(performance.now() - startTime);
}
const MIN_LEN = 10,
MAX_LEN = 1e4,
ITERS = 1e5;
console.log('\t\tArray.find\tArray.ourFind\tList.find');
for (let len = MIN_LEN; len <= MAX_LEN; len *= 10) {
console.log(`${len}\t\t\t` +
`${timeFind(arrayRange(len), Array.prototype.find, ITERS)}\t\t\t` +
`${timeFind(arrayRange(len), Array.prototype.ourFind, ITERS)}\t\t\t` +
`${timeFind(immutListRange(len), Immutable.List.prototype.find, ITERS)}`)
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/immutable/3.8.1/immutable.js"></script>
在Chrome中，我得到：
Length . Array.find Array.ourFind List.find
10 28 13 96
100 60 44 342
1000 549 342 3016
10000 5533 3142 36423
我在 Firefox 和 Safari 中得到的结果大致相似。需要注意的几点：
List.find 与 Array.find 之间的差异不仅仅是由于本机（即解释器内置）实现与 JS 实现，因为 Array.ourFind 的 JS 实现执行至少和 Array.find.- 所有实现都在 O(n) 时间内工作（即执行时间与输入长度成线性关系）。这是意料之中的，因为查找算法将始终必须通过遍历集合元素来工作，直到找到谓词 returns true.
的元素。
Immutable.List.find 比 Array.find 慢约 6 倍，与您的基准测试结果一致。
Immutable.List数据表示
要理解为什么 Immutable.List.find 这么慢，您首先必须考虑 Immutable.List 是如何表示列表内容的。
一个快速的方法是生成一个 Immutable.List 并在控制台中检查它：
console.log(immutListRange(1000)); // immutListRange defined above
所以基本上看起来 Immutable.List 将内容表示为分支因子为 32 的树。
现在考虑对以这种方式表示的数据进行 运行 查找操作需要什么。您必须从根节点开始，向下遍历树到第一个叶节点（包含一个包含实际数据的数组），然后遍历叶的内容；如果找不到该元素，则必须转到下一个叶节点并搜索该数组，依此类推。这是一个比仅搜索单个数组更复杂的操作，并且需要开销才能执行。
在工作中观看 Immutable.List.find
欣赏 Immutable.List.find 所做工作的一个好方法是在您选择的调试器中设置一个断点并逐步完成操作。您会发现 Immutable.List.Find 远不只是循环遍历单个数组那样简单的操作。
补充评论
Immutable.js 中的数据树表示可能会加速其他操作，但会导致一些函数的性能下降，例如查找。
附带说明一下，我认为在大多数情况下，选择使用不可变数据结构并不是出于性能考虑。在某些情况下，不可变数据结构的性能优于可变数据结构（当然，不可变数据结构使并行计算不那么复杂，从而显着提高性能），但在很多情况下情况恰恰相反。相反，在大多数情况下，不变性的选择是由设计考虑驱动的——即使用不可变数据结构会强制程序设计更加健壮，并且从长远来看 运行 会提高开发人员的工作效率。
基准测试并未考虑 Immutable 必须提供的所有数据类型。 Immutable 实际上有一些特性，普通 objects/arrays 没有：OrderedSet and OrderedMap 具有索引 arrays/List 和 key-based 结构的优点，如 object/Map.
下面是@Keith 的完美测试的改编版本，它表明我们实际上可以变得比 Array.find 更快，尤其是在处理大型数据集时。
当然，这也是有代价的：
- Set/Map 不允许重复（虽然与对象不同）。
- 在幕后，有序变体将 Map/Set 与列表组合在一起，因此会消耗更多内存。
Note that OrderedSet are more expensive than non-ordered Set and may consume more memory. OrderedSet#add is amortized O(log32 N), but not stable.
function arrayFind(coll, searchVal) {
return coll.find(item => item === searchVal);
}
function immutableSetGet(coll, searchVal) {
return coll.get(searchVal);
}
function arrayRange(len) {
return new Array(len).fill(null).map((_, i) => i);
}
function immutOrderedSetRange(len) {
return Immutable.OrderedSet(arrayRange(len));
}
function timeFind(what, coll, find, iters) {
let startTime = performance.now();
let size = coll.length || coll.size;
for (let i = 0; i < iters; i++) {
let searchVal = i % size,
result = find(coll, searchVal);
}
return Math.floor(performance.now() - startTime);
}
const MIN_LEN = 100,
MAX_LEN = 1e5,
ITERS = 50000;
console.log('\t\t\tArray.find\tOrderedSet.find');
for (let len = MIN_LEN; len <= MAX_LEN; len *= 10) {
console.log(`${len}\t\t\t` +
`${timeFind('find', arrayRange(len), arrayFind, ITERS)}\t\t` +
`${timeFind('set', immutOrderedSetRange(len), immutableSetGet, ITERS)}`)
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/immutable/3.8.1/immutable.js"></script>
示例结果，在 Chrome 86:
Array.find OrderedSet.find
100 10 18
1000 10 6
10000 74 10
100000 346 11
问题
我的基准测试有问题吗？ Immutable.js find() 怎么会比 array.find() 慢 8 倍呢？
好吧，不完全公平，因为我在 Immutable.List 中使用 Immutable.Map。但对我来说，这是一个真实世界的例子。如果我使用 Immutable.js 它是为了保护不变性并在某些方面获得性能（结构共享发挥作用的地方）。仅在对象的根部使用 Immutable.js 是没有意义的。
下面的基准实际上来自 another question（我的也是）。我对结果感到非常惊讶，我不得不单独 post 它才能弄清楚。是我的基准测试有问题，还是性能差异真的有这么大？
背景
我应用中的一些数据可以被视为应用元数据。原始数据存在于服务器的数据库中。不会经常更新元数据。该应用程序将在启动时检查更新的元数据。
我到处都在使用 Immutable.js，但我会返回纯 js 来获取元数据。这种数据不需要花哨的结构共享。
测试是在集合中按键查找值
合集 10 件商品
求值一百万次
Mac 迷你酷睿 i7 2.6
结果：
带强制键的普通 JS 对象：8 毫秒
使用 find() 的普通 JS 数组：127 毫秒
Immutable.Map 带数字键：185 ms
Immutable.List 使用 find()：972 毫秒 !! 我莫名其妙
当我使用 React Native 时，如果我想达到 60 fps，我总是必须注意 16 毫秒的限制。基准值似乎不是线性的。 运行 只有 100 次查找的测试使用 Map 需要 1 ms，使用 List 需要 2 ms。挺贵的。
测试代码
let Immutable = require('immutable');
let mapTest = Immutable.Map()
.set(1, Immutable.Map({value: 'one'}))
.set(2, Immutable.Map({value: 'two'}))
.set(3, Immutable.Map({value: 'three'}))
.set(4, Immutable.Map({value: 'four'}))
.set(5, Immutable.Map({value: 'five'}))
.set(6, Immutable.Map({value: 'six'}))
.set(7, Immutable.Map({value: 'seven'}))
.set(8, Immutable.Map({value: 'eight'}))
.set(9, Immutable.Map({value: 'nine'}))
.set(10, Immutable.Map({value: 'ten'}));
let listTest = Immutable.fromJS([
{key: 1, value: 'one'},
{key: 2, value: 'two'},
{key: 3, value: 'three'},
{key: 4, value: 'four'},
{key: 5, value: 'five'},
{key: 6, value: 'six'},
{key: 7, value: 'seven'},
{key: 8, value: 'eight'},
{key: 9, value: 'nine'},
{key: 10, value: 'ten'}
])
let objTest = {
1: {value: 'one'},
2: {value: 'two'},
3: {value: 'three'},
4: {value: 'four'},
5: {value: 'five'},
6: {value: 'six'},
7: {value: 'seven'},
8: {value: 'eight'},
9: {value: 'nine'},
10: {value: 'ten'}
};
let arrayTest = [
{key: 1, value: 'one'},
{key: 2, value: 'two'},
{key: 3, value: 'three'},
{key: 4, value: 'four'},
{key: 5, value: 'five'},
{key: 6, value: 'six'},
{key: 7, value: 'seven'},
{key: 8, value: 'eight'},
{key: 9, value: 'nine'},
{key: 10, value: 'ten'}
];
const runs = 1e6;
let i;
let key;
let hrStart;
console.log(' ')
console.log('mapTest -----------------------------')
key = 1;
hrstart = process.hrtime();
for(i=0; i<runs; i++) {
let result = mapTest.getIn([key, 'value'] )
key = (key >= 10) ? 1 : key + 1;
}
hrend = process.hrtime(hrstart);
console.info("Execution time (hr): %dms", hrend[0] * 1000 + hrend[1]/1000000);
console.log(' ')
console.log('listTest -----------------------------')
key = 1;
hrstart = process.hrtime();
for(i=0; i<runs; i++) {
let result = listTest
.find(item => item.get('key') === key)
.get('value');
key = (key >= 10) ? 1 : key + 1;
}
hrend = process.hrtime(hrstart);
console.info("Execution time (hr): %dms", hrend[0] * 1000 + hrend[1]/1000000);
console.log(' ')
console.log('arrayTest -----------------------------')
key = 1;
hrstart = process.hrtime();
for(i=0; i<runs; i++) {
let result = arrayTest
.find(item => item.key === key)
.value
key = (key >= 10) ? 1 : key + 1;
}
hrend = process.hrtime(hrstart);
console.info("Execution time (hr): %dms", hrend[0] * 1000 + hrend[1]/1000000);
console.log(' ')
console.log('objTest -----------------------------')
key = 1;
hrstart = process.hrtime();
for(i=0; i<runs; i++) {
let result = objTest[key].value
key = (key >= 10) ? 1 : key + 1;
}
hrend = process.hrtime(hrstart);
console.info("Execution time (hr): %dms", hrend[0] * 1000 + hrend[1]/1000000);
JS 引擎非常擅长优化 'hot' 操作 - 那些重复很多并且尽可能简单的操作（例如 TurboFan in V8). Plain JS objects and array functions are always going to beat a library like Immutable.js, where List calls Collection calls Seq calls Operations （等等），尤其是当操作重复了很多次。
Immutable.js 似乎是为了方便使用而设计的，避免了可变 JS 集合的许多麻烦，而不是纯粹的性能。
如果你有一百万个东西，使用低级 JS 对象或数组（或 Web Assembly，如果性能很关键）。如果你有一千件事并且 需要 确定不丢帧，那么纯 JS 仍然是可行的方法。这些都是特殊情况 - 对于大多数用例来说，Immutable.js 的便利性值得降低速度。
简短的回答是，与原生 JS 数组相比，Immutable.js 使用的数据结构表示需要大量额外开销来遍历 List 的元素。
基准测试 Immutable.List.find 和 Array.find
你的基准测试很好，但我们可以通过去掉嵌套映射来简化问题；考虑实际问题的性能是正确的，但它有助于理解性能差异以尽可能简化问题。在基准测试中考虑性能如何随不同的输入大小变化也通常很有用。例如，在 Immutable.js 中，List.prototype.find 的实现方式可能会导致初始调用和设置需要一段时间，但随后遍历 List 的方式与原生 JS 数组的执行方式类似；在这种情况下，原生 JS 数组和 Immutable.js 列表之间的性能差异会随着输入长度变长而减小（事实并非如此）。
让我们也为原生 JS 数组创建我们自己的查找函数，Array.prototype.ourFind 与原生进行比较 Array.prototype.find 以确定差异是否部分是由于 JS 函数本身的性能 vs . 实现内置功能的性能。
Array.prototype.ourFind = function(predicate) {
for (let i = 0; i < this.length; i++) {
if (predicate(this[i])) return this[i];
}
}
function arrayRange(len) {
return new Array(len).fill(null).map((_, i) => i);
}
function immutListRange(len) {
return Immutable.fromJS(arrayRange(len));
}
function timeFind(coll, find, iters) {
let startTime = performance.now();
for (let i = 0; i < iters; i++) {
let searchVal = i % coll.length,
result = find.call(coll, item => item === searchVal);
}
return Math.floor(performance.now() - startTime);
}
const MIN_LEN = 10,
MAX_LEN = 1e4,
ITERS = 1e5;
console.log('\t\tArray.find\tArray.ourFind\tList.find');
for (let len = MIN_LEN; len <= MAX_LEN; len *= 10) {
console.log(`${len}\t\t\t` +
`${timeFind(arrayRange(len), Array.prototype.find, ITERS)}\t\t\t` +
`${timeFind(arrayRange(len), Array.prototype.ourFind, ITERS)}\t\t\t` +
`${timeFind(immutListRange(len), Immutable.List.prototype.find, ITERS)}`)
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/immutable/3.8.1/immutable.js"></script>
在Chrome中，我得到：
Length . Array.find Array.ourFind List.find
10 28 13 96
100 60 44 342
1000 549 342 3016
10000 5533 3142 36423
我在 Firefox 和 Safari 中得到的结果大致相似。需要注意的几点：
List.find与Array.find之间的差异不仅仅是由于本机（即解释器内置）实现与 JS 实现，因为Array.ourFind的 JS 实现执行至少和Array.find. 一样好
- 所有实现都在 O(n) 时间内工作（即执行时间与输入长度成线性关系）。这是意料之中的，因为查找算法将始终必须通过遍历集合元素来工作，直到找到谓词 returns true. 的元素。
Immutable.List.find比Array.find慢约 6 倍，与您的基准测试结果一致。
Immutable.List数据表示
要理解为什么 Immutable.List.find 这么慢，您首先必须考虑 Immutable.List 是如何表示列表内容的。
一个快速的方法是生成一个 Immutable.List 并在控制台中检查它：
console.log(immutListRange(1000)); // immutListRange defined above
所以基本上看起来 Immutable.List 将内容表示为分支因子为 32 的树。
现在考虑对以这种方式表示的数据进行 运行 查找操作需要什么。您必须从根节点开始，向下遍历树到第一个叶节点（包含一个包含实际数据的数组），然后遍历叶的内容；如果找不到该元素，则必须转到下一个叶节点并搜索该数组，依此类推。这是一个比仅搜索单个数组更复杂的操作，并且需要开销才能执行。
在工作中观看 Immutable.List.find
欣赏 Immutable.List.find 所做工作的一个好方法是在您选择的调试器中设置一个断点并逐步完成操作。您会发现 Immutable.List.Find 远不只是循环遍历单个数组那样简单的操作。
补充评论
Immutable.js 中的数据树表示可能会加速其他操作，但会导致一些函数的性能下降，例如查找。
附带说明一下，我认为在大多数情况下，选择使用不可变数据结构并不是出于性能考虑。在某些情况下，不可变数据结构的性能优于可变数据结构（当然，不可变数据结构使并行计算不那么复杂，从而显着提高性能），但在很多情况下情况恰恰相反。相反，在大多数情况下，不变性的选择是由设计考虑驱动的——即使用不可变数据结构会强制程序设计更加健壮，并且从长远来看 运行 会提高开发人员的工作效率。
基准测试并未考虑 Immutable 必须提供的所有数据类型。 Immutable 实际上有一些特性，普通 objects/arrays 没有：OrderedSet and OrderedMap 具有索引 arrays/List 和 key-based 结构的优点，如 object/Map.
下面是@Keith 的完美测试的改编版本，它表明我们实际上可以变得比 Array.find 更快，尤其是在处理大型数据集时。
当然，这也是有代价的：
- Set/Map 不允许重复（虽然与对象不同）。
- 在幕后，有序变体将 Map/Set 与列表组合在一起，因此会消耗更多内存。
Note that OrderedSet are more expensive than non-ordered Set and may consume more memory. OrderedSet#add is amortized O(log32 N), but not stable.
function arrayFind(coll, searchVal) {
return coll.find(item => item === searchVal);
}
function immutableSetGet(coll, searchVal) {
return coll.get(searchVal);
}
function arrayRange(len) {
return new Array(len).fill(null).map((_, i) => i);
}
function immutOrderedSetRange(len) {
return Immutable.OrderedSet(arrayRange(len));
}
function timeFind(what, coll, find, iters) {
let startTime = performance.now();
let size = coll.length || coll.size;
for (let i = 0; i < iters; i++) {
let searchVal = i % size,
result = find(coll, searchVal);
}
return Math.floor(performance.now() - startTime);
}
const MIN_LEN = 100,
MAX_LEN = 1e5,
ITERS = 50000;
console.log('\t\t\tArray.find\tOrderedSet.find');
for (let len = MIN_LEN; len <= MAX_LEN; len *= 10) {
console.log(`${len}\t\t\t` +
`${timeFind('find', arrayRange(len), arrayFind, ITERS)}\t\t` +
`${timeFind('set', immutOrderedSetRange(len), immutableSetGet, ITERS)}`)
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/immutable/3.8.1/immutable.js"></script>
示例结果，在 Chrome 86:
Array.find OrderedSet.find
100 10 18
1000 10 6
10000 74 10
100000 346 11