Making the original

Front-end inherent programming thinking is single thread, such as JavaScript language single thread, browser JS thread and UI thread mutually exclusive and so on, Web Woker is HTML5 new ability, for the front-end to bring multi-threading ability. This article briefly records some practice schemes of using Web Worker in Sogou Map WebGL engine (hereinafter referred to as WebGL engine). Although this project died in the end and I resigned from Sogou, some experiences and practices in the process of developing WebGL engine are still worth writing.

Sogou Map WebGL engine uses Actor model to manage worker threads, so this article focuses on this and includes the following:

  • Why does the WebGL engine use Web workers and demand location for Worker threads
  • What is the Actor model and why is it appropriate for Web workers
  • Actor model of WebGL engine +Web Worker practice scheme

WebGL engine needs to position Web workers

What we see on a digital map is actually a patchwork of grids called tiles. According to the type of tiles, maps can be divided into two kinds, one is to use static images with CSS Mosaic, this is called raster map; The other is for WebGL to draw data as graphs, which are real geographic coordinates, called vector maps.

Most digital maps use Mercator coordinates, which are computed and converted to screen coordinates rather than actual latitude and longitude coordinates. This topic is outside the scope of this article and will be covered separately

Raster map is bitmap Mosaic, non-vector, scaling distortion, this is a disadvantage; The advantage is good performance because it doesn’t require a lot of calculation. Vector maps, on the other hand, require a lot of computation, but the advantage is that zooming is non-distorting and 3D is possible.

Most traditional websites do not use Web workers or have light requirements on Worker threads, such as pulling data or something. The best application scenario of Web Worker is compute-intensive business, while WebGL engine is the most compute-intensive application in the front-end field, which is reflected in two aspects:

  • Huge amount of data
  • The calculations are complex and intensive

For example, here is a map of China at Level 8:

Each red grid is a tile, and the data in the tile is actually a coordinate point and POI information (coordinates, documents, etc.). The work of WebGL engine includes the following:

  • Calculate tile coordinates according to current field of view;
  • Get tile data from background interface;
  • Rendering.

WebGL’s rendering pipeline is quite complex. In addition to the basic GPU rendering pipeline, there is also heavy work at the CPU level, such as data governance, caching, texture creation, matrix calculation, etc. I’ll write an introduction to the rendering pipeline later.

It seems very simple, just like “putting the elephant in the refrigerator”, which is divided into three steps, but in fact, the logic and calculation are very complicated, AND I will analyze them one by one in the following articles. This one will only select the content related to worker threads. The main tasks of Web workers are as follows:

  • Get tile data from the interface. This is relatively simple, there is nothing to say, to put it plainly is the network request, slightly special is the map tile data is relatively large, the request time is relatively long;

  • Parse tile data into data available for drawing. Tile data can be simply interpreted as geographic coordinates + rules, and the WebGL engine needs to convert geographic coordinates to screen coordinates, and then follow the rules to further convert them into the final drawable data. These rules include style (color /Line width, etc.), graphic category (Polygon/Line/Point, etc.), weight, etc. Weight is a special rule, representing the drawing priority of the graph, and the post-drawing with high priority. This is because in the drawing process of WebGL, the post-drawing graph will cover the existing graph at the same position.

  • Perform positioning calculation for POI. This is the most complex set of calculations in the entire map engine. The POI raw data in the tile is just the geographic coordinates of a point and the text, which needs to create a 2D canvas corresponding to the WebGL texture. The WebGL engine first needs to get the POI icon from the style file, then convert the text to the canvas size to calculate the size of the entire POI graph. For example, tianjin’s POI graph looks like this:

    Its final size is the size that includes the coordinate red dot icon + coordinate text (actually the canvas texture). However, this kind of POI is relatively simple, because there are almost no other POI around. For more complex POI, the relative position of text and icon needs to be dynamically adjusted according to the result of conflict detection. For example, the two POI in the following figure, “Microelectronics and nano electronic learning” POI text is below the icon. The text of the “Superconducting Quantum Information Processing Laboratory” POI can only be placed to the left, right or below, otherwise it will clash.

    The last step is to conduct conflict detection for all POIS in the field of vision and eliminate the entries with low priority and conflicting positions with high-priority POIS. There is a common algorithm for this kind of calculation in WebGIS industry, called R-tree algorithm, which is recommended by rbush, an open source tool available in JavaScript.

  • For example, the name of the road needs to be arranged along the road lines as shown in the figure below. This workload is also complicated, and I will write a separate article later.

Based on the above description, WebGL’s requirements for worker threads can be summarized into two points: network request and calculation. Once these tasks are handed over to the worker thread, the main thread can focus its resources on handling user interactions, thereby improving the user experience.

All of the above are premises and requirements. Next, we will talk about how to practice. First, we will introduce another protagonist today: Actor model.

What is the Actor model

The Actor model is an abstract concept designed to solve parallel computing problems. It is not a new word. It was born more than 40 years ago. The Actor model is designed to solve the problems of race condition, dead lock and other problems caused by shared variable state in parallel computing. For more details, see Wiki.

The Actor model has not been widely used in the front-end field, because before the appearance of Web Worker, there was no condition for parallel computing in the front-end. In Chrome Dev Submit in 2018, Google introduced a set of simple architecture using the Actor model to match Web Worker. This leads to more front-end developers looking at the Actor model.

The Actor model has the following characteristics:

  • Light weight: each Actor is only responsible for their own work, no side effects;
  • No shared state: Each Actor’s state is private and there is no shared state. Ideally, each Actor runs in a different thread and there is no shared memory;
  • Communicate with message: Each Actor distributes tasks by receiving messages, which can be understood as each message triggers a task, so there may be a queue of tasks. Each Actor maintains a private task queue, and after the execution of each task, information is transmitted through message.

The above characteristics can be summarized as the model shown below:

In addition to the above features, Actor operations are also limited, allowing only the following three:

  1. Send messages outward;
  2. Distribute tasks based on received messages. Actors are not limited to static tasks corresponding to message, but can carry dynamic data and even functions, which greatly enhances the customizability of actors.
  3. Create other actors. An Actor has administrator rights over other actors it creates and can customize certain behaviors of other actors. For example, Actor A creates Actor B. For Actor B, Actor A is Supervisor Actor. Actor A can restrict the behavior of Actor B, for example, by sending A message to notify Actor A when Actor B crashes, so that Actor A can restart Actor B upon receiving the message. This mechanism is similar to the PM2 restart mechanism. It can also be seen from this feature that the Actor model is not only suitable for parallel computing problems, but also suitable for distributed systems.

Let’s talk more about why the Actor model is suitable for managing Web Worker threads.

The front-end multithreading realized by Web Worker is a master-slave mode:

  • Worker threads only have limited permissions and cannot operate DOM. From this perspective, worker threads are thread-safe for browsers.
  • The worker thread communicates with the master thread (i.e. the JS main thread) through postMessage.
  • The master thread specifies which actions the worker performs by sending a message, and the worker thread returns the results via message.

The theoretical model of Actor does not specify which mode is used by multithreading, but the existence of Supervisor Actor is very suitable for master and slave multithreading, so the combination with Web Worker looks very appropriate.

However, at the implementation level, the theoretical model of Actor may not be completely followed, and some transformation is often required for specific scenes. The following is a brief description of the specific implementation method of WebGL engine in Actor+Web Worker.

Practical application of Actor model in WebGL engine rendering

WebGL engine’s management of worker threads is a mode similar to load balancing, and a Dispatcher is added on the basis of Actor model for overall management of all actors, as shown in the following figure:

The work of each Actor includes the following:

  1. Manage a worker thread, responsible for the actual behavior of sending and receiving messages to worker threads;
  2. Maintain a private task queue, when the thread is occupied, the subsequent task will be queued, and when the thread is idle, automatically remove the next task in the queue and execute;
  3. Maintain a private state – Private BUSY, which indicates whether the thread is occupied and provides access to the external interface public busy. Dispacher can use the busy state to perform load balancing among all actors.

The core code for Actor is as follows:

export default class Actor {
  private readonly _worker:Worker;
  private readonly _id:number;

  private _callbacks:KV<Function> = {};
  private _counter: number = 0;
  private _queue:MessageObject[]=[];
  private _busy:boolean=false;

  constructor(worker:Worker, id:number) {
    this._id=id;
    this._worker = worker;
    this.receive = this.receive.bind(this);
    this._worker.addEventListener('message'.this.receive, false);
  }
  /** * Occupied *@memberof Actor* /
  get busy() :boolean{
    return this._busy;
  }
  set busy(status:boolean) {this._busy = status;
    // If the queue to be executed is not empty, the first queue task is executed
    if(! status&&this._queue.length){
      const {action,data,callback} = this._queue.shift();
      this.send(action,data,callback); }}/ * * *@memberof Actor* /
  get worker() :Worker{
    return this._worker;
  }
  / * * *@private
   * @method _postMessage
   * @param message* /
  private _postMessage(message) {
    this._worker.postMessage(message);
  }
  private _queueTask(action:WORKER_ACTION, data, callback? :Function){
    this._queue.push({action,data,callback});
  }
  public receive(message:TypePostMessage) {
    this.busy = false;
    const {id,data} = message.data;
    const callback = id?this._callbacks[id]:null;
    callback&&callback(data);
    delete this._callbacks[id];
  }
  public send(action:WORKER_ACTION, data, callback? :Function) {
    if(this.busy){
      this._queueTask(action,data,callback);
      return;
    }
    this.busy = true;
    const callbackId = `The ${this._id}-${action}-cb-The ${this._counter}`;
    if(callback){
      this._callbacks[callbackId] = callback;
      this._counter++;
    }
    this._postMessage({
      action,
      data,
      id: callbackId, }); }}Copy the code

The work of Dispatcher is relatively simple. It is responsible for receiving the call commands of the outer logic up and managing the scheduling of all actors down. The code is as follows:

export default class Dispatcher {
  private readonly _actorsCount: number = 1;
  private _actors: Actor[]=[];

  constructor(count:number) {
    this._actorsCount = count;
    for (let i = 0; i < count; i++) {
      this._actors.push(new Actor(new IWorker(' '),i)); }}/ * * *@public
   * @method Broadcast Broadcast command *@param {WORKER_ACTION} Action directive name *@param {Object} The data data * /
  public broadcast(action: WORKER_ACTION, data: any) {
    for(const actor of this._actors){ actor.send(action, data); }}/ * * *@public
   * @method Send Sends action instructions * to a single worker@param {WORKER_ACTION} Action directive name *@param {Object} The data data *@param {Function} [callback] Callback function *@param {string} [workerId] Specifies the worker ID */
  public send(action:WORKER_ACTION, data: any, callback? :Function,workerId? :string) {
    const actor = this._actors.filter(a= >! a.busy)[0];
    if(actor){
      actor.send(action, data, callback);
    }else{
      const randomId = Math.floor(Math.random()*this._actorsCount);
      this._actors[randomId].send(action,data,callback); }}/ * * *@public
   * @method Clear Terminates all workers, clears actors */
  public clear() {
    for(const actor of this._actors){
      actor.worker.terminate();
    }
    this._actors = []; }}Copy the code

The Dispatcher needs a broadcast API to synchronize information to all actors. For example, the DPR of the screen is needed to convert geographic coordinates in tile data to screen coordinates. The broadcast API can be used to send this information to all actors.

In addition, instead of accepting messages from actors, the Dispatcher assigns a handler to each task in the form of a callback function, which triggers the corresponding handler when the Actor completes the task. Taking a typical user interaction that triggers a redraw as an example, the process is as follows:

  1. [Fixed] The WebGL engine redraws the map when the user manipulates the map and changes the bound.
  2. The first step is to calculate the list of tile coordinates visible through the current field of view and trigger loading if new tiles are needed.
  3. tile_pyramid.tsCall distributordispatcher.tsPerform the task of loading tiles;
  4. dispatcher.tsFirst of all, it will judge whether any Actor is occupied. If there are idle actors, the task will be directly assigned to it; if there are no idle actors, an Actor will be randomly selected to perform the task. At this time, the selected Actor will cram the task into the task queue for execution.

conclusion

The above is the specific implementation mode of WebGL engine for Actor+worker. Adding the concept of load balancing can more effectively solve the dynamic assignment of tasks when threads are occupied. Since the WebGL engine is an internal project, it is not convenient to write more detailed code, such as the specific tasks of workers, so we will have to see.