Robbert,
The code itself is a great place to extract information about how the tuple
types fit together; in this case, have a look at the Java hierarchy below
TupleDescriptor, the base abstraction.
I'm pretty sure I finally got the nesting right when I added tree tuples; there
used to be serious pathologies. Since individual tree tuples are pretty cheap,
attempting to construct a subtuple of a tree tuple always creates another tree
tuple rather than simply wrapping it. Not only does this prevent an
arbitrarily deep nesting of alternate layers of tree tuples and subtuple
tuples, but it also limits how many spurious out-of-range elements are held
onto ("reference leaked") by subtuples of large tuples, since the large tuples
tend to be tree tuples.
Forcing a reverse tuple to be below tree tuples would have forced the whole
tree except the leaves to be copied (after the recursion settled we would have
layers of fresh tree tuples, then one layer of reverse tuples, then all the
leaf tuples). Instead, we allow reverse tuples to be anywhere in the tree,
although attempting to construct a reverse of a reverse simply cancels away the
reverses. So the tree is at most doubled in height by the reverse tuple nodes.
Most of the other kinds of tuples are leaf representations, which can only
occur at the bottom level of a tree. All paths from a tree tuple to its leaf
tuples cross the same number of levels, not counting reverses (which at most
doubles the number of steps).
Sufficiently short tuples are always forced to be flat anyhow, just because a
tight loop copying a couple of dozen elements is probably going to outperform
the extra eventual dispatching cost of a more complex structure. We haven't
measured the trade-offs, so it's just "winging it" numbers for now, but feel
free to collect some stats for performance tuning the tree tuple thresholds. A
new project at every turn!
> On Jan 25, 2015, at 8:56 AM, Robbert van Dalen <[email protected]> wrote:
>
> Hi Leslie,
>
> I’ve just noticed your latest push: the implementation of repeated element
> tuples. Nice!
> It appears both you and hciR (you know who!) are keen on optimising various
> tuple shapes.
>
> I do wonder how all the tuples specialisations interact at runtime.
> For example, is it possible for a TreeTuple to hold non-TreeTuples as childs
> (i.e. reversed, repeated element tuples, etc) ?
>
> I’m especially interested to know whether the endless concatenation and
> slicing of specialised tuples doesn’t incur too much copying, but instead
> results in a lot of sharing between immutable (sub)tuples.
> Can we be sure that the (amortized) runtime complexities of combining the
> specialised tuples are not worse than TreeTuple’s runtime complexities?
>
> cheers,
> Robbert.
