优化高性能JS代码的几个要点,以及背后的原理
web前端开发
共 9189字,需浏览 19分钟
·
2020-10-23 15:03
写在前面
void lower(char *s) {
size_t i;
for (i = 0; i < strlen(s); i++) {
if (s[i] >= 'A' && s[i] <= 'Z')
s[i] -= ('A' - 'a');
}
}
模拟其他语言的行为 可以动态的计算数组的长度 提供错误检查 即使是o(1)的调用,也会有性能上的影响
版本1:
// 本代码可直接运行
function getFromArray(arr, index) { // 提供越界检查的数组getter
if (index < 0 || index >= arr.length) throw new Error('OUT OF INDEX' + index);
return arr[index]
}
function getLengthFromArray(arr) { // 得到数组长度
if (arr == null) throw new Error(arr + 'is not an Array.')
return arr.length; // 即使是常数级的函数调用,依旧产生开销
}
void function() {
console.log('start');
const numberOfElement = 9999999;
const arr = Array(numberOfElement).fill(2);
(function combine1() {
console.time('combine1');
let sum = 0;
for (let i = 0; i < getLengthFromArray(arr); i++) { // 每次循环都要重新计算长度
sum += getFromArray(arr, i); // 使用提供越界检查getter得到数组元素
}
console.log('sum', sum);
console.timeEnd('combine1');
}());
console.log('end');
}();
消除循环的低效率
(function combine2() {
// 可直接执行
console.time('combine2');
let sum = 0;
const len = getLengthFromArray(arr); // 消除每次循环对数组长度的计算
for (let i = 0; i < len; i++) {
sum += getFromArray(arr, i);
}
console.log('sum', sum);
console.timeEnd('combine2');
}());
减少多余的函数调用
(function combine3() {
/**
* 现在消除了每次循环对数组长度的计算
* 并且确定访问不会越界,不需要越界检查,直接访问数组
*/
console.time('combine3');
let sum = 0;
const len = getLengthFromArray(arr);
for (let i = 0; i < len; i++) {
sum += arr[i]; // 直接访问
}
console.log('sum', sum);
console.timeEnd('combine3');
}());
消除不必要的内存访问
1)对于一个函数,其内部变量一般存储在寄存器中,你可以把寄存器看成一个CPU和内存之间的一个缓存 2)程序访问寄存器的速度远快于访问内存 3)对于值为数组的变量,其在寄存器中的值是数组在内存中的地址,所以更改或访问其数据需要访问内存
(function combine4() {
let sum = [0]; // 负优化在这里,sum现在是个指针了
console.time('combine4');
const len = getLengthFromArray(arr);
for (let i = 0; i < len; i++) {
sum[0] += arr[i]; // 三次内存访问
}
console.log('sum', sum[0]);
console.timeEnd('combine4');
}());
读取sum[0] 读取arr[i] 写回sum[0] 两次读,一次写,总共三次
(function combine4_anothor() {
let sum = [0];
let tmp = 0; // 通过设计临时变量,减少内存访问次数
console.time('combine4_anothor');
const len = getLengthFromArray(arr);
for (let i = 0; i < len; i++) {
tmp += arr[i]; // 一次内存访问
}
sum[0] = tmp;
console.log('sum', sum[0]);
console.timeEnd('combine4_anothor');
}());
combine3: 15.298ms combine4: 28.701ms combine4_anothor: 17.618ms
使用循环展开
(function combine5() {
/**
* 利用循环展开
*/
let sum = 0;
console.time('combine5');
const len = getLengthFromArray(arr);
const limit = len - 1; //防止越界
let i;
for (i = 0; i < limit; i += 2) { // 步长为2的展开
sum += arr[i]; // 直接访问
sum += arr[i + 1];
}
for (; i < len; i++) { //处理剩余未访问的元素
sum += arr[i];
}
console.log('sum', sum);
console.timeEnd('combine5');
}());
再次分析性能瓶颈
let a = 1 + 1;
let b = 2 + 2;
let c = a + b;
let d = c + c;
1)我们都至少要访问arr数组 length次数 2)计算机对于 sum += arr[i] 执行必须是按序的,无论是否采用循环展开,因为每一次计算sum都依赖于上一次sum的计算值
提高代码并行性
(function combine5_another() {
/**
* 提高并行性
*/
console.time('combine5_another');
let sum = 0;
let tmp1 = 0;
const len = getLengthFromArray(arr);
const limit = len - 1; //防止循环展开后越界
let i;
for (i = 0; i < limit; i += 2) {
sum += arr[i]; // 直接访问
tmp1 += arr[i + 1];
}
for (; i < len; i++) { //处理剩余未访问的元素
sum += arr[i];
}
sum += tmp2;
console.log('sum', sum);
console.timeEnd('combine5_another');
}());
优化前: 47.267ms 优化后: 12.731ms
利用程序的局部性
时间局部性(已经被访问的数据(代码),很可能会被再次访问) 空间局部性(对于已经访问的数据(代码),其临近的数据(代码)很可能被访问)
const matrix = getMatrix(10, 10);
let sum = 0;
for (let row = 0; row < matrix.length; row++) {
for (let col = 0; col < matrix[0].length; col++) {
sum += matrix[row][col];
}
}
arr[0][0] -> 内存地址 0 arr[0][1] -> 内存地址 1 .... arr[0][9] -> 内存地址 9 arr[1][0] -> 内存地址 10 arr[1][1] -> 内存地址 11 ... arr[9][0] -> 内存地址 90 arr[9][1] -> 内存地址 91 ... arr[9][9] -> 内存地址 99
let sum = 0;
for (let col = 0; col < matrix[0].length; col++) {
for (let row = 0; row < matrix.length; row++) {
sum += matrix[row][col];
}
}
start
sum 99980001
良好的局部性: 159.879ms
sum 99980001
坏的局部性: 3420.815ms
end
// 本代码可直接复制到浏览器运行
void function() {
console.log('start');
const size = 9999;
const matrix = Array(size);
for (let i = 0; i < matrix.length; i++) {
matrix[i] = Array(size).fill(1);
}
(function goodVersion() {
console.time('良好的局部性');
let sum = 0;
for (let row = 0; row < matrix.length; row++) {
for (let col = 0; col < matrix[0].length; col++) {
sum += matrix[row][col];
}
}
console.log('sum', sum);
console.timeEnd('良好的局部性');
})();
(function worseVersion() {
console.time('坏的局部性');
let sum = 0;
for (let col = 0; col < matrix[0].length; col++) {
for (let row = 0; row < matrix.length; row++) {
sum += matrix[row][col];
}
}
console.log('sum', sum);
console.timeEnd('坏的局部性');
})();
console.log('end');
}();
小结
评论