优化高性能JS代码的几个要点，以及背后的原理
写在前面
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) { // 提供越界检查的数组getterif (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];}}
startsum 99980001良好的局部性: 159.879mssum 99980001坏的局部性: 3420.815msend
// 本代码可直接复制到浏览器运行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');}();
小结
评论