# ParallelTable slower than Table in the presence of an Association?

So after testing some things I am completely reformulating my problem. First an example

as = Association[{2 -> 7, 3 -> 8, 4 -> 9, 5 -> 10, 6 -> 11}]
<|2 -> 7, 3 -> 8, 4 -> 9, 5 -> 10, 6 -> 11|>
calcF[x_, y_, Max_] := Sum[Lookup[as, x + y, 0], {i, 1, Max}]
doo[Max_] := Table[calcF[x, y, Max], {x, 1, 5}, {y, 1, 5}]

AbsoluteTiming[doo[50000]]
{0.539171, {{350000, 400000, 450000, 500000, 550000}, {400000, 450000,
500000, 550000, 0}, {450000, 500000, 550000, 0, 0}, {500000,
550000, 0, 0, 0}, {550000, 0, 0, 0, 0}}}

doo[Max_] := ParallelTable[calcF[x, y, Max], {x, 1, 5}, {y, 1, 5}]

AbsoluteTiming[doo[50000]]
{2.45135, {{350000, 400000, 450000, 500000, 550000}, {400000, 450000,
500000, 550000, 0}, {450000, 500000, 550000, 0, 0}, {500000,
550000, 0, 0, 0}, {550000, 0, 0, 0, 0}}}

ls = {0, 7, 8, 9, 10, 11, 0, 0, 0, 0}
{0, 7, 8, 9, 10, 11, 0, 0, 0, 0}
malcF[x_, y_, Max_] := Sum[ls[[x + y]], {i, 1, Max}]
foo[Max_] := Table[malcF[x, y, Max], {x, 1, 5}, {y, 1, 5}]

AbsoluteTiming[foo[50000]]
{0.07679, {{350000, 400000, 450000, 500000, 550000}, {400000, 450000,
500000, 550000, 0}, {450000, 500000, 550000, 0, 0}, {500000,
550000, 0, 0, 0}, {550000, 0, 0, 0, 0}}}

foo[Max_] := ParallelTable[malcF[x, y, Max], {x, 1, 5}, {y, 1, 5}]

AbsoluteTiming[foo[50000]]
{0.032803, {{350000, 400000, 450000, 500000, 550000}, {400000, 450000,
500000, 550000, 0}, {450000, 500000, 550000, 0, 0}, {500000,
550000, 0, 0, 0}, {550000, 0, 0, 0, 0}}}


So, from this it seems like ParallelTable has some issue with an Association, as it performs slower than Table. Is this behaviour expected? Is it a bug and can I get over it somehow?

Forgot to mention, in case it matters - my laptop has 4 cores that are hyper-threaded, but I have stuck with the default Mathematica setting to launch 4 kernels for parallel computations.

The reason I want to use an Association is because in my actual calculation ls will be a massive 5-dimensional Table with hundreds of millions of elements (thus taking all my RAM), but 95% of them will be zeroes. Therefore, I want to replace it with an Association that will have only non-zero terms and will thus be much smaller, hence allowing me to perform the calculation.

• You haven't given enough details, i.e. a working example of the problem, to enable anyone to help. – Ymareth Jun 4 '15 at 10:30
• @Ymareth I added more information. My code is too long to include everything - especially alternativeSum – ThunderBiggi Jun 4 '15 at 11:10
• User, have you attempted to create a minimum working example? If Association doesn't work with ParallelTable generally it should be possible to demonstrate it in only a few lines of code. If not there may be a contributing factor that also needs to be discovered. – Mr.Wizard Jun 4 '15 at 15:05
• @Mr.Wizard I created a minimal example and it seems to be working well, so the problem is apparently in my code. I am in the process of updating my question, but it will take a lot of time – ThunderBiggi Jun 6 '15 at 12:09

I don't have a complete explanation, but some observations that may be helpful.

First, this behavior doesn't specifically have to do with Association, since you see a similar slow-down when parallelizing using a plain old list of rules:

rules = {2 -> 7, 3 -> 8, 4 -> 9, 5 -> 10, 6 -> 11, _ -> 0};
calcF[x_, y_, Max_] := Sum[x + y /. rules, {i, 1, Max}]
First@AbsoluteTiming[Table[calcF[x, y, 50000], {x, 1, 5}, {y, 1, 5}]]
First@AbsoluteTiming[ParallelTable[calcF[x, y, 50000], {x, 1, 5}, {y, 1, 5}]]
(* 1.00533 *)
(* 1.91048 *)


On the other hand, it does seem to have to do with the many repeated replacements or lookups. If instead of using Sum, we make a list of the entries to be replaced, do one replacement operation, and then Total the result, there is a parallel speed-up. For example, using Association:

as = Association[{2 -> 7, 3 -> 8, 4 -> 9, 5 -> 10, 6 -> 11}];
calcF[x_, y_, Max_] := Total[Lookup[as, Table[x + y, {i, 1, Max}], 0]]
First@AbsoluteTiming[Table[calcF[x, y, 50000], {x, 1, 5}, {y, 1, 5}]]
First@AbsoluteTiming[ParallelTable[calcF[x, y, 50000], {x, 1, 5}, {y, 1, 5}]]
(* 0.195367 *)
(* 0.084041 *)


I'm no expert, but I might guess that when doing many repeated lookups, most of the time is spent retrieving values from memory, so multiple cores aren't going to help.

Also, to directly translate your original matrix-based method to the sparse case you can use SparseArray, which is designed for exactly this purpose:

spls = SparseArray[{0, 7, 8, 9, 10, 11, 0, 0, 0, 0}];
malcF[x_, y_, Max_] := Sum[spls[[x + y]], {i, 1, Max}]
First@AbsoluteTiming[Table[malcF[x, y, 50000], {x, 1, 5}, {y, 1, 5}]]
First@AbsoluteTiming[ParallelTable[malcF[x, y, 50000], {x, 1, 5}, {y, 1, 5}]]
(* 1.14774 *)
(* 0.501875 *)


(Note that SparseArray can also be entered as a list of rules, like Association.) This is slower than the Association method, but if we again make a table and do all of the lookups at once, we get the fastest result of all:

malcF[x_, y_, Max_] := Total[spls[[Table[x + y, {i, 1, Max}]]]]
First@AbsoluteTiming[Table[malcF[x, y, 50000], {x, 1, 5}, {y, 1, 5}]]
First@AbsoluteTiming[ParallelTable[malcF[x, y, 50000], {x, 1, 5}, {y, 1, 5}]]
(* 0.064648 *)
(* 0.028374 *)


Vectorizing operations using Listable functions in this way is often the best method of obtaining speedups in Mathematica.

• I am currently trying to implement your alternative method for the Association (one replacement on a Table, then Total) in my code. I assume that I need to have the matrix generated, in order to apply SparseArray. It is the generation of the massive 5D-table that I am trying to avoid, as I need to increase the size further and it just freezes my laptop from one point onwards. I can create the Association without the need of first creating the massive array, using this question. – ThunderBiggi Jun 7 '15 at 10:45
• @user1482714, Rather than assuming, you should check the documentation for SparseArray, which shows that you can create it using a list of rules. – Simon Rochester Jun 7 '15 at 18:24
• Yea, sorry, I found that after commenting. Unfortunatelly, SparseArray doesn't seem to be an option for me, as I need the unique keys in the Association and they were created with Cantor Pairing function, so some of them have a value of a few millions, thus the SparseArray is huge as well. – ThunderBiggi Jun 7 '15 at 19:33
• @user1482714, Of course, use whatever method works best for you, but actually SparseArray should use much less memory than the equivalent Association, since it can use the fact that the keys are all integers and the values are all numeric (assuming that they are) to store the data very efficiently ("Packed array", see this post). As far as I can tell, Association can not do this. – Simon Rochester Jun 8 '15 at 2:57
• I tried with a SparseArray as well - the dimensions/length (it is 1D) is extremely huge and this apparently seems to create some kind of a problem, as whenever I try to use it for some actual calculation (creating it is not a problem and checking its Dimensions), Mathematica just clears all variables and everything and nothing happens. – ThunderBiggi Jun 12 '15 at 8:16