SAMZA-1331; Optimize Snapshot class constructor
authorMaksim Logvinenko <mlogvinenko@gmail.com>
Fri, 9 Jun 2017 17:33:08 +0000 (10:33 -0700)
committervjagadish1989 <jvenkatr@linkedin.com>
Fri, 9 Jun 2017 17:33:08 +0000 (10:33 -0700)
In some of our workloads (where we need to gather samza metrics five times per minute) `SlidingTimeWindowReservoir.getSnapshot()` method takes up to 10% of processor time.

Almost all of `getSnapshot` time is taken by Collections.sort method. So, the complexity of Snapshot constructor is O(NlogN) + iteration through passed values.

This ticket asks to improve the performance of Snapshot constructor but keep the performance of all other methods at least on the same level.

Author: Maksim Logvinenko <mlogvinenko@gmail.com>

Reviewers: Jagadish V<jagadish@apache.org>

Closes #221 from logarithm/fix-snapshot

samza-api/src/main/java/org/apache/samza/metrics/Snapshot.java
samza-api/src/test/java/org/apache/samza/metrics/TestSnapshot.java

index 1e6f161..6f20de0 100644 (file)
@@ -21,19 +21,47 @@ package org.apache.samza.metrics;
 
 import java.util.ArrayList;
 import java.util.Collection;
-import java.util.Collections;
 
 /**
  * A statistical snapshot of a collection of values
  */
 public class Snapshot {
   private final ArrayList<Long> values;
+  private final long min;
+  private final long max;
+  private final double sum;
   private final int size;
 
-  public Snapshot(Collection<Long> values) {
-    this.values = new ArrayList<Long>(values);
+  Snapshot(Collection<Long> values) {
+    this.values = new ArrayList<>(values.size());
+
+    long max = Long.MIN_VALUE;
+    long min = Long.MAX_VALUE;
+    double sum = 0;
+
+    for (Long value: values) {
+      sum += value;
+      this.values.add(value);
+
+      if (value > max) {
+        max = value;
+      }
+
+      if (value < min) {
+        min = value;
+      }
+    }
+
+    this.sum = sum;
     this.size = this.values.size();
-    Collections.sort(this.values);
+
+    if (this.size == 0) {
+      this.max = 0;
+      this.min = 0;
+    } else {
+      this.max = max;
+      this.min = min;
+    }
   }
 
   /**
@@ -42,10 +70,7 @@ public class Snapshot {
    * @return maximum value
    */
   public long getMax() {
-    if (size == 0) {
-      return 0;
-    }
-    return values.get(size - 1);
+    return max;
   }
 
   /**
@@ -54,10 +79,7 @@ public class Snapshot {
    * @return minimum value
    */
   public long getMin() {
-    if (size == 0) {
-      return 0;
-    }
-    return values.get(0);
+    return min;
   }
 
   /**
@@ -66,14 +88,16 @@ public class Snapshot {
    * @return average value
    */
   public double getAverage() {
-    if (size == 0) {
-      return 0;
-    }
-    double sum = 0;
-    for (long value : values) {
-      sum += value;
-    }
-    return sum / size;
+    return size == 0 ? 0 : sum / size;
+  }
+
+  /**
+   * Get the sum of values in the collection
+   *
+   * @return sum of the collection
+   */
+  public double getSum() {
+    return sum;
   }
 
   /**
@@ -94,4 +118,4 @@ public class Snapshot {
   public ArrayList<Long> getValues() {
     return (ArrayList<Long>) values.clone();
   }
-}
\ No newline at end of file
+}
index b7aecb2..c2c0983 100644 (file)
@@ -29,17 +29,19 @@ import org.junit.Test;
 public class TestSnapshot {
 
   @Test
-  public void testGetMaxMinAverageSize() {
+  public void testGetMaxMinAverageSumSize() {
     Snapshot snapshot = new Snapshot(Arrays.asList(1L, 2L, 3L, 4L, 5L));
     assertEquals(5, snapshot.getMax());
     assertEquals(1, snapshot.getMin());
     assertEquals(3, snapshot.getAverage(), 0);
+    assertEquals(15, snapshot.getSum(), 0);
     assertEquals(5, snapshot.getSize());
 
-    Snapshot emptySnapshot = new Snapshot(new ArrayList<Long>());
+    Snapshot emptySnapshot = new Snapshot(new ArrayList<>());
     assertEquals(0, emptySnapshot.getMax());
     assertEquals(0, emptySnapshot.getMin());
     assertEquals(0, emptySnapshot.getAverage(), 0);
+    assertEquals(0, emptySnapshot.getSum(), 0);
     assertEquals(0, emptySnapshot.getSize());
   }
 }