After a long discussion on the pgsql-docs list, it came to light that openjade's implementation of linked lists is extremely sub-par. Tom Lane came up with a patch that improves it by leaps and bounds. It cuts the processing time of the postgresql docbook source from 52+ hours to ~15 minutes.
Created attachment 104407 [details, diff] Patch from Tom Lane, improving linked list implementation
Patch applies fine to openjade-1.3.2-r1, and builds fine on x86.
Well, that's pretty impressive, however should be submitted upstream so that everyone can enjoy the speed... ;) http://openjade.sourceforge.net/bugs.html
Tom has sent a message to their -devel list about it, but seeing as current development is about nil I thought it would be easiest to get it included into portage. http://sourceforge.net/mailarchive/forum.php?thread_id=31202888&forum_id=2437
Very interesting. I'd of course love to add a patch like this, however, it seems not so easy to follow. Not that the patch itself is overly complicated, but openjade sources are, let's say, less than ideal. If you or the original author of the patch could comment the changes, specially those in style/primitive.cxx regarding to the protect and protect2 objects, it would help a lot. Also, for future reference, please create your patches as unified diffs when submitting them to resources such as this bugzilla (many other projects encourage this as well). Thanks.
(In reply to comment #5) > If you or the original author of the patch could comment the changes, specially > those in style/primitive.cxx regarding to the protect and protect2 objects, it > would help a lot. Here is Tom's reply: Date: Sat, 09 Dec 2006 23:35:54 -0500 From: Tom Lane <tgl@sss.pgh.pa.us> To: openjade-devel@lists.sourceforge.net Subject: Performance problems with NodeListObj lists It's been folklore for some time at the PostgreSQL project (www.postgresql.org) that running our documentation through jade to produce TeX output requires about three days on current hardware :-( Today I got motivated to look into why, and what I find is a pretty localized problem, as illustrated by this oprofile trace: samples % symbol name 2082917 98.5829 OpenJade_DSSSL::PairNodeListObj::nodeListFirst(OpenJade_DSSSL::EvalContext&, OpenJade_DSSSL::Interpreter&) 9713 0.4597 OpenJade_DSSSL::PairNodeListObj::nodeListRest(OpenJade_DSSSL::EvalContext&, OpenJade_DSSSL::Interpreter&) 5019 0.2375 OpenJade_DSSSL::AppendSosofoObj::traceSubObjects(Collector&) const 3571 0.1690 Collector::collect() 1938 0.0917 OpenJade_DSSSL::FlowObj::traceSubObjects(Collector&) const While I've not traced through the stylesheets to determine exactly what causes this, the behavior seen at the C++ level is that long NodeListObj lists (on the order of 10K elements) are built by successive "append" operations using the NodeList primitive. This produces a PairNodeListObj tree that's nested in the wrong direction; if you'll pardon some crude ASCII art: PairNodeListObj / \ PairNodeListObj e / \ PairNodeListObj d / \ PairNodeListObj c / \ a b This means that for an N-element list, nodeListFirst requires O(N) time to recurse down to the first element, and so does nodeListRest. So iterating through the list in the usual way requires O(N2) time. To add to the problem, nodeListRest generates another PairNodeListObj on each call, imposing a ton of mostly-useless load on the memory allocation/garbage collection machinery. Attached is a first-cut attempt at fixing this. With this patch, jade gets through the Postgres doc sources in 5 minutes rather than the reported three days. (I've never actually built the sources on the machine I'm testing on, so these numbers are not strictly comparable.) As patched, PairNodeListObj is used only in ReverseNodeListObj; it's tempting to get rid of it entirely by merging it somehow with the new CellNodeListObj class. But since I've never looked at the jade sources before today, I figured I'd better send it in without any more ado, so someone who knows better can tell me why this is not gonna work ... regards, tom lane [ plus patch, stripped ] ------- End of Forwarded Message The point of the patch is to introduce a version of NodeListObj that tracks both the head and the tail of the list it represents, so that successive appends can produce a tree that's right-deep instead of left-deep. The individual list cells (CellNodeListObj) just have Lisp-style car and cdr pointers, while HeadNodeListObj is the top of the list and remembers the current first and last cells. As for the changes in primitive.cxx, assuming that I have wrapped my head around the usage of ELObjDynamicRoot correctly, the original coding is actually wrong because it invokes PairNodeListObj() without protecting the "tem" pointer. If that were to point to a freshly-created, not-otherwise-referenced object, then if any garbage collection occurred during PairNodeListObj()'s memory allocation request you'd have a problem. I suppose this bug has not been seen because no version of asNodeList() that is actually used here returns a freshly created object, but it sure seems like an accident waiting to happen. So I modified the code to be sure that both nl and tem are ELObjDynamicRoot-protected during the nodeListAppend call. regards, tom lane
