[Research] Benchmarking approaches

**EDIT** Sep 29 '25: Updated with improved implementation performance figures **EDIT** Oct 29 '25: Updated with more recent v8 build that uses interning for `JSON.stringify` map keys. ---- As per my comment here: https://github.com/tc39/proposal-composites/issues/15#issuecomment-2834555940 > I do think that the best next step here is for someone (maybe me, maybe someone else) to try and implement the different approaches natively and get some experimental performance measurements. As I think numbers are the main missing ingredient. I've got two working implementations of Composites in V8 - **Composite (native)**: Where each Composite created is a new object, and `Map` and `Set` has custom handling to ensure composites are compared by structure. [branch](https://github.com/acutmore/v8/tree/composite) - **Intern Composite (native)**: One where creating a Composite looks up in a global map to see if an equal composite already exists and returns that. So equal composites are `===` pointer equal. [branch](https://github.com/acutmore/v8/tree/composites-intern) I've done this with my spare time and I'm no JS engine expert so the implementations could probably be significantly improved. However I think they are good enough to get starting numbers for how the performance is likely to look, at least for not heavily specialised native implementations. I also have the same two approaches implemented as JavaScript polyfills too. - **Composite (JS)**: [branch](https://github.com/tc39/proposal-composites/tree/main/polyfill) - **Intern Composite (JS)**: [branch](https://github.com/tc39/proposal-composites/tree/interning/polyfill). Note: The polyfills are written defensively. To ensure they continue to work correctly even if globals are mutated after they are loaded, e.g. someone putting a setter on `Object.prototype`, or deleting `Map.prototype.set`. This adds non-trivial overhead. Variations of them which do not prioritize this level of correctness go noticeably faster. i.e. these represent worst case instead of being optimized for speed. The test case revolves around creating _keys_ that represent a 3D position `{ x: number, y: number, z: number }`. For baselines to compare against I also have: - **JSON**: `createKey = (val) => JSON.stringify(val)` - Note: The version of v8 I've branched _does_ include the recent https://v8.dev/blog/json-stringify optimization - **JSON (custom)**: `ID=(k,v)=> v; createKey = (val) => JSON.stringify(val, ID)` - **Intern (bespoke JS)**: A JavaScript implementation specifically for creating objects with `x,y,z` numbers that are `===` equal. i.e. the bare minimum needed. <details> <summary>Bespoke Vec3 JS implementation</summary> ```js (function (global) { "use strict"; global.weakVec3 = weakVec3; var freeze = Object.freeze; var root = new Map(); function cleanUp(map, ns) { let next = ns.shift(); let result = map.get(next); if (!result) return map.size === 0; if (ns.length === 0) { // WeakRef leaf if (!result.deref()) { map.delete(next); return map.size === 0; } return false; } else { if (cleanUp(result, ns)) { map.delete(next); return map.size === 0; } else { return false; } } } var fr = new FinalizationRegistry((ns) => { cleanUp(root, ns); }); function weakVec3(arg) { let xv = arg.x; let x = root.get(xv); if (x === void 0) { x = new Map(); weakRoot.set(xv, x); } let yv = arg.y; let y = x.get(yv); if (y === void 0) { y = new Map(); x.set(yv, y); } let zv = arg.z; let vec = y.get(zv)?.deref(); if (vec === void 0) { vec = freeze({ x: xv, y: yv, z: zv }); fr.register(vec, [xv, yv, zv]); y.set(zv, new WeakRef(vec)); } return vec; } }(globalThis)); ``` </details> ## Setup <details><summary>cube.js</summary> ```js (function main(require, cliArgs) { "use strict"; // CONFIG: // =============================== var technique; // technique = "json"; // technique = "bespoke-js"; // technique = "json-custom"; technique = "native"; // technique = "polyfill"; // =============================== var testCase; // testCase = "creation"; testCase = "fill-set"; // testCase = "fill-set-reads"; // =============================== const [D = 50, N = 1] = cliArgs.map(v => parseInt(v)).filter(v => isFinite(v)); if (D < 1) throw new Error("D must be >= 1"); if (N < 1) throw new Error("N must be >= 1"); // =============================== var offset = Number.MAX_SAFE_INTEGER - D; // =============================== function assert(v, msg) { if (!v) { const err = new Error(msg || "assertion failed"); Error.captureStackTrace(err, assert); throw err; } } var theSet = new Set(); var createKey, parseKey; function addKeyToSet(_vec, k) { theSet.add(k); }; function validateKey(vec, k) { const rec2 = parseKey(k); assert(vec.x === rec2.x); assert(vec.y === rec2.y); assert(vec.z === rec2.z); } if (technique === "native") { createKey = function createKey(k) { return new Composite(k); }; parseKey = function parseKey(k) { return k; }; } else if (technique === "polyfill") { require("../composite-intern.js"); // require("../composite.js"); globalThis["compositePolyfill"].install(globalThis); createKey = function createKey(k) { return Composite(k); } parseKey = function parseKey(k) { return k; }; } else if (technique === "json") { createKey = function createKey(k) { return JSON.stringify(k); } parseKey = function parseKey(k) { return JSON.parse(k); }; } else if (technique === "json-custom") { let customJson = (k, v) => v; createKey = function createKey(k) { return JSON.stringify(k, customJson); } parseKey = function parseKey(k) { return JSON.parse(k, customJson); }; } else if (technique === "bespoke-js") { require("../interned-vector.js"); createKey = function createKey(k) { return weakVec3(k); } parseKey = function parseKey(k) { return k; }; } else { throw new Error("Unknown technique " + technique); } function cubeLoop(D, cb) { var vec = {}; vec.x = 0; vec.y = 0; vec.z = 0; for (var x = 0; x < D; x++) { vec.x = offset + x; for (var y = 0; y < D; y++) { vec.y = offset + y; for (var z = 0; z < D; z++) { vec.z = offset + z; cb(vec, createKey(vec)); } } } } if (testCase === "creation") { var results = []; var i = 0; function add(_, key) { results[i] = key; i += 1; if (i > 10) { i = 0; } } cubeLoop(D, add); results.length = 0; i = 0; cubeLoop(D, add); results.length = 0; } else if (testCase === "fill-set") { cubeLoop(D, addKeyToSet); cubeLoop(D, addKeyToSet); assert(theSet.size === D ** 3, `Expected ${D ** 3}, got ${theSet.size}`); } else if (testCase === "fill-set-reads") { let arr = []; cubeLoop(D, (_, key) => { arr[arr.length] = key; }); for (let i = 0; i < N; i++) { for (let k = 0; k < arr.length; k++) { theSet.add(arr[k]); } } } else { throw new Error("unknown testcase: " + testCase) } theSet.clear(); })( typeof require === "function" ? require : load, typeof process !== "undefined" ? process.argv.slice(2) : typeof arguments !== "undefined" ? arguments : [] ); ``` </details> The script is always run with [hyperfine](https://github.com/sharkdp/hyperfine). Taking the average of 10 runs. Meaning the times are the total process time. Including process startup and exit. Results are reported in milliseconds ⏱️. ⚠️ As the scripts are sync and do not yield, the tests do not trigger the `FinalizationRegistry ` in the polyfills. In general these tests are unlikely to reflect the GC cost of the different approaches. I also do not measure peak memory usage. I would like to do separate tests that focus on these aspects, when I find the time. Please keep this in mind when making opinions based on the results. We are not seeing the full picture. I'm running the tests on an 💻 Apple M2 Pro (32 GB) (15.6.1 (24G90)). My build of `d8` is branched off version `14.3.0 (candidate)`. ## Creation This test takes a size D(epth) and creates all 3D integer points of a D*D*D cube, twice. Three different values of D are tested: - **70**: `77 ** 3 === 343_000`, (twice: `686_000`) - **88**: `88 ** 3 === 681_472`, (twice: `1_362_944`) - **111**: `111 ** 3 === 1_367_631`, (twice: `2_735_262`) To make things a little more realistic, instead of creating small integers like `x: 1, y: 1, z: 1` the integers are offset so that they are real 64bit floats. | |JSON | Intern (bespoke JS) | Composite (native) |Composite (JS)| JSON custom | Intern Composite (native) | Intern Composite (JS) | |----------|----|----------------------|--------------------|---------------|---------------|---------------------------|-------------------------| | **D=70** | 74 | 178 | 111 | 254 | 252 | 144 | 623 | | **D=88** | 130 | 337 | 201 | 489 | 494 | 273 | 1281 | | **D=111** | 242 | 678 | 379 | 965 | 966 | 549 | 2802 | <img width="1165" height="554" alt="Image" src="https://github.com/user-attachments/assets/434c0b0e-84a3-472e-af69-1b880ee4629d" /> - JSON comes out on top. Which is perhaps not a surprise given [how optimized it is in V8](https://v8.dev/blog/json-stringify). - Perhaps more surprisingly the bespoke JS comes in 3rd. Showing just how fast JS can go in an engine like V8 and when it's doing the bare minimum needed for the task. - With the two native implementations of Composites, interning during construction is adding between 30% and 90% more time. - However a cache hit when creating a interned Composite can be about 40% faster - The polyfills are the slowest, which is to be expected here. The interning polyfill is twice as slow to creates the composites, but it is still able to create around 1 million composites per second. ## `Set` fill As above the test creates the the same vectors but this time it puts them into a JS `Set`. Because each position is created twice, the 2nd `Set` insertion will always be a collision with the existing value. So the test is testing: creations, insertion, and lookup. | |JSON | Intern (bespoke JS) | Composite (native) |Composite (JS)| JSON custom | Intern Composite (native) | Intern Composite (JS) | |----------|----|----------------------|--------------------|---------------|---------------|---------------------------|-------------------------| | **D=70** | 159 | 190 | 172 | 852 | 337 | 166 | 655 | | **D=88** | 346 | 376 | 327 | 1659 | 677 | 322 | 1518 | | **D=111** | 760 | 950 | 690 | 3581 | 1410 | 786 | 3294 | <img width="1166" height="554" alt="Image" src="https://github.com/user-attachments/assets/5178806f-6179-4ab7-afa0-43e8c5eff4a9" /> - JSON holds the lead, but the margin is reduced. This is because inserting strings into a Set now triggers some of the extra work that the native Composite has already done during it's creation such as calculating it's hash value. - The Intern Composite is slightly slower than the _regular_ Composite. Which makes sense because interning is a HashMap lookup, so it's having to do two different types of HashMap lookup. Instead of one. ## Repeated `Set` insertion This tests creates all the positions once (half the number of creations) and then keeps inserting all of them into the same Set **N** times. This tracks the cost of repeated lookups using the same key. **D=111**. | |JSON | Composite (native) | Intern Composite (native) | |----------|-----|--------------------|---------------------------| | **N=1** | 400 | 327 | 549 | | **N=2** | 428 | 387 | 574 | | **N=3** | 453 | 461 | 609 | | **N=4** | 487 | 520 | 643 | | **N=5** | 508 | 585 | 664 | | **N=6** | 534 | 666 | 689 | | **N=7** | 569 | 718 | 737 | | **N=8** | 587 | 798 | 761 | | **N=9** | 624 | 854 | 802 | | **N=10**| 649 | 929 | 823 | <img width="1160" height="697" alt="Image" src="https://github.com/user-attachments/assets/c0181896-1e83-4d98-93bc-3e78ee5c7208" /> - Doing lookups of the Interning composite is the fastest, which is what we'd expect because we are effectively inserting pointers. - Interning Composites and JSON strings have the same slope, showing they both do similar amounts of work (now that v8 interns JSON strings when used as keys). - The extra overhead of the interning eventually pays off after enough repeated lookups using the same reference. - The head start that _regular_ Composites get from being cheaper to create eventually loses out to the interned Composite after 8 lookups. ## Repeated creation and `Set` insertion This test is similar to above, except that it keeps creating fresh keys every time and inserting them into the same `Set`. Instead of only creating the keys once and then re-using them. | |JSON | Composite (native) | Intern Composite (native) | |----------|-----|--------------------|---------------------------| | **N=1** | 452 | 441 | 570 | | **N=2** | 777 | 782 | 800 | | **N=3** | 1094 | 1138 | 1053 | | **N=4** | 1407 | 1164 | 1318 | | **N=5** | 1747 | 1799 | 1537 | | **N=6** | 2065 | 2168 | 1767 | | **N=7** | 2381 | 2514 | 2002 | | **N=8** | 2694 | 2832 | 2248 | | **N=9** | 3011 | 3184 | 2492 | | **N=10**| 3331 | 3488 | 2809 | <img width="1160" height="697" alt="Image" src="https://github.com/user-attachments/assets/2344566d-dd4e-4eeb-a4ed-77a93cabafb8" /> - They all have similar slopes. Interning composites is the shallowest, _regular_ composites the steepest, JSON in the middle. - While _regular_ Composites and JSON start out the fastest, the extra cost of interning Composites balances out once created the same key twice. ### Polyfill overhead When Composites are not interned, the polyfill needs to replace `Set.prototype.add` with a custom implementation that changes the logic when the argument is a Composite. This naturally adds overhead to each call to `set.add` even for non-composite values. https://github.com/tc39/proposal-composites/blob/1c8c3f2f7b8bf856debdb7237c6f52986a0e86dd/polyfill/collection-set.ts#L28-L33 Technically this also applies to the native implementation however there are already many branches to test for the different value types that an object pointer may be in v8 (e.g. it could be a string, a double, or a bigint etc) and my tests did not show any observable overhead of the extra branch to also check if the type is a Composite. Potentially because the CPU was able to track that the branch was never taken. I repeated the test above but with the Polyfill installed. | |JSON | JSON (Composite polyfill loaded) | |----------|-----|-----------------------------------| | **N=1** | 333 | 362 | | **N=2** | 394 | 455 | | **N=3** | 455 | 577 | | **N=4** | 534 | 628 | | **N=5** | 597 | 737 | | **N=6** | 656 | 862 | | **N=7** | 727 | 930 | | **N=8** | 785 | 1009 | | **N=9** | 865 | 1116 | | **N=10**| 923 | 1210 | <img width="1010" height="609" alt="graph of above" src="https://github.com/user-attachments/assets/d49908b9-2ce1-436f-aa5c-1c7dd8d4ff16" /> After 13_676_310 lookups, the overhead of the polyfill was 287ms. The overhead may be higher on lower spec CPUs such as on handheld devices. The overhead will, almost certainly, also be higher for the more complex methods such as `Set.prototype.intersection` which would also need to be [replaced by the polyfill](https://github.com/tc39/proposal-composites/blob/1c8c3f2f7b8bf856debdb7237c6f52986a0e86dd/polyfill/collection-set.ts#L76-L94). The interning polyfill does not need to replace these methods, though it _may_ still need to replace things like `WeakMap.prototype.add`. ## Some follow on questions - The different memory profiles of the approaches may be interesting. Speed is not the only concern of applications. Memory also tends to have fixed limits. - If this proposal is aiming to be a better approach than `JSON.stringify`, are we concerned with JSON sometimes being faster? - Composites still have advantages (supports more values types, property order does not impact equality, data can be accessed directly without parsing) - A more advanced implementation may be able to go faster. (e.g. specialized inlining at call sites ) - What is the GC overhead from the global interning store? - Can the initial cost of interning be reduced so that it takes fewer `Set` lookups before it pays off?