0
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ You haven't given enough details, i.e. a working example of the problem, to enable anyone to help. $\endgroup$
    – Ymareth
    Jun 4, 2015 at 10:30
  • $\begingroup$ @Ymareth I added more information. My code is too long to include everything - especially alternativeSum $\endgroup$
    – ThunderBiggi
    Jun 4, 2015 at 11:10
  • $\begingroup$ 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. $\endgroup$
    – Mr.Wizard
    Jun 4, 2015 at 15:05
  • 1
    $\begingroup$ @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 $\endgroup$
    – ThunderBiggi
    Jun 6, 2015 at 12:09

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – ThunderBiggi
    Jun 7, 2015 at 10:45
  • $\begingroup$ @user1482714, Rather than assuming, you should check the documentation for SparseArray, which shows that you can create it using a list of rules. $\endgroup$
    – Simon Rochester
    Jun 7, 2015 at 18:24
  • $\begingroup$ 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. $\endgroup$
    – ThunderBiggi
    Jun 7, 2015 at 19:33
  • $\begingroup$ @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. $\endgroup$
    – Simon Rochester
    Jun 8, 2015 at 2:57
  • $\begingroup$ 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. $\endgroup$
    – ThunderBiggi
    Jun 12, 2015 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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