Ours & Hippy — le blog [performance]

Those who have been keeping an eye on my Git repository have surely noticed the recent update of the bitvopt branch, which contains alternate implementations of the core routines of the matching engine (match.c): followsibling and followparent. The bitvopt code replaces the direct tests and propagation entirely with bit vector operations (masking, shifting, etc.).

The main advantage of this approach is vectorization. Such operations are easily done on a single unit (the type of which is defined in bitv.h and somewhat configurable with the USE_STDINT macro) and can be generalized to loops that carry no dependencies between iterations. These loops can then be auto-vectorized by a sufficiently smart compiler. The current code in bitvopt is understood and vectorized by both GCC 4 with -ftree-vectorize and ICC 10.1. Beware, ICC 10.0 fails because of the restrict qualifiers, which are necessary; also note that, on x86, you have to pass USE_STDINT in order to select a type bigger than unsigned char, or else, SIMD shift operations won’t be available. To see the vectorization reports, you can use -ftree-vectorizer-verbose=5 for GCC and -vec-report for ICC.

The results are not quite satisfactory and the branch was not merged into master:

On the chart, GCC has vectorization disabled by default while ICC always has vectorization (even though I have not specified -vect anywhere). The measurements have been done on my old Pentium 4, with -O2 and appropriate architecture flags, with GCC 4.1.2 and ICC 10.1. The values are averages computed over 100 runs of the following pattern on the same dictionary as before:

$ xmlgrep 'p[hw/?="Ab\"a*cus"]#'

I must say I can’t explain why operations on native integers (the -int builds) are slower than those on bytes. As for the relative gain of non-vectorized code over vectorized one, this is most probably because the pattern is not long enough (less than one base unit) to take advantage of SIMD so we lose in the overhead introduced with vectorization (all the more so as data may be unaligned on entry of these functions). Lastly, it seems auto-vectorization in GCC really is not advantageous right now, since the non-vectorized versions tend to outperform their vectorized counterparts when compiled with GCC (and this is not the case with ICC).

Anyway, this was just a side experiment of mine; work on the main tools continue: plans for more features in the matcher (on request, case insensitivity, arithmetic predicates, maybe some other things) as well as the introduction of xmlsed are underway.

After spending some days fixing bugs in the xmlgrep matcher code, I took some time again to look at the performance issues. The previous measurements showed xmlgrep was slower than xmlstarlet, even on patterns without subpatterns, which are theoretically optimal for my implementation. That really bothered me.

Profiling seemed to show xmlgrep spent most of its time in bit vector operations – that much was expected. But my vain attempt (Git branch bitvopt) at replacing tests (the FOREACHVSTATE macro) with bit vector operations proved actually slower than the master version.

Then I had a talk with David Young, my mentor, and we concluded that both the input mechanism and the memory allocation pattern were suboptimal.

About the input problem, I’ve replaced the old input feeder, which used fgets(3), with direct read(2) calls, and this has indeed shaved some seconds off the counter. This is especially noticeable for patterns without subpatterns, since I/O accounts for more in that case.

The memory allocation issue was more serious. Basically, a lot of bit vectors and subcontext frames were needlessly allocated then almost immediately freed afterwards. This is due to the following construct commonly found in patterns (maybe I should optimize this one case specifically): patterns which start with an anchored subpattern, typically something like a[b] or {a%b}. This kind of patterns causes the matcher to try to match every node in the tree against the subpattern yet fail almost all the time (on all those nodes that do not match a). Such a failed subpattern match entails a call to pushsub followed by a call to popsub, which are responsible for the management of the subcontext stack.

I’ve switched to pool allocators for both internal tree nodes and bit vectors. This has drastically reduced the number of allocations made during a run. David also pointed out that I could use a pre-allocated vector instead of a linked list for the subcontext stack, and I remembered one of the nice properties of my implementation: the number of subcontext is bounded by the maximal nesting depth of subpatterns. He also suggested I should use copy-on-write bit vectors, but that proved unnecessary as I now use pointer swapping instead of copying then erasing (which was quite stupid in the first place, I agree).

All these changes were developed in the memopt2 branch overnight and are now in master. The same measurements as before show some exciting improvements, most notably the fact that we are now faster than libxml on patterns that do not use look-ahead! Basically, on this example, we are about 50% faster than before.

As xmlgrep is approaching a pre-pre-alpha release (something that is still very experimental, but nonetheless working, somewhat :), I’ve been doing some basic tests on it, including one simple benchmark. The results are, IMHO, encouraging. The benchmark pits xmlgrep against equivalent existing software:

• the selection tool from the xmlstarlet project (available in pkgsrc as textproc/xmlstarlet);
• another xmlgrep from the Perl Twig package (textproc/p5-XML-Twig in pkgsrc);
• and GNU grep, though it does not really accomplish the same, from the base NetBSD-5 distribution, as a reference.

Since each tool accepts its own patterns and treats them differently, I’ve tried my best to get meaningful results with each, but obviously, the behaviors obtained differ somewhat.

The tests/memplot script was used to make the sampling. The data were plotted using Gnuplot. The following commands were run:

$ xmlgrep 'hw/?="Ab\"a*cus"' d.xml
$ xmlgrep 'hw[?="Ab\"a*cus"]' d.xml
$ xml sel -t -c "//hw[text()='Ab"a*cus']" d.xml
$ xml_grep "hw[string()='Ab\"a*cus']" d.xml
$ grep 'Ab"a\*cus' d.xml

The goal was to retrieve the <hw> element which contains the Ab"a*cus string from a 53M dictionary, retrieved from http://www.ibiblio.org/webster/ and merged into a single file.

The first two lines correspond to two different invocations of xmlgrep, which do not do exactly the same thing, and with the first being the good one, the other inefficiently abusing the look-ahead mechanism. Yet, it was included for comparison purposes and maybe to be fair to the XPath-based alternatives, which have to rely on a predicate.

Results follow; the second and third pictures are just zooms which omit one or another of the candidates.

As expected, xmlstarlet, which uses a full DOM model requires a lot of memory to do its work (more than 400M!). But it is the fastest.

My xmlgrep, when used right, is still nearly 42% slower than xmlstarlet (from above 4s to below 6s), but I think the times remain reasonable; memory-wise, it is also the lightest, with a constant 2.9M in use throughout the whole run. Even GNU grep requires about 2.8M.

Surprisingly, the Twig xmlgrep is not too big a memory killer, though its memory usage increases over time, by steps (though it looks linear on the long run). This appears somewhat strange to me; why some nodes should be pruned from its internal DOM-like tree while others seem to remain for the duration of the program. However, on the speed side, Twig is predictably very slow; it takes nearly two minutes to produce the results comparable to those of its C counterparts.

That’s it for tonight; as one friend of mine told me, more interesting benchmarks will probably come from actual users.