fix: add accurate percentiles approximation computation (#87)

jerome-benoit · web-flow · commit ab467e292bd2 · 2024-10-13T14:34:45.000+02:00
Signed-off-by: Jérôme Benoit &lt;jerome.benoit@piment-noir.org&gt;
diff --git a/src/task.ts b/src/task.ts
@@ -10,7 +10,7 @@ import Bench from './bench';
 import tTable from './constants';
 import { createBenchEvent } from './event';
 import { AddEventListenerOptionsArgument, RemoveEventListenerOptionsArgument } from './types';
-import { getVariance, isAsyncTask } from './utils';
+import { getVariance, isAsyncTask, quantileSorted } from './utils';
 
 /**
  * A class that represents each benchmark task in Tinybench. It keeps track of the
@@ -152,11 +152,10 @@ export default class Task extends EventTarget {
       const moe = sem * critical;
       const rme = (moe / mean) * 100;
 
-      // mitata: https://github.com/evanwashere/mitata/blob/3730a784c9d83289b5627ddd961e3248088612aa/src/lib.mjs#L12
-      const p75 = samples[Math.ceil(samplesLength * 0.75) - 1]!;
-      const p99 = samples[Math.ceil(samplesLength * 0.99) - 1]!;
-      const p995 = samples[Math.ceil(samplesLength * 0.995) - 1]!;
-      const p999 = samples[Math.ceil(samplesLength * 0.999) - 1]!;
+      const p75 = quantileSorted(samples, 0.75);
+      const p99 = quantileSorted(samples, 0.99);
+      const p995 = quantileSorted(samples, 0.995);
+      const p999 = quantileSorted(samples, 0.999);
 
       if (this.bench.signal?.aborted) {
         return this;
diff --git a/src/utils.ts b/src/utils.ts
@@ -15,14 +15,6 @@ function isPromiseLike<T>(maybePromiseLike: any): maybePromiseLike is PromiseLik
   );
 }
 
-/**
- * Computes the variance of a sample.
- */
-export const getVariance = (samples: number[], mean: number) => {
-  const result = samples.reduce((sum, n) => sum + ((n - mean) ** 2), 0);
-  return result / (samples.length - 1) || 0;
-};
-
 // eslint-disable-next-line @typescript-eslint/no-empty-function
 const AsyncFunctionConstructor = (async () => {}).constructor;
 
@@ -64,3 +56,60 @@ export const isAsyncTask = async (task: Task) => {
     return false;
   }
 };
+
+/**
+ * Computes the average of a sample.
+ *
+ * @param samples the sample
+ * @returns the average of the sample
+ */
+export const average = (samples: number[]) => {
+  if (samples.length === 0) {
+    throw new Error('samples must not be empty');
+  }
+
+  return samples.reduce((a, b) => a + b, 0) / samples.length || 0;
+};
+
+/**
+ * Computes the variance of a sample with Bessel's correction.
+ *
+ * @param samples the sample
+ * @param avg the average of the sample
+ * @returns the variance of the sample
+ */
+export const getVariance = (samples: number[], avg = average(samples)) => {
+  const result = samples.reduce((sum, n) => sum + ((n - avg) ** 2), 0);
+  return result / (samples.length - 1) || 0;
+};
+
+/**
+ * Computes the q-quantile of a sorted sample.
+ *
+ * @param samples the sorted sample
+ * @param q the quantile to compute
+ * @returns the q-quantile of the sample
+ */
+export const quantileSorted = (samples: number[], q: number) => {
+  if (samples.length === 0) {
+    throw new Error('samples must not be empty');
+  }
+  if (q < 0 || q > 1) {
+    throw new Error('q must be between 0 and 1');
+  }
+  if (q === 0) {
+    return samples[0];
+  }
+  if (q === 1) {
+    return samples[samples.length - 1];
+  }
+  const base = (samples.length - 1) * q;
+  const baseIndex = Math.floor(base);
+  if (samples[baseIndex + 1] != null) {
+    return (
+      (samples[baseIndex]!)
+      + (base - baseIndex) * ((samples[baseIndex + 1]!) - samples[baseIndex]!)
+    );
+  }
+  return samples[baseIndex];
+};
