Composites' Comparator Choice

For discussion

quick recap

last presented April 2025

2

Core problem space - 'composite map keys'

3

const position1 = Object.freeze({ x: 1, y: 4 });

const position2 = Object.freeze({ x: 1, y: 4 });

​

const positions = new Set([

position1,

position2

]);

positions.size; // 2 😭

​

Common solution

4

const position1 = Object.freeze({ x: 1, y: 4 });

const position2 = Object.freeze({ x: 1, y: 4 });

​

const positions = new Set([

JSON.stringify(position1),

JSON.stringify(position2)

]);

positions.size; // 1 🙃

​

Downsides of stringification

5

• JSON stringify
• impacted by key-order
• Can throw (e.g. BigInts)
• data loss (NaN becomes null, dates become strings)
• potential for higher memory footprint
• Map keys are then strings
• Need a reverse mapping

Composite Keys

6

const position1 = Composite({ x: 1, y: 4 });

const position2 = Composite({ x: 1, y: 4 });

​

const positions = new Set([

position1,

position2

]);

positions.size; // 1 😀

​

To be interned, or not to be,

that is the question.

7

Menu A: "Unique objects"

8

let c1 = new Composite({ x:1, y:4 });

let c2 = new Composite({ x:1, y:4 });

​

c1 === c2; // false

​

Composite.equal(c1, c2); // true

new Set([c1, c2]).size; // 1�new Map([[c1], [c2]]).size; // 1

[c1].includes(c2); // true

Menu A: "Unique objects"

9

fun Composite(data) {

return freeze({ ...data, #isComposite: true, #hash: Hash(data) });

}

​

fun Set.prototype.has(this, v) {

switch type (v) {

case "number": …

case "etc" …

case "object":

if (isComposite(v)) {

bucket = this.#buckets[v.#hash];

return bucket?.includes(compositeMatchFor(v)) ?? false;

}� …

}

}

Menu B: "Interned Objects"

10

let c1 = Composite({ x:1, y:4 });

let c2 = Composite({ x:1, y:4 });

​

c1 === c2; // true (everywhere)

​

​

Menu B: "Interned Objects"

11

compositesCache = new Map<Hash, WeakArray>();

​

fun Composite(data) {

hash = Hash(data);

bucket = compositesCache.getOrInsert(hash, new WeakArray);

c = bucket.find(matchFor(data));

if (!c) {

c = freeze({ ...data, #isComposite: true });

arr.push(c);

}

return c;

}

​

fun GC_sweep() {

for (const [hash, bucket] of compositesCache)

if (bucket.empty) compositesCache.remove(hash)

}

Comparing the Comparisons

12

• "Unique"
• Creation cost similar to regular objects
• GC semantics follow regular objects
• Equality only works in certain APIs
• Map, Set, Array.prototype.{includes, indexOf}, 🔮Signals, iterator.uniqueBy
• SameValueZero? Unsorted/Symbol Keys? Prototypes?
• "Interned"
• Variable creation cost
• New GC semantics
• Equality works everywhere
• SameValueZero, Unsorted/Symbol keys, Prototypes?

Experimental implementation

#27

13

Micro Benchmarking

14

function cubeLoop(D, callback) {

let vec = { x:0, y:0, z:0 };

​

for (let x = 0; x < D; x++) {

vec.x = x + offset;

for (let y = 0; y < D; y++) {

vec.y = y + offset;

for (let z = 0; z < D; z++) {

vec.z = z + offset;

callback(vec);

}

}

}

}

Creating lots of composite-keys

15

Creating lots of composite-keys and inserting them into a Set

16

Repeatedly creating composite-keys and inserting them into a Set

17

Iterations

Creating composite-keys and then repeatedly inserting them into a Set

18

Iterations

GC Semantics of interning objects

19

let c = Composite({ x: 1, y: 4 });

let ws = new WeakSet();

ws.add(c); // 1 ?

ws.has(c); // 2 ?

c = null;

await time(); // 💤

c = Composite({ x: 1, y: 4 });

ws.has(c); // 3 ?

GC Semantics of interning objects

20

ws.add(c); // 1 ?

​

ws.has(c); // 2 ?

ws.has(c); // 3 ?

throws

false

false

true

Not all objects are valid weak keys 😰

true|false 🎲 ❌

Unreliable weak keys 😤 🎲 ❌

Memory leak risk 😬 🛠️

💤

true

GC Semantics of interning objects

21

ws.add(c); // 1 ?

​

ws.has(c); // 2 ?

ws.has(c); // 3 ?

throws

false

false

true

Not all objects are valid weak keys 😰

Memory leak risk 😬 🛠️

💤

true

Queue time

22

Continuing�Composites' Comparator�Choice

23

🌡️ Temperature check

24

Based on what you have seen so far…��If interning,�is your preference to throw for leaky composites?

🌡️ Temperature check

25

Based on what you have seen so far…��If doing composites as one of the presented designs,�Are you learning towards interning?