Use buffers when constructing string node lists.
authorConrad Irwin <conrad.irwin@gmail.com>
Fri, 11 May 2012 03:17:25 +0000 (20:17 -0700)
committerDaniel Veillard <veillard@redhat.com>
Mon, 14 May 2012 05:51:30 +0000 (13:51 +0800)
commit7d553f834e2573c3352dc61a70ce4a7506db3c8c
tree90422cdb64e1ef69f74d29d83fd189d4dbd8ad1b
parenta0cd075d94518cd254d5fe122cc6825a1dfc6093
Use buffers when constructing string node lists.

Hi Veillard and all,

Firstly, thanks for libxml: it's awesome!

I noticed recently that libxml was taking a surprisingly long time to perform some
operations (many minutes instead of milliseconds), and so I did some digging. It turns out
that the problem was caused by the realloc()ing done in xmlNodeAddContentLen() which can
be called many (many) times when assigning some content into a node.

For background, I'm dealing with XML that contains emails, these can have large
attachments (~6MB) which are base-64 encoded, line-wrapped at 78 chars, and each line ends
with &#13;. This means that xmlNodeAddContentLen() is being called about 200,000 times,
and so there are 200,000 reallocs of a 6MB string, which takes a while... (I put a synthetic
example of this at https://gist.github.com/2656940)

The attached patch works around that problem by using the existing buffer API to merge the
strings together before even creating the text node, this keeps the number of realloc()s
at a managable level.

I'd love feedback on the patch, and am happy to fix problems with it, or explore other
solutions if you think that this is barking up the wrong tree :).

Thanks,

Conrad

P.S. Should I create a bug for this too?

------8<------

Before this change xmlStringGetNodeList would perform a realloc() of the
entire new content for every XML entity in the assigned text in order to
merge together adjacent text nodes. This had the effect of making
xmlSetNodeContent O(n^2), which led to unexpectedly bad performance on
inputs that contained a large number of XML entities.

After this change the memory management is done by the buffer API,
avoiding the need to continually re-measure and realloc() the string.

For my test data (6MB of 80 character lines, each ending with &#13;)
this takes the time to xmlSetNodeContent from about 500 seconds to
around 50ms. I have not profiled smaller cases, though I tried to
minimize the performance impact of my change by avoiding unnecessary
string copying.

Signed-off-by: Conrad Irwin <conrad.irwin@gmail.com>
include/libxml/tree.h
tree.c