Avoid Temporary Memory Allocation in Impulse Velocity Calculation

During calculating impulse velocity, we used to create arrays to store
the data ponits that are within the HORIZON, and then pass those arrays
(1 for position and one for time) to a separate static function to
calculate velocity. This means that we have to do extra space allocation
(~O(n)), plus process most/all data points twice - once during
collecting the valid data points, and once during using their data to
get velocity.

This implementation avoids new array allocation by using a single linear
processing to both get the valid data points (i.e. the ones within
HORIZON from the latest data point), and to get the velocity. This
approach also has the side-effect benefit of avoiding consideration of
any old data-point on future calls on "computeCurrentVelocity", as we
will effectively mark a data point permanently "invalid" if it fails to
fall within the HORIZON at any point.

Trace-based analysis indicates that this approach improves the
`getVelocity` method by ~20% in time.

Bug: 267211645
Test: unit tests unaffected
Change-Id: Ie7671194476cd17131d79c06b5bc1440a958d384

2 files changed, 53 insertions, 75 deletions

diff --git a/include/input/VelocityTracker.h b/include/input/VelocityTracker.h
index 6d1de649f9..f218c512e8 100644
--- a/include/input/VelocityTracker.h
+++ b/include/input/VelocityTracker.h
@@ -159,6 +159,8 @@ public:
  */
 class AccumulatingVelocityTrackerStrategy : public VelocityTrackerStrategy {
 public:
+    AccumulatingVelocityTrackerStrategy(nsecs_t horizonNanos, bool maintainHorizonDuringAdd);
+
     void addMovement(nsecs_t eventTime, int32_t pointerId, float position) override;
     void clearPointer(int32_t pointerId) override;
 
@@ -173,6 +175,16 @@ protected:
     // protected const field.
     static constexpr uint32_t HISTORY_SIZE = 20;
 
+    /**
+     * Duration, in nanoseconds, since the latest movement where a movement may be considered for
+     * velocity calculation.
+     */
+    const nsecs_t mHorizonNanos;
+    /**
+     * If true, data points outside of horizon (see `mHorizonNanos`) will be cleared after each
+     * addition of a new movement.
+     */
+    const bool mMaintainHorizonDuringAdd;
     std::map<int32_t /*pointerId*/, RingBuffer<Movement>> mMovements;
 };
 
diff --git a/libs/input/VelocityTracker.cpp b/libs/input/VelocityTracker.cpp
index ba266b3969..150b68b9d2 100644
--- a/libs/input/VelocityTracker.cpp
+++ b/libs/input/VelocityTracker.cpp
@@ -55,6 +55,9 @@ const bool DEBUG_IMPULSE =
 // Nanoseconds per milliseconds.
 static const nsecs_t NANOS_PER_MS = 1000000;
 
+// Seconds per nanosecond.
+static const float SECONDS_PER_NANO = 1E-9;
+
 // All axes supported for velocity tracking, mapped to their default strategies.
 // Although other strategies are available for testing and comparison purposes,
 // the default strategy is the one that applications will actually use.  Be very careful
@@ -369,6 +372,10 @@ VelocityTracker::ComputedVelocity VelocityTracker::getComputedVelocity(int32_t u
     return computedVelocity;
 }
 
+AccumulatingVelocityTrackerStrategy::AccumulatingVelocityTrackerStrategy(
+        nsecs_t horizonNanos, bool maintainHorizonDuringAdd)
+      : mHorizonNanos(horizonNanos), mMaintainHorizonDuringAdd(maintainHorizonDuringAdd) {}
+
 void AccumulatingVelocityTrackerStrategy::clearPointer(int32_t pointerId) {
     mMovements.erase(pointerId);
 }
@@ -390,13 +397,25 @@ void AccumulatingVelocityTrackerStrategy::addMovement(nsecs_t eventTime, int32_t
     }
 
     movements.pushBack({eventTime, position});
+
+    // Clear movements that do not fall within `mHorizonNanos` of the latest movement.
+    // Note that, if in the future we decide to use more movements (i.e. increase HISTORY_SIZE),
+    // we can consider making this step binary-search based, which will give us some improvement.
+    if (mMaintainHorizonDuringAdd) {
+        while (eventTime - movements[0].eventTime > mHorizonNanos) {
+            movements.popFront();
+        }
+    }
 }
 
 // --- LeastSquaresVelocityTrackerStrategy ---
 
 LeastSquaresVelocityTrackerStrategy::LeastSquaresVelocityTrackerStrategy(uint32_t degree,
                                                                          Weighting weighting)
-      : mDegree(degree), mWeighting(weighting) {}
+      : AccumulatingVelocityTrackerStrategy(HORIZON /*horizonNanos*/,
+                                            false /*maintainHorizonDuringAdd*/),
+        mDegree(degree),
+        mWeighting(weighting) {}
 
 LeastSquaresVelocityTrackerStrategy::~LeastSquaresVelocityTrackerStrategy() {}
 
@@ -808,7 +827,9 @@ void IntegratingVelocityTrackerStrategy::updateState(State& state, nsecs_t event
 
 // --- LegacyVelocityTrackerStrategy ---
 
-LegacyVelocityTrackerStrategy::LegacyVelocityTrackerStrategy() {}
+LegacyVelocityTrackerStrategy::LegacyVelocityTrackerStrategy()
+      : AccumulatingVelocityTrackerStrategy(HORIZON /*horizonNanos*/,
+                                            false /*maintainHorizonDuringAdd*/) {}
 
 LegacyVelocityTrackerStrategy::~LegacyVelocityTrackerStrategy() {
 }
@@ -881,7 +902,9 @@ std::optional<float> LegacyVelocityTrackerStrategy::getVelocity(int32_t pointerI
 // --- ImpulseVelocityTrackerStrategy ---
 
 ImpulseVelocityTrackerStrategy::ImpulseVelocityTrackerStrategy(bool deltaValues)
-      : mDeltaValues(deltaValues) {}
+      : AccumulatingVelocityTrackerStrategy(HORIZON /*horizonNanos*/,
+                                            true /*maintainHorizonDuringAdd*/),
+        mDeltaValues(deltaValues) {}
 
 ImpulseVelocityTrackerStrategy::~ImpulseVelocityTrackerStrategy() {
 }
@@ -960,57 +983,6 @@ static float kineticEnergyToVelocity(float work) {
     return (work < 0 ? -1.0 : 1.0) * sqrtf(fabsf(work)) * sqrt2;
 }
 
-static float calculateImpulseVelocity(const nsecs_t* t, const float* x, size_t count,
-                                      bool deltaValues) {
-    // The input should be in reversed time order (most recent sample at index i=0)
-    // t[i] is in nanoseconds, but due to FP arithmetic, convert to seconds inside this function
-    static constexpr float SECONDS_PER_NANO = 1E-9;
-
-    if (count < 2) {
-        return 0; // if 0 or 1 points, velocity is zero
-    }
-    if (t[1] > t[0]) { // Algorithm will still work, but not perfectly
-        ALOGE("Samples provided to calculateImpulseVelocity in the wrong order");
-    }
-
-    // If the data values are delta values, we do not have to calculate deltas here.
-    // We can use the delta values directly, along with the calculated time deltas.
-    // Since the data value input is in reversed time order:
-    //      [a] for non-delta inputs, instantenous velocity = (x[i] - x[i-1])/(t[i] - t[i-1])
-    //      [b] for delta inputs, instantenous velocity = -x[i-1]/(t[i] - t[i - 1])
-    // e.g., let the non-delta values are: V = [2, 3, 7], the equivalent deltas are D = [2, 1, 4].
-    // Since the input is in reversed time order, the input values for this function would be
-    // V'=[7, 3, 2] and D'=[4, 1, 2] for the non-delta and delta values, respectively.
-    //
-    // The equivalent of {(V'[2] - V'[1]) = 2 - 3 = -1} would be {-D'[1] = -1}
-    // Similarly, the equivalent of {(V'[1] - V'[0]) = 3 - 7 = -4} would be {-D'[0] = -4}
-
-    if (count == 2) { // if 2 points, basic linear calculation
-        if (t[1] == t[0]) {
-            ALOGE("Events have identical time stamps t=%" PRId64 ", setting velocity = 0", t[0]);
-            return 0;
-        }
-        const float deltaX = deltaValues ? -x[0] : x[1] - x[0];
-        return deltaX / (SECONDS_PER_NANO * (t[1] - t[0]));
-    }
-    // Guaranteed to have at least 3 points here
-    float work = 0;
-    for (size_t i = count - 1; i > 0 ; i--) { // start with the oldest sample and go forward in time
-        if (t[i] == t[i-1]) {
-            ALOGE("Events have identical time stamps t=%" PRId64 ", skipping sample", t[i]);
-            continue;
-        }
-        float vprev = kineticEnergyToVelocity(work); // v[i-1]
-        const float deltaX = deltaValues ? -x[i-1] : x[i] - x[i-1];
-        float vcurr = deltaX / (SECONDS_PER_NANO * (t[i] - t[i-1])); // v[i]
-        work += (vcurr - vprev) * fabsf(vcurr);
-        if (i == count - 1) {
-            work *= 0.5; // initial condition, case 2) above
-        }
-    }
-    return kineticEnergyToVelocity(work);
-}
-
 std::optional<float> ImpulseVelocityTrackerStrategy::getVelocity(int32_t pointerId) const {
     const auto movementIt = mMovements.find(pointerId);
     if (movementIt == mMovements.end()) {
@@ -1023,29 +995,22 @@ std::optional<float> ImpulseVelocityTrackerStrategy::getVelocity(int32_t pointer
         return std::nullopt; // no data
     }
 
-    // Iterate over movement samples in reverse time order and collect samples.
-    float positions[HISTORY_SIZE];
-    nsecs_t time[HISTORY_SIZE];
-    size_t m = 0; // number of points that will be used for fitting
-    const Movement& newestMovement = movements[size - 1];
-    for (ssize_t i = size - 1; i >= 0; i--) {
-        const Movement& movement = movements[i];
-
-        nsecs_t age = newestMovement.eventTime - movement.eventTime;
-        if (age > HORIZON) {
-            break;
-        }
+    float work = 0;
+    for (size_t i = 0; i < size - 1; i++) {
+        const Movement& mvt = movements[i];
+        const Movement& nextMvt = movements[i + 1];
 
-        positions[m] = movement.position;
-        time[m] = movement.eventTime;
-        m++;
-    }
+        float vprev = kineticEnergyToVelocity(work);
+        float delta = mDeltaValues ? nextMvt.position : nextMvt.position - mvt.position;
+        float vcurr = delta / (SECONDS_PER_NANO * (nextMvt.eventTime - mvt.eventTime));
+        work += (vcurr - vprev) * fabsf(vcurr);
 
-    if (m == 0) {
-        return std::nullopt; // no data
+        if (i == 0) {
+            work *= 0.5; // initial condition, case 2) above
+        }
     }
 
-    const float velocity = calculateImpulseVelocity(time, positions, m, mDeltaValues);
+    const float velocity = kineticEnergyToVelocity(work);
     ALOGD_IF(DEBUG_STRATEGY, "velocity: %.1f", velocity);
 
     if (DEBUG_IMPULSE) {
@@ -1053,8 +1018,9 @@ std::optional<float> ImpulseVelocityTrackerStrategy::getVelocity(int32_t pointer
         // Calculate the lsq2 velocity for the same inputs to allow runtime comparisons.
         // X axis chosen arbitrarily for velocity comparisons.
         VelocityTracker lsq2(VelocityTracker::Strategy::LSQ2);
-        for (ssize_t i = m - 1; i >= 0; i--) {
-            lsq2.addMovement(time[i], pointerId, AMOTION_EVENT_AXIS_X, positions[i]);
+        for (size_t i = 0; i < size; i++) {
+            const Movement& mvt = movements[i];
+            lsq2.addMovement(mvt.eventTime, pointerId, AMOTION_EVENT_AXIS_X, mvt.position);
         }
         std::optional<float> v = lsq2.getVelocity(AMOTION_EVENT_AXIS_X, pointerId);
         if (v) {