利用lxml 實作高效率的parser

最近實作facebook message viewer 的時候，需要去處理相當大的html 檔案，原始檔案大小約50 MB，beautify 之後會加到近80 MB。
實作上我用lxml 來實作，用了最基本的寫法，最直覺而簡單的寫法：

from lxml import etree
parser = etree.HTMLParser(encoding='UTF-8')
root = etree.parse("largefile.htm", parser)

問題是什麼呢，這樣lxml 一開場就把整個htm 給載到記憶體裡面，消耗一堆記憶體。
我們執行一下，看到的結果是這樣：

group count 525
parse 280895 entries
./parser.py   25.80s  user 0.21s system 99% cpu 26.017 total
  avg shared (code):         0 KB
  avg unshared (data/stack): 0 KB
  total (sum):               0 KB
  max memory:                710 KB
  page faults from disk:     0
  other page faults:         181328

710KB！根本記憶體不用錢一樣在浪費…，我把這個丟到網路服務上，光記憶體就害自己被砍了。

要打造節省記憶體的 xml parser，相關的資訊都來自這篇：
http://www.ibm.com/developerworks/xml/library/x-hiperfparse/

文中提供了兩種方式，一種是在parse 中指定我們的target class，我們要實作一個class 包含下列四個method：
1. start(self, tag, attrib): 有tag open的時候會呼叫這個method，這時只有tag name跟attribute 是可用的
2. end(self, tag): tag close 時呼叫，此時這個elem 的child, text都可以取用了
3. data(self, data): 在parser 收到這個tag 中的text child的時候，會將text 變為作為參數呼叫這個method
4. close: 當parse 結束時呼叫，這個method 應該回傳parse 的結果：
之後取用

results = etree.parse(target=TargetClass)

results 就會是close method return 的結果，這個方法不會消耗大量記憶體，不過它的問題是每一個遇到的tag 都會觸發一次事件，如果大檔中之有少量elements 是想剖析的，這個方法就會比較花時間；我的案例比較沒這個問題，因為我要剖析的內容幾乎橫跨整份文件。

另一個方法是用lxml 本身提供的 iterparse，可是傳入指定events的tuple跟一個有興趣的tag name的list，它就只會關注這些tags 的events：

context = etree.iterparse(infile, events=('end',), tag='div')
for events, element in context:
  print(elem.text)

文中並有說，iterparse 雖然不會把整個檔案載入，為了加速整份檔案可能被多次讀取的狀況，它會保留過去element 的reference，因此剖析會愈跑愈慢；解決方法是在iterparse 中，取完element 的資料就把它給刪除，同時還有element已經剖析過的sibiling，在iteration 最後加上這段：

element.clear()
while element.getprevious() is not None:
  del element.getparent()[0]

要注意的一個是，使用iterparse 的時候，要避免使用如getnext() 方法，我用這個方法，有機會在剖析的時候遇到它回傳None，應該是iterparse 在處理的時候，next element 還沒有被載入，因此getnext 還拿不到結果；從上面的end 事件來說，每個iteration，就只能取用element 裡面的元素。

改寫過之後的parse 的執行結果：

group count 525
parse 280895 entries
./parser.py   22.59s  user 0.07s system 99% cpu 22.669 total 
  avg shared (code):         0 KB
  avg unshared (data/stack): 0 KB
  total (sum):               0 KB
  max memory:                68 KB
  page faults from disk:     0
  other page faults:         21457

跟文中不同，因為我有興趣的tag 比例較高，執行時間沒有下降太多，但記憶體用量大幅下降。

另外文中也有提到其他技巧，像是不要用find, findall，它們會用XPath-like expression language called ElementPath。
lxml 提供iterchildren/iterdescendents 跟XPath，前兩者相較 ElementPath速度會更快一些；對於複雜的模式，XPath可以經過事先compile，比起每次呼叫元素的xpath() method，經過precompile 的XPath在頻繁取用下會快很多，兩種寫法分別是：

# non-precompile:
xpathContent = "//div[@class='contents']"
content = root.xpath(xpathContent)
# precompile:
xpathContent = etree.XPath("//div[@class='contents']")
content = xpathContent(root)

下面是我實測的結果，在都是完全載入記憶體下，有無precompile 的速度差接近兩倍，不過這也表示我用了iterparse 其實速度是下降的，因為我iterparse 其實是有使用precompile 的：

./parser.py 14.99s user 0.35s system 99% cpu 15.344 total
./parser.py 25.82s user 0.40s system 99% cpu 26.232 total

以上大概是使用lxml 時，一些減少記憶體用量的技巧，記錄一下希望對大家有幫助。

題外話：
在寫這篇的過程中，我發現Shell script 的time 其實是一個相當強大的指令，除了時間之外它還能記錄其他有用的數值，像是 memory usage, I/O, IPC call 等等的資訊。
我的time 是用zsh 下的版本，我也不確定它是哪裡來的，用whereis 找不到，用time --version 也看不到相關資訊，但man time 有相關的說明，總之copy and paste from stack overflow，把我的TIMEFMT 變數設定為：

export TIMEFMT='%J   %U  user %S system %P cpu %*E total'$' \
  avg shared (code):         %X KB'$'\
  avg unshared (data/stack): %D KB'$'\
  total (sum):               %K KB'$'\
  max memory:                %M KB'$'\
  page faults from disk:     %F'$'\
  other page faults:         %R'

其他的變數選項可以在man time 的format string 一節找到，這裡就不細講了，算是寫code 的一個小小收穫吧。