Yeah, I’ve seen the code - it’s great stuff. I just wanted to know more about the background story. I was hoping for Leslie and Rich to tell their story about what are their goals and what they want to achieve.
Anyway, Soon, I’m going to convince myself that tuples work the way I think they work: via unit tests. Now, I’ve been boosting about writing unit tests. Where are they? Good question indeed. My problem is: there are so many things that make me wonder, still. So I hope you don’t find it too troublesome that I ask first… and write unit tests later. Because I want to write stuff that have the most impact, covering Avail’s most unique aspects. Tests that prove Avail’s correctness *and* efficiency. Everything you tell and explain about the efficiency of tuples I care about deeply. I believe that tuples are Avail’s most versatile datatype, in terms of scalability and in static typing. To see where I’m coming from: my (now defunct) programming language Enchilada has untyped ‘tuples’ as first class. And just like Avail, Enchilada provides many specialised tuples (compressed, ordered, reversed, etc) under the hood. cheers, Robbert. > On 26 Jan 2015, at 06:02, Mark van Gulik <[email protected]> wrote: > > 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.
signature.asc
Description: Message signed with OpenPGP using GPGMail
