Note that this is also a issue in GitHub.
I noticed that the $tw.utils.each function (a very important core function used in most filters) in $:/boot/boot.js first determines the type of the object to be traversed, and uses a for loop to traverse it if it is an array, or a for + Object.keys loop to traverse it if it is an object. I recently conducted performance tests on various ways of traversing arrays and objects on several major browsers and came to some conclusions.
- For array traversal, using the sequential Duff’s Device algorithm can improve performance somewhat.
- For object traversal, the
for+Object.keysapproach is very efficient in most cases, butfor...in...should be preferred in Safari (by detecting Safari browser first using/version.*safari/i.test(navigator.userAgent)).
The following is used to prove my conclusion.
Benchmark test part
My test environment:
- Apple MacBook Pro 2017 (15-inch)
- macOS Big Sur (v11.6 (20G165)), Darwin Kernel Version 20.6.0
- CPU: 3.1 GHz Quad-Core Intel Core i7-7920HQ
- Memory: LPDDR3 2133 MHz 8G x 2
I have tested it in four browsers:
- Chrome 94.0.4606.81 (Official Build) (x86_64)
- FireFox 93.0 (x86_64)
- Safari 15.0 (16612.1.29.41.4, 16612)
- Edge 94.0.992.37 (Official build) (x86_64) (Note that Edge also uses Chrome kernel)
Test Method:
I encapsulate the various traversal methods into a function each(obj, callback), which takes an argument obj to be traversed (possibly an array or object) and traverses the elements of it and calls the function callback one by one. For the array traversal test and the object traversal test, the following callback functions are used, respectively.
// For Array
let arr_ = [];
each(EXAMPLE_ARRAY, (x) => {
arr_.push(x);
});
// For Object
let obj_ = {};
each(EXAMPLE_OBJECT, (key, value) => {
obj_[key] = value + 1;
});
The sizes of EXAMPLE_ARRAY and EXAMPLE_OBJECT are both 10000000. I timed each traversal method and counted the average of five timings as the test result.
Array
Benchmark script for array
Thanks to nullqube;
!(function () {
const TEST_TIMES = 5;
const ARRAY_SIZE = 10000000;
const EXAMPLE_ARRAY = new Array(ARRAY_SIZE).fill(255);
function time(name, each) {
var totalDuration = 0;
console.log(`[${name}]`);
for (var i = 0; i < TEST_TIMES; i++) {
let arr_ = [];
const start = new Date();
each(EXAMPLE_ARRAY, (x) => {
arr_.push(x);
});
const end = new Date();
var duration = end - start;
console.log(` * ${duration}ms`);
totalDuration += duration;
arr_ = undefined;
}
console.log(` average: ${totalDuration / 5}ms`);
}
time("for i<len", (arr, func) => {
var i, len;
for (i = 0, len = arr.length; i < len; i++) {
func(arr[i]);
}
});
time("for i<arr.length", (arr, func) => {
var i;
for (i = 0; i < arr.length; i++) {
func(arr[i]);
}
});
time("while i<len", (arr, func) => {
var i = 0,
len = arr.length;
while (i < len) {
func(arr[i++]);
}
});
time("forEach", (arr, func) => {
arr.forEach(func);
});
time("for var..of..", (arr, func) => {
for (var x of arr) {
func(x);
}
});
time("for let..of..", (arr, func) => {
for (let x of arr) {
func(x);
}
});
time("for const..of..", (arr, func) => {
for (const x of arr) {
func(x);
}
});
time("for var..in..", (arr, func) => {
for (var i in arr) {
func(arr[i]);
}
});
time("for let..in..", (arr, func) => {
for (let i in arr) {
func(arr[i]);
}
});
time("for const..in..", (arr, func) => {
for (const i in arr) {
func(arr[i]);
}
});
time("Duff's device", (arr, func) => {
var len = arr.length;
var n = len % 8;
var i;
if (n > 0) {
do {
func(arr[len - n]);
} while (--n); // n must be greater than 0 here
}
n = (len * 0.125) ^ 0;
if (n > 0) {
do {
i = --n << 3;
func(arr[i]);
func(arr[i + 1]);
func(arr[i + 2]);
func(arr[i + 3]);
func(arr[i + 4]);
func(arr[i + 5]);
func(arr[i + 6]);
func(arr[i + 7]);
} while (n); // n must be greater than 0 here also
}
});
time("Duff's device (Ordered)", (arr, func) => {
var len = arr.length;
var block = (len * 0.125) ^ 0;
var i, n;
if (block > 0) {
n = 0;
do {
i = n++ << 3;
func(arr[i]);
func(arr[i + 1]);
func(arr[i + 2]);
func(arr[i + 3]);
func(arr[i + 4]);
func(arr[i + 5]);
func(arr[i + 6]);
func(arr[i + 7]);
} while (n < block); // n must be greater than 0 here also
}
n = len % 8;
if (n > 0) {
do {
func(arr[len - n]);
} while (--n); // n must be greater than 0 here
}
});
})();
Please note: I didn’t do a deep verification of my Duff’s Device algorithm implementation, I just tested it with some general arrays and verified it is correct. So there is no guarantee that this way of implementing the algorithm is completely correct. If someone finds a problem with it, please just point it out!
Result (details are here):
| Chrome | FireFox | Safari | Edge | |
|---|---|---|---|---|
| for i<len | 269.8ms | 211.4ms | 295.4ms | 252.8ms |
| for i<arr.length | 201.4ms | 204ms | 222.4ms | 240.2ms |
| while i<len | 258ms | 201.2ms | 363ms | 184.2ms |
| forEach | 332.8ms | 235.6ms | 260.2ms | 272.2ms |
| for var…of… | 310.6ms | 254ms | 360ms | 249.6ms |
| for let…of… | 272ms | 241.8ms | 339.2ms | 236.6ms |
| for const…of… | 289.2ms | 261.8ms | 342.2ms | 271.6ms |
| for var…in… | 3680.2ms | 15953.6ms | 6477.2ms | 3151ms |
| for let…in… | 2862.8ms | 15977.8ms | 6657.6ms | 3001.6ms |
| for const…in… | 3087.2ms | 15790ms | 8089ms | 2947.2ms |
| Duff’s device | 162.2ms | 184.4ms | 248.2ms | 133.4ms |
| Duff’s device (Ordered) | 176ms | 184.6ms | 241ms | 175.8ms |
As a result, Duff’s Device algorithm is even faster than for loop. Considering that it is more suitable for optimizing complex traversal operations, I think it should be used as the traversal method for arrays.
Object
Benchmark script for object
Thanks to pod4g/tool.
!(function () {
const TEST_TIMES = 5;
const OBJECT_SIZE = 10000000;
const EXAMPLE_OBJECT = {};
for (var i = 0, j = OBJECT_SIZE; i < j; i++) EXAMPLE_OBJECT[i] = i;
function duffOrdered(arr, func) {
var len = arr.length;
var block = (len * 0.125) ^ 0;
var i, n;
if (block > 0) {
n = 0;
do {
i = n++ << 3;
func(arr[i]);
func(arr[i + 1]);
func(arr[i + 2]);
func(arr[i + 3]);
func(arr[i + 4]);
func(arr[i + 5]);
func(arr[i + 6]);
func(arr[i + 7]);
} while (n < block); // n must be greater than 0 here also
}
n = len % 8;
if (n > 0) {
do {
func(arr[len - n]);
} while (--n); // n must be greater than 0 here
}
}
function time(name, each) {
var totalDuration = 0;
console.log(`[${name}]`);
for (var i = 0; i < TEST_TIMES; i++) {
let obj_ = {};
const start = new Date();
each(EXAMPLE_OBJECT, (key, value) => {
obj_[key] = value + 1;
});
const end = new Date();
var duration = end - start;
console.log(` * ${duration}ms`);
totalDuration += duration;
obj_ = undefined;
}
console.log(` average: ${totalDuration / 5}ms`);
}
time("for..in..", (obj, func) => {
for (var key in obj) {
func(key, obj[key]);
}
});
time("duff+Object.getOwnPropertyNames", (obj, func) => {
duffOrdered(Object.getOwnPropertyNames(obj), (key) => {
func(key, obj[key]);
});
});
time("duff+Reflect.ownKeys", (obj, func) => {
duffOrdered(Reflect.ownKeys(obj), (key) => {
func(key, obj[key]);
});
});
time("duff+Object.entries", (obj, func) => {
duffOrdered(Object.entries(obj), (entry) => {
func(entry[0], entry[1]);
});
});
time("duff+Object.keys", (obj, func) => {
duffOrdered(Object.keys(obj), (key) => {
func(key, obj[key]);
});
});
time("for+Object.keys", (obj, func) => {
var keys = Object.keys(obj);
var i, length;
for (i = 0, length = keys.length; i < length; i++) {
func(keys[i], obj[keys[i]]);
}
});
})();
Result (details are here):
| Chrome | FireFox | Safari | Edge | |
|---|---|---|---|---|
| for…in… | 3256.2ms | 16665ms | 6635.6ms | 3199.2ms |
| duff+Object.getOwnPropertyNames | 7922.6ms | 1483ms | 8904.8ms | 9849.4ms |
| duff+Reflect.ownKeys | 8602.4ms | 1410ms | 7912.8ms | 8044.2ms |
| duff+Object.entries | 11984.8ms | 5405.8ms | 8453.8ms | 11502ms |
| duff+Object.keys | 3120.4ms | 1458.8ms | 7920.6ms | 3004.6ms |
| for+Object.keys | 3178.8ms | 1329.2ms | 8613.2ms | 3020ms |
Surprisingly, the Duff’s Device algorithm is not the fastest way to iterate over objects, so a for loop should be used. But we noticed a detail that for + Object.keys is less efficient on Safari browser, so for... should be used. .in... loop for traversal.