前端内存优化的探索与实践
grandPang 2019-11-11
引言
标注是地图最基本的元素之一，标明了地图每个位置或线路的名称。在地图 JSAPI 中，标注的展示效果及性能也是需要重点解决的问题。
新版地图标注的设计中，引入了 SDF （ signed distance field）重构了整个标注部分的代码。新的方式需要把标注的位置偏移，避让，三角拆分等全部由前端进行计算，不仅计算量激增，内存的消耗也成了重点关注的问题之一。
例如，3D 场景下需要构建大量的顶点坐标，一万左右的带文字的标注，数据量大约会达到 8 （attributes） 5 (1个图标 + 4个字) 6（个顶点） 1E4 ，约为 250w 个顶点，使用 Float32Array 存储，需要的空间约为 2.5E6 4（byte）空间(海量地图标注 DEMO)。前端这样大量的存储消耗，需要对内存的使用十分小心谨慎。于是借此机会研究了一下前端内存相关的问题，以便在开发过程中做出更优的选择，减少内存消耗，提高程序性能。
01 前端内存使用概述
首先我们来了解一下内存的结构。
内存结构
内存分为堆（heap）和栈（stack），堆内存存储复杂的数据类型，栈内存则存储简单数据类型，方便快速写入和读取数据。在访问数据时，先从栈内寻找相应数据的存储地址，再根据获得的地址，找到堆内该变量真正存储的内容读取出来。
在前端中，被存储在栈内的数据包括小数值型，string ，boolean 和复杂类型的地址索引。
所谓小数值数据(small number), 即长度短于 32 位存储空间的 number 型数据。
一些复杂的数据类型，诸如 Array，Object 等，是被存在堆中的。如果我们要获取一个已存储的对象 A，会先从栈中找到这个变量存储的地址，再根据该地址找到堆中相应的数据。如图：
简单的数据类型由于存储在栈中，读取写入速度相对复杂类型（存在堆中）会更快些。下面的 Demo 对比了存在堆中和栈中的写入性能：
实验环境1：
mac OS/firefox v66.0.2
对比结果：
实验环境2：
mac OS/safari v11.1(13605.1.33.1.2)
对比结果：
在每个函数运行 10w 次的数据量下，可以看出在栈中的写入操作是快于堆的。
对象及数组的存储
在JS中，一个对象可以任意添加和移除属性，似乎没有限制（实际上需要不能大于 2^32 个属性）。而JS中的数组，不仅是变长的，可以随意添加删除数组元素，每个元素的数据类型也可以完全不一样，更不一般的是，这个数组还可以像普通的对象一样，在上面挂载任意属性，这都是为什么呢？
Object 存储
首先了解一下，JS是如何存储一个对象的。
JS在设计复杂类型存储的时候面临的最直观的问题就是，选择一种数据结构，需要在读取，插入和删除三个方面都有较高的性能。
数组形式的结构，读取和顺序写入的速度最快，但插入和删除的效率都非常低下；
链表结构，移除和插入的效率非常高，但是读取效率过低，也不可取；
复杂一些的树结构等等，虽然不同的树结构有不同的优点，但都绕不过建树时较复杂，导致初始化效率低下；
综上所属，JS 选择了一个初始化，查询和插入删除都能有较好，但不是最好的性能的数据结构 -- 哈希表。
哈希表
哈希表存储是一种常见的数据结构。所谓哈希映射，是把任意长度的输入通过散列算法变换成固定长度的输出。
对于一个 JS 对象，每一个属性，都按照一定的哈希映射规则，映射到不同的存储地址上。在我们寻找该属性时，也是通过这个映射方式，找到存储位置。当然，这个映射算法一定不能过于复杂，这会使映射效率低下；但也不能太简单，过于简单的映射方式，会导致无法将变量均匀的映射到一片连续的存储空间内，而造成频繁的哈希碰撞。
关于哈希的映射算法有很多著名的解决方案，此处不再展开。
哈希碰撞
所谓哈希碰撞，指的是在经过哈希映射计算后，被映射到了相同的地址，这样就形成了哈希碰撞。想要解决哈希碰撞，则需要对同样被映射过来的新变量进行处理。
众所周知，JS 的对象是可变的，属性可在任意时候（大部分情况下）添加和删除。在最开始给一个对象分配内存时，如果不想出现哈希碰撞问题，则需要分配巨大的连续存储空间。但大部分的对象所包含的属性一般都不会很长，这就导致了极大的空间浪费。
但是如果一开始分配的内存较少，随着属性数量的增加，必定会出现哈希碰撞，那如何解决哈希碰撞问题呢？
对于哈希碰撞问题，比较经典的解决方法有如下几种：
- 开放寻址法
- 再哈希法
- 拉链法
这几种方式均各有优略，由于本文不是重点讲述哈希碰撞便不再缀余。
在 JS 中，选择的是拉链法解决哈希碰撞。所谓拉链法，是将通过一定算法得到的相同映射地址的值，用链表的形式存储起来。如图所示（以倾斜的箭头表明链表动态分配，并非连续的内存空间）：
映射后的地址空间存储的是一个链表的指针，一个链表的每个单元，存储着该属性的 key, value 和下一个元素的指针；
这种存储的方式的好处是，最开始不需要分配较大的存储空间，新添加的属性只要动态分配内存即可；
对于索引，添加和移除都有相对较好的性能；
通过上述介绍，也就解释了这个小节最开始提出的为何JS 的对象如此灵活的疑问。
Array 存储
JS 的数组为何也比其他语言的数组更加灵活呢？因为 JS 的 Array 的对象，就是一种特殊类型的数组！
所谓特殊类型，就是指在 Array 中，每一个属性的 key 就是这个属性的 index；而这个对象还有 .length 属性；还有 concat, slice, push, pop 等方法；
于是这就解释了：
- 为何 JS 的数组每个数据类型都可以不一样？因为他就是个对象，每条数据都是一个新分配的类型连入链表中；
- 为何 JS 的数组无需提前设置长度，是可变数组？答案同上；
- 为何数组可以像 Object 一样挂载任意属性？因为他就是个对象；
等等一系列的问题。
内存攻击
当然，选择任何一种数据存储方式，都会有其不利的一面。这种哈希的拉链算法在极端情况下也会造成严重的内存消耗。
我们知道，良好的散列映射算法，可以讲数据均匀的映射到不同的地址。但如果我们掌握了这种映射规律而将不同的数据都映射到相同的地址所对应的链表中去，并且数据量足够大，将造成内存的严重损耗。读取和插入一条数据会中了链表的缺陷，从而变得异常的慢，最终拖垮内存。这就是我们所说的内存攻击。
构造一个 JSON 对象，使该对象的 key 大量命中同一个地址指向的列表，附件为 JS 代码，只包含了一个特意构造的对象（引用出处），图二为利用 Performance 查看的性能截图：
相同 size 对象的 Performance 对比图：
根据 Performance 的截图来看，仅仅是 load 一个 size 为 65535 的对象，竟然足足花费了 40 s！而相同大小的非共计数据的运行时间可忽略不计。
如果被用户利用了这个漏洞，构建更长的 JSON 数据，可以直接把服务端的内存打满，导致服务不可用。这些地方都需要开发者有意识的避免。
但从本文的来看，这个示例也很好的验证了我们上面所说的对象的存储形式。
02 视图类型（连续内存）
通过上面的介绍与实验可以知道，我们使用的数组实际上是伪数组。这种伪数组给我们的操作带来了极大的方便性，但这种实现方式也带来了另一个问题，及无法达到数组快速索引的极致，像文章开头时所说的上百万的数据量的情况下，每次新添加一条数据都需要动态分配内存空间，数据索引时都要遍历链表索引造成的性能浪费会变得异常的明显。
好在 ES6 中，JS 新提供了一种获得真正数组的方式：ArrayBuffer，TypedArray 和 DataView
ArrayBuffer
ArrayBuffer 代表分配的一段定长的连续内存块。但是我们无法直接对该内存块进行操作，只能通过 TypedArray 和 DataView 来对其操作。
TypedArray
TypeArray 是一个统称，他包含 Int8Array / Int16Array / Int32Array / Float32Array等等。
拿 Int8Array 来举例，这个对象可拆分为三个部分：Int、8、Array
首先这是一个数组，这个数据里存储的是有符号的整形数据，每条数据占 8 个比特位，及该数据里的每个元素可表示的最大数值是 2^7 = 128 , 最高位为符号位。
// DataView
var arrayBuffer = new ArrayBuffer(8 * 10);
var dataView = new DataView(arrayBuffer);
dataView.setInt8(0, 2);
dataView.setFloat32(8, 65535);
// 从偏移位置开始获取不同数据
dataView.getInt8(0);
// 2
dataView.getFloat32(8);
// 65535
// 普通数组
function arrayFunc(){
}
// dataView
function dataViewFunc(){
}
// typedArray
function typedArrayFunc(){
}
// main
var worker = new Worker('./worker.js');
worker.onmessage = function getMessageFromWorker(e){
};
var msg = [1, 2, 3];
worker.postMessage(msg);
// worker
onmessage = function(e){
};
function increaseData(data){
}
var worker = new Worker('./sharedArrayBufferWorker.js');
worker.onmessage = function(e){
// 传回到主线程已经被计算过的数据
// 和传统的 postMessage 方式对比，发现主线程的原始数据发生了改变
};
var sharedArrayBuffer = new SharedArrayBuffer(3);
var int8Array = new Int8Array(sharedArrayBuffer);
int8Array[0] = 1;
int8Array[1] = 2;
int8Array[2] = 3;
worker.postMessage(sharedArrayBuffer);
onmessage = function(e){
};
function increaseData(arrayData){
}
作者：高德技术小哥
本文为云栖社区原创内容，未经允许不得转载。
