Feature request: collections that use referential equality

[philnguyen]

Is there a way to customize the collections to use referential equality that I'm not aware of, or is it not available yet?

Many thanks.

[qurbonzoda]

Currently all implementations are internal, only interfaces are public.

to customize the collections to use referential equality

Do you mean to treat two elements of a collection equal only if they are referentially equal?

Could you please share your use case?

[bubenheimer]

Wonder if this could be reopened? I have the same need. My use case is StateFlow<PersistentMap> (implementing a persistent in-memory cache), with a potentially large map size, where the common map write operation is updating an existing entry. Currently using ordered map, but expecting to switch to unordered for better iteration performance.

From code inspection it looks like current equals() implementation may be relatively expensive in this case, perhaps at least O(log(n))? The StateFlow has high update frequency, so this looks forbidding, I don't really need non-identity equals() in the first place.

I guess I will wrap the PersistentMap for the time being.

I suppose complexity of the update operation would be O(log(n)) ideally, which would make an equals() at O(log(n)) relatively less expensive. At O(n) that would no longer be true. It looks quite wasteful in either case, as I don't really need it at all.

There may need to be a broader discussion on persistent collections equality handling. I see use cases being quite different from traditional collections, which I would not really want to update incrementally in this fashion and push through a flow (when they're large). Doing full equals by default in the persistent collections case looks wrong to me, because I think comparing incrementally changed collections, perhaps inadvertently, is much more common than in the traditional collections case, so it's an expensive default. Also keep in mind Compose usages, where equality comparisons are everywhere. (It looks like Compose's own SnapshotStateMap thankfully uses identity-based equals.)

[bubenheimer]

N.B. I was able to replace my StateFlow with a volatile var, so I've lost my use case for now. I still think it's at least a messy situation, with it being an implementation detail and no documentation. Also, inconsistency between different collection-style classes, e.g. PersistentList currently using object identity for equals.

Actually, I still have a use case, with an ImmutableList. IntelliJ's (broken) "Structure" view on PersistentVector misled me into believing it was using object identity for equals(), but that's not true.

I have StateFlow<ImmutableList<...>> for a potentially large cache and there I definitely need the Flow part to track changes, but I also would want access to the current value. Again, once I am aware of the problem, I can replace ImmutableList with a delegating class, but I do lose out on some of the straightforward equality checks, like empty lists. I guess these collection classes just don't really work with StateFlow, even though it is such a tempting use case. I will use SharedFlow & another volatile var to work around it for now, I think.

[bubenheimer]

The more I think about it, I believe I have a good case for not having custom equals() by default at all for kotlinx.collections.immutable classes:

Compose used to treat these classes just like any other, meaning non-@Stable. However, that changed not too long ago (and I even asked to make it more pervasive myself); all these classes are treated as @Stable (or rather, @Immutable) now. This makes sense, because they are indeed immutable. One would think this change would generally have a beneficial performance impact on function recompositions, but actually it could make recomposition behavior much worse: the compiler would always recompose a function in the case of a non-stable collection class parameter, but now it will do a full equals check on the stable collection parameter on every recomposition, which could crater performance if a persistent collection is not small and is updated frequently.

I do not think this is a problem with Compose. I think what this highlights is that the use cases for persistent collections are different from those for traditional collections. Using structural equality as the default is not really appropriate for persistent collections.