[jdom-interest] AttributeList performance

[Michael Kay]

> It's not actually all _that_ difficult to create a
> specialized List
> that has fast by-name access, compact presentation ...


But it does depend very much on usage patterns. In one application with a
similar requirement years ago, we found that the best solution was a linked
list in which the matched item was always moved to the front of the list.
This works brilliantly if there are many repeated requests and some items
are much more frequently requested than others; but it isn't a general
solution.

Generally in this kind of application one needs dynamic, self-adjusting data
structures. Saxon has gradually moved in that direction. For example, it
adds "prior pointers" (previous sibling pointers) to a tree the first time
someone attempts reverse navigation. Recently I've changed it so that it
inserts parent pointers at intervals (of 20 nodes or so) in the chain of
siblings, to prevent pathological performance problems with database
extracts that have 50,000 children of one parent. Saxon does linear
searching for attributes (and for child elements), but if I wanted something
better, then I would look to some kind of dynamic approach that adjusts to
the actual volumetrics and usage patterns on the data. You can't allow
solutions for the worst-case scenarios to impose costs on the common case,
and providing lots of user tuning options doesn't work unless you want a
heavy support load.

Michael Kay
http://www.saxonica.com/