自幹 JavaScript 的 Tail Call Optimization


ECMAScript 6 開始,規範中出現了一項被稱為「尾呼叫優化(Tail Call Optimization, TCO)」的優化技術,這讓開發者可以在函數的執行過程中,減少 Stack Frame 的數量,進而提升效能。TCO 尤其是在遞迴這種不停呼叫自己或新函數的工作上,能得到最大的優化效益,能提升遞迴的執行效能如同迴圈一樣。

只不過很可惜的是,截至本文發稿前,大多數瀏覽器及 JavaScript 引擎尚未支援這項技術。但我們還是可以自幹並模擬一個 TCO 的行為,雖然比起語言本身、編譯器(Compiler)及虛擬機(VM)層面的實現,效果差了些,但仍然可以減少 Stack Frame 的數量避免達到 Stack Frame 的數量上限。

什麼時候會啟用尾呼叫優化機制?


如果 JavaScript 引擎有支援,通常一個函數執行到最後一行 return 時,是回傳另一個函數的執行結果,就會啟用 TCO 機制,如:

const f = () => {
    return 999;
};

const g = () => {
    // 執行並直接回傳 f 函數的執行結果:會啟用尾呼叫優化機制
    return f();
};

g();

但要注意的是,回傳的「必定為函數的直接回傳值」,所以下面這些寫法不會啟用 TCO 機制:

// 不會啟用 TCO 機制的設計
const g = () => {
    return f() + 1;
};

// 不會啟用 TCO 機制的設計
const g = () => {
    let ret = f();

    return ret;
};

創造一個跑不完的函數


首先我們先創造一個肯定跑不完的遞迴,然後改善它:

const func = (x) => {

    // 讓他跑 10000000 次
    if (x === 10000000)
        return x;

    return func(x + 1);
};

let ret = func(0);

理論上,如果你直接執行上述程式碼,會得到 stack size 超過上限的錯誤訊息:

RangeError: Maximum call stack size exceeded

簡單模擬實現自己的 TCO 效果


簡單來說,尾呼叫優化對開發者最主要的效果,就是避免每次呼叫函數時,就產生一個新的 Stack Frame,所以這是我們實現的主要訴求。而我們可以實現的作法,是讓函數的遞迴呼叫轉換成迴圈形式執行,避免不斷增加 Stack Frame,使遞迴可以無窮的跑下去。

我們可以創造一個閉包,來包裝我們的函數:

const tco = (fn) => {

    return (...args) => {

        let f = fn.bind(this, ...args);

        // 每次執行函數後,若得到的回傳值是函數物件,則繼續執行下去
        while(f instanceof Function) {
            f = f();
        }

        // 沒有需要繼續執行的函數,回傳結果
        return f;
    }
};

然後,我們用此閉包把待優化的函數包裝起來,並做點修改:

const func = (x) => {

    // 讓他跑 10000000 次
    if (x === 10000000)
        return x;

    // 不直接執行函數,改為綁定參數後產生並回傳一個函數物件
    return func.bind(this, x + 1);
};

// 包裝我們的遞迴函數
const improvedFunc = tco(func);

// 執行方法和舊函數一樣
let ret = improvedFunc(0);

執行優化後的函數,就不會再出現 stack size 的錯誤了。

自己自幹的限制


需要一提的是,在我們自己實現的版本中,我們無法做到合併所有的 Stack,也無法減少函數的來回跳轉數量,這些是屬於虛擬機和語言層面才能做到的設計。

使用遞迴時要注意事件引擎鎖死的問題


要記得,雖然 TCO 可以解決 stack size 上限的問題,但 JavaScript 仍然依賴著事件引擎,而密集運算會造成事件引擎鎖死,所以在一般的應用中,我們應該避免運用太深的遞迴,除非你確定你的應用程式沒有其他需要事件機制的地方,或是真的要拿 JavaScript 做密集運算的工作。

後記


一如程式語言的發展趨勢,所有現代化的程式語言都向 Functional Programming 靠攏。考量到為了讓函數可以無窮的遞迴執行下去,尾呼叫優化(Tail Call Optimization, TCO)就是一個重要的機制。

留言

  1. 開眼界了,原來尾呼叫消除可以這樣在應用層實現。

    回覆刪除

張貼留言

這個網誌中的熱門文章

有趣的邏輯問題:是誰在說謊

Web 技術中的 Session 是什麼?

淺談 USB 通訊架構之定義(二)

淺談 USB 通訊架構之定義(一)

Reverse SSH Tunnel 反向打洞實錄