Gentoo Websites Logo
Go to: Gentoo Home Documentation Forums Lists Bugs Planet Store Wiki Get Gentoo!
Bug 158605 - app-text/openjade - patch to improve openjade processing speed
Summary: app-text/openjade - patch to improve openjade processing speed
Alias: None
Product: Gentoo Linux
Classification: Unclassified
Component: Current packages (show other bugs)
Hardware: All Linux
: Normal normal (vote)
Assignee: Michał Górny
Keywords: PATCH
Depends on:
Reported: 2006-12-19 17:00 UTC by David Blewett
Modified: 2019-09-17 07:15 UTC (History)
0 users

See Also:
Package list:
Runtime testing required: ---

Patch from Tom Lane, improving linked list implementation (pg.patch,10.25 KB, patch)
2006-12-19 17:01 UTC, David Blewett
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description David Blewett 2006-12-19 17:00:45 UTC
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.
Comment 1 David Blewett 2006-12-19 17:01:39 UTC
Created attachment 104407 [details, diff]
Patch from Tom Lane, improving linked list implementation
Comment 2 David Blewett 2006-12-19 17:03:08 UTC
Patch applies fine to openjade-1.3.2-r1, and builds fine on x86.
Comment 3 Jakub Moc (RETIRED) gentoo-dev 2006-12-20 00:53:53 UTC
Well, that's pretty impressive, however should be submitted upstream so that everyone can enjoy the speed... ;)
Comment 4 David Blewett 2006-12-20 03:48:44 UTC
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.
Comment 5 Leonardo Boshell (RETIRED) gentoo-dev 2006-12-21 20:57:35 UTC
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).

Comment 6 David Blewett 2006-12-24 05:05:52 UTC
(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 <>
Subject: Performance problems with NodeListObj lists

It's been folklore for some time at the PostgreSQL project
( 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    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

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