阿里：图可视化解决方案性能优化

在大规模数据场景下，海量节点/边的计算和渲染都会引发浏览器的性能问题。在传统场景下，计算由CPU完成，渲染则使用Canvas2D或者SVG。随着浏览器提供的API⽇益丰富，我们有机会使用更强大的计算和渲染能⼒解决极端场景下的性能问题。02.背景介绍的场景下，性能问题通常来自三⽅面：计算、渲染和交互。当性能问题凸显时，浏览器长时间未响应会造成用户⽆法正常进⾏其他交互，体验很差。图领域中的常⻅计算任务按类型可分成布局计算和分析算法两类，当数据量达到⼀定规模，CPU⽆法承受这种高算法复杂度，例如：Bellman-ford单源最短路径算法，复杂度为O(V*E)。Fruchterman布局算法，复杂度为O(V*E*迭代次数)。然而这些算法通常都是可线程级并⾏的，特别适合由GPU完成，在浏览器端可以借助WebGL和WebGPU实现。解决渲染性能问题可以从多⽅面⼊⼿：按需渲染，对视⼝外元素进行裁剪：不同渲染技术采用不同做法，例如Canvas2D使用“局部渲染”、3D场景下可以使用基于视锥的裁剪、instancing绘制等优化⼿段。我们在G与GWebGPU中默认开启了这个特性。使用更先进的图形渲染API：Canvas2D和SVG的易用性决定了它们适合大部分场景，但在⼀些海量数据场景下，WebGL和WebGPU这样更底层的渲染API会有更好的表现。随着前端应用⽇益复杂，浏览器主线程会非常忙碌，在完成以上计算和渲染⼯作前都⽆法响应用户的其他交互，造成卡顿感(jank)。可以使用OffscreenCanvas解决这⼀问题，将计算和渲染交由WebWorker场景中的对象也⼗分关键。我们在G和GWebGPU中使用了高效的包围盒计算和color-based拾取来解决这⼀问题。2.1名词解释GPGPU：General-purposecomputingongraphicsprocessingunits，即充分利用GPU的强大并⾏计算能⼒完成渲染之外的其他通用计算任务。CUDAComputeUnifiedDeviceArchitecture架构，由Nvidia提出，开发者可以使用C、Java、Python等语⾔编写自⼰的并⾏计算任务代码。nvGraph：基于CUDA提供了大量可并⾏的图分析算法(PageRank、SSSP、SSWP等)，可⽀持20亿条边的数据规模。核函数：即Kernel，每个线程执⾏的计算任务。2Culling剔除，按需绘制视口中的可见对象，减轻渲染压⼒，在2D和3D渲染⽅案中有不同实现。OffscreenCanvas：离屏渲染技术，在浏览器WebWorker线程完成渲染任务，减轻主线程压⼒避免阻塞交互。03.解决方案我们的解决⽅案将从高性能计算、渲染和交互三⽅面展开。3.1高性能计算下面我们将介绍：GPGPU的概念和GPU编程模型，其中涉及线程、线程组和GPU内存模型。GPU内存模型和高效的图存储。布局和分析算法，各举⼀例。3.1.1GPGPU的概念由于硬件结构不同，GPU与CPU擅长执行不同类型的计算任务。尤其在单指令流多数据流(SIMD)场景下，GPU的运算速度远超CPU，并且这种差距还在不断拉大[1]。⼈们很自然想到把GPU的并行计算能⼒推广到渲染之外的通用场景，因此GPGPU概念被提出。早期的经典系列书籍GPUGems中就收录了大量通用计算领域的实践，包括了视频解码、实时加解密、图片压缩、随机数生成、仿真等等。现代的GPU更是针对特定类型的计算任务设计硬件。例如Nvidia的Turing架构中就包含了专门进行张量计算的TensorCore和光线追踪计算的RTCore[2]。3为了降低开发者⾯向GPU编程的⻔槛，Nvidia提出了CUDA(统⼀计算架构)，开发者可以使用C、Java、Python等语⾔编写自⼰的计算任务代码。在图领域，Nvidia的nvGRAPH基于CUDA提供了大量可并⾏的图分析算法(PageRank、SSSP、SSWP等)，可支持20亿条边的数据规模。刨除针对N卡特定的优化，我们能否将这些成熟的图分析算法实现移植到Web端呢？事实上，在Web端已经有了很多优秀的GPGPU实践，例如：tensorflow.js用户通过API组合调用完成针对张量的计算任务。GPU.js用户使用JS编写简单的计算任务。Stardust.js用户使用Mark语⾔定义计算任务，实现Sanddance效果。从实现⻆度看，以上方案都使用WebGL图形API来模拟并不支持的ComputeShader(我们把GPU能看懂的程序称为Shader)，仍存在以下问题：1.缺乏针对图计算场景的支持。以tensorflow.js为例，即使我们能使用张量(邻接表)存储⼀个有向图，内置的算⼦也无法理解其中的节点/边的属性数据，直接应用计算显然导致错误。2.并⾏计算中⼀些高级特性的缺失，尤其是线程间共享内存和同步，无法用WebGL模拟。导致部分并⾏算法无法迁移。3.前端开发者迁移算法成本很高。除了缺少并⾏算法的编写经验，Shader语法也有不⼩的学习成本。因此，⼀方⾯我们需要表达能⼒更强的计算/渲染API(WebGPU)，另⼀方⾯需要深⼊理解图存储和具体的算法实现。当然如果能像CUDA⼀样降低前端开发者的编程⻔槛就再好不过了，这也正是GWebGPU的努⼒方向之⼀。3.1.2线程和线程组对于前端开发者来说，鲜有机会在浏览器中实现⼀个可线程并⾏的算法。而在GPU编程模型中线程、共享内存和同步都是⾮常重要的概念。从逻辑视图[2]上看：开发者在CPU侧通过API(例如dispatch(x,y,z))分配⼀个3维的线程⽹格(Grid)4指定指定numthreads(x,y,网格中包含了许多线程组(WorkGroup、ThreadGroup、ThreadBlock、本地工作组不同叫法)，每⼀个线程组中又包含了许多线程，numthreads(x,y,zz)我们的核函数最终会运行在每⼀个线程上。对于每⼀个线程，可以获取自己在线程组中的3维坐标，也可以获取线程组在整个线程网格中的3维坐标，以此映射到不同的数据上从硬件视图上看，网格、线程组与线程有如下对应关系。GPU上有很多个SM(StreamingMultiprocessor)，每⼀个SM包含了很多核心，下图为CUDA实现的对应关系[2]：在实际执行时，网格中每个线程组交给⼀个SM执行，其中每个核心负责⼀个线程的运行。每个线程负责执行我们编写的核函数，传入不同的数据完成并行计算。3.1.3高效的图存储在讨论如何高效地存储⼀个图之前，我们需要对GPU内存结构有初步的了解。由于最初针对图形渲染设计，GPU使用⼀种被称作“纹理”的内存结构存储数据，在我们的场景中简单理解为⼀维数组即可。数组中每⼀个元素可视作⼀个长度为4的向量，包含rgba四个分量。因此我们需要使用线性结构来表示图。使用邻接矩阵(adjacencymatrix)[11]是最直接的，但对于⼀个稀疏图来说会造成很大的存储空间浪费。邻接表(adjacencylist)[4]则要紧凑的多，整个结构分成两部分0->8和来了。00->6这两条边就表示出在实际存储中⼜有很多可以优化点，在进⼀步压缩GPU内存的同时，也考虑了对于顺序读的优化，如下图所示[7]：将点和边的数组合成⼀个充分利用每个向量的RGBA四个分量。在节点数据部分，分别存储每个节点的位置(xy)、边的偏移量(offset)和边的数目(length)。在边的数据部分存储的是终点的索引这个通用的结构需要根据不同的图算法进行调整，例如在我们的最短路径算法中，并不关心节点的位置，同时在每条边的数据中，除了终点索引还需要存储边的权重(weight)。3.1.4布局计算我们以Fruchterman布局算法为例。简单来说在每⼀次迭代中，每⼀个节点的位置都需要和其他节点/边计算斥⼒和引⼒，再加上重⼒完成该轮迭代自身位置的更新，最终重复多次迭代达到稳定状态，下图来自[7]。在G6中有该布局算法的CPU版实现，尽管节点数目并不多(本例中为200+)，但每个节点需要和其他节点进行大量计算，并且需要进行⼀定次数的迭代才能达到稳定(本例中为8000次)。因此性能问题主要出在计算而非渲染上。我们让每⼀个线程组负责计算⼀个节点的位置，因此可以设置⼀个⼀维的线程网格，长度等于节点数目。具体实现可以参考G6GPULayout，基本上是串行算法的简单移植。3.1.5图分析算法这里我们只举图分析算法中的⼀个例子：最短路径问题。这是图论研究中的⼀个经典算法问题，旨在寻找图(由节点和路径组成的)中两节点之间的最短路径。其中⼀种算法具体的形式为：确定起点的最短路径问题，简称为SSSP(Singlesourceshortestpath)。7例如下图[6]展示了以的节点。例如上图中A为起点，到所有点的最短路径。除了起点到所有点的路径值，也需要输出上⼀跳点的上⼀跳为D：在图G(V,E)(V是顶点数目，E是边的数目)中，Bellman-Ford算法对所有边进行V-1次“松串行算法[5]伪代码如上，JS实现也并不困难：改造成并行算法时，我们指定每个线程组大⼩为[16,1,V核函数计算逻辑包含如下步骤：1.每个线程需要从全局数组中拷贝自⼰处理的节点数据到共享内存中，涉及线程组内同步3.完成计算后使用共享内存更新全局数组中当前节点数据(当前的最⼩距离和前序节点索引)以下示例测试了⼀个拥有1k+点和2k+边的图，在ChromeCanary中的运行效果，测试数据来自netscience.out3.2高性能渲染在G的Canvas2D实现中，我们已经使用了局部渲染。而在3D场景下，使用更底层的图形API意味着我们有更多优化方案可以选用：裁剪/剔除。Canvas2D的局部渲染也是这⼀思路的应用。在3D场景中，基于视锥的裁剪是渲染引擎常用的手段。instancing绘制。经过裁剪，我们得到了待渲染对象的最小集合，instancing绘制能最大程度减少drawcall。这也是使用底层渲染API的优势之⼀。使用更现代化的图形API。受制于老旧的底层OpenGLES，WebGL1/2存在明显的性能瓶颈。如果不考虑兼容性，依赖更现代化API(Vulkan/Metal/DX)的WebGPU无疑是最好的选择。3.2.1裁剪/剔除Culling(剔除)能够按需渲染可视范围内的渲染对象。OcclusionCulling(遮挡剔除)，需要依赖高级的图形API(例如WebGL2)，在3D引擎中更⼴泛使用的剔除技术其实是FrustumCulling(视锥剔除)和FaceCulling(面剔除)，后者实现又比较简单，因此我们着重介绍视锥剔除[8]。在GWebGPU中我们实现视锥剔除时应用了以下技术：1.基础相交测试thebasicintersectiontest2.平面⼀致性测试theplane-coherencytest3.标记masking3.2.2instancing绘制完成了裁剪，我们得到了待渲染对象的最小集合，在直接调用底层渲染API(WebGL、WebGPU)逐个绘制之前，仍有机会做进⼀步优化。在图场景中我们经常需要绘制大量的同类对象，例如1000个节点，每个节点除了位置其他属性(颜色、大小)都完全⼀致，直接调用底层绘制API将产生1000个drawcall，而WebGL和WebGPU提供了instancing绘制命令，只产生⼀个drawcall。3.2.3使用更先进的渲染API抛开众多新特性，仅仅使用WebGL2，相比WebGL1就能带来约7%的性能提升[9]。而WebGPU底层使用更现代化的Vulkan/Metal/DX，在带来更丰富特性的同时，性能提升也十分明显[10]。目前可以在Chrome/EdgeCanary、SafariPreview中体验WebGPU。3.3高性能交互3.3.1OffscreenCanvas以上⼀⼩节提到的Fruchterman布局算法为例，在8000次迭代计算完成前，主线程会处于阻塞状态，呢？这里我们需要引⼊OffscreenCanvas技术，从名字中可以看出，这是⼀种离屏渲染技术，可以在WebWorker中完成渲染，将结果同步给主线程。目前WebGPU尚不⽀持在OffscreenCanvas中渲染/计算，但WebGL中可以使用。事实上Babylon.js已经⽀持开发者在Worker中创建引擎完成渲染，我们在实现中也参考了这种用法，并没有内置Worker实现，而是将选择权交给开发者。应用该技术之后主线程不会出现“卡住”的情景了，在Worker计算完成前我们可以展示⼀个loading组件。在G6官⽹中也有对应的例⼦：GPULayoutwithWebWorker。3.3.2拾取3D引擎常用的拾取技术通常有两种：RayPicking和PixelPicking。前者从鼠标点击处沿着投影⽅向发射⼀根射线，通过包围盒碰撞检测获取到接触到的第⼀个对象，后续就可以进行选中对象的高亮甚至是跟随移动了，以上运算均在CPU侧完成。但是在海量数据场景下，计算每个要素的包围盒开销很大，因此在GPU中完成PixelPicking更加适合。我们在GWebGPU中默认开启了这⼀特性。04.总结的图场景下，性能问题通常来自三⽅面：计算、渲染和交互。在定位性能瓶颈后，我们可以采用针对性的优化⽅案。在底层计算/渲染引擎(G、GWebGPU)的实现