[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]

ent optimization ideas

Abstract: Just wanted to post some optimizations that have been
floating in my head.  These are not intelligible even to the

When a rotate operation on crum A makes a new child crum form an old
childCrum B and a grandChild crum C, it should first check to see if B
and C already have a parent that points to both of them with the
approrpiate differential dsp.  If so, it should just use the
pre-existing crum.  This prevents the splay operation from gradually
separating trees that share substructure.  The simplest version of
this optimization will only do it when the hCut of the discovered
parent for B and C has an hCut <= to A's hCut.  This will recover all
the pealing of trees caused by the splay operation.  

A further optimization (much later) can discover unanticipated sharing
by considering crums with hCuts unrelated to A's hCut.  Since A and
the new crum B both sare at least B and C, the discovery routine could
modify the DagWood to represnt the sharing between the two versions,
and/or modify the otrees so that they actually share the similar
subtrees (mostly by updating hCtus and then using the discovered crum
D as the new child of A).

Finally, the operation described above is essentially a combine
operation on InnerLoaves.  This operation should be separated out and
used by the combine oepration for OrglRoots.  The optimizations above
would mean that if two orgls had been previously combined, that tree
would be used rather than building another one.

Perfectly clear, right?