談到 XML 的使用,最令人頭疼的兩件事莫過於它的高冗餘度與解析速度。當要處理大文件時,這個問題會被放大到無法忽視。本文要聊的就是如何突破 XML 的處理效能瓶頸。
選定解析方案時,大致只有兩種主流選擇:
兩者各有利弊,卻都不是理想的答案。
DOM 優點是易用性極強——所有結構資訊都在記憶體裡,遍歷簡單,還支持 XPath。缺點是解析太慢、記憶體佔用過高(約為原檔的 5~10 倍),處理大文件幾乎不可行。
SAX 優點是解析快,記憶體佔用不隨 XML 大小線性增長(真正做到「XML 漲、記憶體不漲」)。缺點是易用性差:沒有結構資訊、無法遍歷、不支持 XPath。需要結構就得一邊讀一邊自己湊,可維護性很低。
看得出來,DOM 與 SAX 恰好是兩個相反的極端,誰都不能很好地滿足大多數場景。順帶一提,XML 的效能問題並不是 XML 本身的錯,而是解析器的問題。
我們喜歡 DOM 式的用法,因為能遍歷、能支持 XPath。那效率究竟耗在哪裡?
結論很清楚:DOM(與 SAX)的效能瓶頸主要出在 extractive parsing 模式上,並由此衍生出一連串相關問題。若能擊破這一層,XML 的處理效率與易用性都將躍升,其應用範圍與模式也可能被推向全新的高度。
VTD-XML 正是針對上述問題给出的答案。它是一個 non-extractive 的 XML 解析器,機制設計巧妙地把前面那些問題一一繞開,還順帶獲得了 non-extractive 的其他好處:快速的解析與遍歷、XPath 支持、增量更新等。
先看一組取自 VTD-XML 官方網站的數據:
比 DOM 更好用、比 SAX 還快——聽起來不可思議?那就來看它的原理。
像大多數好設計一樣,VTD-XML 的原理並不複雜,只是夠巧妙。為了做到 non-extractive,它把原 XML 檔原封不動地以二進位方式讀進記憶體,連解碼都不做;接著在這個 byte 陣列上解析每個元素的所在位置並記錄下來。之後的遍歷操作全在這些記錄上進行;真的需要取出內容時,才依記錄中的位置資訊回到原始 byte 陣列上解碼並回傳字串。
過程看起來簡單,細節裡卻藏著不少效能考量與潛在能力:
為了避免過多物件建立,VTD-XML 決定用原始的數值型別作為記錄型別,不必动用 heap。這套記錄機制就叫 VTD(Virtual Token Descriptor),它把效能瓶頸在 tokenization 階段就解決掉了,做法相當俐落。每個 VTD 是一個 64 bits 的數值,記錄該元素或 token 的起始位置(offset)、長度(length)、深度(depth)與類型(type)等資訊。
VTD 採用固定長度(官方定為 64 bits),目的就是為了效能:長度固定,讀取與查詢可以做到 O(1),也就能用陣列這種高效結構來組織大量 VTD,大幅迴避了物件帶來的效能問題。
VTD-XML 最厲害的地方在於:它把 XML 這種樹形結構,簡化成了對一個 byte 陣列的操作。任何你能想到的字節級操作,如今都能套用到 XML 上——因為讀進來的 XML 本身就是 byte 陣列,而 VTD 記住了每個元素的位置等存取資訊。找到目標的 VTD 之後,用 offset 與 length 就能對原始 byte 陣列做任何處理。
舉例:想在一個大 XML 中刪除某個元素,只需找到它的 VTD(遍歷方式後述),把這個 VTD 從 VTD 陣列中移除,再把剩下的 VTD 全部寫入另一個 byte 陣列。因為被刪的 VTD 標明了該元素的範圍,新寫出的 byte 陣列裡自然就不含那段內容了。而「依 VTD 寫出新 byte 陣列」本質上就是一次陣列複製,效率極高——這就是所謂的增量更新。
VTD-XML 用 LC(Location Cache)來遍歷,簡單說就是以 VTD 的深度為標準構築出的一組樹形表結構。LC 的每個 entry 同樣是 64 bits 的數值:前 32 bits 是一個 VTD 的索引,後 32 bits 是該 VTD 第一個子節點的索引。靠這些資訊,任何你想抵達的位置都能算出來(具體算法可參考官方網站文章)。
這種遍歷方式讓 VTD-XML 的操作介面與 DOM 不同(合理,因為底層模型不同),但代價換來的是極少的步數就能抵達目標節點,遍歷效能相當出色。
VTD-XML 的特性確實迷人。1.5 版已經加入 XPath 支持(能遍歷就能支持 XPath,這遲早的事),實用性已超出多數人的想像。它還有一項潛力:以目前的處理方式,未來完全能對接 Binary XML 標準,把 XML 的應用推向更高一層。
當然,它仍有許多值得改進與探討之處。順帶一提,VTD-XML 是開源專案(GPL),目前有 Java 與 C 兩種平台支持;若想在 .NET 上試用,建議用 IKVM(BSD 授權)把它轉成 .NET 組件。