Is it possible to avoid unpacking when merging Association?

Question

For example, if we have

assoc = 
  AssociationThread[{1, 2, 3} -> RandomReal[1., {3, 10}]];

and

Developer`PackedArrayQ/@ assoc

gives

<|1 -> True, 2 -> True, 3 -> True|>

so each Value is packed array.

Now, I want to Merge several Assocation like this. Then I checked packedness,

Developer`PackedArrayQ /@ Merge[{assoc, assoc}, Flatten]

it gives

<|1 -> False, 2 -> False, 3 -> False|>

It unpacks, even though Flatten should not unpack list.

So is it possible to avoid this unpacking in Merge?

Answer 1

One can use TracePrint to see how Flatten is being used by Merge:

TracePrint[
    Merge[{assoc,assoc}, Flatten],
    _Flatten,
    TraceAction->Print@*Developer`PackedArrayForm
];

Flatten[{PackedArray[Real,<10>],PackedArray[Real,<10>]}]

Flatten[{PackedArray[Real,<10>],PackedArray[Real,<10>]}]

Flatten[{PackedArray[Real,<10>],PackedArray[Real,<10>]}]

Notice how Merge builds a list of two packed arrays, and then flattens them. This is why the the arrays become unpacked. To workaround this, you can either convert the list of two packed arrays into a packed array first:

Developer`PackedArrayQ /@ Merge[{assoc, assoc}, Flatten @* Developer`ToPackedArray]

<|1 -> True, 2 -> True, 3 -> True|>

Or you can use Join with Apply (as in Henrik's answer, but using slot free syntax):

Developer`PackedArrayQ /@ Merge[{assoc, assoc}, Apply[Join]]

<|1 -> True, 2 -> True, 3 -> True|>

Answer 2

Instead of using Merge, you can also use AssociationTranspose which is often much faster than Merge and doesn't unpack:

m1 = Merge[{assoc, assoc}, Flatten];
m2 = Flatten /@ GeneralUtilities`AssociationTranspose[{assoc, assoc}];
m1 === m2
Developer`PackedArrayQ /@ m1
Developer`PackedArrayQ /@ m2

True

<|1 -> False, 2 -> False, 3 -> False|>

<|1 -> True, 2 -> True, 3 -> True|>

Frankly, AssociationTranspose + Map is pretty much just superior to Merge like 99% of the time.

Answer 3

Join tries to pack whenever it is possible:

Developer`PackedArrayQ /@ Merge[{assoc, assoc}, Join @@ # &]

<|1 -> True, 2 -> True, 3 -> True|>

One might expect that Catenate should also work, but it does not.

Answer 4

Here goes a self answer.

To be honest, I almost decide to delete my post right after I posted. Because I naively thought unpacking may be unavoidable. Luckily, I keep this post, and this problem becomes more interesting. Thank you so much to @Carl Woll, @Sjoerd Smit and @Henrik Schumacher for providing great answers. Learned a lot.

Now, I summarize and add some benchmarks to other answers.

First, two related post on flatten or join pure list(not association)

https://mathematica.stackexchange.com/a/75592/4742 https://mathematica.stackexchange.com/a/184578/4742

these two post suggest us, we need to differentiate three cases:

1. completely packed array
2. completely unpacked array
3. sublist packed array(unpacked at first level)

Briefly,

1. for completely packed array, Flatten is much faster to Apply[Join], because Apply unpacked first level.
2. for completely unpacked array, 'Apply[Join]` is faster, but timing is much closer than completely packed.
3. for sublist packed array, Apply[Join] is much faster to Flatten

Before benchmark, we need routines to generated three kind of array

ClearAll[genCompletelyPacked];
genCompletelyPacked[sublistLen_, totalLen_] := ConstantArray[Range[sublistLen], totalLen];
ClearAll[genCompletelyUnpacked];
genCompletelyUnpacked[sublistLen_, totalLen_] := 
  Developer`FromPackedArray@genCompletelyPacked[sublistLen, totalLen];
ClearAll[genSublistPacked];
genSublistPacked[sublistLen_, totalLen_] := 
  Developer`ToPackedArray /@ genCompletelyUnpacked[sublistLen, totalLen];

and define below function (I add Catenate suggested by Mr.Wizard in other post)

f = Flatten[#, 1] &;
g = Join @@ # &;
h = Catenate[#] &;
Needs["GeneralUtilities`"];

Below for every case, I give two benchmark: one for small sublist, the other for long sublist.

complete packed array

BenchmarkPlot[{f, g, h}, genCompletelyPacked[10, #] &, 
 PowerRange[10, 10^3, 2], "IncludeFits" -> True]

BenchmarkPlot[{f, g, h}, genCompletelyPacked[1000, #] &, 
 PowerRange[10, 10^3, 2], "IncludeFits" -> True]

The jumping maybe due to memory issue as suggested by Michael E2.

completely unpacked array

BenchmarkPlot[{f, g, h}, genCompletelyUnpacked[10, #] &, 
 PowerRange[10, 10^3, 2], "IncludeFits" -> True]

BenchmarkPlot[{f, g, h}, genCompletelyUnpacked[1000, #] &, 
 PowerRange[10, 10^3, 2], "IncludeFits" -> True]

sublist packed array

BenchmarkPlot[{f, g, h}, genSublistPacked[10, #] &, 
 PowerRange[10, 10^3, 2], "IncludeFits" -> True]

BenchmarkPlot[{f, g, h}, genSublistPacked[1000, #] &, 
 PowerRange[10, 10^3, 2], "IncludeFits" -> True]

Now, we return to Association case:

As point out by Carl Woll, Merge simply put list together, and resulting sublist packed case that is unpacked at the first level(In this sense, unpacking is unavoidable in Merge, because first level is unpacked). So we can envisage, Apply[Join] will be much faster, however, we will see things getting a little different.

Sjoerd Smit suggested quite novel GeneralUtilitiesAssociationTransposewhich is even better, because it doesn't unpack at all, and we can give much hopeGeneralUtilitiesAssociationTranspose will be much faster. However, we will see this is not always the case.

First, we define routines to generate list of Association with values are packed list.

ClearAll[genAssoc];
genAssoc[len_, n_] := 
  Table[AssociationThread[{1, 2, 3} -> RandomReal[1., {3, len}]], n];

and several functions

f1 = Merge[#, Flatten] &;
f2 = Merge[#, Apply[Join]] &;
f3 = Merge[#, Catenate] &;
f4 = Flatten /@ GeneralUtilities`AssociationTranspose[#] &;

BenchmarkPlot[{f1, f2, f3, f4}, genAssoc[10, #] &, 
 PowerRange[10, 10^4, 2], "IncludeFits" -> True]

BenchmarkPlot[{f1, f2, f3, f4}, genAssoc[1000, #] &, 
 PowerRange[10, 10^4, 2], "IncludeFits" -> True]

you can clearly see some peculiarity as I pointed out previous. For example,

1. AssociationTranspose is only good for small sublist.
2. For small sublist, Flatten becomes comparable to Apply[Join] when number of association becomes large.

I have no answer, waiting other to explain.