LibDSP: Optimize note processing

Previously, a collection of notes (Vector or Array) would be created and
promptly deleted for every sample (at least 44 thousand times per
second!). This was measured to be one of the most significant
performance drawbacks as well as the most obvious performance
improvement I could currently find here. Although it will not cause
Piano to lag currently (at least on virtualized systems), I see an
incoming issue once we get the capability to use more processors.

Now, we use a HashMap correlating pitches to notes, and Track reuses the
data structure in order to avoid reallocations. That is the reason for
introducing the fast clear_with_capacity to HashMap.

3 files changed, 33 insertions, 25 deletions

diff --git a/Userland/Libraries/LibDSP/Music.h b/Userland/Libraries/LibDSP/Music.h
index f495cf7a3b..30059f22b1 100644
--- a/Userland/Libraries/LibDSP/Music.h
+++ b/Userland/Libraries/LibDSP/Music.h
@@ -6,6 +6,7 @@
 
 #pragma once
 
+#include <AK/HashMap.h>
 #include <AK/Types.h>
 #include <AK/Variant.h>
 #include <AK/Vector.h>
@@ -33,12 +34,14 @@ enum class SignalType : u8 {
     Note
 };
 
-struct Signal : public Variant<Sample, Vector<RollNote>> {
+using RollNotes = OrderedHashMap<u8, RollNote>;
+
+struct Signal : public Variant<Sample, RollNotes> {
     using Variant::Variant;
     ALWAYS_INLINE SignalType type() const
     {
-        return has<Sample>() ? SignalType::Sample : has<Vector<RollNote>>() ? SignalType::Note
-                                                                            : SignalType::Invalid;
+        return has<Sample>() ? SignalType::Sample : has<RollNotes>() ? SignalType::Note
+                                                                     : SignalType::Invalid;
     }
 };
 
diff --git a/Userland/Libraries/LibDSP/Track.cpp b/Userland/Libraries/LibDSP/Track.cpp
index 5369201d07..dd049c66c4 100644
--- a/Userland/Libraries/LibDSP/Track.cpp
+++ b/Userland/Libraries/LibDSP/Track.cpp
@@ -4,9 +4,10 @@
  * SPDX-License-Identifier: BSD-2-Clause
  */
 
-#include "Track.h"
-#include "Processor.h"
+#include <AK/Optional.h>
 #include <AK/Types.h>
+#include <LibDSP/Processor.h>
+#include <LibDSP/Track.h>
 
 using namespace std;
 
@@ -49,15 +50,17 @@ bool NoteTrack::check_processor_chain_valid() const
 
 Sample Track::current_signal()
 {
-    Signal the_signal = current_clips_signal();
+    compute_current_clips_signal();
+    Optional<Signal> the_signal;
+
     for (auto& processor : m_processor_chain) {
-        the_signal = processor.process(the_signal);
+        the_signal = processor.process(the_signal.value_or(m_current_signal));
     }
-    VERIFY(the_signal.type() == SignalType::Sample);
-    return the_signal.get<Sample>();
+    VERIFY(the_signal.has_value() && the_signal->type() == SignalType::Sample);
+    return the_signal->get<Sample>();
 }
 
-Signal NoteTrack::current_clips_signal()
+void NoteTrack::compute_current_clips_signal()
 {
     u32 time = m_transport->time();
     // Find the currently playing clip.
@@ -68,26 +71,25 @@ Signal NoteTrack::current_clips_signal()
             break;
         }
     }
-    if (playing_clip == nullptr) {
-        return Signal(Vector<RollNote>());
-    }
 
-    // Find the playing notes inside the clip.
-    Vector<RollNote> playing_notes;
+    auto& current_notes = m_current_signal.get<RollNotes>();
+    m_current_signal.get<RollNotes>().clear_with_capacity();
+
+    if (playing_clip == nullptr)
+        return;
+
     // FIXME: performance?
     for (auto& note_list : playing_clip->notes()) {
         for (auto& note : note_list) {
             if (note.on_sample >= time && note.off_sample >= time)
                 break;
             if (note.on_sample <= time && note.off_sample >= time)
-                // FIXME: This copies the note, but we don't rely on playing_clip to keep its notes around.
-                playing_notes.append(note);
+                current_notes.set(note.pitch, note);
         }
     }
-    return Signal(playing_notes);
 }
 
-Signal AudioTrack::current_clips_signal()
+void AudioTrack::compute_current_clips_signal()
 {
     // Find the currently playing clip.
     u32 time = m_transport->time();
@@ -99,12 +101,12 @@ Signal AudioTrack::current_clips_signal()
         }
     }
     if (playing_clip == nullptr) {
-        return Signal(static_cast<Sample const&>(SAMPLE_OFF));
+        m_current_signal = Signal(static_cast<Sample const&>(SAMPLE_OFF));
     }
 
     // Index into the clip's samples.
     u32 effective_sample = time - playing_clip->start();
-    return Signal(playing_clip->sample_at(effective_sample));
+    m_current_signal = Signal(playing_clip->sample_at(effective_sample));
 }
 
 }
diff --git a/Userland/Libraries/LibDSP/Track.h b/Userland/Libraries/LibDSP/Track.h
index 95f075b3f8..af873f791c 100644
--- a/Userland/Libraries/LibDSP/Track.h
+++ b/Userland/Libraries/LibDSP/Track.h
@@ -19,6 +19,7 @@ class Track : public Core::Object {
 public:
     Track(NonnullRefPtr<Transport> transport)
         : m_transport(move(transport))
+        , m_current_signal(Sample {})
     {
     }
     virtual ~Track() override = default;
@@ -36,10 +37,12 @@ protected:
     bool check_processor_chain_valid_with_initial_type(SignalType initial_type) const;
 
     // Subclasses override to provide the base signal to the processing chain
-    virtual Signal current_clips_signal() = 0;
+    virtual void compute_current_clips_signal() = 0;
 
     NonnullRefPtrVector<Processor> m_processor_chain;
-    NonnullRefPtr<Transport> const m_transport;
+    NonnullRefPtr<Transport> m_transport;
+    // The current signal is stored here, to prevent unnecessary reallocation.
+    Signal m_current_signal;
 };
 
 class NoteTrack final : public Track {
@@ -50,7 +53,7 @@ public:
     NonnullRefPtrVector<NoteClip> const& clips() const { return m_clips; }
 
 protected:
-    virtual Signal current_clips_signal() override;
+    virtual void compute_current_clips_signal() override;
 
 private:
     NonnullRefPtrVector<NoteClip> m_clips;
@@ -64,7 +67,7 @@ public:
     NonnullRefPtrVector<AudioClip> const& clips() const { return m_clips; }
 
 protected:
-    virtual Signal current_clips_signal() override;
+    virtual void compute_current_clips_signal() override;
 
 private:
     NonnullRefPtrVector<AudioClip> m_clips;