Alternative tail representations

[treeowl]

To make consecutive (unboxed) snoc and (future) unsnoc operations faster, we might consider more compact representations of the tails. In particular, we can "chunk" them if we like. Something like this:

data ListTwos a
  = Snoc2 !(ListTwos a) a a
  | Nil2

data Tail a = Tail
  { pairs :: !(ListTwos a)
  , maybeLast :: a }

The maybeLast component of the Tail is the last element if the Vector (and therefore the Tail) has an odd number of elements, and is undefined if the Vector has an even number of elements.

Of course, we could choose any small power of 2 for the chunk size, and some experimentation will be required to pick the right one.

[treeowl]

We really do have to do something about this. Indexing performance is really important for a persistent vector, and sometimes having to walk a 32-element list will just kill it. I think we should really arrange to walk only about as many pointers in the tail as we might have to walk in the tree. For the current implementation of the tree, that means groups of two. For the WIP implementation with more compact trees, that means groups of four. We can tune how many (if any) of the tail elements are buffered in the Vector constructor.

[travitch]

We could start with just Seq - it is cheap enough to add an element and indexing is okay. We can measure it and see if it seems worthwhile to take more drastic steps to amortize the storage cost

[treeowl]

Not a bad idea, but it's definitely not where we want to end up. One finger will be helpful for snoc/unsnoc; surely we don't need two.

…

On Sat, Oct 24, 2020, 3:43 PM Tristan Ravitch ***@***.***> wrote: We could start with just Seq - it is cheap enough to add an element and indexing is okay. We can measure it and see if it seems worthwhile to take more drastic steps to amortize the storage cost — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#20 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAOOF7JE7LK6JMVGBNAMACTSMMU4XANCNFSM4SVIJS3Q> .

[treeowl]

We'd also prefer a non-redundant data structure to avoid needing size annotations. Since we don't need splitting or concatenation, this should be eminently doable. I think Okasaki has one that'll work; I don't remember what he calls it.

[treeowl]

Oh yeah, a random-access list.

[travitch]

If we are willing to "waste" a bit of space, we could just use a straight up array segment. At worst, 31 elements will be undefined, but indexing is really efficient. Also, the step where we "roll" the tail into a full array element in the tree is cheaper, since we already have the array we want.

[treeowl]

That'll make snoc and unsnoc quite expensive! I think clojure gets around that with transients mostly; that's an extra layer of difficulty. I'd like to get the basics down first.

…

On Sat, Oct 24, 2020, 4:15 PM Tristan Ravitch ***@***.***> wrote: If we are willing to "waste" a bit of space, we could just use a straight up array segment. At worst, 31 elements will be undefined, but indexing is really efficient. Also, the step where we "roll" the tail into a full array element in the tree is cheaper, since we already have the array we want. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#20 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAOOF7PXAKXXSR7GWD56UXLSMMYUXANCNFSM4SVIJS3Q> .

[treeowl]

Anyway, there's nothing really gained by making indexing into the tail faster than indexing into the tree. Comparably fast is sufficient.

[treeowl]

Regardless, I believe that we should have a separate module to define the Tail type. Everything in this package is making me want to learn backpack.... It would let us parametrize vectors over tail type, array size/shift, and with a bit more effort should win us vectors of unboxed things. We just need to sell our souls break things up as needed and accept a bunch of mysterious incantations in Cabal files.

[travitch]

I'm 100% on board with factoring out a Tail ADT. I'm not necessarily opposed to Backpack, but what do you think about just parameterizing the Vector type with its tail as a type parameter? It might be friendlier to the various build systems that people use while still admitting a lot of different experiments (or even user choice). I suppose the downside is that it might miss out on some tail unboxing opportunities - do you think that is a major issue? It doesn't seem obviously problematic to me in the way that the tree-of-arrays structure is.

[treeowl]

Unpacking a small "buffer" into the root node could potentially have big performance benefits. When there are many snoc or unsnoc operations strung together, we could heap-allocate only every few operations, instead of every time. We could probably skip backpack for the array size and tail type by going old-school with CPP. I really want to try testing with more than one array size/shift.