BPS 開發分享之 5：平行運算

眾所周知地，JavaScript 是一種單一執行緒的程式語言，而且這個單一執行緒跟 DOM 是共用的，這使得純粹的 JavaScript 並不是用來進行耗時運算的頂尖選擇。只要一個 macrotask 執行的時間超過 50ms，在 Chrome 的標準中就叫作「long task」，是不利於使用者體驗的東西；因為在這段時間裡面網頁的主執行緒都沒辦法和使用者互動，包括像是 hover 的 CSS 效果等等都會暫停 ¹，看起來就好像網頁當機了一樣。

這個問題在 BPS 上面也是頗為困擾的：當載入的專案夠大的時候，每次使用者拖曳畫面上的物件時，即便已經把演算法改進到了極致，即時重新計算畫面花上的時間還是會長達 500ms 以上，這比標準要慢了十倍。既然演算法已經盡可能改進了，那麼剩下的就只有一招：想辦法開多執行緒來平行運算。這當然就開始超脫了純粹 JavaScript 的範疇，而是靠瀏覽器的 Web Worker API 來達成的 ²。本篇中我就來談一些 BPS 中對於 Web Worker 的使用的心得。

基本概念

首先我們必須先有一個基本的認知是，即便用上了 Web Worker，還是不會讓 JavaScript 突然就變成像 C# 那些真的內建有多執行緒支援的語言一樣；真正的多執行緒語言是可以讓不同的執行緒來共同存取相同的記憶體資料的，但是 Web Worker 使用的記憶體卻跟主執行緒是分開的，換句話說它根本就是獨立執行的另外一個單一執行緒。它沒有辦法直接操作 DOM，也不能直接讀取位於主執行緒上的資料。Web Worker 跟主執行緒之間只能透過 postMessage() 方法來溝通，而且能夠過這個方法傳遞的資料僅限於可以被序列化的資料 ³。

因此，這邊與其說是多執行緒運算、還不如想像成分散式運算比較貼切；主執行緒會透過 postMessage() 方法通知 Worker 來進行特定的耗時運算，Worker 計算完成了以後純粹把序列化的結果丟回來，除此之外 Worker 跟主執行緒之間都不會有其它互動。

撰寫 Web Worker 基本上也就是寫一個獨立的 JavaScript 檔案，裡面可以透過 importScripts() 方法來載入其它的 JavaScript 檔案，這樣可以方便跟主執行緒共用部份的程式碼和函式庫。

純粹利用 postMessage() 方法來通訊的話，要正確串接回覆的訊息並且寫成一個 Promise 物件會比較麻煩，所以建議的作法是利用 MessageChannel 來寫，其最大的好處就是可以精確地配對每次送出的請求和回傳，不用自己刻管理的機制。主執行緒啟動和呼叫 Worker 的程式碼大是如下的形式：

const worker = new Worker("worker.js");

function callWorker(data) {
    return new Promise(resolve => {
        let channel = new MessageChannel();
        channel.port1.onmessage = event => resolve(event.data);
        worker.postMessage(data, [channel.port2]);
    });
}

而 Worker 裡面負責接收訊息的程式碼則是如下的形式：

self.onmessage = async function(event) {
    if(event.ports[0]) {
        // 其中 compute 是某個很花時間的運算
        let result = await compute(event.data);
        event.ports[0].postMessage(result);
    }
};

當然這邊的 compute() 也可以是同步函數，那樣的話上面的 async 和 await 可以省略不寫，雖然寫了也沒差。

實作分散式運算分配系統

理所當然地，為了要把平行運算的效果發揮到極致，我們會希望多開幾個一樣的 Worker 來分攤運算，此時我們可以參考 navigator.hardwareConcurrency 屬性來評估我們最多要開到幾個。不過需要注意的是有些瀏覽器（尤其是 Safari）會故意回報較低的數字或甚至沒有定義這個屬性，所以這個是僅供參考。

接著我們會希望有一個這樣的系統：當主執行緒準備要請求一項運算的時候，會自動找出目前沒有正在工作的 Worker、並且把運算請求傳遞給它；而如果目前所有的 Worker 都忙碌中，就等到其中第一個完成前一次運算的 Worker 空出來之後再傳遞請求。底下的程式碼是這樣的一個系統的範例：

/** 所有開啟的 worker */
const workers = [];

/** 各個 worker 是否正在執行 */
const working = [];

/** 佇列的 Promise resolver */
const queue = [];

// 盡量開啟到 CPU 數那麼多個 worker，但總之至少開一個（否則根本不能跑）
const max = navigator.hardwareConcurrency ?? 1;
for(let i = 0; i < max; i++) {
    workers.push(new Worker("worker.js"));
    working.push(false);
}

/** 取得下一個可用的 worker 的 id */
function getNextId() {
    let id = working.findIndex(p => !p);
    if(id >= 0) {
        working[id] = true; // 傳回之前要先佔據 id
        return id;
    } else {
        // 找不到的話就佇列工作
        return new Promise(resolve => queue.push(resolve));
    }
}

/** 這是主執行緒請求運算的入口 */
async function process(data) {
    let id = await getNextId();
    return await new Promise(resolve => {
        let channel = new MessageChannel();
        channel.port1.onmessage = ev => {
            resolve(ev.data); // 運算完成，回傳結果

            // 如果有佇列工作就通知它來接手，不然就空出 id
            if(queue.length) queue.shift()(id);
            else working[id] = false;
        }
        workers[id].postMessage(event.data, [channel.port2]);
    });
};

不過這邊需要注意一個小坑：這套管理機制如果也要放在主執行緒裡面，前提必須是請求運算的主要程式本身也是非同步程式才行，否則一旦 Worker 全都滿了，連 await getNextId() 的這個動作都會被排程到當前的 macrotask 之後，這樣一來之後的 Worker 運算就沒有真的跟我們的 macrotask 平行地進行，無謂浪費時間。如果主要程式暫且沒辦法改寫成非同步程式（BPS 暫時就是這樣），那麼一個解決的辦法就是把上面這個管理系統也拉出來變成是一個 master Worker，如此一來 await getNextId() 就會是平行於主執行緒地在等候，使得 Worker 的運算塞滿時間軸。

在本地測試 Web Worker

Chrome 在預設的情況下是不允許執行 file:// 開頭的 Web Worker 的，但是可以在啟動 Chrome 的時候配合參數 --allow-file-access-from-files 來允許這種執行。這個搭配 VS Code 的 launch.json 來一起設定比較方便，可以使得按下 F5 時啟動的 Chrome 自動帶有該參數：

{
    "type": "pwa-chrome",
    "request": "launch",
    "name": "Launch in Chrome",
    "internalConsoleOptions": "neverOpen",
    "file": "${workspaceFolder}/index.htm",
    "sourceMaps": true,
    "runtimeArgs": ["--allow-file-access-from-files"]
}