Discussion/Proposal: StreamCore to Stream.core

[mscuthbert]

I've been thinking for a bit about some Stream/StreamCore refactors that I think will improve music21's speed and improve typing and flexibility for the next decade, and wanted to open up for discussion.

A Stream is basically a sorted list of notes, other streams, and other Music21Objects -- functioning as a mutable sequence. To make it all work well, there are a bunch of "core" calls such as coreInsert, coreAppend, and some hidden data structures like _elements, _endElements, _offsetDict, etc. For small Streams (up to about 1000 objects) this is all fast enough that the fact that some of our worst case scenarios are O(n^2) doesn't matter.

For larger streams, we have the tree.trees.ElementTree data structure, but almost no one uses it, because it doesn't function much like a Stream, it's underdocumented, and below about 1000 objects in the stream it is so much slower than a normal stream, I wouldn't ever use it.

Furthermore, because of the way StreamCore basically functions as a Mixin class for Stream, there are a lot of problems with typing and subclassing that are not easy to deal with. So some proposals:

---

Proposal 1:

Change the ontology/hierarchy so core is an attribute of Stream

currently we have a taxonomy: Stream IS-A StreamCore IS-A Music21Object
core becomes a meronomy: Stream IS-A Music21Object directly. Stream HAS-A .core which is StreamCore.

Renaming:
methods like self.coreInsert() become self.core.insert()

What it slows down: self.core.func(), etc. has to dereference .core which costs about 1ns per call or a 10% slowdown. But for even the simplest functions that we're calling, 1ns per call is a tiny part of the call (like usually less than 1% if that), so it's not a real hinderance (we can gain back 1% easily in a lot of places; timing evidence at bottom)

Immediate gains: some private methods will be opened (endElements will lose its underscore, I'm pretty sure).

The boundaries between Stream (iter, getElementsByClass etc.) and core (offsetDict, etc.) become very clear. Optimizations can take place within core and testing becomes simpler.
One Optimization I'm already considering is storing data this was: [(sortTuple, element), ...] -- this is how music21j implements some things and it ends up working so much better with multiple sites than the current system.

---

Proposal 2:

Streams become always sorted. We remove isSorted, autoSort, etc. anything that works with a Stream that doesn't cross into the .core boundary can always be sure that correct sorting is taking place. (This gets back way more than 1% time I think with removing all the if not self.isSorted(): self.sort() routines).

The notion that sometimes we'd want to work with non-sorted streams was a 2006-2010 music21 idea that did not ever pan out.

---

Proposal 3

Here's the big eventual gain from 1 and 2 that makes me excited:

the current StreamCore--with elements in two lists with a second offsetDict data structure--does not need to be the only available .core -- when a stream gets over 1000 elements, we might have it automatically changed to use a different stream representation internally as .core (like "BigStreamCore" etc.)

We have one such data structure already: the Tree representation, which is slow for small trees but very fast for bigger structures.

Another one to consider using is sortedcontainers's SortedList. (I tried some experiments on always using them for every Stream, but it made the tests take over twice as long; but for big streams, they got huge improvements).

I've been mulling this over for more than a decade, but I think that it might finally be the right time to make changes of this size to make sure that Streams "just work" for another decade or more.

Thoughts?

---

Timing Evidence for .core

class A():
    def i(self):
        pass

class B():
    def __init__(self):
        self.a = A()

a_obj = A()
b_obj = B()

%timeit a_obj.i()
10.2 ns ± 0.0435 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)

%timeit b_obj.a.i()
11.9 ns ± 0.0588 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)

even making the function i() do any tiny thing makes the difference between the two methods be nearly a wash (2%) difference -- not enough to decide to go ahead or stop over (we're in the single ns range per call).

class A():
    def i(self):
        return randint(10, 20)

a_obj = A()
b_obj = B()

%timeit a_obj.i()
97.8 ns ± 0.266 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

%timeit b_obj.a.i()
101 ns ± 0.524 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

[mscuthbert]

(Oh, one of the other internal representations could be an interval tree, which is really helpful for finding things that happen a certain moments, what key is active at a certain time, etc. J. Oberholtzer's TimespanTree, already in music21, is a really good start for that)