Implement time measurement utility

Added a TimeMeasure interface as a utility class
to be able to measure running time of specific parts
of code. Usually, this will be used for benchmarking.

Implemented SamplerHistogramTimeMeasurement that uses
reservior sampling to calculate percentiles of large
amount of data.

Also updated maven pom.xml:
- update java version from 1.7 to 1.8 to be able to use java 8
- update guava to 27.0 to use Stats Percentiles
- update cassandra java plugin version to 3.6 to fix guava dependency problem

Change-Id: I168432ff2e6f5507fedc1678684dd96608703e5a
Issue-ID: MUSIC-148
Signed-off-by: Mohammad Salehe <salehe@cs.toronto.edu>

5 files changed, 210 insertions, 13 deletions

diff --git a/pom.xml b/pom.xml
index 2c90b00d..6703b445 100755
--- a/pom.xml
+++ b/pom.xml
@@ -29,13 +29,13 @@
 		<relativePath /> <!-- lookup parent from repository -->
 	</parent>
 
-	<properties>
-		<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
-		<jersey1.version>1.19</jersey1.version>
-		<jersey2.version>2.25.1</jersey2.version>
-		<jaxrs.version>2.0.1</jaxrs.version>
-		<cassandra.version>3.4.0</cassandra.version>
-		<zookeeper.version>3.4.11</zookeeper.version>
+    <properties>
+        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
+        <jersey1.version>1.19</jersey1.version>
+        <jersey2.version>2.25.1</jersey2.version>
+        <jaxrs.version>2.0.1</jaxrs.version>
+        <cassandra.version>3.6.0</cassandra.version>
+        <zookeeper.version>3.4.11</zookeeper.version>
 
 		<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
 		<project.reporting.outputEncoding>UTF-8</project.reporting.outputEncoding>
@@ -104,8 +104,8 @@
 				<artifactId>maven-compiler-plugin</artifactId>
 				<version>3.5.1</version>
 				<configuration>
-					<source>1.7</source>
-					<target>1.7</target>
+					<source>1.8</source>
+					<target>1.8</target>
 					<excludes>
 						<exclude>jar/**</exclude>
 					</excludes>
@@ -348,7 +348,7 @@
 		<dependency>
 			<groupId>com.google.guava</groupId>
 			<artifactId>guava</artifactId>
-			<version>18.0</version>
+			<version>21.0</version>
 		</dependency>
 		<dependency>
 			<groupId>org.mindrot</groupId>
@@ -503,7 +503,4 @@
 			<url>dav:${nexusproxy}${sitePath}</url>
 		</site>
 	</distributionManagement>
-
-
-
 </project>
diff --git a/src/main/java/org/onap/music/util/NullTimeMeasure.java b/src/main/java/org/onap/music/util/NullTimeMeasure.java
new file mode 100644
index 00000000..cc956554
--- /dev/null
+++ b/src/main/java/org/onap/music/util/NullTimeMeasure.java
@@ -0,0 +1,29 @@
+package org.onap.music.util;
+
+import org.apache.commons.lang3.tuple.Pair;
+
+import java.util.ArrayList;
+import java.util.Map;
+
+public class NullTimeMeasure implements TimeMeasure
+{
+    public NullTimeMeasure() {
+    }
+
+    public void enter(String context) {
+    }
+
+    public void exit() {
+    }
+
+    @Override
+    public Map<String, ArrayList<Double>> percentiles()
+    {
+        return null;
+    }
+
+    @Override
+    public Map<String, Pair<Double, Double>> stats() {
+        return null;
+    }
+}
diff --git a/src/main/java/org/onap/music/util/SamplerHistogramTimeMeasure.java b/src/main/java/org/onap/music/util/SamplerHistogramTimeMeasure.java
new file mode 100644
index 00000000..b1766e08
--- /dev/null
+++ b/src/main/java/org/onap/music/util/SamplerHistogramTimeMeasure.java
@@ -0,0 +1,106 @@
+package org.onap.music.util;
+
+import com.google.common.math.Quantiles;
+import com.google.common.math.Stats;
+import org.apache.commons.lang3.tuple.ImmutablePair;
+import org.apache.commons.lang3.tuple.Pair;
+
+import java.util.*;
+import java.util.concurrent.ThreadLocalRandom;
+import java.util.stream.Collectors;
+import java.util.stream.IntStream;
+
+class ReserviorSampler {
+    private double[] samples;
+    private long length;
+    private int size;
+
+    public ReserviorSampler(int size) {
+        this.samples = new double[size];
+        this.size = size;
+        this.length = 0;
+    }
+
+    public void insert(double x) {
+        if (length < size) {
+            samples[(int)length] = x;
+            length++;
+        }
+        else {
+            long r = ThreadLocalRandom.current().nextLong(length);
+            if (r < size) {
+                samples[(int)r] = x;
+            }
+        }
+    }
+
+    public double[] getSamples() {
+        if (length < size)
+            return Arrays.copyOfRange(samples, 0, (int)length);
+        else
+            return samples;
+    }
+}
+
+public class SamplerHistogramTimeMeasure implements TimeMeasure
+{
+    public static final int SAMPLER_SIZE = 1000;
+    private Map<String, ReserviorSampler> histograms;
+    private ThreadLocal<LinkedList<Pair<String, Long>>> tlContexts;
+    int[] p100;
+
+    public SamplerHistogramTimeMeasure() {
+        histograms = new HashMap<>();
+        tlContexts = ThreadLocal.withInitial(() -> new LinkedList<>());
+        p100 = IntStream.rangeClosed(0, 100)
+                .toArray();
+    }
+
+    public void init() {
+        tlContexts.get();
+    }
+
+    @Override
+    public void enter(String context) {
+        LinkedList<Pair<String, Long>> contexts = tlContexts.get();
+        String concatContext = (contexts.size() > 0 ? contexts.getLast().getLeft() + "." : "") + context;
+        contexts.add(new ImmutablePair<>(concatContext, System.nanoTime()));
+    }
+
+    @Override
+    public void exit() {
+        long nanoTime = System.nanoTime();
+        LinkedList<Pair<String, Long>> contexts = tlContexts.get();
+        Pair<String, Long> e = contexts.removeLast();
+        double t = (nanoTime - e.getRight()) * 1e-6;
+        ReserviorSampler h = histograms.computeIfAbsent(e.getLeft(), k -> new ReserviorSampler(SAMPLER_SIZE));
+        h.insert(t);
+    }
+
+    @Override
+    public Map<String, ArrayList<Double>> percentiles() {
+        Map<String, ArrayList<Double>> mapped = histograms.entrySet().stream()
+                .collect(Collectors.toMap(Map.Entry::getKey,
+                    entry -> new ArrayList<>(new TreeMap<>(
+                        Quantiles.percentiles().indexes(p100).compute(entry.getValue().getSamples())
+                    ).values())
+                ));
+        return mapped;
+    }
+
+    @Override
+    public Map<String, Pair<Double, Double>> stats(){
+        Map<String, Pair<Double, Double>> mapped = histograms.entrySet().stream()
+                .collect(Collectors.toMap(Map.Entry::getKey,
+                        entry -> {
+                            Stats s = Stats.of(entry.getValue().getSamples());
+                            if (s.count() <= SAMPLER_SIZE)
+                                return new ImmutablePair<>(s.mean(), s.populationStandardDeviation() / s.count());
+                            else
+                                return new ImmutablePair<>(s.mean(), s.sampleStandardDeviation() / s.count());
+
+                        }
+                ));
+        return mapped;
+    }
+}
diff --git a/src/main/java/org/onap/music/util/TimeMeasure.java b/src/main/java/org/onap/music/util/TimeMeasure.java
new file mode 100644
index 00000000..cbb04ff6
--- /dev/null
+++ b/src/main/java/org/onap/music/util/TimeMeasure.java
@@ -0,0 +1,52 @@
+package org.onap.music.util;
+
+import org.apache.commons.lang3.tuple.Pair;
+
+import java.text.DecimalFormat;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Map;
+import java.util.concurrent.ThreadLocalRandom;
+
+public interface TimeMeasure {
+    void enter(String context);
+
+    void exit();
+
+    /*
+        Return a map of measure contexts to a list of 101 percentiles [0,100]
+     */
+    Map<String, ArrayList<Double>> percentiles();
+
+    /*
+        Returns a map of measure contexts to <mean, sme>
+     */
+    Map<String, Pair<Double, Double>> stats();
+}
+
+class TimeMeasureExample
+{
+    public static void main(String[] args) {
+        TimeMeasure tm = new SamplerHistogramTimeMeasure();
+        double x = 0;
+
+        tm.enter("A");
+        for (int i = 0; i < 100000; i++) {
+            tm.enter("B");
+            tm.enter("C");
+            x += ThreadLocalRandom.current().nextDouble(100);
+            tm.exit();
+            tm.exit();
+        }
+        tm.enter("C");
+        tm.exit();
+        tm.exit();
+
+        System.out.println(x);
+        Map<String, ArrayList<Double>> e = tm.percentiles();
+        Map<String, Pair<Double, Double>> m = tm.stats();
+        DecimalFormat df = new DecimalFormat("000.000000");
+        e.forEach((k,v) -> System.out.println("" + k + "\t\t: " + Arrays.toString(v.stream().map(w -> "" + df.format(w)).toArray())));
+        m.forEach((k,v) -> System.out.println("" + k + "\t\t: " + df.format(v.getLeft()) + " (" + df.format(v.getRight()) + ")"));
+    }
+}
diff --git a/src/main/java/org/onap/music/util/TimeMeasureInstance.java b/src/main/java/org/onap/music/util/TimeMeasureInstance.java
new file mode 100644
index 00000000..579fcdfc
--- /dev/null
+++ b/src/main/java/org/onap/music/util/TimeMeasureInstance.java
@@ -0,0 +1,13 @@
+package org.onap.music.util;
+
+public class TimeMeasureInstance {
+    private static TimeMeasure instance = new NullTimeMeasure();
+
+    public static TimeMeasure instance() {
+        return TimeMeasureInstance.instance;
+    }
+
+    public static void setInstance(TimeMeasure instance) {
+        TimeMeasureInstance.instance = instance;
+    }
+}