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). Changes involved: -Don't allocate a node list until we actually HAVE children -When allocating a node-list, go ahead and make it 4 elements long (instead of 0) so we don't immediately reallocate, and again. -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. -Use the has-child-nodes function instead of comparing length everywhere.
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
Hi,
Quoting Nathan Bird (nathan@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
-
David Lichteblau -
Nathan Bird