为什么第一个函数调用的执行速度比所有其他顺序调用快两倍?
Why is the first function call is executed two times faster than all other sequential calls?
我有一个自定义的 JS 迭代器实现和用于测量后者实现性能的代码:
const ITERATION_END = Symbol('ITERATION_END');
const arrayIterator = (array) => {
let index = 0;
return {
hasValue: true,
next() {
if (index >= array.length) {
this.hasValue = false;
return ITERATION_END;
}
return array[index++];
},
};
};
const customIterator = (valueGetter) => {
return {
hasValue: true,
next() {
const nextValue = valueGetter();
if (nextValue === ITERATION_END) {
this.hasValue = false;
return ITERATION_END;
}
return nextValue;
},
};
};
const map = (iterator, selector) => customIterator(() => {
const value = iterator.next();
return value === ITERATION_END ? value : selector(value);
});
const filter = (iterator, predicate) => customIterator(() => {
if (!iterator.hasValue) {
return ITERATION_END;
}
let currentValue = iterator.next();
while (iterator.hasValue && currentValue !== ITERATION_END && !predicate(currentValue)) {
currentValue = iterator.next();
}
return currentValue;
});
const toArray = (iterator) => {
const array = [];
while (iterator.hasValue) {
const value = iterator.next();
if (value !== ITERATION_END) {
array.push(value);
}
}
return array;
};
const test = (fn, iterations) => {
const times = [];
for (let i = 0; i < iterations; i++) {
const start = performance.now();
fn();
times.push(performance.now() - start);
}
console.log(times);
console.log(times.reduce((sum, x) => sum + x, 0) / times.length);
}
const createData = () => Array.from({ length: 9000000 }, (_, i) => i + 1);
const testIterator = (data) => () => toArray(map(filter(arrayIterator(data), x => x % 2 === 0), x => x * 2))
test(testIterator(createData()), 10);
测试函数的输出非常奇怪和出乎意料 - 第一个测试 运行 的执行速度始终比所有其他 运行 快两倍。结果之一,其中数组包含所有执行时间,数字是平均值(我在 Node 上 运行):
[
147.9088459983468,
396.3472499996424,
374.82447600364685,
367.74555300176144,
363.6300039961934,
362.44370299577713,
363.8418449983001,
390.86111199855804,
360.23125199973583,
358.4788999930024
]
348.6312940984964
使用 Deno 运行time 可以观察到类似的结果,但是我无法在其他 JS 引擎上重现此行为。 V8 背后的原因是什么?
环境:
节点 v13.8.0,V8 v7.9.317.25-node.28,
Deno v1.3.3、V8 v8.6.334
(此处为 V8 开发人员。)简而言之:内联或缺乏内联,由引擎启发式决定。
对于优化编译器,内联被调用的函数可以带来显着的好处(例如:避免调用开销,有时使常量折叠成为可能,或消除重复计算,有时甚至为额外的内联创造新的机会),但是代价是:它使编译本身变慢,并且增加了以后由于某些假设不成立而不得不丢弃优化代码(“去优化”)的风险。什么都不内联会浪费性能,内联所有东西都会浪费性能,内联完全正确的功能需要能够预测程序的未来行为,这显然是不可能的。所以编译器使用启发式方法。
V8 的优化编译器目前有一个启发式内联函数,仅当它始终是在特定位置调用的相同函数时。在这种情况下,这是第一次迭代的情况。随后的迭代然后创建新的闭包作为回调,从 V8 的角度来看,它们是新函数,因此它们不会被内联。 (V8 实际上知道一些高级技巧,允许它 de-duplicate 在某些情况下来自同一源的函数实例并无论如何内联它们;但在这种情况下这些不适用 [我不确定为什么])。 =21=]
所以在第一次迭代中,所有内容(包括 x => x % 2 === 0
和 x => x * 2
)都被内联到 toArray
中。从第二次迭代开始,情况不再如此,而是生成的代码执行实际的函数调用。
这可能没问题;我猜想在大多数实际应用中,差异几乎无法测量。 (减少测试用例往往会使这种差异更加突出;但是根据对小型测试的观察来更改较大应用程序的设计通常不是花费时间的最有效方式,最坏的情况下会使事情变得更糟。)
此外,hand-optimizing engines/compilers 的代码很难平衡。我通常建议 而不是 这样做(因为引擎会随着时间的推移而改进,而使您的代码更快确实是他们的工作);另一方面,显然存在更高效的代码和更低效的代码,为了最大的整体效率,每个相关人员都需要尽自己的一份力量,也就是说,您最好尽可能简化引擎的工作。
如果您确实想要 fine-tune 执行此操作,您可以通过分离代码和数据来实现,从而确保始终调用相同的函数。例如像你的代码的这个修改版本:
const ITERATION_END = Symbol('ITERATION_END');
class ArrayIterator {
constructor(array) {
this.array = array;
this.index = 0;
}
next() {
if (this.index >= this.array.length) return ITERATION_END;
return this.array[this.index++];
}
}
function arrayIterator(array) {
return new ArrayIterator(array);
}
class MapIterator {
constructor(source, modifier) {
this.source = source;
this.modifier = modifier;
}
next() {
const value = this.source.next();
return value === ITERATION_END ? value : this.modifier(value);
}
}
function map(iterator, selector) {
return new MapIterator(iterator, selector);
}
class FilterIterator {
constructor(source, predicate) {
this.source = source;
this.predicate = predicate;
}
next() {
let value = this.source.next();
while (value !== ITERATION_END && !this.predicate(value)) {
value = this.source.next();
}
return value;
}
}
function filter(iterator, predicate) {
return new FilterIterator(iterator, predicate);
}
function toArray(iterator) {
const array = [];
let value;
while ((value = iterator.next()) !== ITERATION_END) {
array.push(value);
}
return array;
}
function test(fn, iterations) {
for (let i = 0; i < iterations; i++) {
const start = performance.now();
fn();
console.log(performance.now() - start);
}
}
function createData() {
return Array.from({ length: 9000000 }, (_, i) => i + 1);
};
function even(x) { return x % 2 === 0; }
function double(x) { return x * 2; }
function testIterator(data) {
return function main() {
return toArray(map(filter(arrayIterator(data), even), double));
};
}
test(testIterator(createData()), 10);
观察热路径上如何不再有动态创建的函数,以及“public接口”(即arrayIterator
、map
、filter
的方式, and toArray
compose) 和之前完全一样,只有 under-the-hood 细节有变化。为所有函数命名的一个好处是您可以获得更有用的分析输出 ;-)
精明的读者会注意到,此修改只会转移问题:如果您的代码中有多个地方调用 map
和 filter
的 modifiers/predicates,那么内联性问题会再次出现。正如我上面所说:微基准测试往往具有误导性,因为真实的应用程序通常具有不同的行为...
(FWIW,这与 的效果几乎相同。)
为了补充这项调查,我将 OP 的原始代码与 jmrk 建议的声明为单独函数的谓词和选择器函数与其他两个实现进行了比较。所以,这段代码有三种实现方式:
- 带有谓词和选择器函数的 OP 代码分别声明为命名函数(非内联)。
- 使用标准
array.map()
和 .filter()
(你会认为这会因为额外创建中间数组而变慢)
- 使用在一次迭代中同时执行过滤和映射的自定义迭代
OP 在节省时间和加快速度方面的尝试实际上是最慢的(平均而言)。自定义迭代最快。
我想这里的教训是,如何使用优化编译器使事情变得更快并不一定是直观的,所以如果你正在调整性能,你必须衡量“典型”的做事方式(这可能会受益来自最多的优化)。
另外,请注意,在方法 #3 中,前两次迭代最慢,然后它变得更快——与原始代码相反的效果。去图吧。
结果在这里:
[
99.90320014953613,
253.79690098762512,
271.3091011047363,
247.94990015029907,
247.457200050354,
261.9487009048462,
252.95090007781982,
250.8520998954773,
270.42809987068176,
249.340900182724
]
240.59370033740998
[
222.14270091056824,
220.48679995536804,
224.24630093574524,
237.07260012626648,
218.47070002555847,
218.1493010520935,
221.50559997558594,
223.3587999343872,
231.1618001461029,
243.55419993400574
]
226.01488029956818
[
147.81360006332397,
144.57479882240295,
73.13350009918213,
79.41700005531311,
77.38950109481812,
78.40880012512207,
112.31539988517761,
80.87990117073059,
76.7899010181427,
79.79679894447327
]
95.05192012786866
代码在这里:
const { performance } = require('perf_hooks');
const ITERATION_END = Symbol('ITERATION_END');
const arrayIterator = (array) => {
let index = 0;
return {
hasValue: true,
next() {
if (index >= array.length) {
this.hasValue = false;
return ITERATION_END;
}
return array[index++];
},
};
};
const customIterator = (valueGetter) => {
return {
hasValue: true,
next() {
const nextValue = valueGetter();
if (nextValue === ITERATION_END) {
this.hasValue = false;
return ITERATION_END;
}
return nextValue;
},
};
};
const map = (iterator, selector) => customIterator(() => {
const value = iterator.next();
return value === ITERATION_END ? value : selector(value);
});
const filter = (iterator, predicate) => customIterator(() => {
if (!iterator.hasValue) {
return ITERATION_END;
}
let currentValue = iterator.next();
while (iterator.hasValue && currentValue !== ITERATION_END && !predicate(currentValue)) {
currentValue = iterator.next();
}
return currentValue;
});
const toArray = (iterator) => {
const array = [];
while (iterator.hasValue) {
const value = iterator.next();
if (value !== ITERATION_END) {
array.push(value);
}
}
return array;
};
const test = (fn, iterations) => {
const times = [];
let result;
for (let i = 0; i < iterations; i++) {
const start = performance.now();
result = fn();
times.push(performance.now() - start);
}
console.log(times);
console.log(times.reduce((sum, x) => sum + x, 0) / times.length);
return result;
}
const createData = () => Array.from({ length: 9000000 }, (_, i) => i + 1);
const cache = createData();
const comp1 = x => x % 2 === 0;
const comp2 = x => x * 2;
const testIterator = (data) => () => toArray(map(filter(arrayIterator(data), comp1), comp2))
// regular array filter and map
const testIterator2 = (data) => () => data.filter(comp1).map(comp2);
// combine filter and map in same operation
const testIterator3 = (data) => () => {
let result = [];
for (let value of data) {
if (comp1(value)) {
result.push(comp2(value));
}
}
return result;
}
const a = test(testIterator(cache), 10);
const b = test(testIterator2(cache), 10);
const c = test(testIterator3(cache), 10);
function compareArrays(a1, a2) {
if (a1.length !== a2.length) return false;
for (let [i, val] of a1.entries()) {
if (a2[i] !== val) return false;
}
return true;
}
console.log(a.length);
console.log(compareArrays(a, b));
console.log(compareArrays(a, c));
我有一个自定义的 JS 迭代器实现和用于测量后者实现性能的代码:
const ITERATION_END = Symbol('ITERATION_END');
const arrayIterator = (array) => {
let index = 0;
return {
hasValue: true,
next() {
if (index >= array.length) {
this.hasValue = false;
return ITERATION_END;
}
return array[index++];
},
};
};
const customIterator = (valueGetter) => {
return {
hasValue: true,
next() {
const nextValue = valueGetter();
if (nextValue === ITERATION_END) {
this.hasValue = false;
return ITERATION_END;
}
return nextValue;
},
};
};
const map = (iterator, selector) => customIterator(() => {
const value = iterator.next();
return value === ITERATION_END ? value : selector(value);
});
const filter = (iterator, predicate) => customIterator(() => {
if (!iterator.hasValue) {
return ITERATION_END;
}
let currentValue = iterator.next();
while (iterator.hasValue && currentValue !== ITERATION_END && !predicate(currentValue)) {
currentValue = iterator.next();
}
return currentValue;
});
const toArray = (iterator) => {
const array = [];
while (iterator.hasValue) {
const value = iterator.next();
if (value !== ITERATION_END) {
array.push(value);
}
}
return array;
};
const test = (fn, iterations) => {
const times = [];
for (let i = 0; i < iterations; i++) {
const start = performance.now();
fn();
times.push(performance.now() - start);
}
console.log(times);
console.log(times.reduce((sum, x) => sum + x, 0) / times.length);
}
const createData = () => Array.from({ length: 9000000 }, (_, i) => i + 1);
const testIterator = (data) => () => toArray(map(filter(arrayIterator(data), x => x % 2 === 0), x => x * 2))
test(testIterator(createData()), 10);
测试函数的输出非常奇怪和出乎意料 - 第一个测试 运行 的执行速度始终比所有其他 运行 快两倍。结果之一,其中数组包含所有执行时间,数字是平均值(我在 Node 上 运行):
[
147.9088459983468,
396.3472499996424,
374.82447600364685,
367.74555300176144,
363.6300039961934,
362.44370299577713,
363.8418449983001,
390.86111199855804,
360.23125199973583,
358.4788999930024
]
348.6312940984964
使用 Deno 运行time 可以观察到类似的结果,但是我无法在其他 JS 引擎上重现此行为。 V8 背后的原因是什么?
环境: 节点 v13.8.0,V8 v7.9.317.25-node.28, Deno v1.3.3、V8 v8.6.334
(此处为 V8 开发人员。)简而言之:内联或缺乏内联,由引擎启发式决定。
对于优化编译器,内联被调用的函数可以带来显着的好处(例如:避免调用开销,有时使常量折叠成为可能,或消除重复计算,有时甚至为额外的内联创造新的机会),但是代价是:它使编译本身变慢,并且增加了以后由于某些假设不成立而不得不丢弃优化代码(“去优化”)的风险。什么都不内联会浪费性能,内联所有东西都会浪费性能,内联完全正确的功能需要能够预测程序的未来行为,这显然是不可能的。所以编译器使用启发式方法。
V8 的优化编译器目前有一个启发式内联函数,仅当它始终是在特定位置调用的相同函数时。在这种情况下,这是第一次迭代的情况。随后的迭代然后创建新的闭包作为回调,从 V8 的角度来看,它们是新函数,因此它们不会被内联。 (V8 实际上知道一些高级技巧,允许它 de-duplicate 在某些情况下来自同一源的函数实例并无论如何内联它们;但在这种情况下这些不适用 [我不确定为什么])。 =21=]
所以在第一次迭代中,所有内容(包括 x => x % 2 === 0
和 x => x * 2
)都被内联到 toArray
中。从第二次迭代开始,情况不再如此,而是生成的代码执行实际的函数调用。
这可能没问题;我猜想在大多数实际应用中,差异几乎无法测量。 (减少测试用例往往会使这种差异更加突出;但是根据对小型测试的观察来更改较大应用程序的设计通常不是花费时间的最有效方式,最坏的情况下会使事情变得更糟。)
此外,hand-optimizing engines/compilers 的代码很难平衡。我通常建议 而不是 这样做(因为引擎会随着时间的推移而改进,而使您的代码更快确实是他们的工作);另一方面,显然存在更高效的代码和更低效的代码,为了最大的整体效率,每个相关人员都需要尽自己的一份力量,也就是说,您最好尽可能简化引擎的工作。
如果您确实想要 fine-tune 执行此操作,您可以通过分离代码和数据来实现,从而确保始终调用相同的函数。例如像你的代码的这个修改版本:
const ITERATION_END = Symbol('ITERATION_END');
class ArrayIterator {
constructor(array) {
this.array = array;
this.index = 0;
}
next() {
if (this.index >= this.array.length) return ITERATION_END;
return this.array[this.index++];
}
}
function arrayIterator(array) {
return new ArrayIterator(array);
}
class MapIterator {
constructor(source, modifier) {
this.source = source;
this.modifier = modifier;
}
next() {
const value = this.source.next();
return value === ITERATION_END ? value : this.modifier(value);
}
}
function map(iterator, selector) {
return new MapIterator(iterator, selector);
}
class FilterIterator {
constructor(source, predicate) {
this.source = source;
this.predicate = predicate;
}
next() {
let value = this.source.next();
while (value !== ITERATION_END && !this.predicate(value)) {
value = this.source.next();
}
return value;
}
}
function filter(iterator, predicate) {
return new FilterIterator(iterator, predicate);
}
function toArray(iterator) {
const array = [];
let value;
while ((value = iterator.next()) !== ITERATION_END) {
array.push(value);
}
return array;
}
function test(fn, iterations) {
for (let i = 0; i < iterations; i++) {
const start = performance.now();
fn();
console.log(performance.now() - start);
}
}
function createData() {
return Array.from({ length: 9000000 }, (_, i) => i + 1);
};
function even(x) { return x % 2 === 0; }
function double(x) { return x * 2; }
function testIterator(data) {
return function main() {
return toArray(map(filter(arrayIterator(data), even), double));
};
}
test(testIterator(createData()), 10);
观察热路径上如何不再有动态创建的函数,以及“public接口”(即arrayIterator
、map
、filter
的方式, and toArray
compose) 和之前完全一样,只有 under-the-hood 细节有变化。为所有函数命名的一个好处是您可以获得更有用的分析输出 ;-)
精明的读者会注意到,此修改只会转移问题:如果您的代码中有多个地方调用 map
和 filter
的 modifiers/predicates,那么内联性问题会再次出现。正如我上面所说:微基准测试往往具有误导性,因为真实的应用程序通常具有不同的行为...
(FWIW,这与
为了补充这项调查,我将 OP 的原始代码与 jmrk 建议的声明为单独函数的谓词和选择器函数与其他两个实现进行了比较。所以,这段代码有三种实现方式:
- 带有谓词和选择器函数的 OP 代码分别声明为命名函数(非内联)。
- 使用标准
array.map()
和.filter()
(你会认为这会因为额外创建中间数组而变慢) - 使用在一次迭代中同时执行过滤和映射的自定义迭代
OP 在节省时间和加快速度方面的尝试实际上是最慢的(平均而言)。自定义迭代最快。
我想这里的教训是,如何使用优化编译器使事情变得更快并不一定是直观的,所以如果你正在调整性能,你必须衡量“典型”的做事方式(这可能会受益来自最多的优化)。
另外,请注意,在方法 #3 中,前两次迭代最慢,然后它变得更快——与原始代码相反的效果。去图吧。
结果在这里:
[
99.90320014953613,
253.79690098762512,
271.3091011047363,
247.94990015029907,
247.457200050354,
261.9487009048462,
252.95090007781982,
250.8520998954773,
270.42809987068176,
249.340900182724
]
240.59370033740998
[
222.14270091056824,
220.48679995536804,
224.24630093574524,
237.07260012626648,
218.47070002555847,
218.1493010520935,
221.50559997558594,
223.3587999343872,
231.1618001461029,
243.55419993400574
]
226.01488029956818
[
147.81360006332397,
144.57479882240295,
73.13350009918213,
79.41700005531311,
77.38950109481812,
78.40880012512207,
112.31539988517761,
80.87990117073059,
76.7899010181427,
79.79679894447327
]
95.05192012786866
代码在这里:
const { performance } = require('perf_hooks');
const ITERATION_END = Symbol('ITERATION_END');
const arrayIterator = (array) => {
let index = 0;
return {
hasValue: true,
next() {
if (index >= array.length) {
this.hasValue = false;
return ITERATION_END;
}
return array[index++];
},
};
};
const customIterator = (valueGetter) => {
return {
hasValue: true,
next() {
const nextValue = valueGetter();
if (nextValue === ITERATION_END) {
this.hasValue = false;
return ITERATION_END;
}
return nextValue;
},
};
};
const map = (iterator, selector) => customIterator(() => {
const value = iterator.next();
return value === ITERATION_END ? value : selector(value);
});
const filter = (iterator, predicate) => customIterator(() => {
if (!iterator.hasValue) {
return ITERATION_END;
}
let currentValue = iterator.next();
while (iterator.hasValue && currentValue !== ITERATION_END && !predicate(currentValue)) {
currentValue = iterator.next();
}
return currentValue;
});
const toArray = (iterator) => {
const array = [];
while (iterator.hasValue) {
const value = iterator.next();
if (value !== ITERATION_END) {
array.push(value);
}
}
return array;
};
const test = (fn, iterations) => {
const times = [];
let result;
for (let i = 0; i < iterations; i++) {
const start = performance.now();
result = fn();
times.push(performance.now() - start);
}
console.log(times);
console.log(times.reduce((sum, x) => sum + x, 0) / times.length);
return result;
}
const createData = () => Array.from({ length: 9000000 }, (_, i) => i + 1);
const cache = createData();
const comp1 = x => x % 2 === 0;
const comp2 = x => x * 2;
const testIterator = (data) => () => toArray(map(filter(arrayIterator(data), comp1), comp2))
// regular array filter and map
const testIterator2 = (data) => () => data.filter(comp1).map(comp2);
// combine filter and map in same operation
const testIterator3 = (data) => () => {
let result = [];
for (let value of data) {
if (comp1(value)) {
result.push(comp2(value));
}
}
return result;
}
const a = test(testIterator(cache), 10);
const b = test(testIterator2(cache), 10);
const c = test(testIterator3(cache), 10);
function compareArrays(a1, a2) {
if (a1.length !== a2.length) return false;
for (let [i, val] of a1.entries()) {
if (a2[i] !== val) return false;
}
return true;
}
console.log(a.length);
console.log(compareArrays(a, b));
console.log(compareArrays(a, c));