In Yandex.Maps, a vector map consists of pieces called tiles. In fact, a tile is the indexed area of the map. The map is vector, so each tile contains many geometric primitives. Tiles are encoded from the server to the client, and all primitives must be processed before displaying. Sometimes it takes a considerable amount of time. A tile can contain more than 2 thousand polylines and polygons.
When processing primitives, performance is most important. If the tile is not prepared quickly enough, then the user will see it too late, and the next tiles will be delayed in the queue. To speed up processing, we decided to try the relatively new WebAssembly (Wasm) technology.
Using WebAssembly in Maps
Now most of the processing of primitives takes place in the background thread (Web Worker), which lives a separate life. This is done in order to unload the main thread as much as possible. Thus, when the code for showing the card is embedded on the service page, which can itself add a significant load, there will be less brakes. The downside is that you need to properly configure messaging between the main thread and the Web Worker.
The part of the processing taking place in the background thread consists essentially of two steps:
- The protobuf format that comes from the server is decoded .
- Geometries are generated and written to buffers.
At the second step, vertex and index buffers for WebGL are formed . These buffers are used when rendering as follows. A vertex buffer contains for each vertex its parameters, which are necessary to determine its position on the screen at a particular moment. An index buffer consists of triples of indices. Each triple means that the triangle with the vertices from the vertex buffer at the indicated indices should be displayed on the screen. Therefore, the primitive must be divided into triangles, which can also be a time-consuming task:
Obviously, during the second step, a lot of memory manipulation and mathematical calculations take place, because for the correct rendering of primitives, a lot of information about each vertex of the primitive is needed:
We were not happy with the performance of our JavaScript code. At this time, everyone began to write about WebAssembly, the technology was constantly evolving and improving. After reading the research, we suggested that Wasm could speed up our operations. Although we were not completely sure of this: it turned out to be difficult to find data on the use of Wasm in such a large project.
Wasm is also somewhat worse than TypeScript:
- We need to initialize a special module with the functions we need. This may lead to a delay before this functionality starts working.
- The size of the source code when compiling Wasm is much larger than in TS.
- Developers have to support an alternative version of the code execution, which is also written in a language atypical for the frontend.
However, despite all this, we risked rewriting part of our code using Wasm.
WebAssembly General Information
Wasm is a binary format; You can compile different languages into it, and then run the code in a browser. Often such pre-compiled code is faster than classic JavaScript. The code in WebAssembly format does not have access to the DOM elements of the page and, as a rule, is used to perform laborious computational tasks on the client.
We chose C ++ as the compiled language, since it is quite convenient and fast.
To compile C ++ in WebAssembly, we used emscripten . After installing it and adding it to a C ++ project, in order to get the module, you need to write the main project file in a certain way. For example, it might look like this:
#include <emscripten/bind.h> #include <emscripten.h> #include <math.h> struct Point { double x; double y; }; double sqr(double x) { return x * x; } EMSCRIPTEN_BINDINGS(my_value_example) { emscripten::value_object<Point>("Point") .field("x", &Point::x) .field("y", &Point::y) ; emscripten::register_vector<Point>("vector<Point>"); emscripten::function("distance", emscripten::optional_override( [](Point point1, Point point2) { return sqrt(sqr(point1.x - point2.x) + sqr(point1.y - point2.y)) ; })); }
Next, I will describe how you can use this code in your TypeScript project.
In the code, we define the Point structure and map it to the Point interface in TypeScript, in which there will be two fields - x and y, they correspond to the fields of the structure.
Further, if we want to return the standard vector container from C ++ to TypeScript, then we need to register it for the Point type. Then in TypeScript the interface with the necessary functions will correspond to it.
And finally, the code shows how to register your function in order to call it from TypeScript by the corresponding name.
Compile the file using emscripten and add the resulting module to your TypeScript project. Now, for an arbitrary emscripten module, we can write a common d.ts file in which useful functions and types are predefined:
declare module "emscripten_module" { interface EmscriptenModule { readonly wasmMemory: WebAssembly.Memory; readonly HEAPU8: Uint8Array; readonly HEAPF64: Float64Array; locateFile: (path: string) => string; onRuntimeInitialized: () => void; _malloc: (size: size_t) => uintptr_t; _free: (addr: size_t) => uintptr_t; } export default EmscriptenModule; export type uintptr_t = number; export type size_t = number; }
And we can write the d.ts file for our module:
declare module "emscripten_point" { import EmscriptenModule, {uintptr_t, size_t} from 'emscripten_module'; interface NativeObject { delete: () => void; } interface Vector<T> extends NativeObject { get(index: number): T; size(): number; } interface Point { readonly x: number; readonly y: number; } interface PointModule extends EmscriptenModule { distance: (point1: Point, point2: Point) => number; } type PointModuleUninitialized = Partial<PointModule>; export default function createModuleApi(Module: Partial<PointModule>): PointModule; }
Now we can write a function that will create Promise for module initialization, and use it:
import EmscriptenModule from 'emscripten_module'; import createPointModuleApi, {PointModule} from 'emscripten_point'; import * as pointModule from 'emscripten_point.wasm'; /** * Promisifies initialization of emscripten module. * * @param moduleUrl URL to wasm file, it could be encoded data URL. * @param moduleInitializer Escripten module factory, * see https://emscripten.org/docs/compiling/WebAssembly.html#compiler-output. */ export default function initEmscriptenModule<ModuleT extends EmscriptenModule>( moduleUrl: string, moduleInitializer: (module: Partial<EmscriptenModule>) => ModuleT ): Promise<ModuleT> { return new Promise((resolve) => { const module = moduleInitializer({ locateFile: () => moduleUrl, onRuntimeInitialized: function (): void { // module itself is thenable, to prevent infinite promise resolution delete (<any>module).then; resolve(module); } }); }); } const initialization = initEmscriptenModule( 'data:application/wasm;base64,' + pointModule, createPointModuleApi );
Now on this Promise we get our module along with the distance function.
Unfortunately, you cannot debug the Wasm code line by line in the browser. Therefore, it is necessary to write tests and run code on them like normal C ++, then you will have the opportunity of convenient debugging. Nevertheless, even in the browser, you have access to the standard cout stream, which will output everything to the browser console.
A project example from the article is available via this link , where you can see the settings for webpack.config and CMakeLists.
results
So, we rewrote part of our code and launched an experiment to consider parsing polygons and polygons. The diagram shows the median results for one tile for Wasm and JavaScript:
As a result, we got such relative coefficients for each metric:
As you can see from the pure parsing time of primitives and the decoding time of a tile, Wasm is more than four times faster. If you look at the total parsing time, then the difference is also significant, but it is still a little less. This is due to the cost of transferring data to Wasm and collecting the result. It is also worth noting that in the first tiles the overall gain is very high (in the first ten - more than five times). However, then the relative coefficient decreases to about three.
As a result, all this together helped to reduce the processing time of one tile in the background thread by 20–25%. Of course, this difference is not as great as the previous ones, but you need to understand that parsing polygons and polygons is not all tile processing.
If we talk about the need to initialize the module, because of it, about half of the users had a delay before parsing the first tile. The median delay is 188 ms. The delay happens only before the first tile, and the win in parsing is constant, so you can put up with a small pause at the start and not consider it a serious problem.
Another negative side is the size of the source code file. Gzip-compressed minified code for the entire vector map engine without Wasm is 85 KB, with Wasm - 191 KB. At the same time, only parsing of broken lines and rectangles is implemented in Wasm, and not all primitives that can be in a tile. Moreover, to decode protobuf, I had to choose a library implementation in pure C, with a C ++ implementation the size was even larger. This difference can be slightly reduced if you use the -Oz compiler flag instead of -O3 when compiling C ++, but it is still significant. In addition, with such a replacement, we lose performance.
Nevertheless, the size of the source did not significantly affect the speed of initialization of the card. Wasm is only worse on slow devices, and the difference is less than 2%. But the initial visible set of vector tiles in the implementation with Wasm was shown to users a little faster than with the JS implementation. This is due to the greater gain on the first processed tiles, while JS has not yet been optimized.
Thus, Wasm now is a worthy option if you are not comfortable with JavaScript code performance. At the same time, you can get less performance gain than us, or you can not get it at all. This is due to the fact that sometimes JavaScript itself works quite quickly, and in Wasm you need to transfer data and collect the result.
Our maps now run regular JavaScript. This is due to the fact that the gain in parsing is not so great against the general background, and due to the fact that only some types of primitives are implemented in Wasm. If this changes, perhaps we will begin to use Wasm. Another powerful argument against this is the complexity of assembly and debugging: supporting a project in two languages makes sense only when the performance gain is worth it.