大数据图表业务技术基础

我们定义一下什么是大数据图表。所谓大数据图表，是指在 5000 分组以上仍能不卡顿、不崩溃地显示图表的技术。我们定义数据规模为 1kw，设定这个技术标准的考量是，我们想做一个性能最高的图表应用（忽略广告法）。

这在性能以及内存上都有极大挑战。这篇文章主要是向大家揭示我们在应用开发过程中不能忽略的计算机基础知识，主要包括时间复杂度与空间复杂度。

对时间复杂度的理解

这一节很重要。读大学的时候，第一节数据结构课非常重要，即对时间复杂度的理解，这就决定了我们应该怎么优化自己的程序。有可能仅仅几行代码带来的效果，就会比没有意义地优化一年更明显。

我们知道，算法复杂度分为 O(N)、O(LogN)、O(N2)。我看了很多文章，都在强调一些技巧去提高代码的性能，这些技巧只能说仁者见仁，智者见智吧。比如说，数据类型固定时，尽可能使用 TypedArray 代替 JS 中的 Array，或者尽可能使用静态类结构。这些能够让我们的程序提高好几倍的性能。

但是我的想法是，提高两倍性能没多大意义，我们的硬件会越来越好的。在大数据设计下，只做了一个关键点：把不可能实现的渲染变成有可能。即全局仅允许 O(N)、O(LogN) 的算法。

任何一点错误的算法对全局都是毁灭性的，这些错误的算法遍布在了各种地方，Preact、Lodash、动画库。

比如说数组去重，老版本的 lodash 就有一些不够理想的写法。虽然它的程序看起来运行得很好，但是无论客户机器多强大，如果加到 1000w，它就扛不住了。

如果我们的程序能很自信地说出，我们能支持千万级别数据量了，那么比起只优化几倍性能，是不是更好一点。

对空间复杂度的理解

如果要使用严谨的定义空间占用情况，需要理解 I/O 和内存，还挺复杂的。

好了，用通俗不严谨的话讲：程序内部创建的就是内存，从外部拿来的就是 I/O。

比如用程序创建 JS、创建对象，就是内存。从磁盘，从数据库，从网络，从后端拿来的数据，那都是外存。

再来说说他们的特点，从外存读数据很慢，但是外存空间很大。在内存读数据很快，但是空间很小。

有两句话讲得好：

程序 = 算法 + 数据结构。
世界上的一切事物都是运动的。

我们程序的作用就是执行这条链路：把 I/O 数据读入内存，然后一步一步转换成不同的数据结构，当然也有可能把内部数据再写回外部数据。

为什么会OOM

内存过载

对于浏览器来说，一个 JS 引擎大致就是 4GB 的量级。我们可以理解成单个 Chrome 标签页下可用的内存容量不能无限增长。

先分享一个很有意思的公式，程序 = 算法 + 数据。如果从程序的实现角度出发，我们可以把算法理解成计算机指令，那这里的数据是什么呢。

这里声明了一万个变量，然后累加。程序的逻辑很容易翻译成 add 指令，但有一个问题，一次 add 的操作数可能就一个或两个，而且我们的寄存器数量是有限的。

为了完成程序设计，在程序运行开始时，就需要在内存中开辟一块空间，用来暂时保存计算过程中的中间变量，这块空间我们称为执行栈。在这一段函数执行完成以后，里面的数据会被销毁，再出栈，数据的计算结果“复制”给调用方。

但是很显然，这个模型有问题，就是我们的数据会直接被销毁，并不是所有的程序调用都是纯函数式的，也有可能需要在原始数据上进行修改。所以我们还需要引入一片所有执行栈共享的区域，即堆区。这块区域在程序执行完成以后，不会立刻被操作系统回收，在 JS 里，它由垃圾回收算法处理。

一般来说，在带垃圾回收的语言中，基本数据类型存放在栈区，引用类型的数据本身存放在堆区，栈上存放数据的引用。

内存回收

在 JS 中，栈区的内存是操作系统控制的，堆区的内存是由垃圾回收机制控制的。

垃圾回收算法需要解决三个核心问题：

有效的清除垃圾
整合内存空间
尽可能避免主线程阻塞

为了避免一次暂停太久（stop the world），我们可以把堆区分为新生区和老生区，新生区的垃圾回收是非常频繁的。

垃圾回收不是在总内存满了时进行的，也不是在函数执行完时完成的。而是在新生区满了后会触发副垃圾回收算法，在合适的时机触发主垃圾回收算法。

内存泄漏的定义

我们不需要的数据，没有被垃圾回收算法处理掉，即为内存泄漏。常规情况下，造成内存泄漏的情形，通常是因为较长生命周期的对象引用了较短生命周期的对象。内存泄漏导致的后果就是，当内存分配到 4GB 的时候，我们的程序就会走向崩溃。

内存泄露案例

全局性的单例
定时器或者任何全局性的 Observer、EventBus
Static 变量

内存泄露小结

对于一些显著性的例子，比如内存一下子崩了，其实是可以快速定位到的。而像细节性的问题，只能在设计代码的时候就考虑清楚，大家相互 review review 代码。

Web 算力基础

类型	概述	性能	兼容性
原生JS	CPU，用原生JS去实现计算	不适合大规模计算	语言迁移成本高
WebAssembly	CPU，跨浏览器的二进制格式	跨语言的便利性	具体的运行依赖不同版本浏览器
WebAssembly-SIMD	CPU，单条指令同时处理多个数据	数据级并行优化手段	Chrome 从 v91 版本开始支持
WebAssembly-Threads	CPU，通过WebWorker实现线程管理	多线程并行计算	SharedArrayBuffer兼容性存在问题
WebGL	GPU，提供Web浏览器中渲染高性能图形能力	初步利用GPU进行并行计算	WebGL2.0支持程度很弱
WebGPU	GPU，GPU硬件向Web开放的低级API	支持ComputeShader，大幅提升	浏览器都还在实验阶段

性能排序：WebGPU > WebGL > WebAssembly-Threads > WebAssembly > JS 兼容性排序：JS > WebGL > WebAssembly > WebAssembly-Threads > WebGPU

JS算力不足示例

在大数据场景，在应对 n^2 算法时，不得不采用其它方式加快运算速度。比如图表中点图的采样：我们有 100w 个圆，我们希望判断一个圆是否被其它圆覆盖掉。

四叉树加速运算

四叉树特别适合具有局部性特征的二维数据，比如空间场景中的物体分布、地理信息系统（GIS）的区域划分等。

借助GPU的算力

使用 GPU 计算，需要编写 WebGL 代码。找到了一个很有意思的库，GPU.js。它可以将现有的代码编译成 WebGL 代码，通过 GPU 进行计算。

对 GPU 计算的误解

GPU 计算弱于 CPU，GPU 计算弱于 CPU，GPU 计算弱于 CPU。

GPU 计算仅适用于可以拆解多个线程的任务。