Benchmarks
Benchmark tests will always yield different results across various platforms, different JavaScript engines, different memory configurations, and different hardware.
The following benchmark test results have selected the relatively poor container performance results during fluctuations for your reference.
TL;DR;
Section titled “TL;DR;”Here are some results that everyone is interested in. The following tests the performance per second with 500,000 elements already emplaced:
In each second, the access by subscript is as follows:
- Native array: ~23,000,000 times.
BlockArray: ~11,000,000 times.BlockList: ~19,000,000 times. (Fastest access!)BlockDeque~16,000,000 times.
Insertion/deletion in the middle per second:
- Native array ~4,500 times.
BlockArray~1,100,000 times. (Very balanced!)BlockList~140,000 times.BlockDeque~110,000 times.
Insertion/deletion (approximately 600 elements from the head) per second:
- Native array ~2,000 times.
BlockArray~710,000 times.BlockList~75,000 times.BlockDeque~2,800,000 times. (Very fast at both ends!)
since Sorted- containers are wrappers for them, the efficiency of most operations is always the same.
Let’s take a look at their performance under wrappers such as SortedSet.
| Random Rank Access | Random ins/del | |
|---|---|---|
| SortedBlockArray | 11,000,000 hz | 818,000 hz |
| SortedBlockList | 19,000,000 hz | 200,000 hz |
| SortedBlockDeque | 16,000,000 hz | 220,000 hz |
| SplayTree | 2,300,00 hz | 460,000 hz |
To ensure that the size of the container remains basically unchanged, we will insert one element and delete another element each time (there are two operations).
We guarantee that these two elements exist and are randomly generated in advance, so the actual performance may be much higher than the test results.
Blocks
Section titled “Blocks”按下标随机访问
Section titled “按下标随机访问”见 test/bench/flat-visit.bench.ts (N = 500,000)
✓ test/bench/flat-visit.bench.ts > Flat Containers access Bench (N=500,000) > Tail Mutation (Push/Pop) 13787ms name hz min max mean p75 p99 p995 p999 rme samples · Native Array 23,274,806.00 0.0000 0.1796 0.0000 0.0001 0.0001 0.0001 0.0002 ±0.33% 11637403 · BlockArray 19,049,952.00 0.0000 0.6768 0.0001 0.0001 0.0001 0.0002 0.0003 ±0.61% 9524976 · BlockArray.n 11,411,794.00 0.0000 0.4670 0.0001 0.0001 0.0002 0.0002 0.0004 ±0.32% 5705897 · BlockList 19,027,586.00 0.0000 0.8045 0.0001 0.0001 0.0001 0.0002 0.0002 ±0.47% 9513793 · BlockDeque 16,887,240.00 0.0000 0.4088 0.0001 0.0001 0.0001 0.0002 0.0004 ±0.52% 8443620BlockArray.n 表示 isUniform = false 的情况。以原生数组的效率为单位：
- BlockArray 和 BlockList 约为 4/5 倍；
- BlockDeque 约为 3/4 倍；
- BlockArray.n 约为 1/2 倍。
此外，由于 Sorted- 容器是他们的包装器，因此按排名查询的效率总是一样的。
见 test/bench/flat-mutation.bench.ts (N = 500,000)
尾部突变 (Push/Pop)
✓ test/bench/flat-mutation.bench.ts > Flat Containers Mutation Bench (N=500,000) > Tail Mutation (Push/Pop) 13123ms name hz min max mean p75 p99 p995 p999 rme samples · Native Array 24,163,440.00 0.0000 0.1665 0.0000 0.0001 0.0001 0.0001 0.0001 ±0.23% 12081720 · BlockArray 21,959,519.61 0.0000 0.7863 0.0000 0.0001 0.0001 0.0001 0.0002 ±0.51% 10979762 · BlockList 21,431,529.71 0.0000 0.7739 0.0000 0.0001 0.0001 0.0001 0.0002 ±0.59% 10715767 · BlockDeque 20,859,851.83 0.0000 0.1410 0.0000 0.0001 0.0001 0.0001 0.0002 ±0.26% 10429928评价 吞吐量基本与数组持平。
头部突变 (Unshift/Shift)
✓ test/bench/flat-mutation.bench.ts > Flat Containers Mutation Bench (N=500,000) > Head Mutation (Unshift/Shift) 4660ms name hz min max mean p75 p99 p995 p999 rme samples · Native Array 2,574.84 0.3026 1.0032 0.3884 0.4099 0.7055 0.8268 0.9086 ±1.02% 1288 · BlockArray 885,710.41 0.0010 0.5731 0.0011 0.0011 0.0014 0.0016 0.0062 ±0.36% 442856 · BlockList 86,653.13 0.0094 0.3526 0.0115 0.0118 0.0242 0.0279 0.0767 ±0.37% 43327 · BlockDeque 17,506,762.00 0.0000 0.2404 0.0001 0.0001 0.0001 0.0001 0.0002 ±0.33% 8753381评价 以原生数组为单位，分别是 343、33、6796 倍。
中部突变 (Insert/Delete at N/2)
✓ test/bench/flat-mutation.bench.ts > Flat Containers Mutation Bench (N=500,000) > Middle Mutation (Insert/Delete at N/2) 2594ms name hz min max mean p75 p99 p995 p999 rme samples · Native Array 4,573.38 0.1644 0.8142 0.2187 0.2282 0.4382 0.4973 0.6832 ±1.05% 2287 · BlockArray 1,100,278.24 0.0007 1.1413 0.0009 0.0009 0.0015 0.0016 0.0032 ±0.64% 550140 · BlockList 140,515.66 0.0051 1.8340 0.0071 0.0067 0.0143 0.0179 0.0524 ±0.92% 70258 · BlockDeque 101,187.47 0.0077 0.2120 0.0099 0.0099 0.0172 0.0228 0.0641 ±0.35% 50594评价 以原生数组为单位，分别是 340、30、22 倍。
靠近头部突变 (Insert/Delete at index ~600)
✓ test/bench/flat-mutation.bench.ts > Flat Containers Mutation Bench (N=500,000) > Near Head Mutation (Insert/Delete at index 600) 3025ms name hz min max mean p75 p99 p995 p999 rme samples · Native Array 2,017.28 0.3538 2.6648 0.4957 0.5458 0.8589 0.9205 1.0269 ±1.55% 1009 · BlockArray 717,047.13 0.0011 0.7922 0.0014 0.0014 0.0021 0.0024 0.0069 ±0.47% 358525 · BlockList 75,132.59 0.0106 0.4392 0.0133 0.0129 0.0239 0.0322 0.0691 ±0.36% 37567 · BlockDeque 2,821,178.31 0.0002 0.7511 0.0004 0.0004 0.0007 0.0007 0.0011 ±0.49% 1410590评价 以原生数组为单位，分别是 355、37、1398 倍。
靠近尾部突变 (Insert/Delete at N - ~600)
✓ test/bench/flat-mutation.bench.ts > Flat Containers Mutation Bench (N=500,000) > Near Tail Mutation (Insert/Delete at N - 600) 3828ms name hz min max mean p75 p99 p995 p999 rme samples · Native Array 2,483,457.50 0.0003 0.8689 0.0004 0.0004 0.0006 0.0006 0.0014 ±0.55% 1241729 · BlockArray 3,375,713.04 0.0002 0.4293 0.0003 0.0003 0.0004 0.0005 0.0016 ±0.62% 1688585 · BlockList 2,121,567.58 0.0004 0.2408 0.0005 0.0005 0.0005 0.0006 0.0016 ±0.35% 1060784 · BlockDeque 1,943,682.00 0.0004 0.7937 0.0005 0.0005 0.0006 0.0008 0.0024 ±0.54% 971841评价 差距不是特别大，BlockArray 总是最快。BlockList 和 BlockDeque 有一些额外的寻址开销。