Ref: Your note of Thu, 8 Oct 2015 09:12:39 -0400
A digital tree (also known as a "radix tree" or a "trie") can be
a very efficient way of looking up keyed items, as used for
example in CICS Shared Data Tables. It is often faster than
binary search (because each decision can select between more than
two choices) but still supports sequential and approximate key
("greater than") retrieval, and it does not require "rebalancing"
to maintain performance. For keys containing EBCDIC characters,
a base-16 tree is a reasonable compromise between performance and
storage use.
One thing to watch out for in main storage searches is processor
cache equivalence class side-effects. Cache storage is typically
not organised as a single big pool but is instead partitioned
into a number of "equivalence classes" determined by some number
of low-order bits of the address. This means for example that
addresses at the same offset within different 4K pages are likely
to be cached in the same equivalence class, so repeated scans of
a set of such fields can encounter degraded performance if the
number of such fields exceeds the number of cache lines within
the equivalence class, resulting in that class being depleted
even when there is plenty of cache left in other classes. If the
data within the pages is not often actually needed, this method
also requires an unnecessarily large real storage working set.
So for the best performance it's a good idea to use an index
structure where the most frequently referenced information for
searching is stored in a fairly dense form, even if storage is
not particularly constrained, in order both to minimise the
number of cache lines that need to be accessed, and to ensure
that they are not likely to end up in the same equivalence class.
Keep in mind that cache performance characteristics are not part
of the architecture, and can change from one processor family to
the next. The general principle of trying to keep frequent
storage references closer together if possible is always good,
but I would expect it to be rare for any search routine to be
sufficiently performance-critical to require detailed
consideration of cache implementation aspects.
Jonathan Scott
IBM Hursley, UK
