8
$\begingroup$

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...)

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ it is not only complicated, you also loose immutability. This might not be a problem for many usecases so I think your workaround has its place, but remember that every piece of code using one of these associations would need to be aware of it containing such pointers... $\endgroup$ – Albert Retey May 22 '18 at 9:32
  • $\begingroup$ Loosing immutability is the point of in-place modifications. The use case would be an object-type whose properties (data, options, caches etc.) are stored within a nested association. Think about a type like Graph but with all properties visible to the user and not behind this Property-mess. Think about minimal invasive methods like GraphComputation`VertexAddTo and GraphComputation`EdgeAddTo. For example, I don't need the cache of an object to be immutible and it would be even harmful performancewise. By the way, standard syntax a[["Data", i]] = y does violate immutability, too. $\endgroup$ – Henrik Schumacher May 22 '18 at 10:40
  • $\begingroup$ There is a big difference, as you can see from a = <|"Data" -> {1, 2, 3}|>; b = a; b[["Data", 2]] = 0;. If you look now at a and b you find that a is still the same but b has changed. This is what I was addressing with "immutability" (cf. the definition in Leonids answer to the question you are refering to). This "copy on write" behavior is very different from what you would have with your implementation of pointers. And yes, there are many use cases where that is not a problem or even favorable, but you should understand and be aware of the difference to be safe from surprises. $\endgroup$ – Albert Retey May 22 '18 at 13:03
  • $\begingroup$ I see what you mean. Of course a class of such objects would need a deep copy instruction (and optionally overload Set as follows object /: Set[a_, b_object] := DeepCopy[a, b]). But I am with you that a[["Data", i]] = y; would be much cleaner and would lead to less headaches--if only the in-place modification would not be emulated in such a poor way. $\endgroup$ – Henrik Schumacher May 22 '18 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.