benchmark.diff

commit 618e4f19f47bb6473f15e70973fbb54ca7bb3cbc
Author: Mark Probst <mark.probst@gmail.com>
Date:   Tue Sep 28 20:28:02 2021 -0400

    Benchmark

diff --git a/functions/src/cli-routines/all-routines.ts b/functions/src/cli-routines/all-routines.ts
index f0d4f219dc..555077558d 100644
--- a/functions/src/cli-routines/all-routines.ts
+++ b/functions/src/cli-routines/all-routines.ts
@@ -182,6 +182,7 @@ import { syncPromoCodeRoutine } from "./sync-promo-code";
 import { syncUsersHubspotContactsRoutine } from "./sync-users-hubspot-contacts";
 import { testAllowedEditsRoutine } from "./test-allowed-edits";
 import { copyTestAppByNameRoutine, copyTestAppsRoutine } from "./test-apps";
+import { testAVLRoutine } from "./test-avl";
 import { testDirtyingModelRoutine } from "./test-dirtying-model";
 import {
     testFunctionInvocationTimesRoutine,
@@ -380,4 +381,5 @@ export const routines: CLIRoutine[] = [
     replicatePgMirrorTablesRoutine,
     setAppKind,
     compressJSONRoutine,
+    testAVLRoutine,
 ];
diff --git a/functions/src/cli-routines/test-avl.ts b/functions/src/cli-routines/test-avl.ts
new file mode 100644
index 0000000000..72565bd33f
--- /dev/null
+++ b/functions/src/cli-routines/test-avl.ts
@@ -0,0 +1,78 @@
+import { assert } from "@glideapps/ts-necessities";
+import AVLTree from "avl";
+
+import { logInfo } from "../debug-print";
+import { ResultStatus } from "../honeycomb";
+import { CLIRoutine } from "./routine";
+
+const numInserts = 3000000;
+// We clear when the map hits this size
+const clearAbove = 1000;
+// Once we clear, we clear until we get down to this size, or in the case
+// of `Map`, approximately.
+const clearTo = 800;
+
+function testAVL(): void {
+    const start = Date.now();
+
+    const tree = new AVLTree<number, number>();
+    for (let i = 0; i < numInserts; i++) {
+        tree.insert(Math.random(), Math.random());
+
+        if (tree.size >= clearAbove) {
+            while (tree.size >= clearTo) {
+                const minNode = tree.minNode();
+                assert(minNode !== null);
+                assert(minNode.key !== undefined);
+
+                tree.remove(minNode.key);
+            }
+        }
+    }
+
+    logInfo("AVL took", Date.now() - start);
+}
+
+function testMap(): void {
+    const pKeep = clearTo / clearAbove;
+
+    const start = Date.now();
+
+    const map = new Map<number, number>();
+    for (let i = 0; i < numInserts; i++) {
+        map.set(Math.random(), Math.random());
+
+        if (map.size >= clearAbove) {
+            const toDelete = new Set<number>();
+            for (const [k, _v] of map) {
+                // We're approximating clearing as many items as we need to
+                // get down to our target.  I verified that we get to about
+                // the correct number here.  Note that we also generate random
+                // numbers here which might make this test slower.
+                if (Math.random() >= pKeep) {
+                    toDelete.add(k);
+                }
+            }
+            for (const k of toDelete) {
+                map.delete(k);
+            }
+        }
+    }
+
+    logInfo("map took", Date.now() - start);
+}
+
+export const testAVLRoutine: CLIRoutine = {
+    name: "test-avl",
+    usage: "test-avl",
+    allowProd: false,
+    minArgs: 0,
+    maxArgs: 0,
+    safetyLevel: "safe",
+    validateArgs: undefined,
+    fn: async () => {
+        testAVL();
+        testMap();
+        return ResultStatus.OK;
+    },
+};

This assumes we get 200 new entries per minute, we cache for 5 minutes (=1000), and we clear every minute (1000-200=800).

[2021-09-29T00:30:49.526Z] INFO (test-avl.js:40) - AVL took 819
[2021-09-29T00:30:50.328Z] INFO (test-avl.js:64) - map took 802

This simulates ~1.7 years worth of insert/delete operations.