Самый быстрый SAX-парсер для python

Внезапно захотелось пересчитать все xml-теги в 240 тысячах xml-файлов общим весом 180 GB. Питоном — и побыстрее.

Задача


На самом деле захотелось прикинуть — насколько реально перегнать Библиотеку, Чье Имя Нельзя Произносить Вслух, из fb2 в docbook. В связи со «специфичностью» FB2 надо прикинуть — какие теги можно просто пропустить ввиду редкости. Т.е. просто пересчитать количество вхождения каждого тега во все файлы.
По дороге планировалось сравнить разные sax-парсеры. К сожалению — тестирования не получилось, т.к. и xml.sax и lxml на первом же fb2 поломались. В итоге остался xml.parsers.expat.
Да, и еще — файлы *.fb2 упакованы в zip-архивы.

Исходные данные


Исходными данными является снапшот Библиотеки по состоянию на 2013.02.01, цельнотянутый из тор Интернетов: 242525 файла *.fb2 общим весом 183909288096 байт, упакованые в 56 zip-архивов общим весом 82540008 байт.
Платформа: Asus X5DIJ (Pentium DualCore T4500 (2x2.30), 2GB RAM); Fedora 18, python 2.7.

Код


Написано на скорую руку, с претензией на универсальность:
#!/bin/env python
# -*- coding: utf-8 -*-
'''
'''

import sys, os, zipfile, hashlib, pprint
import xml.parsers.expat, magic

mime = magic.open(magic.MIME_TYPE)
mime.load()
tags = dict()
files = 0

reload(sys)
sys.setdefaultencoding('utf-8')

def start_element(name, attrs):
	tags[name] = tags[name] + 1 if name in tags else 1

def	parse_dir(fn):
	dirlist = os.listdir(fn)
	dirlist.sort()
	for i in dirlist:
		parse_file(os.path.join(fn, i))

def	parse_file(fn):
	m = mime.file(fn)
	if (m == 'application/zip'):
		parse_zip(fn)
	elif (m == 'application/xml'):
		parse_fb2(fn)
	else:
		print >> sys.stderr, 'Unknown mime type (%s) of file %s' % (m, fn)

def	parse_zip(fn):
	print >> sys.stderr, 'Zip:', os.path.basename(fn)
	z = zipfile.ZipFile(fn, 'r')
	filelist = z.namelist()
	filelist.sort()
	for n in filelist:
		try:
			parse_fb2(z.open(n))
			print >> sys.stderr, n
		except:
			print >> sys.stderr, 'X:', n

def	parse_fb2(fn):
	global files
	if isinstance(fn, str):
		fn = open(fn)
	parser = xml.parsers.expat.ParserCreate()
	parser.StartElementHandler = start_element
	parser.Parse(fn.read(), True)
	files += 1

def	print_result():
	out = open('result.txt', 'w')
	for k, v in tags.iteritems():
		out.write(u'%s\t%d\n' % (k, v))
	print 'Files:', files

if (__name__ == '__main__'):
	if len(sys.argv) != 2:
		print >> sys.stderr, 'Usage: %s <xmlfile|zipfile|folder>' % sys.argv[0]
		sys.exit(1)
	src = sys.argv[1]
	if (os.path.isdir(src)):
		parse_dir(src)
	else:
		parse_file(src)
	print_result()


Результаты


Заряжаем:
time nice ./thisfile.py ~/Torrent/....ec > out.txt 2>err.txt

Получаем:
* Время выполнения — 74'15..45" (параллельно выполнялась небольшая работа и слушалась музыка, ессно);
* Получилось, что скорость обработки — ~40 MB/s (или 58 тактов/байт)
* Отброшено 2584 файлов *.fb2 (expat хоть и non validate parser — но не до такой же степени...) — ~10%;
* в файле results.txt — чего только нет…
* ну и, собственно то, ради чего всё затевалось: из 65 тегов FB2 _не_ применяется только только один (output-document-class); еще парочку (output, part, stylesheet) можно пропустить; остальные применяются от 10 тыс. раз.
* по грубым прикидкам чтение файлов (с распаковкой) занимает 52%, парсинг — 40%, обработка start_element — 8%.

А быстрее — можно? На python.
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 14

    +5
    Автор, конечно можно. Вот только это вы должны были нам рассказать как именно.
      +2
      Есть ощущение что если надо просто посчитать частоты тегов, то можно и без xml парсера обойтись. Возможно это будет быстрее.
        0
        Что еще можно попробовать:
        — раззиповать все или по очереди, но не питоном
        — попробовать не создавать парсер для каждого файла, возможно проканает (надо проверять)
        — парсить не все, а подмножетство, например 10% от библиотеки

        Хотя лично я думаю, что для разовой оценочной задачи можно часок и подождать :)
        +3
        А быстрее — можно?

        А вдруг вы просто уперлись в HDD или в CPU?
          0
          Конечно уперся. в CPU одного процессора. Не забываем про GIL Пайтона и то что таких программ должно быть запущено минимум 2 (в кол-во ядер процессора). Тогда можно и ускориться.
            0
            Я бы предложил под термином «быстрее» понимать «эффективнее» — кол-во перемолоченных байт на мегагерцеядро.
            Я пересчитал в такты процессора.
              +1
              Я бы сделал параллельное выполнение (можно даже в лоб — на bash). Делим входные файлы на сегменты по количеству ядер (например и у нас 4000 файлов и 4 ядра — значит делим на 4 группы по 1000 файлов) и на каждую кучу натравливаем свой парсер.
            +2
            А зачем переводить fb2 в docbook?
            Формат docbook предназначен в первую очередь для технических публикаций, есть тэги для вставок схем, примеров исходного кода, при этом читать его практически нечем на большинстве устройств, при этом можно автоматически конвертировтать в pdf, html и т.д. Fb2 расчитан на нетехнические тексты, зато читать его можно на почти на любом устройстве. Боюсь, что такое преобразование не имеет никакой практической пользы.
              0
              Вашей статье, если ваша цель таки найти более быстрое решение, место на Codereview.SE. Там и посоветуют и оценят и обсудят.
                +2
                вам бы хватило лексера без парсера. Кстати, интересно — xml.parsers.expat преобразует XML Entities? Если да, то при значительном их количестве производительность может просесть очень сильно из за множеств копирований памяти.

                Вместо
                def start_element(name, attrs):
                    tags[name] = tags[name] + 1 if name in tags else 1
                


                посоветовал бы использовать

                def start_element(name, attrs):
                    try:
                        tags[name] += 1
                    except KeyError:
                        tags[name] = 1
                
                Или вообще collections.Counter().
                Это потому что вероятность НЕ встретить тег в таблице гораздо меньше вероятности встретить. Так что эксепшны будут выпадать крайне редко (в основном в начале), зато избегаем лишнего поиска по хеш таблице if name in tags. Учитывая то, что эта функция вызывается крайне часто, можно получить существенный прирост скорости.
                  0
                  1. если речь идет о пойти на рекорд — то да, хватит даже grep'а. Но это только начало. Дальше надо будет анализировать библиотеку, составлять индексы и всё такое. Т.е. нужен именно sax-парсер.
                  2. try-except немного помогло, спасибо за идею.
                    0
                    Не проверял на скорость, но я в таких случаях использую defaultdict:

                    from collections import defaultdict
                    …
                    tags = defaultdict(lambda: 0)
                    …
                    def start_element(name, attrs):
                        tags[name] += 1
                    

                      0
                      Даже в первом варианте работа триггера занимает 8% времени. А 40% — таки сам парсер.
                      Но за подсказку спасибо
                        0
                        Здесь главный вопрос не скорость. Автосоздание переменных в таком виде зачастую весьма удобно: если проигнорировать импорт, то это одна короткая и понятная строчка (определение tags не считается, так как должно присутствовать в обоих случаях) против либо длинной, либо и вовсе четырёх. Читаемость везде нормальная, но если конструкций с except KeyError: много, то, если скорость позволяет, уж лучше использовать ваш вариант.

                        Кстати, вспомнил про аналогичный benchmark из этой темы. Если воспользоваться кодом оттуда (но файлом увеличенным в десять раз простым «умножением»), то распределение по скорости выглядит следующим образом (от самого быстрого: 3,3, 3,4, 3,7, 4,1):

                        d = defaultdict(int)
                        …
                            d[x] += 1
                        

                        try:
                            d[x] += 1
                        except KeyError:
                            d[x] = 1
                        

                        if x in d:
                            d[x] += 1
                        else:
                            d[x] = 1
                        

                        d[x] = d[x] + 1 if x in d else 1
                        

                        Собственно весь код:
                        import re
                        
                        n = 5
                        with open("./pg2600.txt", "r") as f:
                            s = f.read()
                        d={}
                        for x in re.findall(r'\w+',s):
                            <tested code here>
                        print repr([k for k,v in d.items() if v == n])
                        

                        Мой вариант стабильно быстрее except KeyError: (разница мала или очень мала, но он всегда быстрее), последние два могут показывать близкую производительность (но ваш всегда медленнее).

                        Замечу, что здесь используется int, а не lambda: 0. Разница в скорости, впрочем, не обнаружена.

                Only users with full accounts can post comments. Log in, please.