Enhance the performance of map merges

Question

It would be nice if merge used transients.

Patch
- clj-1458-7.patch

Approach
Migrate c.c/merge later in core after transients & reduce. Leave older version as merge1 for use in cases the precede the newer definition. Make APersistentMap/conj & ATransientMap/cons aware of IKVReduce.

The attached patch preserves two existing behaviors of merge
- metadata propagation
- the right hand side of the merges can be a Map.Entry, an IPersistentVector where size=2, and regular maps.

Screened by:

Answer 1

Comment made by: jawolfe

I will take a crack at a patch today.

Answer 2

Comment made by: jawolfe

This patch (transient-merge.diff) makes merge, merge-with, and zipmap (since it was right there and could obviously benefit from transients as well) use transients.

Three potential issues:
- I had to move the functions, since they depend on transient and friends. I assume this is preferable to a forward declaration. This was the best place I could find, but happy to move them elsewhere.
- I added multiple arities, to avoid potential performance cost of transient-ing a single argument. Happy to undo this if desired.
- I had to slightly alter the logic in merge-with, since transient maps don't support contains? (or find).

Answer 3

Comment made by: michalmarczyk

I posted a separate ticket for {{zipmap}}, with patch, on 30/May/12: CLJ-1005.

Answer 4

Comment made by: jawolfe

Ah, sorry if I overstepped then. Happy to remove that change from this patch then if that will simplify things -- just let me know.

Answer 5

Comment made by: gshayban

alternate approach attached delaying merge until after protocols load, and then using transducers.

Answer 6

Comment made by: michaelblume

Looks like you're doing (get m k) twice -- shouldn't that be thrown in a local?

Answer 7

Comment made by: michaelblume

um, put, in a local, I mean, 'throw' was a bad choice of word.

Answer 8

Comment made by: gshayban

Yeah there's that -- won't be using get anyways after CLJ-700 gets committed.

We should add performance tests too. merging two maps, three, many maps, also varying the sizes of the maps, and for merge-with, varying the % of collisions.

Need to go back to the (some identity) logic, otherwise metadata is propagated from maps other than the first provided. I'll fix later.

Answer 9

Comment made by: michaelblume

I don't know if this is supposed to be allowed, but this breaks

(merge {} (link: :foo 'bar))

which is used in the wild by compojure-api

Answer 10

Comment made by: michaelblume

https://github.com/metosin/compojure-api/blob/0.16.6/src/compojure/api/meta.clj#L198

Answer 11

Comment made by: michaelblume

Ghadi, contains? uses get under the covers, so it's still two gets, right? It seems like it'd be more performant to stick with the ::none trick.

Answer 12

Comment made by: bronsa

This calls for if-let + find.

Answer 13

Comment made by: gshayban

new patch addressing concerns so far

Answer 14

Comment made by: gshayban

CLJ-1458-transient-merge3.patch removes silly inlining macro, uses singleton fns instead.

Answer 15

Comment made by: michaelblume

Nice =)

This should come with tests. If we want to preserve the ability to merge with a MapEntry, we should test it. This isn't so much a weakness of the patch as of the existing tests. I see merge and merge-with being used a few times in the test suite, but I see no test whose purpose is to test their behavior.