[影片推薦]瀏覽器中Javascript的運作機制

瀏覽器是如何做渲染的?

Browserwork Image 01

當使用者點擊一個按鈕觸發了 eventListener callback,瀏覽器會照上圖的步驟依序執行,先跑完 Javascript 再解析 CSS,CSS parser 產出的 CSSOM 會和 HTML DOM Tree 結合產生 Render Tree 後,交給 Layout 畫 element 佈局、Paint 畫像是圖片、顏色、文字等內容物、Composite 做不同圖層的疊加,最後輸出 pixel 到 Browser 頁面上。

上述過程中,有很多有趣的細節值得學習,下面針對 Javascript 的部分提供好康給大家參考!

Browserwork Image 02

Jake Archibald: In The Loop - JSConf.Asia 2018

這個演講對上面的流程做了一個很棒的梳理,必看啊!

影片裡面提到 JS 解析和渲染 GUI 兩者不會產生 race condition,是因為它們之間有 event loop 幫忙協調。Event loop、JS engine 和 render engine 的工作都是由瀏覽器的 main thread 負責執行,其他耗時操作 (ex. setTimeout, network, monitor) 會被分配到其他 thread 去執行,再回報給 main thread 去 render 畫面或執行 Javascript callback,如下圖。

Browserwork Image 03

Event loop 要搭配 task queue 才 work!Task queue 可以比喻成 event loop 的 To Do List,event loop 會在空閒時取出 queue 中的任務 (task) 執行。

JS engine 和 GUI render engine 因為都是使用同一條 main thread,故如果在 JS task 裡定義執行 while 無限迴圈,會 block event loop 導致瀏覽器畫面無法更新而死當,參考下面程式碼。

setTimeout(function(){
    while (true) // run here forever
}, 0);

下圖白色的方框代表目前 main thread 走到的地方,左邊是 Task queue,右邊是 GUI render engine,requestAnimationFrame 會在畫 Frame 之前執行 (Safari 的 Raf 是在畫 Frame 之後),瀏覽器會保證在畫 Frame 前執行完全部 “已經發出” 的 Animation callbacks。

Browserwork Image 04

影片裡面有提到為何做動畫時推薦使用 requestAnimationFrame,而不是 setTimeout。

我們知道 setTimeout(callback, 0) 會將 callback 放到 task queue 等待執行,但我們無法強制瀏覽器在下個 Frame 被畫出來之前就執行這個 callback。

瀏覽器是根據當下資源利用的狀況來決定何時執行 task queue 的 task,它可以在兩個 Frame 之間的空檔執行任意多個 tasks,也可以一個 task 都不執行,這是我們用程式無法控制的,故像動畫這種講求畫面流暢度的 feature,為了保證動畫的 script 能在畫下一個 Frame 之前跑到,並避免因重複執行而浪費資源的風險,requestAnimationFrame 比 setTimeout 更適合用在做 UI 動畫上面。

Browserwork Image 05

講者還建議把 animation task 批量放在 requestAnimationFrame callback 執行,如果有需求要強制更新 Layout 可以使用 getComputedStyle 直接強迫 style recalculate,有些人會利用這個特性產生動畫,如下圖,但這種不正常的渲染方式會耗費較多資源,不建議常用。

Browserwork Image 06

講者最後有介紹到 microTask,Promise 的 callback 都會放在 microTask 等待執行,microTask有兩個和 Task 比較不同的特性:

  1. microTask 會等 Task queue 空了才執行
  2. 當執行 microTasks 時,會 block event loop 直到 microTask queue 的 task 都執行完,如果 microTask queue 的 task 太多會造成畫面停滯

整個 JS 執行的順序如下: Task –> microTask –> requestAnimationFrame,影片裡給了很棒的題目測試大家對 task / microTask 執行順序的理解,如果想深入探討可以參考這篇Tasks, microtasks, queues and schedules


在聽影片的過程,我也找了一些文章來解答自己的一些疑問,在下面分享。

Notes on How Browser works!

這篇文章再一次詳細的書裡整個Browser的運作架構,也提到困擾我已久的”瀏覽器哪個process是single thread,哪個是multi-thread”等問題…

簡單來說,瀏覽器是 multi-process,一個瀏覽器只有一個 Browser Process,負責管理 Tabs、協調其他 process 和將 Renderer process 存至 memory 內的 Bitmap 繪製到畫面上 (pixel);在 Chrome,一個 Tab 一個 Renderer Process,Renderer process 是 multi-thread,其中 main thread 負責頁面渲染 (GUI render engine)、執行JS (JS engine) 和 event loop;network component 可以開 2~6 個 I/O threads 平行去處理。

當用戶輸入網址,Browser process 會下載頁面資料,將它交付給 Renderer process 做渲染,之後再將 Renderer process 吐出的結果拿來做繪製。

從 Event Loop 規範探討 Javascript 異步和瀏覽器更新渲染時機

這篇討論將 event loop 梳理的很仔細,留言的部分也有很多人補充。裡面有說到 event loop 是在 HTML Standard 定義的,不包含在 Javascript engine 的實作裡面。撰寫 Javascript 時所用到的 Ajax 網路資源請求、修改 DOM、EventListener attach 等,都是使用瀏覽器的 Web API,Web API 會將這些任務丟到其他相對應的 thread 執行,threads 執行完會將 callback 丟到 event loop 的 task queue 等待。

What forces layout / reflow

這篇 Gist 說明在 Javascript 哪些設值/取值的過程會造成畫面 reflow!

Browserwork Image 07

Reflow 是造成 Layout style 重新計算的意思,它同時也會將新的 Javascript 變更都計算進去,用下面同一段 code 舉例,當執行 getComputedStyle 時,在 getComputedStyle 之前的程式碼,像是 translateX(1000px) 也會被計算進去並呈現在畫面上;但在 getComputedStyle 之後的程式碼則不會,有人會用這個特性製造動畫效果,但不推薦。

Browserwork Image 06

[Performance]瀏覽器運作與效能指標評估

透過這次撰寫 Performance Report 的機會,學習一點瀏覽器運作的方法和網頁效能指標。

Performace 標籤總攬

這頁是我們這次的觀察範例: Yahoo 購物中心的 Mobile 版時時樂頁面。開啟 Chrome Dev Tool 的 Performance Tab 後按重新整理,會看到下圖。

Metric Image 01

Google 的 Performance tunning 教學可以參考此篇,下面會根據上圖的四個區塊再做一些解釋:

(1) Capture settings:按右上角的”齒輪”開啟設定,我們用它來設定跟環境相關的參數,像是降低 CPU 速度、模擬 3G 網速環境之類。

  • 發現網頁有渲染阻塞時,勾選 Enable “Advanced paint instrumentation (slow)”後,便可以在 Paint Profiler 看到更詳細的渲染事件過程,詳見此篇的 See Li’s answer

  • 沒有勾選 Disable JavaScript samples 時,會看到 JS call stack 的全部過程,如果你對 JS function 的呼叫過程沒興趣,可以勾選 Disable JavaScript samples,讓 Main 區塊乾淨一些。

    • 下方第一張圖是 rushbuy.js 在時時樂頁面的執行過程。由左到右是時間,由上到下是 function 呼叫順序。如圖,Rushbuy.js 執行了 window.webpackJsonp,這部分的 code 是 webpack 在打包時插入的,目的是使前端資源調用時能正常運作,稱為 webpack runtime。window.webpackJsonp 呼叫相對應的 JS 資源,該 JS 檔會再繼續呼叫此頁面使用到的 React component。
    • 下方第二張圖是勾選 Disable JavaScript samples 時的畫面,少了 JS call stack 花花綠綠的紀錄,看起來清爽許多。

Metric Image 02

Metric Image 03

(2) Overview: 第二個部分是渲染過程總覽,含三個部分,FPS、CPU 和 Net。

  1. FPS 代表每秒幾個 Frame。綠色線越高代表 FPS 越高,如果是動畫盡量要達到 60 FPS,綠色線上有紅色代表可能出現卡頓。
  2. CPU 代表消耗 CPU 資源執行哪些工作
  3. NET 比較少用,通常看 Network Tab 比較清楚

(3) 火焰圖: 這部分包含多個面向的詳細資料,我主要看的地方只有 Network 和 Main 而已。Network 看資源下載的順序,Main 看資源執行的順序。

  • 舉例,我們可以藉由下面火焰圖的 Network section,看到 HTML 檔下載完成後緊接著 Main section 的 HTML parsing,在執行過程中先遇到放在 head 的 CSS 並發出 HTTP request 請求 CSS 資源,後遇到放在 boby 尾端的 JS 再發出 HTTP request 請求 JS 資源。

Metric Image 04

(4) Details: 在火焰圖中點擊中意的事件,該事件的詳細資料會被顯示在 Detail 區塊。這個部分的圓餅圖總結、Call Tree 內每個 Activity 的耗時, Rendering 的 repaint flashing 和 Layout borders 標示都很有用!

瀏覽器運作簡介

簡單的瀏覽器架構如下:

Metric Image 05

  1. User Interface 是使用者看到的 UI 介面
  2. Browser Engine 負責與 Data Storage (localStorage, Cookies…) 溝通和操作 Render Engine,Firefox 的 Gecko engine 和 Safari / Chrome 的 WebKit engine 都是 Browser Engine
  3. Render Engine 是瀏覽器核心,為 Single thread,會一直循環等待事件觸發任務,它負責三種工作:

    • UI Backend: 渲染 (Paint) 頁面 (Single thread)
    • JS Engine: 負責運行Javascript (Single thread)
    • Network Component: 網路資源請求 (含HTTP Request / WebSockets / WebRTC),可同時發出多個請求

我們的重點在於頁面是如何被渲染出來給使用者觀賞的,也就是 UI Backend 的部分。當 Network Component 接收到 response 資源時,若該資源是 HTML 會被 UI Backend 解析成 DOM Tree;若該資源是 CSS 會被 UI Backend 解析成 CSSDOM Tree;若該資源是 JS 則會交給 JS Engine 處理。

DOM 和 CSSDOM 會被拿來建構 Render Tree,瀏覽器會根據 Render Tree 執行三段過程: Layout (版面佈局) –> Paint (繪製內容) –> Composite (圖層合併) 來完成 Frame 的繪製,如下圖。

Metric Image 06

這裡要特別提到 CSS 和 JS 的阻塞特性:

  • Javascript - parser blocking:當執行 JS 時,HTML / CSS 都會停止解析直到 JS 完成。其原因是 JS 擁有改變 HTML / CSS 的能力,故瀏覽器被設計成等待 JS 執行完後再繼續解析 HTML / CSS,避免無用的 HTML / CSS 解析。
  • CSS - render blocking:當執行 CSS 時,HTML可以繼續被 parsing,但 render tree 的建構會被暫停。因為 render tree 有 DOM 和 CSSDOM 這兩個來源,瀏覽器會等待整個 CSS file 的 CSSDOM 解析完後,再產生 render tree。

以瀏覽器的角度,會希望越快讓使用者看到畫面越好,所以它不會全部的 HTML 解析完才 Paint 頁面,而是將任務切成很多塊,解析完一部分就直接渲染到頁面,導致網頁擁有漸進出現的視覺效果。

時時樂頁面觀察

有了以上觀念後,我們再來對照看看真實網頁的頁面渲染過程。開啟 Dev Tool 後,建議禁用所有 chrome extension 來避免分析干擾,由下圖的 Main section 可以觀察到,chrome extension script 也會造成 parser blocking,安裝Disable Extensions Temporarily可以方便我們禁用 chrome 插件。

Metric Image 07

在開測之前,先簡單介紹這個頁面的架構。本頁面是採用 React + Redux 的 isomorphic app 架構,畫面大部分的 HTML 標籤和 store 的部分資料已經包含在 HTTP response 中 (server side render),isomorphic app 的好處有避免敏感的 API endpoint 露出、讓 First Meaning Paint (FMP) 的時間快一點、SEO 較好 (給搜尋引擎較多 HTML 資訊) 等…

大部分的 server side render 都會包含到 hero element (重點元件) 的內容,我們可以藉由勾選 disable javascript 來禁用本頁面的 JS,觀察 server side render 出來的 HTML 畫面長什麼樣子。

Metric Image 08

下圖是沒有執行任何 JS 的時時樂頁面,由此我們可以知道標籤列以下的內容是 client side render;標籤列以上的大 Banner 可能就是本頁的 hero element。

Metric Image 09

如果妳嘗試點擊標籤列會發現根本無法切換標籤,這是因為 client side 的 JS 被拔掉導致 onClick handler 沒有被附加到 HTML 元件上,使用者因此無法和元件互動,只能閱讀頁面內容。所以我們會建議在撰寫 React Component 時多使用原生 HTML tag 擁有的功能,像是要做 hyperlink 就要用 <a href=”” > 而不是 <div onClick={this.clickHandler} >,讓使用者在等待 client side JS 跑完之前,能和頁面做一些簡單互動。

接著我們回到設定,將 disable javascript 取消掉並 reload,會看到畫面由下面的左圖變成右圖。

左邊server side render,右邊加上client side render

本頁面的 main JS (rushbuy.js) 光是下載就花了 250ms,執行約花 500ms,兩者加起來共約 750ms。故使用者只能看著畫面乾瞪眼,直到 750ms 後才能和畫面做互動,很可能造成不好的使用者體驗。

Metric Image 12

效能指標

由上述經驗,我們可以總結出幾個會影響到使用者體驗的時間因子:

  1. 使用者多快能看到畫面?(Is it happening?)
  2. 使用者多快能看到有意義的畫面?(Is it useful?)
  3. 使用者多快能和畫面做互動?(Is it usable?)
  4. 使用者在與畫面互動的過程是否順暢?(Is it delightful?)

第一點和第二點的時間越快對使用者越好;第二點與第三點之間的時間差如果太大,使用者點擊畫面時會沒反應,或是造成卡頓,導致用戶體驗變差;第四點必須直接靠觀察 Performance Tab 分析,沒有相應的指標,偵錯範例可以參考這一篇,寫得非常清楚。

下面介紹幾個跟上述因子相關的效能指標,由 Google 提出!詳細說明可以參考這篇 User-centric Performance Metrics

  • First Paint (FP):當第一個 pixel 畫到畫面上的時間 (First Fame time),下圖是時時樂頁面的FP畫面。

Metric Image 13

  • First Meaning Paint (FMP):hero element 出現在畫面上的時間,hero element 由我們開發者自己定義,Dev Tool 會用黃色線標示出幾個候選的 hero element 給我們參考,如下圖。

Metric Image 14

  • Time to Interactive (TTI):Google 將這部分的評估劃分為兩個指標 (TTFI、TTCI),目前還在 Beta 階段,詳細計算方式可以參考其文件。我個人認為 TTFI 和 TTCI 沒那麼好用,不如直接取網頁的主要的 JS 所執行完的時間當作 TTI。下圖的 rushbuy.js 就是時時樂頁面最主要的 JS script,它執行完後就能應付此畫面大部分的互動行為。

Metric Image 15

以上三個都是和時間相關的效能指標,但使用者的感官體驗不只與時間相關,也與畫面漸進變化的過程有關。如果頁面在渲染過程中跳來跳去,就算渲染速度很快,也會讓使用者感到不舒服,Perceptual Speed Index / Speed Index 就是能幫助開發者評估使用者視覺體驗的指標。

  • Perceptual Speed Index / Speed Index (PSI/SI): 此數值能透過 Google LightHouse 獲得,它除了考慮時間,也會拿畫面截圖做分析比對,數字越小代表視覺體驗越佳。

Chrome Dev Tool 所標示出的指標線

Metric Image 16

依照上圖的標示依序看,橘色線是 First Meaning Paint candidate,是 Chrome Dev Tool 建議我們的 FMP 時間,可能會有一到多個,由開發者自己決定要取哪個時間作為 FMP;綠色線是 First Paint (FP),是第一屏 (Frame) 的時間點;藍色線和紅色線是前人常用的舊指標,藍色是 DOMContentLoaded event,會在 HTML 解析完呼叫,可以當成 Server side code 完成解析的時間,紅色線是 Load event,會在所有資源 (不包含 Async 等 Non-Blocking 資源) 解析完後觸發,時間大約會在 TTI 附近,可以用它作為 TTI 的參考。

結語

前端工程師追求給網頁使用者最好的互動體驗,了解瀏覽器運作和效率測量工具,能讓我們對自己作品的品質更有信心,共勉之XD


參考

[Web Component v1]JS Framework 以外的另一條道路

為了維護並修改同事寫的 web component v0 元件,我接觸到這個,標榜可以相容所有 JS Framework 的 web component 技術,在此做個紀錄。

Web Component 的意義

初入前端領域的小毛頭如我,在學完HTML, DOM, CSS, JS的基礎後,下一個抉擇就是要選什麼 JS Framework 入坑 (ex. Angular, React, VueJS…)。學習 JS Framework 可以增加我們的開發速度,引導我們正確的實踐方法,但每個 Framework 都有各自的生態圈,它們之間的相容性極低,若專案轉換到新的 Framework,舊 Framework 實作出來的 Components 大部分都無法拿到新的 Framework 中使用,過去努力開發的 share component 都付諸流水,這在變化極快的前端領域顯然增加不少成本。web component 被提出來就是希望能解決上述問題,並期望它的四個主要技術可以列入 W3C 擬定的標準

  • Custom elements
  • Shadow DOM
  • HTML templates
  • HTML Imports

目前只有 HTML templates 已經成為標準,其他三個仍在草稿階段,列為標準的好處是瀏覽器會接著跟進實作,如果未來做到全面支援,所有人就能直接利用原生的 BOM API 開發 web component,不只網頁效率倍增 (ex. Alex Russell 在 Chrome Dev Summit 2016 提到,如果使用 Framework,網頁渲染效率就會受限於框架本身,Framework是個對開發者方便,但將效率成本加築在終端使用者上的東西…),也解決前端框架無法相容的問題了。要撰寫自己的 web component,重點在活用 custom elements API 和 shadow DOM,因為目前各大瀏覽器的支援度仍不足,在開發前要先引入 web component polyfill

1
https://cdnjs.cloudflare.com/ajax/libs/webcomponentsjs/0.7.20/webcomponents.min.js

Custom Element 簡介

Custom Element是骨幹,讓我們能開發自定義元件,自定義標籤或是做屬性的擴充等…

自定義元件可以使用 ES6 class 來定義,用繼承 HTMLElement 來確保自定義的元件擁有完整的 DOM API,創建自定義元件有以下三個規則:

  1. 自定義元件的 TAG 名稱必須包含短橫線(-)。因此,<x-tags>、<my-element> 和 <my-awesome-app> 均爲有效名稱,而 <tabs> 和 <foo_bar> 則爲無效名稱。這個要求是為了讓 HTML 解析器能夠區分自定義元件和 HTML自身元件 (ex. div, span…)
  2. 不能多次註冊同一個 TAG,否則將產生 DOMException。
  3. 自定義元件不能自我封閉 (ex. <App />),因爲 HTML 只允許少數元件自我封閉。所以撰寫時,必須寫成封閉的 TAG (ex. <app-drawer></app-drawer>)。

我們可以把 web component 的自定義元件想成 React 的 Component,他和 React Component 一樣有自己的生命週期,可以根據 attribute 的變化觸發 element 做出改變,下面介紹幾個常用的 Custom Elements’ Life Cycle methods:

  • constructor:Custom Elements 剛建立時呼叫,通常會在這邊註冊 Event listener 或是創建 Shadow Dom。
  • connectedCallback:當自定義元件被插入頁面的 DOM 時會被呼叫,很像 React 的 componentDidMount
  • disconnectedCallback:當自定義元件被移除時會被呼叫,很像 React 的 componentWillUnmount,可以在這邊 remove Event listener 之類的。
  • attributeChangedCallback(attrName, oldVal, newVal):監聽的屬性有變動時會被呼叫,要搭配 observedAttributes() 使用。
  • adoptedCallback:整個 custom element 被人用 document.adoptNode(el) 呼叫時觸發。

以下是自定義元件範例的JS部分,這裡的 this 代表該 custom element 本身,其擁有的 DOM API (ex. hasAttribute) 都可以使用。下方範例裡的 Example class 繼承了 HTMLElement class,開放 ex 屬性給使用者做 getter/setter JS 設置,並監控其屬性變更,我們可以藉由 console.log 觀察剛剛提到的生命週期。

class Example extends HTMLElement {

  // A getter/setter for an open property.
  get ex() {
    return this.getAttribute("ex");
  }

  set ex(val) {
    // Reflect the value of the open property as an HTML attribute.
    if (val) {
      console.log("set ex attritube: " + val);
      this.setAttribute('ex', val);
    } else {
      this.removeAttribute('ex');
    }
  }

  set id(val) {
    // Reflect the value of the open property as an HTML attribute.
    if (val) {
      console.log("set id attritube:" + val);
      this.setAttribute("id", val);
    } else {
      this.removeAttribute("id");
    }
  }
  
  static get observedAttributes() {
      return ["ex"];
  }

  attributeChangedCallback(name, oldValue, newValue) {
    const hasValue = newValue !== null;
    switch (name) {
      case "ex":
        console.log("the ex is changed on " + oldValue + " to " + newValue);
        break;
    }
  }

  constructor() {
      super(); // always call super() first in constructor.
      console.log("In constructor");
  }
}

customElements.define('my-example', Example);

// set attribute by JS
document.getElementsByTagName("my-example")[0].ex = "setByJS"

// set id but not trigger attributeChangedCallback
document.getElementsByTagName("my-example")[0].id = "example"

在 HTML 插入剛剛定義的 custom Tag:

<div>
  <my-example ex="HAHA">
  </my-example>
</div>

我們可以觀察到 console 輸出為:

webComp Image 01

HTML 解析器解析到 my-example 標籤後,會先運行 constructor,再觸發 attributeChangedCallback,設定 ex 屬性為 HAHA,接著我在 JS 呼叫 set ex method 將 ex 設定為 setByJS,一樣也觸發了 attributeChangedCallback! 接著我們再用 JS 呼叫 set id method,設定屬性 id 為 example,但這次沒有觸發 attributeChangedCallback,因為只有 observedAttributes 所列的屬性被改變,才會觸發 attributeChangedCallback。

有了custom element 所提供的 DOM API,我們就能透過自定義屬性和添加 Event Listener,編寫 custom element 與終端使用者互動的邏輯,再配合 shadow dom 的封裝特性,做出華麗的外觀與變化。如何配合運用會在下面繼續說明。

以上範例原始碼可參考我的CodePen: Custom Element Example

Shadow Dom 簡介

Shadow Dom 是 web component 的靈魂,它讓開發者可以將自己的元件「模組化」

Shadow Dom 封裝元件內部的 HTML DOM/CSS,使其不受元件外面的環境影響,且因為外部的 CSS 無法直接修改到 shadow dom 的 CSS 內容,故 Shadow Dom 的 CSS class 命名可以和外部的 CSS class 撞名。目前的 HTML5 元件像是 <video>, <audio>, 各種 <input> 等等,都是 Shadow Dom 應用的產物。

要加 Shadow Dom,直接在 custom element class 的 constructor 裡用 this.attachShadow() 綁定 Shadow Dom Tree,官方建議不要用關閉模式 { mode: ‘closed’ } 創建 Shadow Dom,因為它會讓使用此 custom element 的開發者不能透過任何方式修改該 Shadow Dom 的 style 樣式,使該 custom element 的修改彈性變很低。綁定後,用 innerHTML 直接插入 dom 和 style 字串,之後的撰寫方式都和編寫普通的 HTML/CSS 相同,標籤 <slot> 代表插入 custom element 的 child element 位置所在,我們能用 ::slotted(css slector) 來裝飾該 child element。

以下是JS的範例,style 說如果 child element 為 p,則字的大小設 30px、顏色設為綠色

class Example extends HTMLElement {

  constructor() {
      super(); // always call super() first in constructor.
      let shadowRoot = this.attachShadow({mode: 'open'});
      shadowRoot.innerHTML = '<style>h1{ color: red; } ::slotted(p){ color: green; font-size:30px; }</style><div><h1>Hello Shadow DOM</h1><slot></slot></div>';
  }
}

customElements.define('my-example', Example);

Html範例,my-example標籤內有子元件 <p>I am slot</p>:

<div>
  <my-example>
    <p>I am slot</p>
  </my-example>
</div>

以下是呈現出來的畫面,我們可以看到子元件在紅色的 Hello Shadow DOM 後面,且被裝飾成綠色。

webComp Image 02

開 chrome console 可以觀察到 render dom tree 的 my-example 標籤下有 #shadow-root,內能觀察到被渲染的 shadow dom tree,外面的 CSS 是無法修改到此區域的 style

webComp Image 03

以上範例原始碼可參考我的CodePen: Custom Element Example & Shadow DOM

Shadow Dom + HTML template 讓程式更易維護

使用 HTML template 先定義好 Shadow Dom 的 HTML 結構和 style,再在 custom element 的 constructor 內複製 template 的內容節點到 shadow root。這種做法讓 custom element 的 shadow dom tree 更易讀也更好維護。

首先在 HTML 定義 template:

<template id="my-template">
  <style>
    :host { /* 整個 template */
      display: inline-block;
      padding: 20px;
      border: solid 1px red;
    }
    p {
      font-size: 20px;
      color: orange;
    }
    .slot {
      font-size: 20px;
      color: black;
    }
  </style>
  <p>My example</p>
    <div class="slot">
      <slot></slot>
    <div>
</template>
<div>
  <my-example>
    <p>Hello Web!</p>
  </my-example>
</div>

在 JS 的 custom element 複製 template content node 到 shadow root:

class Example extends HTMLElement {

  constructor() {
      super(); // always call super() first in constructor.
      let shadowRoot = this.attachShadow({mode: 'open'});
      const t = document.querySelector('#my-template');
      const instance = t.content.cloneNode(true); // copy template content node
      shadowRoot.appendChild(instance);
  }
}

customElements.define('my-example', Example);

結果畫面如下,一樣有裝飾到子元件:

webComp Image 04

以上範例原始碼可參考我的CodePen: Custom Element Example & Shadow DOM & HTML template

從 Web Component v0 到 v1

關於兩個版本的差異可以參考此篇,基本上 v0 的 custom element API 都有被 v1 向下支援,但 v0 的 Shadow piercing combinators 功能,也就是從外部透過 /deep/ 和 ::shadow 更改 shadow dom 的 style 方法已經完全被 v1 棄用,取而代之的是用 custom css property 釋出 style 接口,讓使用元件的開發者,透過元件作者所定義的 css property 更改 style 樣式。我個人覺得這樣的改版讓元件使用者很不方便,因為元件開發者不太可能知道元件使用者要怎麼裝飾元件,所以不一定能提供出足夠多的客製 css properties 出來。

實例

Yahoo 購物中心商品頁 的手機版,下方出現的 App 下載橫幅就是由 web component 做的!觀看時請開無痕,並開Dev Tool Console 轉到 Mobile mode ~


參考

[Javascript]非同步的救星Promise

Javascript Asynchronous Code

不論是撰寫前端 Javascript還是後端 NodeJS,異步操作都是無法避免的,像是向後端請求資料、處理瀏覽器事件、計時器等等都是常見的異步操作。 異步操作和我們熟悉的同步不同,當異步操作執行時,瀏覽器/NodeJS 不會等待當前操作的結果回傳後才執行下一行程式碼,他會繼續不回頭的執行下去,也就是我們常聽到的無阻塞特性 (non-blocking)。等遠端資料回傳後,瀏覽器或 NodeJS 才會通知 Javascript 引擎去呼叫使用者當初指定的 callback 做處理。

以下面程式碼為例。先定義一個函式 getRemoteData,其目的是用 Ajax 技術發出GET請求。我們運用 Javascript 中 function 可以當成變數使用的特性,將成功和失敗要執行的函式當成參數傳入 getRemoteData,並在裡面定義兩個函式的呼叫時機。這種撰寫方式稱為 callback pattern,被當成參數傳入的函式就叫callback,之後這個異步函式會在本文後面的例子不斷被使用到。

const getRemoteData = function (url, success, error) {
   let req = new XMLHttpRequest();
   req.responseType = 'json';
   req.open('GET', url);
   req.onload = function() {
      if(req.status == 200) {
         let data = JSON.parse(req.responseText);
         success(data);
      }
      else {
         req.onerror();
      } 
    }
   req.onerror = function () {
      if(error) {
         error(new Error(req.statusText));
      }
};
   req.send();
};

我們知道 Ajax 請求為異步操作,所以這裡程式不會等待 getRemoteData 完成後才繼續執行,而是會馬上接著跑 showStudents,此時 showStudents 的參數 students 仍為 null,故造成程式錯誤。

var students = null;
getRemoteData('/students', function(studentObjs) {
	 students = studentObjs; // 回傳資料
  },
  function (errorObj) {
     console.log(errorObj.message);
} );
showStudents(students); // null

要解決此問題,必須將 showStudents 放入 callback 函式,讓Ajax在資料回傳後執行 success callback 時,才執行 showStudents。

getRemoteData('/students', function(studentObjs) {
	 showStudents(studentObjs);
  },
  function (errorObj) {
     console.log(errorObj.message);
} );

這種寫法會讓熟悉多執行緒的 C#、JAVA 使用者一開始很不習慣,其中也有許多優點與缺點,本篇專注在討論缺點:callback hell,和如何利用 Promise 來解決 callback hell 的問題。

什麼是 callback hell? 如何做初步重構?

如果有異步動作需要有順序性的呼叫,在程式撰寫上常常需要一層包一層,如下面的例子,click 事件的 callback 包了 getRemoteData 這個異步操作,getRemoteData 的 callback 又註冊了 mouseover 事件,mouseover 的 callback 又包了 getRemoteData,這種寫法會導致程式的可讀性變差,我們稱這叫做callback hell。

var _selector = document.querySelector;
_selector('#search-button').addEventListener('click',
   function (event) {
    event.preventDefault();
    let ssn = _selector('#student-ssn').value;
    getRemoteData(`/students/${ssn}`, function (info) {
           _selector('#student-info').innerHTML = info;
           _selector('#student-info').addEventListener('mouseover',
              function() {
                  getRemoteData(`/students/${info.ssn}/grades`,
                      function (grades) {
                          // ... process list of grades for this student
		}); });
       })
       });
} });

為了讓程式更可讀,我們利用 javascript 的 function 是 first class citizen 的特性,將這些 callback 命名成一個個易解讀的變數並分離出來,這種做法叫做 continuation-passing style (CPS)。像上面的例子,可以被重構成如下。

var _selector = document.querySelector;
_selector('#search-button').addEventListener('click', getStudentSNN);

var getStudentSNN = function (event) {
    event.preventDefault();
    let ssn = _selector('#student-ssn').value;
    getRemoteData(`/students/${ssn}`, showInfoAndFindStudentGrade(info)).fail(showError);
} };

var showError = function() {
            console.log('Error occurred!');
};

var showInfoAndFindStudentGrade = function (info) {
           _selector('#student-info').innerHTML = info;
           _selector('#student-info').addEventListener('mouseover',
              function() {
                  getRemoteData(`/students/${info.ssn}/grades`,
                      function (grades) {
                          // ... process list of grades for this student
		}); });
};

在這裡要順道提醒,異步操作和同步操作混用時要多多注意 closure 的特性,他會導致一些超出預期的結果,以下面 loop 內的異步呼叫為例子。

var students = [{ ssn: '111111', country: 'US' },
                { ssn: '111112', country: 'US' },
                { ssn: '111113', country: 'US' }];
for (let i = 0; i < students.length; i++) {
   let student = students[i];
   if (student.country === 'US') {
      getRemoteData(`/students/${student.ssn}/grades`,
         function (grades) {
            showStudents(student.ssn, average(grades));
         },
         function (error) {
           console.log(error.message);
         });
    } 
}

本程式的結果不是大家預期的:

111111 --> 80
111112 --> 78
111113 --> 90

而是

111113 --> 80
111113 --> 78
111113 --> 90

我們會發現,雖然後面的平均成績對了,但其學號都是 students 陣列中最後一位學生的學號。 這個原因是因為 showStudents 並不是馬上執行,而是等到 Ajax 請求的 grades 回傳後才被呼叫,此時的 student 變數已經不是當時請求送出時的 student了,而是被最後一次給值的 student,也就是學號為 111113 的 student。所以我們必須要用 curry 寫法來避免這種問題產生,如下。

var students = [{ ssn: '111111', country: 'US' },
                { ssn: '111112', country: 'US' },
                { ssn: '111113', country: 'US' }];
for (let i = 0; i < students.length; i++) {
   let student = students[i];
   let showGrade = function(student){
        return function (grades) {
            showStudents(student.ssn, average(grades));
        };
    }();
   if (student.country === 'US') {
      getRemoteData(`/students/${student.ssn}/grades`,
         showGrade(grades),
         function (error) {
           console.log(error.message);
      });
   }
}

利用 closure 的特性將 student 變數鎖在 showGrade 的 closure 之中,這樣呼叫 callback 時就會使用到當時指定的 student 變數,並達到我們原本預期的結果。

111111 --> 80
111112 --> 78
111113 --> 90

雖然 CPS 有改善程式的可讀性,但仍遠不夠應付更加複雜的應用程式操作,這時就來到本篇的重點,Promise!

初解Promise

我們常把 Promise 用來包裝異步函式,因為它能做到以下幾點:

  1. 用 pipeline 的方式解決 callback hell 問題
  2. 好的 Error handling 方式

Promise 擁有三種狀態: Pending, Fulfilled, Rejected,Pending 代表此 Promise 內的程式還未完成;Fulfilled 代表程式已執行成功,到達此狀態時 Promise 會呼叫 resolve 函式;Rejected 代表程式執行失敗,到達此狀態時 Promise 會呼叫 reject 函式。

FP

我們可以親自建構 Promise 要何時到達 Pending, Fulfilled, Rejected,如下面是我們用 ES6 Promise 做的展示,ES6 Promise 採用的是 Promises/A+ 的標準。

我們設定 Promise 中異步請求的結果如果回傳成功,就到達 Fulfilled 狀態並執行 resolve(result);請求結果如果回傳失敗,到達 Rejected 狀態並執行 reject 函式。

var fetchData = new Promise(function (resolve, reject) {
    // fetch data async or run long-running computation
    $.get(url, function(result){
        if (<success>) {
            resolve(result); // successful calllback
	    } else {
            reject(new Error('Error performing this operation!'));
        }
    });
});

根據上面的範例,resolve 和 reject 函式都是”非同步操作完成”後才執行,所以在執行到 resolve 或 reject 之前,此 Promise 會一直保持在 Pending 狀態等待遠端的回傳結果,由此達成”異步操作完成後才會繼續執行”的效果。

之後,我們便可以使用 Promise 的 then 指定 resolve 函式,catch 指定 reject 函式,如下:

fetchData.then(function(v){ console.log('Successful-' + v); })
         .catch(function(message){ console.log(message); });

resolve 和 reject 的回傳值會被包裝成新的Promise回傳,之後我們就能利用新的 Promise 繼續做串接,達到 pipeline coding 的效果,讓程式可讀性獲得提升。

fetchData.then(...).then(...).then(...)  // pipeline

Promise串接的圖解可以參考如下,每個操作都是接續同步執行的!

FP

Promise 在 Function Programming 裡類似於 Monad,關於 Monad 的圖解說明可以看這裡。簡單來說,Monad是一個值或是函式的 Wrapper,這個 Wrapper 擁有兩點定義:

  1. unit :: a -> Monad a (將 a 值用 Monad 包裝)
  2. flatMap :: Monad a -> (a -> b) -> Monad b (取出 Monad 的 a 做計算後,生成 b,將結果 b 重新包裝成新的 Monad)

在我們撰寫的 Promise 範例中,function (resolve, reject){ … } 相等於上面定義的 a 值。我們將這個函式用 Promise 包裝,之後用 then 指定 resolve 函式;用 catch 指定 reject 函式。Promise 會在執行 resolve 或 reject 時,將函式執行完的回傳結果包裝成新的 Promise。這樣的流程符合上面定義的 Monad 特性,所以我們可以說 Promise 其實是 Monad。

使用Promise

這節將幫助大家了解如何實際使用Promise。請看下面例子,這段程式首先呼叫後端全部學生的資料,將回傳的學生們經過排名後,用 for 迴圈檢查哪些學生的住所在 US,呼叫每一位在 US 的學生成績後計算平均,最後顯示在頁面。

 
getRemoteData('/students',
    function (students) {
      students.sort(function(a, b){
            if(a.ssn < b.ssn) return -1;
            if(a.ssn > b.ssn) return 1;
            return 0;
      });
      for (let i = 0; i < students.length; i++) {
         let student = students[i];
         if (student.address.country === 'US') {
            getRemoteData(`/students/${student.ssn}/grades`,
              function (grades) {
                  showStudents(student, average(grades));
              },
              function (error) {
                  console.log(error.message);
              }); 
         }
      } 
    },
    function (error) {
        console.log(error.message);
    });

如果單純的使用 callback 撰寫,程式碼的可讀性會變得很差,重用性也不高,接下來我們就用 Promise 改寫。

(1) 將異步操作包成Promise (known as promisifying a function)

首先,讓我們將異步操作 getRemoteData 改寫成回傳 Promise 資料結構的 getPromiseWithRemoteData!

const getPromiseWithRemoteData = function (url) {
    return new Promise(function(resolve, reject) { // return promise
        let req = new XMLHttpRequest();
        req.responseType = 'json';
        req.open('GET', url);
        req.onload = function() {
            if(req.status == 200) {
                let data = JSON.parse(req.responseText);
                resolve(data); // being fulfilled
            }
            else {
                reject(new Error(req.statusText));
            }
        };
        req.onerror = function () {
        if(reject) {
            reject(new Error('IO Error'));
        } };
       req.send();
   });
};

(2) 將連續動作都用 then 的呼叫方式改寫,用 catch 方式補充例外處理

有了 getPromiseWithRemoteData 後,就能將上面的程式改寫成下面,程式碼一下子少了很多。

getPromiseWithRemoteData('/students')
    .then(R.sortBy(R.prop('ssn')))
    .then(R.filter(s => s.address.country == 'US'))
    .then((students) => { 
        return students.map((student) => {
            return getPromiseWithRemoteData(`/students/${student.ssn}/grades`)
                    .then((grades) => showStudents(student, average(grades)))
                    .catch((error) => console.log(error.message))
            })
        })
    .catch((error) => console.log(error.message))

補充 Promise.all()

根據上面的 students.map 程式碼,每個學生會透過 getPromiseWithRemoteData 取得所有分數後將平均顯示到頁面上,再回傳 Fulfilled 狀態的 Promise。但向遠端請求分數時,每個學生的分數回傳時間不一樣,會導致學生們的分數整合困難。舉例,如果我們希望得到住在 US 的學生的平均分數的再平均,根據之前的思路我們可能會撰寫如下。

getPromiseWithRemoteData('/students')
    .then(R.sortBy(R.prop('ssn')))
    .then(R.filter(s => s.address.country == 'US'))
    .then((students) => { 
        return students.map((student) => {
            return getPromiseWithRemoteData(`/students/${student.ssn}/grades`)
                    .then((grades) => average(grades))
                    .catch((error) => console.log(error.message))
            })
        })
    .then((averageGrades) => console.log(average(averageGrades)))  // wrong answer
    .catch((error) => console.log(error.message))

但這種需求用上面的寫法就會出錯,因為學生們的分數不會如我們想的那樣同時到達,而是會陸陸續續回傳,導致無法算出正確的平均,此時就需要使用 Promise.all()。 Promise.all()會將一個 Promise 陣列包裝成新的 Promise 物件,此 Promise 物件會等待陣列中的每個 Promise 都變成 Fulfilled 後,才執行 resolve 函式到達 Fulfilled 狀態,只要陣列中有一個 Promise 到 Rejected,Promise.all() 就會終止並到達 Rejected 狀態。我們可以將上面的程式改寫如下:

getPromiseWithRemoteData('/students')
    .then(R.sortBy(R.prop('ssn')))
    .then(R.filter(s => s.address.country == 'US'))
    .then((students) => { 
            return Promise.all(students)
                .then((student) => getPromiseWithRemoteData(`/students/${student.ssn}/grades`))
                .then((grades) => average(grades))
                .catch((error) => console.log(error.message))
            })
        })
    .then((averageGrades) => console.log(average(averageGrades)))    
    .catch((error) => console.log(error.message))

就算陣列元素本身不是 Promise,Promise.all() 也會先將陣列元素都轉換成 Promise 元素後,再用 Promise 包裝陣列。有了Promise.all(),我們也能做到”等待多個回傳資料”的功能。

後話

熟悉 ES6 Promise 後,可以搭配學習 Generator 和 Async/Await,觀察整個異步撰寫方法的演進。


範例參考與圖片來源

[FP]淺談functional programming效率優化

程式效率是常被人忽略的魔鬼

We should forget about small efficiencies, say about 97% of the time… premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.

– Donald Knuth, The Art of Computer Programming

如果對 functional programming 的 coding 方式有所了解,就會知道它利用 function 去抽象化資料的操作,以語意隱藏每個步驟的實作細節,讓程式碼可讀性更高,更容易用 pipeline 的方式對資料流作分析。

但程式的 效率 和 抽象化(abstraction) 通常無法兩者兼得,像是 functional programming 最常用的 currying, recursion 等等…肯定沒有直接用 for, iterative 來的有效率,還要注意 stack overflow 等問題,但 functional programming 的編程方式有利於一些效率優化的策略,且效果顯著,本文會針對這些策略做說明。

  1. 解說 context stack 和 javascript function 的原理
  2. 三個優化方法
    • lazy evaluation 延遲執行
    • memorization 記憶法
    • recursive call optimization 尾遞歸

Context Stack 和 Javascript Function

當 JavaScript 呼叫 function 時,會在內部創建一個紀錄目前 Function 執行環境的物件 (Execution Context frame) 並放入 Function context stack。Function context stack 被 Javascript 設計用來儲存這些Execution Context frame,記錄整個程式執行的狀況。

當程式一啟動,Global Context frame 會與 Function context stack 一起生成,放在 Stack 最底端,儲存著程式的全局變數。

FP

每一次呼叫 function 都會在 context stack 產生新的 Execution Context frame,最前方的 context frame 叫做 active context,是目前 code 的執行環境。在 code 執行完成後,active context 會被移出 stack,換下一個最前方的 context 當 active context,以下圖為例就是 logger。

FP

程式碼對照

const logger = function (arguments){
	var Log = new Log4js.getLogger(arguments)
	...
}

以下用一個錯誤的 recursive code 為例子,來測試瀏覽器到達 Range Error: Maximum Call Stack Exceeded 的情況。不同瀏覽器能接受的 frame 數量不同,我用 Google Chrome v57.0 測試,發現可以接受約16035個。示意圖如下。

function longest(i) {
	console.log(i);
	longest(++i);
}
longest(1);
FP

Lazy Evaluation

延遲調用 (Lazy Evaluation) 的精髓在於,將需要做的操作事先宣告好,相依資料都準備齊全,在真正需要執行的地方才執行操作。這樣做的好處是只針對必要的資料做計算,不用浪費時間計算不需要用到的資料。如下圖,主流的 Javascript coding 方式是 eager evaluation,資料會在需要用到之前就全部準備好,這種做法會因為浪費無謂的計算時間,而降低程式效率,相比下來,Lazy Evaluation 就只會計算需要用到的資料。

FP

下面再進一步講解 Lazy Evaluation 帶給我們的兩個優點:

  • Avoiding needless computations 避免不必要的計算
  • Using shortcut fusion in functional libraries 使用“融合操作”提升效率

關於”避免不必要的計算”,下面給了一個簡單的例子,將 alt 與 append 兩個 Function 做”事先”組合,在 showStudent 指定的學生學號 (val) 輸入時,才執行 func1, func2 和 append。

// R為Ramda
const alt = R.curry((func1, func2, val) => func1(val) || func2(val));
const showStudent = R.compose(append('#student-info'), alt(findStudent, createNewStudent));
showStudent('444-44-4444');

這種”後執行”的模式,也得利於資料暫存,甚至能在執行時,根據輸入的資料,對一連串 pipeline 步驟做優化,我們叫它 shortcut fusion。很多 functional libraries 已經幫我們實現這種優化,以 Lodash 的 _.chain 為例子,他不只可以將一系列的 function 串起來,並在該執行的時候利用 value() 執行;還可以整合 function 的執行與暫存,使其更有效率,舉例如下。

const square = (x) => Math.pow(x, 2); // 平方
const isEven = (x) => x % 2 === 0;  // 是否偶數
const numbers = _.range(200);
const result =
	_.chain(numbers)
	 .map(square)
	 .filter(isEven)
     .take(3) // 取前三的偶數值
     .value();  //-> [0,4,16]
result.length; //-> 5

我們可以發現結果 result 的容器長度只有 5,代表 Lodash 只計算了5個數值就完成了本操作的計算。對比計算全部 200 個數字才取前三個數值回傳,效率快了不少。

關於優化方法,首先 take(3) 讓 Lodash 知道本操作,只需要取前三個通過 map 和 filter 的數值即可;再來 Lodash 運用 shortcut fusion,將 map 和 filter 操作合併 compose(filter(isEven), map(square)),如此每個數值就不需要等其他數值計算完 map 才執行 filter,而是會一次性的經過平方和偶數判斷,由此省下不必要的計算時間。如果我們在 square 和 isEven 放 console.log,如下。

square = R.compose(R.tap(() => trace('Mapping')), square);
isEven= R.compose(R.tap(() => trace('then filtering')), isEven);

我們會觀察到 console 會 print 出以下的訊息五遍:

Mapping
then filtering

Memoization 記憶法

使用暫存 (cache) 是增加效率很重要的一種做法,而 functional programming 可以將 Memoization 運用到一個極致。

Cache 的實作方式,簡單說如下。在執行費時操作前,先檢查 cache 內是否有相對應的解答,如果沒有才做計算。

Memoization 要對擁有 referential transparency 特性的 function 才適合,因為其回傳值的影響因子只有函式參數,沒有 side effect 干擾,而函數參數正能當 Cache 裡 key-value pair 中的 key。

function cachedFn (cache, fn, args) {
    let key = fn.name + JSON.stringify(args);
	if(contains(cache, key)) { // 檢查是否暫存有相對應的解答
		return get(cache, key); // 回傳暫存的結果
    } else {
    let result = fn.apply(this, args); // 執行費時操作
    put(cache, key, result);
   	return result;
	}
}

我們可以用 cachedFu 來裝飾 findStudent,讓他擁有暫存的功能!如下。

var cache = {};
cachedFn(cache, findStudent, '444-44-4444');
cachedFn(cache, findStudent, '444-44-4444'); // 第二次取暫存的數值,執行速度超快

這種架構類似於 Design pattern 中的 proxy pattern,由 cachedFn 代理 findStudent,在執行 findStudent 前確認是否 cache 已經存有相應的結果;在執行findStudent 後,將回傳的結果儲存進 cache。但這種寫法,cache 和 function 是分離的,不只測試麻煩,還需要花額外邏輯去管理不同 function 的 cache。下面再介紹更進階的做法。

在 Function 中內建 cache

// 將cache儲存在Function的prototype
Function.prototype.memoized = function () {
	let key = JSON.stringify(arguments);
	this._cache = this._cache || {}; // 產生內部的 cache
	this._cache[key] = this._cache[key] || this.apply(this, arguments); // 如果cache的 key-value pair不存在,則執行此耗時操作
	return this._cache[key];
};
Function.prototype.memoize = function () {
	let fn = this;
	if (fn.length === 0 || fn.length > 1) { // 只讓擁有一個參數的function擁有cache
		return fn; 
	}
	return function () {
 		return fn.memoized.apply(fn, arguments);
	};
};

用這種方式將 cache 裝在各自的函式內部,避免創建 Global shared cache 而污染 Global Context,又方便做測試。我們用以下的 code sample 做展示。

var rot13 = s =>
   	s.replace(/[a-zA-Z]/g, c => String.fromCharCode((c <= 'Z' ? 90 : 122) >= (c = c.charCodeAt(0) + 13) ? c : c - 26));
var rot13 = rot13.memoize(); // 使用cache

觀察後發現,第二次呼叫的時間比第一次呼叫的時間快約 0.7 ms!

rot13('functional_js_50_off'); // 0.733 ms
rot13('functional_js_50_off'); // second time: 0.021 ms

他們之間的交互作用如下:

FP

Functional Programming 有利於 Memoization

以化學中的溶解度為例,粉狀的溶質比塊狀的溶質更容易溶解於溶劑,是因為粉狀的溶質接觸的表面積比較大;同樣的,當我們將 function 的步驟切的越細,耦合度越低,Cache 就能做的越仔細,也就能在各種微小的地方節省時間,進而產生很大的效能進步。舉一個例子

const m_cleanInput = cleanInput.memoize(); // 輸入做暫存
const m_checkLengthSsn = checkLengthSsn.memoize(); // 檢查結果做暫存
const m_findStudent = findStudent.memoize(); // 學生結果做暫存
const showStudent = R.compose(
		map(append('#student-info')),
        liftIO,
        chain(csv),
        map(R.props(['ssn', 'firstname', 'lastname'])),
        map(m_findStudent),
        map(m_checkLengthSsn),
        lift(m_cleanInput));
showStudent('444-44-4444').run(); //-> 9.2 ms on average (no memoization)
showStudent('444-44-4444').run(); //-> 2.5 ms on average (with memoization)

由上可知,每個微小的步驟都做暫存,累積起來後,在效能方面會有很大的改善。

遞迴和尾遞迴 (tail-call optimization (TCO))

由上一節,我們已經知道要使用 Memoization,Function 必須要是 referential transparency 且參數重複的可能性大,才有做 cache 的意義。但有的 Function 參數重複的機率低,又超乎想像的耗時,又使用大量 recursive,有什麼方法能讓 recursive 變得跟 loop 一樣有效率呢? 答案是,將 recursive 寫成尾遞迴 (tail-call optimization (TCO)) 的形式。

TCO

尾遞迴如下,將遞迴的 Function 放在函式最尾端,作為最晚執行的部分。

const factorial = (n, current = 1) =>
   	(n === 1) ? current : factorial(n - 1, n * current);

在經過 ES6 compiler 的最佳化後,會跟下面的 loop 一樣快!

var factorial = function (n) {
	let result = 1;
	for(let x = n; x > 1; x--) {
		result *= x; 
	}
	return result;
}

因為尾遞迴的寫法,讓 Javascript 知道它在執行 sub factorial 時,不需要將目前的 frame 保留,因為 sub factorial 執行完後不需要回到 parent context 去做剩下的工作。所以他可以在執行 sub factorial 前就直接將目前的 Active context 給丟棄,並將 sub factorial 的 Context frame 變成新的 Active frame。這種做法不只加快效率,也避免了可能 Stack Overflow 等問題。

FP

如何將遞迴寫成尾遞迴?

首先,來一個不是尾遞迴的函式。

const factorial = (n) =>
	(n === 1) ? 1 : (n * factorial(n - 1));

他不是尾遞迴的原因,是因為在 factorial(n - 1) 執行完後,還需要回到原本呼叫 factorial(n - 1) 的父函式,進行乘 n 的動作。如果要將它轉成尾遞迴,必須依照下面步驟:

  1. 將乘法操作當成 current 參數傳入 factorial
  2. 使用 ES6 default parameters 的特性,為每個參數設定初始值

改寫的結果為:

const factorial = (n, current = 1) =>
	(n === 1) ? current : factorial(n - 1, n * current);

下面有比較,比對 TCO 和 iterative 是多麼地相似,但 TCO 可讀性又比 iterative 更高一些。

FP

再來一個範例,請將下面的 recursive function 改成 TCO

function sum(arr) {
	if(_.isEmpty(arr)) {
		return 0; 
	}
   	return _.first(arr) + sum(_.rest(arr));
	}

一樣遵照上面兩個步驟,先將 function 尾部需要做的事情移成 function 的新參數,再設定參數的 default value,改寫結果如下。

function sum(arr, acc = 0) {
   	if(_.isEmpty(arr)) {
		return 0; 
	}
   	return sum(_.rest(arr), acc + _.first(arr));
	}

在團隊合作中,有時程式的可讀性比程式效率本身來得重要,尤其是在這個電腦運算已經如此快速的年代,也因此,最近 functional programming 的撰寫方式才會流行起來。究竟要使用什麼 coding 方式去實作功能,還是取決在於不同的專案和團隊需求。

總結

  1. Functional Programing 在某些狀況,效率會比 loop 寫法 (imperative code) 來得慢。
  2. 使用 functional libraties,像是 Lodash 來達成 lazy evaluation 和 shortcut fusion 等效率優化
  3. 使用暫存的方式 (Memoization) 來避免重複計算
  4. Functional programming 的低耦合,將 Memoization 發揮到極致
  5. 用尾遞迴 (TCO) 優化 recursive

參考與圖片來源