[cxml-devel] Dom-impl improvements

[David Lichteblau]

Hi,

Quoting Nathan Bird (nathan at acceleration.net):
> We are building up a dom in memory as part of some XHTML and XUL generation.
> Found time/memory being spent in append-child which we make heavy use of.
> 
> Here are some changes that improve this. The children of a node are stored
> in a node-list (adjustable vector).  

Thanks for looking at DOM speed, it is the slowest part of cxml.

> Changes involved:
>   -Don't allocate a node list until we actually HAVE children

Careful here.  Your patch seems to actually return NIL to user code if
there are no children, and that is incorrect.

Node lists are guaranteed to be `live', so when children are added, a
caller who retrieved that nodelist previously must then see those
children appear in the previously empty object.

That's also why I am using vectors instead of lists in the first place,
since we could not add elements into NIL destructively.

>   -When allocating a node-list, go ahead and make it 4 elements long
> (instead of 0) so we don't immediately reallocate, and again.

OK...

>   -When vector-push-extending. Let the lisp implementation take care of
> increasing the size, instead of manually increasing by length 1 every
> time. Again this reduces constant reallocation.

That seems backwards.

We pass an explicit `extension' argument instead of trusting the lisp
implementation precisely because there are indeed implementations (I
forget which ones) that make the questionable choice of defaulting
`extension' to 1.  The lisp spec allows that choice, but as you note, we
would much rather see an exponential algorithm.

And we achieve that exponential increase by computing `extension' as
max(current length, 1).

> I attached some test results I got (kind of long), here are the summary
> lines:
>   seconds  |   consed   |  calls  |  sec/call  |  name  
> ----------------------------------------------------------
>      2.092 | 32,227,920 | 708,718 |            | Total   ;;OLD
>      0.859 | 25,507,240 | 691,366 |            | Total   ;;NEW

That seems very cool, so I hope that you can find a way to keep some of
these optimizations without breaking user code.

Note that the DOM test suite is very good.  Instructions for checking it
out and running it with cxml are at
http://common-lisp.net/project/cxml/doc/installation.html#tests

(Right now, with your patch, the test suite doesn't even start up
because of the NIL-isn't-a-nodelist problem explained above.)


Thanks,
David