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.
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 / TEST_TIMES}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:
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.
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 / TEST_TIMES}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:
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.