Perform on-demand score updates only

[trevorbaca]

Profiling shows the areas of biggest performance improvement in Abjad will come from limiting the number of score updates Abjad performs. What is a score update? A score update is a behind-the-scenes traversal of every note in a score that Abjad performs to bring start-offsets, stop-offsets and a few other properties of components up-to-date. (Consider removing the first note from a voice with 1000 notes: the start- and stop-offsets of the remaining 999 notes all change after the first note is removed. Abjad accomplishes this with a score update.) Score updates are fast. But score updates are also the biggest source of exponential increases of runtime in Abjad because several parts of the system loop over (loops of) score updates, each of which necessitates a full-score traversal.

Strategies for reducing the number of score updates Abjad performs must balance the need to keep score information up-to-date (as sketched above) against runtime performance. Until now, Abjad has favored the up-to-date-ness of score information against runtime performance, by attempting to update score information soon after any structural feature of the score changes. (In addition to adding and removing notes, such structural changes include adding and removing time signatures, metronome marks and other contexted indicators that determine the measure number and duration-in-seconds of components.)

Starting with Abjad 3.5 or 3.6, I'll begin the process of changing this balance. What this means is that score updates that Abjad currently performs behind-the-scenes (meaning without users knowing that the updates are happening) will become on-demand, meaning that composers will decide when score updates should happen (and will then call a convenience function to do so). The trade-off of these changes is clear: Abjad's runtime performance will increase for all users, but composers will be responsible for calling score updates before operations that need up-to-date score information.

The work will be batched because Abjad's score updates fall into groups; batches will appear in the comment history of this thread.

[trevorbaca]

Optimization 1: push abjad.Wrapper._warn_duplicate_indicator() to the user with a new check_duplicate_indicator=False keyword to abjad.attach(). This speeds up contexted indicator attach operations inside a loop.

There is currently a private _warn_duplicate_indicator() method implemented on abjad.Wrapper. The method is complicated, but it is designed to make sure that if (say) a metronome mark is attached to a note at offset 17/8 in voice 1 then a conflicting metronome mark can not be attached to a different note at the same offset in voice 2. The check necessitates a score update, and it is currently called any time a contexted indicator (metronome mark, time signature, clef, dynamic, ...) is attached to a note. In other words, the check is an "attach-time" check, and the cost of the check becomes exponential any time contexted indicators are attached to notes in a loop.

The strategy here is to defer the check that _warn_duplicate_indicator() performs from attach-time to a later use-stage of the system. Running the check at format-time might make sense. It also makes sense to surface the check to users to allow the composer to the check on-demand. The on-demand check will be implemented first, as a new check_duplicate_indicator=False keyword implemented on abjad.attach(). Runtime then falls to zero.

Test functions:

def make_score(staff_count, note_count):
    with abjad.Timer() as timer:
        staves = []
        for i in range(staff_count):
            notes = [abjad.Note("c'4") for _ in range(note_count)]
            voice = abjad.Voice(notes)
            staff = abjad.Staff([voice])
            staves.append(staff)
    total = staff_count * note_count
    time = int(timer.elapsed_time)
    print(f"made {staff_count} * {note_count} == {total} notes in {time} seconds ...")
    return abjad.Score(staves)

def attach_indicators(score, indicator_classes):
    with abjad.Timer() as timer:
        leaves = abjad.select(score).leaves()
        for leaf in leaves:
            for indicator_class in indicator_classes:
                indicator = indicator_class()
                abjad.attach(indicator, leaf)
    total = indicator_count * len(leaves)
    time = int(timer.elapsed_time)
    print(f"attached {total} contexted indicators in {time} seconds ...")

class Foo:
    context = "Voice"

class Bar:
    context = "Voice"

class Baz:
    context = "Voice"

class Qux:
    context = "Voice"

Starting input, output:

for note_count in [400, 800, 1600, 3200]:
    score = make_score(1, note_count)
    attach_indicators(score, [Foo])
    print()

made 1 * 400 == 400 notes in 0 seconds ...
attached 400 contexted indicators in 1 seconds ...

made 1 * 800 == 800 notes in 0 seconds ...
attached 800 contexted indicators in 7 seconds ...

made 1 * 1600 == 1600 notes in 0 seconds ...
attached 1600 contexted indicators in 29 seconds ...

made 1 * 3200 == 3200 notes in 1 seconds ...
attached 3200 contexted indicators in 120 seconds ...

Observation: as note count doubles, attach time quadruples.

Then 2 indicators per leaf:

for note_count in [400, 800, 1600, 3200]:
    score = make_score(1, note_count)
    attach_indicators(score, [Foo, Bar])
    print()

made 1 * 400 == 400 notes in 0 seconds ...
attached 800 contexted indicators in 3 seconds ...

made 1 * 800 == 800 notes in 0 seconds ...
attached 1600 contexted indicators in 15 seconds ...

made 1 * 1600 == 1600 notes in 0 seconds ...
attached 3200 contexted indicators in 61 seconds ...

made 1 * 3200 == 3200 notes in 1 seconds ...
attached 6400 contexted indicators in 249 seconds ...

3 indicators per leaf:

for note_count in [400, 800, 1600, 3200]:
    score = make_score(1, note_count)
    attach_indicators(score, [Foo, Bar, Baz])
    print()

made 1 * 400 == 400 notes in 0 seconds ...
attached 1200 contexted indicators in 6 seconds ...

made 1 * 800 == 800 notes in 0 seconds ...
attached 2400 contexted indicators in 24 seconds ...

made 1 * 1600 == 1600 notes in 0 seconds ...
attached 4800 contexted indicators in 90 seconds ...

made 1 * 3200 == 3200 notes in 1 seconds ...
attached 9600 contexted indicators in 361 seconds ...

4 indicators per leaf:

for note_count in [400, 800, 1600, 3200]:
    score = make_score(1, note_count)
    attach_indicators(score, [Foo, Bar, Baz, Qux])
    print()

made 1 * 400 == 400 notes in 0 seconds ...
attached 1600 contexted indicators in 8 seconds ...

made 1 * 800 == 800 notes in 0 seconds ...
attached 3200 contexted indicators in 32 seconds ...

made 1 * 1600 == 1600 notes in 0 seconds ...
attached 6400 contexted indicators in 131 seconds ...

made 1 * 3200 == 3200 notes in 1 seconds ...
???

Observation: runtime increases linearly with indicators-per-leaf.

Observation: runtime increases exponentially with leaves-per-voice.

Solution: call _warn_duplicate_indicator only on-demand, which will be never for most users.

Performance with this optimization:

print("set 1 ...\n")

for note_count in [400, 800, 1600, 3200]:
    score = make_score(1, note_count)
    attach_indicators(score, [Foo])
    print()

print("set 2 ...\n")

for note_count in [400, 800, 1600, 3200]:
    score = make_score(1, note_count)
    attach_indicators(score, [Foo, Bar])
    print()

print("set 3 ...\n")

for note_count in [400, 800, 1600, 3200]:
    score = make_score(1, note_count)
    attach_indicators(score, [Foo, Bar, Baz])
    print()

print("set 4 ...\n")

for note_count in [400, 800, 1600, 3200]:
    score = make_score(1, note_count)
    attach_indicators(score, [Foo, Bar, Baz, Qux])
    print()

set 1 ...

made 1 * 400 == 400 notes in 0 seconds ...
attached 400 contexted indicators in 0 seconds ...

made 1 * 800 == 800 notes in 0 seconds ...
attached 800 contexted indicators in 0 seconds ...

made 1 * 1600 == 1600 notes in 0 seconds ...
attached 1600 contexted indicators in 0 seconds ...

made 1 * 3200 == 3200 notes in 1 seconds ...
attached 3200 contexted indicators in 0 seconds ...

set 2 ...

made 1 * 400 == 400 notes in 0 seconds ...
attached 800 contexted indicators in 0 seconds ...

made 1 * 800 == 800 notes in 0 seconds ...
attached 1600 contexted indicators in 0 seconds ...

made 1 * 1600 == 1600 notes in 0 seconds ...
attached 3200 contexted indicators in 0 seconds ...

made 1 * 3200 == 3200 notes in 1 seconds ...
attached 6400 contexted indicators in 0 seconds ...

set 3 ...

made 1 * 400 == 400 notes in 0 seconds ...
attached 1200 contexted indicators in 0 seconds ...

made 1 * 800 == 800 notes in 0 seconds ...
attached 2400 contexted indicators in 0 seconds ...

made 1 * 1600 == 1600 notes in 0 seconds ...
attached 4800 contexted indicators in 0 seconds ...

made 1 * 3200 == 3200 notes in 1 seconds ...
attached 9600 contexted indicators in 1 seconds ...

set 4 ...

made 1 * 400 == 400 notes in 0 seconds ...
attached 1600 contexted indicators in 0 seconds ...

made 1 * 800 == 800 notes in 0 seconds ...
attached 3200 contexted indicators in 0 seconds ...

made 1 * 1600 == 1600 notes in 0 seconds ...
attached 6400 contexted indicators in 1 seconds ...

made 1 * 3200 == 3200 notes in 1 seconds ...
attached 12800 contexted indicators in 2 seconds ...