[gdome]Gdome2 performances

[Luca Padovani <lpadovan cs unibo it>]

Hi,

Paolo and I have been playing a bit with gdome2 during the last week to
understand how Gdome2 could be improved w.r.t. performances. We were
concerned about document creation since it occurred that serializing and
parsing the document back was much faster (say at least one order of
magnitude) than cloning the document node by node. 

We can now say that the investigation has been successful, and have
already committed several patches that make gdome2 write-access APIs
almost as fast as read-access APIs. Here is the list of points we
investigated, in chronological time:

a) DOM events. It is well known that DOM mutation events induce a
significant overhead as any modification of the document tree may fire
events walking up and down the structure. There are several points where
event propagation can be improved. We have currently improved only a few
bits, much more can be done. However, we have also implemented a
mechanism for filtering out event generation, on a per-event basis. This
way, say you know you're going to build a document from scratch and are
not interested in capturing events, you can disable all (or a subset) of
them. At first we thought events were the main reason for bad
performances of gdome2 write-access APIs (also testified by the
benchmarks at http://xmlbench.sourceforge.net/). Now we can say (somehow
surprisingly) that they account for a minimal overhead, and that some
other improvements can be done.

b) DOM garbage collection. The older mechanism for node gc was far more
complicated than necessary, as we were counting the number of allocated
wrappers _for_the_main_document_tree_. As it was noted on this list some
time ago, just having a reference to a disconnected subtree is enough
for recovering references to any node in the main document tree. For
this reason, the GC mechanism has been modified as follows: the main
document tree is freed only when no VALID gdome2 wrappers remain. A
valid gdome2 wrapper is an allocated wrapper of the main document tree,
or the wrapper of an disconnected document subtree whose topmost node
has an allocated wrapper. A document subtree is freed as soon as the
wrapper of its topmost element is deallocated. Any VALID wrapper of that
subtree is invalidated. This way, disconnected subtrees get freed
immediately, while the main document tree remains in memory until the
last valid wrapper is deallocated, no matter whether it refers to the
main document tree or a disconnected subtree.
This behaviour made superfluous a number of functions traversing
subtrees for counting the number of allocated wrappers, so that now any
add/remove operation of the main document tree can be performed in
constant time (rather than linear in the depth of the node being added
to/removed from, or in the number of elements in the subtree being
added/removed).

c) namespace declaration. Every time an element in a given namespace is
created, a new xmlNs structure is allocated and APPENDED to the oldNS
field in the document node. This has two consequences: 1) we allocate a
large number of xmlNs structures, but most of them are actually equal.
2) since the xmlNs structure is APPENDED, the oldNs list is scanned to
the end. This means that the cost of creating an element with
createElementNS is quadratic in the number of nodes with namespace
created. By inserting the node at the beginning of the list the time
decreases dramatically. It is still unclear how to implement caching of
xmlNs structures, perhaps we could sneak into libxml2 code, or Daniel
might give us a small hint to walk straight into the right path.
TJ also worked on this, so he may have good suggestions on how to fix
this the right way. I have the impression that any xmlNs pointed to from
an "ns" field is NOT freed, while xmlNs structures pointed to from an
"nsDef" are freed. Daniel? TJ?

Just to give you an idea of the improvements we were able to achieve,
with disabled events, b) and c): creation of a large MathML document
(288K of source XML) fell from more than 30 sec to 0.33 sec. With events
enabled the time is 0.66 sec.

We still need to iron out a few things, but we expect to release this
improved version of gdome2 within one or two weeks at most (and give it
version 0.8.0). And after that we'd like to see the updated
benchmarks...

Yours,
-- luca