DIV CSS 佈局教程網

您现在的位置: DIV+CSS佈局教程網 >> 網頁腳本 >  >> XML學習教程 >> XML詳解
新興 XML 解析方案 VTD-XML 深度介紹(上)
編輯:XML詳解     

談到 XML 的使用,最令人頭疼的兩件事莫過於它的高冗餘度與解析速度。當要處理大文件時,這個問題會被放大到無法忽視。本文要聊的就是如何突破 XML 的處理效能瓶頸。

傳統兩條路:DOM 與 SAX

選定解析方案時,大致只有兩種主流選擇:

  • DOM:W3C 的標準模型,把 XML 的結構資訊以樹形構築於記憶體中,並提供遍歷這棵樹的介面與方法。
  • SAX:低層的串流解析器,逐元素向前只讀處理,不保留結構資訊。

兩者各有利弊,卻都不是理想的答案。

DOM 優點是易用性極強——所有結構資訊都在記憶體裡,遍歷簡單,還支持 XPath。缺點是解析太慢、記憶體佔用過高(約為原檔的 5~10 倍),處理大文件幾乎不可行。

SAX 優點是解析快,記憶體佔用不隨 XML 大小線性增長(真正做到「XML 漲、記憶體不漲」)。缺點是易用性差:沒有結構資訊、無法遍歷、不支持 XPath。需要結構就得一邊讀一邊自己湊,可維護性很低。

看得出來,DOM 與 SAX 恰好是兩個相反的極端,誰都不能很好地滿足大多數場景。順帶一提,XML 的效能問題並不是 XML 本身的錯,而是解析器的問題。

拆解 DOM 的效能帳本

我們喜歡 DOM 式的用法,因為能遍歷、能支持 XPath。那效率究竟耗在哪裡?

  1. 大量物件的新建與銷毀。在今日大多數基於虛擬機器(託管或類似機制)的平台上,物件的建立與回收是耗時作業(主要是 Garbage Collection),而 DOM 機制中大量物件進進出出,無疑會觸發過多的 GC。
  2. 每個物件的額外開銷。每個物件都要額外 32 bits 存放記憶體位址;當物件數量堆到 DOM 那種量級,這筆帳相當可觀。
  3. 根本病灶:extractive parsing。DOM 與 SAX 都採用抽取式解析——解析時先把原檔的一部分(通常是字串)取出,再在記憶體中重建為物件。DOM 會把每個 element、attribute、processing-instruction、comment 都解析成物件並賦予結構,物件量自然爆炸。
  4. 更新效率低。在 DOM 中,每次要改動都得把物件資訊重新完整解析回 XML 字串——注意,是完整解析,原檔完全沒被利用。換句話說,DOM 並不支持增量更新。
  5. 編碼開銷。任何解析方法都得處理 XML 編碼,讀時解碼、寫時編碼。DOM 的另一個問題是:哪怕你只想改大檔案裡的一小塊,它也必須先把整個文件解碼並構築結構。

結論很清楚:DOM(與 SAX)的效能瓶頸主要出在 extractive parsing 模式上,並由此衍生出一連串相關問題。若能擊破這一層,XML 的處理效率與易用性都將躍升,其應用範圍與模式也可能被推向全新的高度。

出路:non-extractive 解析

VTD-XML 正是針對上述問題给出的答案。它是一個 non-extractive 的 XML 解析器,機制設計巧妙地把前面那些問題一一繞開,還順帶獲得了 non-extractive 的其他好處:快速的解析與遍歷、XPath 支持、增量更新等。

先看一組取自 VTD-XML 官方網站的數據:

  • 速度:解析速度是 SAX(掛 NULL content handler,即不插入任何額外處理邏輯的極速狀態)的 1.5~2.0 倍。
  • 記憶體:佔用為原 XML 的 1.3~1.5 倍(其中 1.0 倍是原檔本身,0.3~0.5 倍才是 VTD-XML 的額外開銷),而 DOM 是 5~10 倍。舉例來說,一份 50MB 的 XML 用 VTD-XML 讀進來約佔 65~75MB,用 DOM 則要 250~500MB。僅憑這一點,用 DOM 處理大 XML 幾乎不可能。

比 DOM 更好用、比 SAX 還快——聽起來不可思議?那就來看它的原理。

基本原理

像大多數好設計一樣,VTD-XML 的原理並不複雜,只是夠巧妙。為了做到 non-extractive,它把原 XML 檔原封不動地以二進位方式讀進記憶體,連解碼都不做;接著在這個 byte 陣列上解析每個元素的所在位置並記錄下來。之後的遍歷操作全在這些記錄上進行;真的需要取出內容時,才依記錄中的位置資訊回到原始 byte 陣列上解碼並回傳字串。

過程看起來簡單,細節裡卻藏著不少效能考量與潛在能力:

VTD 記錄結構

為了避免過多物件建立,VTD-XML 決定用原始的數值型別作為記錄型別,不必动用 heap。這套記錄機制就叫 VTD(Virtual Token Descriptor),它把效能瓶頸在 tokenization 階段就解決掉了,做法相當俐落。每個 VTD 是一個 64 bits 的數值,記錄該元素或 token 的起始位置(offset)、長度(length)、深度(depth)與類型(type)等資訊。

VTD 採用固定長度(官方定為 64 bits),目的就是為了效能:長度固定,讀取與查詢可以做到 O(1),也就能用陣列這種高效結構來組織大量 VTD,大幅迴避了物件帶來的效能問題。

把樹變成 byte 陣列操作

VTD-XML 最厲害的地方在於:它把 XML 這種樹形結構,簡化成了對一個 byte 陣列的操作。任何你能想到的字節級操作,如今都能套用到 XML 上——因為讀進來的 XML 本身就是 byte 陣列,而 VTD 記住了每個元素的位置等存取資訊。找到目標的 VTD 之後,用 offset 與 length 就能對原始 byte 陣列做任何處理。

舉例:想在一個大 XML 中刪除某個元素,只需找到它的 VTD(遍歷方式後述),把這個 VTD 從 VTD 陣列中移除,再把剩下的 VTD 全部寫入另一個 byte 陣列。因為被刪的 VTD 標明了該元素的範圍,新寫出的 byte 陣列裡自然就不含那段內容了。而「依 VTD 寫出新 byte 陣列」本質上就是一次陣列複製,效率極高——這就是所謂的增量更新。

遍歷方式:Location Cache

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 組件。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved