Extract upperbound calculation

DieBauer · fstab · commit 95872fc77cd5 · 2022-02-06T22:47:15.000+01:00
The upperbound is constant for a given quantile.
By calculating this once we save O(iterator size * quantiles size) calculations of this constant.

Signed-off-by: Jens &lt;jenskat@gmail.com&gt;
diff --git a/benchmarks/src/main/java/io/prometheus/client/CKMSQuantileBenchmark.java b/benchmarks/src/main/java/io/prometheus/client/CKMSQuantileBenchmark.java
@@ -97,6 +97,10 @@ public void setup() {
             for (Double l : shuffle) {
                 ckmsQuantiles.insert(l);
             }
+            // make sure we inserted all 'hanging' samples (count % 128)
+            ckmsQuantiles.get(0);
+            // compress everything so we have a similar samples size regardless of n.
+            ckmsQuantiles.compress();
             System.out.println("Sample size is: " + ckmsQuantiles.samples.size());
         }
 
diff --git a/simpleclient/src/main/java/io/prometheus/client/CKMSQuantiles.java b/simpleclient/src/main/java/io/prometheus/client/CKMSQuantiles.java
@@ -152,11 +152,12 @@ public double get(double q) {
 
         int r = 0; // sum of g's left of the current sample
         int desiredRank = (int) Math.ceil(q * n);
+        int upperBound = desiredRank + f(desiredRank) / 2;
 
         ListIterator<Sample> iterator = samples.listIterator();
         while (iterator.hasNext()) {
             Sample sample = iterator.next();
-            if (r + sample.g + sample.delta > desiredRank + f(desiredRank) / 2) {
+            if (r + sample.g + sample.delta > upperBound) {
                 iterator.previous(); // roll back the item.next() above
                 if (iterator.hasPrevious()) {
                     Sample result = iterator.previous();

Original file line number	Diff line number	Diff line change
`@@ -97,6 +97,10 @@ public void setup() {`
`97`	`97`	`for (Double l : shuffle) {`
`98`	`98`	`ckmsQuantiles.insert(l);`
`99`	`99`	`}`
	`100`	`+ // make sure we inserted all 'hanging' samples (count % 128)`
	`101`	`+ ckmsQuantiles.get(0);`
	`102`	`+ // compress everything so we have a similar samples size regardless of n.`
	`103`	`+ ckmsQuantiles.compress();`
`100`	`104`	`System.out.println("Sample size is: " + ckmsQuantiles.samples.size());`
`101`	`105`	`}`
`102`	`106`