How to efficiently write into PackedArrays that are stored in Associations?

Question

Using Association to generate complicated data types is very comfortable, in particular if one uses those tricks from How to make use of Associations?. However, I observed that writing into deeper levels of associations can be quite slow in certain circumstance. Here is a minimal example:

m = 1000;
n = 30000;
A = RandomReal[{-1, 1}, {m, n}];
y = RandomReal[{-1, 1}, {n}];
u = RandomReal[{-1, 1}, {m}];
i = RandomInteger[{1, m}];
a = Association["Data" -> A]; 
a[["Data", i]] = y; // AbsoluteTiming // First 
a[["Data", i + 1]] = y + 1.; // AbsoluteTiming // First

0.12598

0.141002

This is inacceptibly slow compared to a direct write into an array:

B = A;
B[[i]] = y; // AbsoluteTiming // First 
B[[i + 1]] = y + 1.; // AbsoluteTiming // First 

0.12496

0.000159

The first timing seems to be dominated by the cost of copying the values of A to B. This is executed with delay due to lazy copy. It's understood that this cost cannot be avoided completely. But as we can see, the second write operation is much faster.

I would have expected that a PackedArray is stored within an Association internally as a pointer so that all but the first modifications do not require copying. When done in some compiled library, this would not effect immutability of Association.

Seemingly, the implementation of deeper write-indexing was done simpler than that; the most naive way coming to my mind being:

(B = a[["Data"]]; B[[i]] = y; b = Association["Data" -> B]); // AbsoluteTiming // First
(B = b[["Data"]]; B[[i + 1]] = y + 1.; c = Association["Data" -> B]); // AbsoluteTiming // First

0.13791

0.143413

And this is not so bad compared to Mathematica's performance.

So, who has ideas to improve on this? (Really, I would pretty much love to use large PackedArrays nested in Associations...)

Answer 1

This may serve as a work-around, but it feels a bit too complicated.

Based on what I learnt from Leonid Shifrin, it is possible to implement a pointer type directly in Mathematica by using a symbol with attribute Temporary as it is produced by Module. Backed up with a write operation, this could look like this:

ClearAll[arraypt]
SetAttributes[arraypt, HoldAll]
WriteTo[arraypt[$array_], args___][vals_] := $array[[args]] = N[vals];

We create an Association containing only the pointer:

a = Association["Data" -> Module[{$array = A}, arraypt[$array]]];

Now, we can write into the "stored" array $array this way:

apt = a[[1]];
WriteTo[apt, i][y]; // AbsoluteTiming // First
a[["Data", 1]][[i]] == y
WriteTo[apt, i + 1][y + 1.]; // AbsoluteTiming // First
a[["Data", 1]][[i + 1]] == y + 1.

leading to the following outputs

0.132042

True

0.000129

True

As expected, we see the copy cost in the first timing. But the second timing is comparable to a direct write to a PackedArray.

Alas, this solutions is by far not as elegant as

a[["Data", i]] = y;

would be - if it worked.