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: michaelblume

Extremely simple merge test, we need more than this, but this is a start

Answer 2

Comment made by: alexmiller

clj-1458-4.patch refreshed to apply to master, no changes.

Answer 3

Comment made by: gshayban

I'd like to reevaluate the scope of this ticket. Can we address 'merge' only and defer 'merge-with'? It's by far the more common function. I've attached a new simplified patch.

Answer 4

Comment made by: gshayban

CLJ-1458-6.patch is yet another cleaner approach

Answer 5

Comment made by: alexmiller

Can you update the ticket approach section to discuss the APersistentMap.cons / ASSOC changes. Also, can you add a before / after perf test for one or more common cases?

Answer 6

Comment made by: michaelblume

Updated patch to handle use of merge in core_print before it's defined in core

Answer 7

Comment made by: gshayban

If anyone wants to take stewardship of this, go ahead. I had trouble getting consistent performance improvements on this. Obviously this needs fresh benchmarks.

Answer 8

Comment made by: alexmiller

Yes, this needs a benchmark showing demonstrable improvement. The whole goal here is improved perf - if we can't prove it's consistently faster, then there is no point in even reviewing it.

Answer 9

Comment made by: gshayban

This ticket needs help. Step 0 is writing a benchmark harness that exercises maps of various sizes, and the various polymorphic arguments below.

After a benchmark harness, implementation code needs to preserve this behavior:
- If the first argument is not nil, its metadata propagates to the result.
- The arguments can be a Map.Entry, an IPersistentVector where size=2, and regular maps.
- When passed a non-map as the first argument, result is undefined.

Answer 10

Reference: https://clojure.atlassian.net/browse/CLJ-1458 (reported by alex+import)