blog dds

2006.04.13

Xerces v Flex

What is the fastest way to process and XML file? I was faced with this question when I recently wanted to process a 452GiB XML file; for this amount of data speed matters. Some obvious choices were XML libraries, hand-crafted code, and lexical analyzer generators.

I dismissed hand-crafted code, because the processing wasn't trivial, and reasoned I had better things to do with my time than reinventing the wheel. Lexical analyzer generators, like lex used to have a rotten reputation regarding their time performance. Programmers often wrote that they hand-crafted a lexical analyzer, for the sake of efficiency. However, I thought that flex advertised as a fast lexical analyzer generator would generate, well, fast code. Because I also had to process the text data inside the XML tags in a non-trivial way I decided to adopt flex both for processing the XML file and the text data.

Here are some representative flex rules I used:

%x TEXT

%%
"<title>"[^<:]*"</title>"		title(yytext);
"<timestamp>"[^<]*"</timestamp>"	timestamp(yytext);
"<username>"[^<]*"</username>"		username(yytext);
"<ip>"					ip();
"<page>"				page_begin();
"<text xml:space=\"preserve\">"		BEGIN(TEXT);
<TEXT>"</text>"				BEGIN(INITIAL);
"</page>"				page_end();
"<restrictions>"			restrictions();
Note how I used flex's state transitions (BEGIN(...)) for creating a specialized text scanner inside the XML scanner.

A golden rule of code optimization is to measure before arriving to conclusions. Although I adopted the flex approach to simplify development, I was curious to see how the time performance of this approach compared with the performance of an XML parsing library. I reasoned that flex's clever generated code optimized for a specific set of XML tags would surely outperform a general-purpose XML parser that would at the very least also have to check that the document was well-formed. I downloaded the apache Xerces-C++ XML Parser and compared its performance against the flex code by running the SAXCount sample (with validation disabled) against the first five million lines of my document (processing about 150000 XML tags).

The results surprised me. All three flex performance times

real    23.411s
user    11.232s
sys      1.028s
were inferior to those of Xerces.
real    18.303s
user     8.355s
sys      0.523s
My conclusion is that Xerces is very good, and that flex is not really that fast; clearly there is ample scope for developing lexical analyzers that create faster code. Hats off to the Xerces team!

Read and post comments    AddThis Social Bookmark Button


Creative Commons License Last modified: Thursday, September 22, 2016 9:48 am
Unless otherwise expressly stated, all original material on this page created by Diomidis Spinellis is licensed under a Creative Commons Attribution-Share Alike 3.0 Greece License.