Merge function performing too slowly; what can be done about it?

It appears GroupBy does not suffer from this performance issue, so here is an alternative implementation using it, compared to Merge:

myMerge[list_, fn_] := GroupBy[Catenate @ Normal[list], Keys -> Values, fn]

SeedRandom[1]
ascList = Table[<|a -> Random[], b -> Random[]|>, {20000}];

Merge[ascList, Total]   // RepeatedTiming
myMerge[ascList, Total] // RepeatedTiming

{2.29, <|a -> 9944.07, b -> 9990.23|>}

{0.038, <|a -> 9944.07, b -> 9990.23|>}

---

Further benchmarking

Benchmarking of more methods including one using Carl Woll's GroupByList.

I don't have UpTo in version 10.1 so I wrote these without it.

Needs["GeneralUtilities`"]
GroupByList = ResourceFunction["GroupByList"];

kirmaMerge[fn_][list_] := 
 First@NestWhile[Merge[fn] /@ Partition[#, 64, 64, 1, {}] &, list, Length[#] > 1 &]

wizMerge1[fn_][list_] := GroupBy[Catenate@Normal[list], Keys -> Values, fn]
wizMerge2[fn_][list_] := 
  <| Reap[KeyValueMap[Sow[#2, #] &] /@ list;, _, # -> fn[#2] &][[2]] |>
wizMerge3[fn_][list_] := Fold[Merge[fn]@*List, {}, Partition[list, 64, 64, 1, {}]]
wizMerge4[fn_][list_] := GroupByList[Catenate@Values@list, Catenate@Keys@list, fn]

gen = Association /@ 
    Table[RandomChoice[{"a", "b", "c", "d"}] -> Random[], {#}, {2}] &;
fns = {Merge, kirmaMerge, wizMerge1, wizMerge2, wizMerge3, wizMerge4};

BenchmarkPlot[Through[fns[Total]], gen, 2]

This would seem to really be a question on runtime complexity of Merge, or more specifically in this case Merge[Total]. It seems to have roughly $O(n^2)$, instead of expected mostly-linear complexity.

In the case of Total as the merging operator this problem can be solved by a divide-and-conquer approach working around the quadratic growth of running time:

First@NestWhile[
 Merge[Total] /@ Partition[#, UpTo@64] &,
 listOfAssoc,
 Length[#] > 1 &]

This splits the input to sublists of at most 64 items and performs the merge operator on all of these sublists individually, repeating until only one list item is left (which is the result). This is identical to the original Merge[Total] operation apart from the order of the summation, which is safe in most scenarios which are not sensitive to summation order (a well known floating point number problem).

If all the associations have same set of keys, then Tr and Total are faster than all the methods posted so far.

Wrapping the list of associations with Dataset and using Total is also quite fast.

Using Mr. Wizard's test setup,

SeedRandom[1]
ascList = Table[<|a -> Random[], b -> Random[]|>, {30000}];

Tr[ascList] // RepeatedTiming

{0.014, <|a -> 14984.3, b -> 15053.|>}

Total[ascList] // RepeatedTiming

{0.014, <|a -> 14984.3, b -> 15053.|>}

Dataset[ascList][Total] // Normal // RepeatedTiming

{0.041, <|a -> 14984.3, b -> 15053.|>}

compare to the methods form kirma's and Mr. Wizard's answers:

First @ NestWhile[Merge[Total] /@ Partition[#, UpTo @ 64] &, ascList, 
   Length[#] > 1 &] // RepeatedTiming

{0.054, <|a -> 14984.3, b -> 15053.|>}

myMerge[ascList, Total] // RepeatedTiming

{0.095, <|a -> 14984.3, b -> 15053.|>}

$Version

"11.3.0 for Microsoft Windows (64-bit) (March 7, 2018)"