VectorMap should cooperate with im/mutable HashMap/Sets/VectorMaps during addAll/removeAll/concat/removedAll etc.

[joshlemer]

Similar to the work done in scala/scala#7520, VectorMaps contain Maps (maybe we should change it to contain specifically HashMaps), which means that like in that PR, VectorMaps can join the club and avoid rehashing of elements during bulk add/remove transformations with those collections.

[MrRexZ]

@joshlemer
Yeah, I think it should be HashMap, as @mdedetrich repository here says it's meant to build with HashMap.
I can help on this (seems very straightforward since it just require changing the underlying implementation of the map) and then it can re-use your implementation. Do I have to wait until scala/scala#7520 is merged, or can I start right away?
Or can I start from your un-merged branch and push there?

[joshlemer]

Yeah, I think it should be HashMap, as @mdedetrich repository here says it's meant to build with HashMap.

Excellent!

Do I have to wait until scala/scala#7520 is merged, or can I start right away?
Or can I start from your un-merged branch and push there?

I think it would be a lot easier to wait until that one is merged, I think it might get weird with rebasing and force pushing if that branch needs to be changed, and then breaking what you are working on, but if you don't mind that, then go ahead! It should only be a very small few lines to change in VectorMap anyways.

I think we should keep this separate maybe though, since that PR already deals with a lot already (4 different collections)

[adriaanm]

Given the timing of RC1, starting asap would be good. We're still hoping to have all PRs merged by the end of Jan / mid Feb.

[szeiger]

As a performance optimization this could go into 2.13.1 but if you're planning to work on it you should make sure that it can be implemented in a binary compatible way. It may be necessary to relax access restrictions or add empty overrides in 2.13.0.

[joshlemer]

@szeiger I'm not sure what we should do because according to discussion in scala/scala#7520 and #11369, we may be rethinking entirely how we do hashing.

I don't think I have the expertise to say what hashing strategy we should use but once that decision is made, I or someone else can run with this ticket and scala/scala#7520.

[szeiger]

We're currently using different hash improvement algorithms because the implementations were developed independently. I can't think of a good reason why we should though. If all implementations can use the same algorithm there's no need for it to be reversible anymore.

[joshlemer]

If all implementations can use the same algorithm there's no need for it to be reversible anymore.

@szeiger we would still like it to be reversible so that mutable hashmaps/sets can share hashes when converting to immutable hashmaps/sets, because immutable hashmaps/sets require (as of now) original hashes

[szeiger]

What's the reason for needing both hashes? Why doesn't it always use the improved hash?

[joshlemer]

After doing some digging I found the relevant Issue and PR:

scala/scala-dev#525

scala/scala#6975

In the latter, @retronym states here:

I've just pushed a further commit that explores the idea of using using the cached hash codes to more efficiently compute set hash codes. The change is a bit cumbersome, because we need to base this on the un-improved hashcode (for hash code compatibility with other Map subclasses).

So it is about efficiently producing HashMap[K,V]'s ## in a compatible way to other Map instances for instance ListMap.

[adriaanm]

Looks like this will slip?

[joshlemer]

@adriaanm consider it slipped!