10 months ago

JSON(Javascript Object Notation)是個輕量且好用的API傳輸資料格式,Spec是基於Javascript, ECMA-262的Spec子集,所以在Javascript原生支援JSON,寫起API相當的方便;
在使用上不免會反覆的使用JSON.parse/JSON.stringify在JSON與string格式間轉換,最近有趣的是發現了 fast-json-stringify,號稱stringify的速度勝過原生的JSON.stringify?!!
那就來研究JSON在Javascript中的實現方式與為何fast-json-stringify執行速度會比原生快。

JSON stringify

JSON stringify的方法定義在ECMA-262中,主要就是將JSON格式的value轉換為string,function中須包含一個必要參數和兩個選擇性參數

value

也就是JSON格式的值。

replacer?

如果是function的話,則會改變object/array轉換成string的方式;
如果是Array<string | int>,則代表object中的該屬性會被轉換為string

space?

<string | int>,用於輔助人類閱讀,會插在結果之前。
接著稍微看一下spec的stringify操作流程,以下有稍微簡化

1. 檢查replace
如果是function(Object && isCallable)則設為ReplaceFUnction
如果是陣列則輪詢元素並放入PropertyList

2. 檢查space
如果space是Object則取得其中的屬性"space"
如果space是Number則取min(10, space)並轉換成對應長度的空白字串,如果space < 0則為空字串。
如果是String,則取string前10個字元或更少
也就是最長space長度為10

3. 創建wrapper
new Object()並指定給wrapper,並將value的名稱(也就是抓出Object中每個屬性並重新建Object),接著呼叫Str(key, holder)並回傳結果,wrapper便是holder、key一開始為空字串

最後一步有點不太懂,原文如下
9. Let wrapper be a new object created as if by the expression new Object(), where Object is the standard built-in constructor with that name.
10. Call the [[DefineOwnProperty]] internal method of wrapper with arguments the empty String, the Property Descriptor {[[Value]]: value, [[Writable]]: true, [[Enumerable]]: true, [[Configurable]]: true}, and false.
11. Return the result of calling the abstract operation Str with the empty String and wrapper.

======= 目前只是創建JSON.stringify的前置作業,str才是將屬性值轉為string的關鍵 ======
接著看Str(key, holder)的步驟,主要就是取值並轉成string格式,這裡可以取得先前的 ReplacerFunction

1. 設定value為 holder中取得key屬性的值

2. 如果value是Object,且如果 toJSON可以被呼叫,則呼叫 toJSON

3. 如果ReplacerFunction存在則呼叫

4. 如果value是屬性且為 Number/String/Boolean則相對呼叫為 ToNumber/ToString/ToBoolean轉換格式

5. 如果value是null回傳"null",true/false回傳"true"/"false"

6. 如果value是string則呼叫設定雙引號" Quote(value)

7. 如果value是Number,則呼叫ToString

8. 如果value是Object且isCallable為false,陣列呼叫JA(value) 物件呼叫JO(value)轉換

9. 其餘回傳undefinded

======= Quote function
稍微喵過,輪詢每個character,如果是以下字元[",\b,\n,\s....控制字元],則加個\變成["\"", "\n",....]

======= JA/JO
最後整合的函式,對應處理陣列與物件,基本上都是輪詢每個屬性與值並呼叫Str(),最後加上space產生的gap(如果有的話)產生結果。

大致瀏覽過Spec,來看一下MDN JSON.stringify()與一些好玩的範例,以下執行於Chrome console

let json = {a:"123", b:123, c: true, d: null, e: undefined, f: function(){} }

JSON.stringify(json)

JSON.stringify(json, function(k,v){ if(typeof k == undefined) return "undefinded"; return v }, "   ")

JSON.stringify(json, function(k,v){ if(typeof v == "undefined") return "undefinded"; return v }, "space_is_max10_other_would_be_cut")
所以我說那個function怎麼沒被stringify呢

回到Spec中的Str()步驟,可以看到value如果是Object且isCallable為false才會被執行,而function屬於Object && isCallable所以就落到最後的條件式 return undefinded。
而undefined的屬性都不會被stringify成字串的一部分。
這部分可以翻到 [ecma-262規格文件]中的isCallable,如果value是type of Object且有[[Call]]內部函式則回傳true;
再一步跟進到ECMAScript Value type definition發現只有function被創建時才有[[Call]]這個內部函式。

The undefined value is not rendered.

Object Literal is not JSON

在JS中創建物件的方式很多,最自由莫過於文字字面變量,也就是Object Literal,在大括號內{}的變數即自動透過new Object創建,但這和JSON是兩種容易被混用,但實則不同的定義方式與規範;
Object Literal可是為JSON的超集合,像JSON的Key必須用雙括號刮著,且不能有function的定義等。

fast-json-stringify: 2x faster than JSON.stringify()

fast-json-stringify好狂啊,盡然可以是比原生的JSON.stringify()快兩倍,到底是怎麼做到的呢?!!!

首先掃過readme可以看到 fast-json-stringify提供的功能為

  1. 定義Schema
  2. 支援型別檢查與而外的檢驗
  3. 如果傳入的物件跟Schema不合者,則不加入結果字串,但可以設定參數改變
  4. 額外支援long:int64型別

這裡稍微分析一下fast-json-stringify的原始碼,真的是蠻妙的,他是把每個驗證方式轉成用字串表示程式碼,然後把所有的程式碼用Function constructor方式創建,所以在一開始定義schema並傳入stringify(schema)後就會回傳對應的stringify方式,所以程式碼充斥著大量 es6 string interpolation的寫法

var addComma = `
  if (addComma) {
    json += ','
  }
  addComma = true
`

if (type === 'object') {
      code += buildObject(pp[regex], '', 'buildObjectPP' + index, externalSchema, fullSchema)
      code += `
          ${addComma}
          json += $asString(keys[i]) + ':' + buildObjectPP${index}(obj[keys[i]])
      `
} else if (type === 'array') {
      code += buildArray(pp[regex], '', 'buildArrayPP' + index, externalSchema, fullSchema)
      code += `
          ${addComma}
          json += $asString(keys[i]) + ':' + buildArrayPP${index}(obj[keys[i]])
      `
}
.....

所以可以看到一堆code不斷連接起來,組成整個stringify的function程式碼,最後module.exports = build,此build function的重點

  var dependencies = []
  var dependenciesName = []
  if (hasAdditionalPropertiesTrue(schema)) {
    dependencies.push(fastSafeStringify)
    dependenciesName.push('fastSafeStringify')
  }
  if (hasAnyOf(schema)) {
    dependencies.push(new Ajv())
    dependenciesName.push('ajv')
  }

  dependenciesName.push(code)

  return (Function.apply(null, dependenciesName).apply(null, dependencies))

這裡我們先簡化,在chrome console打

var func = (Function.apply(null, ["a","console.log(a)"]).apply(null, ["main"]))

這就是把程式碼轉成Function物件回傳使用,同時處理相依套件的問題。

fast-safe-stringify:用於快速字串化Javascript Object,而且遇到Circular會回傳Circular字樣而非拋出錯誤!
原始碼蠻簡單的,就是有個stack會暫存parent名稱,如果child名稱跟parent重複則有cycle存在。
ajv: Another JSON Schema Validator,定義JSON Schema
另外在 readme有提到一個module flatstr,主要是把string壓平成Array,裡頭介紹提到在V8中,如果JS兩個字串相加會以tree的方式儲存而非取得一塊連續記憶體以array方式儲存,因為以tree結構儲存比較彈性,但如果大量concat後tree過大就會導致效能下降,V8會把tree轉成array儲放陣列,flatstr主要就是提供主動呼叫String::Flatten的方式。
在案例中,fs.WriteStream調整後性能提升20~30%,非常驚人。
這麼有趣的方法原始碼就

module.exports = function flatstr(s) {
  Number(s)
  return s
}

結束了,作者表示呼叫Number(s)只是種非直接呼叫String::Flatten的方式(github repo有benchmark),果然山不在高有仙則靈,只能跪了OTZ

所以快在哪裡?

使用文件搜尋快速找 fast-json-stringify原始碼中 JSON.stringify的蹤跡,你只會找到三個真正需要JSON.stringify的地方(廢話繞口令?!),回看第一段 Spec複雜的型別檢查,fast-json-stringify透過 JSON Schema定義已經確定了物件中的值型別,就可以大量降低檢查型別的困擾,達到速度的提升啊!!!!!!

結語:盡量預定義物件的所有屬性

雖然JS Object可以隨時動態插入屬性,但這會導致不好維護、性能低落(V8物件管理有關),導入JSON Schema不但增加物件屬性的預期性,對於維護性與性能也都大大增加,以後可以考慮導入。

← 影音串流服務 - 基本介紹與Wowza教學 Koa2 源碼解析 - 簡潔美麗的框架 →
 
comments powered by Disqus