Should composites be eagerly interned (`===` equal)

[acutmore]

A question raised during yesterday's plenary was if the creation of Composite's should eagerly intern/canonicalize, such that Composite({ x: 1 }) === Composite({ x:1 }).

Upsides:

• "pay to play"
  • not requiring any changes to existing equality checks avoiding adding new code branches which can have a cost even if the application is not using Composites
• No new equality
  • Existing libraries/APIs would 'just work'
• Checking if two composites are equal would be one pointer equality check

Downsides:

• Composite creation becomes more expensive
• This would mean that unique symbol keys would not be possible
  • Only sortable values are usable as keys
  • Symbol.iterator could not be a key
• Could not do SameValueZero
  • Would either be SameValue or -0 is canonicalized to 0.
• Some objects would need to be banned from Weak{Map,Set}
  • e.g. Composite({ x: 1, y: 4 }) has no constituents that provide a non-infinite lifetime
• Potential for more garbage collection time due to added complexity
  • e.g. A WeakMap where Composite({ a: objectA, b: objectB, c: 42 }) is a key should remain in the WeakMap until either objectA or objectB becomes unreachable - this applies deeply for composites made from other composites.
• Prototype equality checks:
  • This may close the door for non-null prototypes with cross-realm equality
  • In a world where there are built in ordinal Composites (Tuples) with a Tuple.prototype to provide Symbol.iterator and list methods such as .map, .some for these to still be equal across realms they would need to have a realm scoped [[prototype]] lookup similar to primitives and the one being discussed for Shared Structs.

Important

The quantity of the above lists should not be interpreted as weights on different sides of a scale. 10 downsides could still be trumped by 1 upside.

One good next step here IMO is to get some empirical data from a prototype implementation to measure some of performance impacts of different designs with different application use cases. Maybe this will be a good time for me to learn how to build v8 and get a custom binary on to some mobile phones!

cc: @syg

[Maxdamantus]

Some objects would need to be banned from Weak{Map,Set}

e.g. Composite({ x: 1, y: 4 }) has no constituents that provide a non-infinite lifetime

Playing devil's advocate: if you're really going for interning semantics, wouldn't Composite({ x: 1, y: 4 }) itself have a non-infinite lifetime, since you'd expect it to eventually be cleaned up from the intern map if it's no longer strongly reachable?

Could not do SameValueZero

Would either be SameValue or -0 is canonicalized to 0.

I'll throw this out there: I wonder if it could be specified such that either -0 is canonicalized to +0 (allowing an interning-based implementation), or -0 is preserved in which case === must consider non-same composites equal where they differ only in zero-signedness (implying an implementation that does not (always) intern).

Composite({ x: +0 }) === Composite({ x: -0 }); // guaranteed true
Object.is(Composite({ x: +0 }), Composite({ x: -0 })); // implementation-dependent

I'll admit I'm not really a JS engine implementer, but I do strongly suspect that if this overall feature is widely used, the non-interning approach would be far more optimal. I'm not aware of any language implementation (at least not one considered to have decent performance) where strings are interned up-front[0], and I don't see why composite types would be fundamentally different in terms of whether interning is useful performance-wise.

If there is concern about implementation complexity of the non-interning solution, it might make sense for composite values (rather than all other values) to take the performance hit by interning initially, and then if/when composite values become popular, engines might put the effort into implementing structural equality instead. Perhaps in the future once no engine is interning, the specification could be made stricter by saying that -0 must be preserved (implying an implementation that does not (always) intern).

It might also be worth mentioning that the JVM does a sort of lazy interning of strings during garbage collection, where it will deduplicate the storage of equal strings (particularly, ones that have been sitting around for a while, so there's no up-front interning cost in string allocation). I'm not sure if JS implementations currently do this with strings, but lacking identity (as suggested by this issue) would likely make this optimization easier for composites. Strings in the JVM do unfortunately have identity, so they achieve this by making multiple distinct String objects share the same private array object which stores the actual string content.

Symbol.iterator could not be a key

Similar to above, I wonder if the spec could allow the implementation to make up an order at first, then a later revision could request order preservation in a post-interning world. I believe this change happened at some point for regular objects, so it seems like there is precedent for allowing implementation-dependent behaviour and then making the requirements stricter in the future, even though the initial state seems like a regression.

---

[0] Although these aren't quite strings, I do believe V8 uses an actual intern map for registered symbols. Theoretically it could instead use structural equality for registered symbols, but I guess the assumption is that construction (or "reforging") of registered symbols (via calls to Symbol.for) is relatively infrequent, so the performance issue is insignificant.

[Maxdamantus]

I'd also like to clarify that === semantics does not imply "interning". Strings in JS have === semantics, but every major implementation implements structural equality (O(n)) of strings instead of runtime interning: tc39/proposal-record-tuple#292 (comment)

[acutmore]

While that is true, for Composites the discussion is specifically around interning as the strategy. This is because the primary problem it is trying to solve, as I understand it, is to have zero impact to the performance of the existing equality paths which is only achieved by interning and re-using the existing object pointer equality.

[sethfowler]

I think this proposal would offer far more value to me, as a web developer, if Composites were ===-equal. Having an object-like data structure with value equality would single-handedly eliminate a major class of performance and correctness issues that I regularly see in real world code. So, I endorse the idea of using interning as a pragmatic strategy to get these benefits without impacting the performance of code that doesn’t use Composites.

[mhofman]

Some objects would need to be banned from Weak{Map,Set}
e.g. Composite({ x: 1, y: 4 }) has no constituents that provide a non-infinite lifetime

Playing devil's advocate: if you're really going for interning semantics, wouldn't Composite({ x: 1, y: 4 }) itself have a non-finite lifetime, since you'd expect it to eventually be cleaned up from the intern map if it's no longer strongly reachable?

The problem is not WeakMap / WeakSet on their own, but the existence of WeakRef / FinalizationRegistry in the language.

Because of this you can observe when the interned value would be cleared, even if you don't allow these composites directly in WeakRef / FinalizationRegistry, as you could associate a regular object to them through WeakMap.

Some previous related discussion: tc39/proposal-symbols-as-weakmap-keys#21

[travislwatson]

Instead of altering the semantics of the root Composite in the proposal, it could be kept as is for the shallow immutability large compatibility (Map/Set/Props), and Composite.deep (or similar syntax, see #14) can be a trigger for the interned variation used for === equality and deep immutability. This would give developers a choice as to whether or not to pay for the interning. The deep case is also the one that benefits the most from a literal syntax #7 since it needs to enforce composites deeply.

[sebinsua]

Maybe there could be a Composite.for(...) that behaves differently to Composite(...) (similar to how Symbol.for("a") === Symbol.for("a") is different from Symbol("a") === Symbol("a")).

[Maxdamantus]

Because of this you can observe when the interned value would be cleared, even if you don't allow these composites directly in WeakRef / FinalizationRegistry, as you could associate a regular object to them through WeakMap.

Some previous related discussion: tc39/proposal-symbols-as-weakmap-keys#21

Right, I think we agree that there are issues with both WeakMap and WeakRef/FinalizationRegistry when it comes to interning.

The point I was getting at is that involves code such as the following:

async function f() {
    const myObject = {};
    const map = new WeakMap();
    map.set(Composite({ x: 42 }), "foo");
    map.set(Composite({ x: myObject }), "bar"); // new composite object; engine can optimize this away as a noop, similar to `map.set({}, "baz")`
    await doSomethingElse();
    map.get(Composite({ x: 42 })); // ???
    map.get(Composite({ x: myObject })); // ???
}

If the composites are truly interned, they would presumably be collectable if there are no strong references remaining (you've made a similar point about registered symbols in the other thread—GlobalSymbolRegistry is a spec fiction, since registered symbol interning is not observable).

It should probably be noted that this is independent of whether the composite members are plain objects or primitives (eg, numbers); in either case, using composites as keys in a WeakMap is unreliable since Composite can return a new composite value for the same members, if the old composite value has no more strong references.

imo either all composites should be banned as WeakMap keys, or they should not have observably interned behaviour, meaning:

• Composite({ x: myObjectA, y: myObjectB }) exists as long as all of [myObjectA, myObjectB] exist
• Composite({ x: myObjectA }) exists as long as all of [myObjectA] exist
• Composite({}) exists as long as long as all of [] exist (forever)

If you store any of these values in a WeakMap, the map will store them for as long as they exist. I don't think making rules about subsets of Composite values helps at all.

[acutmore]

weakMap.set(Composite({ x: 42 }), "foo");

As per the initial issue post, I think this would need to be banned:

Some objects would need to be banned from Weak{Map,Set}

Composites that have no finite lifetime bearing constituents would only be a memory leak from the perspective of the weakMap. But developers may think that they are avoiding memory leaks by using a WeakMap.

Even then I am still concerned that the 'quick fix' here will be that developers will then add some unnecessary long lived object to the composite to satisfy the constraint which would likely lead to the same leak.

This is why I was initially imagining that we wouldn't do interning and that composites in a WeakMap would have the same semantics as all other objects, the value is being associated specifically with that composite's identity (discussed in #10).

Perhaps we can find a design that does do interning that also avoids the potential of increasing the chance of introducing memory leaks.

[Maxdamantus]

As per the initial issue post, I think this would need to be banned:

Okay, so just to be clear, you'd expect that for unbanned keys, WeakMaps would hold composite objects "strongly" (conditional on their members [0]), meaning this works reliably?

async function f() {
    const myObject = {};
    const map = new WeakMap();
    map.set(Composite({ x: myObject }), "bar");
    await doSomethingElse();
    return map.get(Composite({ x: myObject })); // "bar"
}

ie, even though nothing else has a reference to the object returned by the initial Composite({ x: myObject }) call, it will not be evicted from the hypothetical composite registry due to its use as a WeakMap key?

---

[0] Implementation-wise, I believe this means an entry in the WeakMap basically corresponds to a multi-key ephemeron, where the object members are shallowly deeply-ish[1] extracted as keys, and the value includes the map key (composite object) as well as the mapped value, eg:

const myObjectA = {}, myObjectB = {};
const composite = Composite({ x: myObjectA, y: myObjectB, z: 42 });
const map = new WeakMap();
map.set(composite, "foo");

would involve an ephemeron:

Ephemeron {
    keys: [myObjectA, myObjectB],
    value: { mapKey: composite, mapValue: "foo" },
}

where an ephemeron is a special value that defers tracing during GC until all of the keys have been determined reachable (sample inefficient JS implementation).

[1] It would only need to be as deep as the composite values go, so the ephemeron key extraction of Composite({ x: Composite({ y: { myObject } })) would be [myObject], assuming myObject is a non-composite object.

[acutmore]

ie, even though nothing else has a reference to the object returned by the initial Composite({ x: myObject }) call, it will not be evicted from the hypothetical composite registry due to its use as a WeakMap key?

Yes, if Composites are defined as being interned then the two calls to Composite({ x: myObject }) are semantically creating the same value, regardless of if they could theoretically have been garbage collected and a new one was actually created (just like strings).

Otherwise the language would be saying that the lifetime of interned Composites as a key in a WeakMap are effectively implementation defined.

WeakMaps can already be a memory leak hazard (globalThis would be a key that is effectively never collected) but part of me is worried that something that boils down to the following would happen:

export const PositionTag = Symbol("Position");
export function makePos(x: number, y: number) {
   return Composite({ tag: PositionTag, x, y });
}

If the composites returned by makePos are both interned and valid as a WeakMap key (WMK) then any time they are used as a WMK they will leak until they are either explicitly removed from the WeakMap or the weakMap itself is no longer referenced and gets collected.

[Jamesernator]

WeakMaps can already be a memory leak hazard (globalThis would be a key that is effectively never collected) but part of me is worried that something that boils down to the following would happen:

I agree this is possible, but the same problems can occur with weakmap chaining as well. I feel that WeakMap usage is uncommon enough that people generally wouldn't reach for it unless they understand what the lifetime is anyway.

I think lacking the weak composite would be unfortunate as things like caching decorators are useful with weak arguments. For example caching WebGPU render bundles for a mesh per each different camera passed:

class GLMesh {
    // Multiple cameras may exist, for example in split screen
    // when a camera is released, the render bundle can be freed as it no longer possible
    // to be re-used at that point
    @cached((camera, colorFormat) => Composite({ camera, colorFormat }))
    #renderBundle(camera: camera, colorFormat: GPUTextureFormat): GPURenderBundle {
         const renderBundleEncoder = this.#device.createRenderBundleEncoder({ colorFormat, /* ... */ });

         renderBundleEncoder.setBindGroup(CAMERA_BIND_GROUP_INDEX, camera.bindGroup);
         // ...set other bind groups and such
         return renderBundleEncoder.finish();
    }

    render(renderPass: GPURenderPassEncoder, camera: GLCamera, colorFormat: GPUTextureFormat): void {
        renderPass.executeBundles([this.#renderBundle(camera, colorFormat)]);
    }
}

where cached is basically just:

function cached<This, Args extends any[], Ret>(
     toKey: (...args: Args) => WHATEVER_COMPOSITE_KEY_RETURNS,
) {
     return function decorateMethod(method: (this: This, ...args: Args) => Ret) {
         const cache = WeakMap.WITH_WEAK_KEY_SUPPORT<WHATEVER_COMPOSITE_KEY_RETURNS, Ret>();
         return function(this: This, ...args: Args): Ret {
             // NOTE: We also cache *weakly* on the instance of the class
             const key = MAKE_COMPOSITE_SOMEHOW({ this: this, argsKey: toKey(...args) });
             if (cache.has(key)) return cache.get(key);
             const newValue = method.call(this, ...args);
             cache.set(key, newValue);
             return newValue;
         }
     }
}