提起 XML 的實際使用,最令人頭痛的就是冗長(verbosity)與解析速度;一旦要處理大型 XML 檔,問題更形尖銳。本文要介紹的 VTD-XML,正是針對這類效率瓶頸所提出的一套新思路。
處理 XML 時,我們大致有兩種選擇。DOM 是 W3C 的標準模型,把 XML 結構以樹狀建於記憶體中,易用、可遍歷、支援 XPath,但解析慢、記憶體占用高(約為原檔的 5~10 倍),幾乎無法處理大檔。SAX 則是逐元素向前只讀的低階 parser,速度快、記憶體不隨 XML 大小膨脹,卻缺乏結構資訊、無法遍歷、也不支援 XPath,可維護性低落。兩者恰好是相反的兩個極端,都不太理想。
DOM 為何低效?在今日多數基於虛擬機(含垃圾回收機制)的平台上,大量物件的建立與銷毀本身就耗時,而 DOM 正是把每個 element、attribute、comment 都解析成物件。每個物件還額外耗用 32 bits 存記憶體位址,物件一多,開銷可觀。
更根本的問題在於 DOM 與 SAX 都採用「extractive parsing(抽取式解析)」:解析時會把原檔的片段(通常是字串)取出到記憶體中再另行建構物件。由此又衍生出更新效率的問題——DOM 每次改動都得把整个模型重新完整解析回 XML 字串,並不支援增量更新(Incremental Update)。此外,不論何種解析法都得處理編碼問題,DOM 即使只想改一小塊,也必須先將整個文件解碼並建構結構,無形中又是一筆開銷。
VTD-XML 是一個 non-extractive 的解析器,籍由巧妙的機制避開上述問題,還「順帶」帶來快速解析、遍歷、XPath 支援與增量更新等好處。根據官方數據,它的解析速度約為 SAX(不掛任何 content handler)的 1.5~2 倍;記憶體占用僅為原檔的 1.3~1.5 倍。舉例來說,一份 50MB 的 XML 用 VTD-XML 讀入約占 65~75MB,DOM 卻要 250~500MB,差距懸殊。
VTD-XML 把原檔原封不動地以二進位讀進記憶體,連解碼都不做,再在這個位元組陣列上解析每個元素的並記錄相關資訊;之後的遍歷都在這些記錄上進行,需要取值時才依記錄中的位置資訊解碼回字串。
它將每個元素的資訊記錄為 VTD(Virtual Token Descriptor)——一個固定 64 bits 的數值型別,記錄起始位置(offset)、長度(length)、深度(depth)與型別(type)。因為長度固定,讀取與查詢可達 O(1) 效率,用陣列組織即可,大幅避開大量使用物件所衍生的效能問題。
由於讀入的 XML 是位元組陣列、VTD 又標明了每個元素的位置,任何你能想到對位元組陣列的操作都能套用到 XML 上。例如要刪除某個元素,只需找到它的 VTD、從陣列移除,再把其餘 VTD 寫入另一個位元組陣列即可,這就是高效率的增量更新。遍歷方面,VTD-XML 採用 LC(Location Cache),以深度為基礎建構樹狀表結構,每個 entry 也是 64 bits,前 32 bits 為 VTD 索引、後 32 bits 為其首个子元素的索引,能在極少步數內抵達目標位置。
1.5 版已加入 XPath 支援,實用性更上一層。此外,由於其底層以二進位處理,未來完全能對接 Binary XML 標準,把 XML 的應用推向更高層次,值得期待。當然,VTD-XML 仍有許多值得改進之處。值得一提的是,它是採 GPL 授權的開源專案,目前提供 Java 與 C 兩種平台;若想在 .NET 上使用,建議以 IKVM 將其轉為 .NET 組件。