16
$\begingroup$

When you pack lists there is an overhead therefore packing a list with, say, 2 elements is likely to cost more than you get back in efficiency. Mathematica has default list lengths for which functions creating those lists will pack the list (i.e. if the list length is less than the numbers shown below the list will not be packed):

SystemOptions["CompileOptions"]

{"CompileOptions" -> {"ApplyCompileLength" -> \[Infinity], 
   "ArrayCompileLength" -> 250, "AutoCompileAllowCoercion" -> False, 
   "AutoCompileProtectValues" -> False, "AutomaticCompile" -> False, 
   "BinaryTensorArithmetic" -> False, "CompileAllowCoercion" -> True, 
   "CompileConfirmInitializedVariables" -> True, 
   "CompiledFunctionArgumentCoercionTolerance" -> 2.10721, 
   "CompiledFunctionMaxFailures" -> 3, 
   "CompileDynamicScoping" -> False, 
   "CompileEvaluateConstants" -> True, 
   "CompileOptimizeRegisters" -> False, 
   "CompileReportCoercion" -> False, "CompileReportExternal" -> False,
    "CompileReportFailure" -> False, "CompileValuesLast" -> True, 
   "FoldCompileLength" -> 100, "InternalCompileMessages" -> False, 
   "ListableFunctionCompileLength" -> 250, "MapCompileLength" -> 100, 
   "NestCompileLength" -> 100, "NumericalAllowExternal" -> False, 
   "ProductCompileLength" -> 250, "ReuseTensorRegisters" -> True, 
   "SumCompileLength" -> 250, "SystemCompileOptimizations" -> All, 
   "TableCompileLength" -> 250}}

So, for example, if you make a list using Table

Developer`PackedArrayQ[Table[i, {i, 1, 249}]]
False

Developer`PackedArrayQ[Table[i, {i, 1, 251}]]
True

I am assuming that if you plotted the time to make uncompiled lists using Table, vs making compiled lists, the lines would intersect at ~250, beyond which packed lists become more efficient. Is that a correct interpetation of what the autocompilation length represents?

I would expect that the optimal lengths for compilation (incl. packing) vary on system to system, therefore I want to know the best way to construct a set of tests to test that proposition, and to determine the optimal list length for packing for the functions listed above.

Edit

For clarity, as per Albert's comments, there are cases when the evaluations taking place prevent compilation so these discussions are redundant, i.e. compilation is prevented regardless of the default settings. But I am curious about the optimal list lengths in cases where compilation occurs.

$\endgroup$
4
  • $\begingroup$ BTW maybe someone from Wolfram could comment about why the Apply compile length is set to infinity. $\endgroup$ Jan 19, 2012 at 23:55
  • $\begingroup$ Apply replaces the head of an expr. It needs to unpack at some stage. $\endgroup$
    – user21
    Jan 20, 2012 at 7:27
  • $\begingroup$ @ruebenko, of course! thanks :) Having said that, what is the point of having an option for Apply compile length? $\endgroup$ Jan 20, 2012 at 8:38
  • $\begingroup$ I never tried this, but I think the computation which in the end computes with what the head is replaced may be expensive, in this case then you might get a benefit from a compiled function; but I think this is rare. $\endgroup$
    – user21
    Jan 20, 2012 at 8:43

2 Answers 2

10
$\begingroup$

You should note that you are actually controlling the compiling and the array packing is just coupled to that and AFAIK can't be controlled independently (anymore). You can verify this with e.g. this uncompilable table body which generates the same result:

Developer`PackedArrayQ[Table[i /. x_ /; x > 300 :> RandomReal[], {i, 1, 251}]]
False

I would expect that the compiling dominates over the array packing concerning runtime overhead and thus that the dependence on the actual body of the table is much stronger than that of the system you are on. If that expectation isn't completely wrong an optimization with regards to the system might be rather useless. Here are examples to demonstrate this:

SetSystemOptions["CompileOptions" -> {"TableCompileLength" -> \[Infinity]}];
uncompiled = Map[
   Function[x, Timing[Do[With[{y = RandomReal[]},
         Table[
          Abs[i - y]/(Exp@Sin[y*i]*i^2 + 1 - 0.5*(i + y)^23), {i, x}]
         ], {1000}];][[1]]],
   Range[1, 50]
   ];

SetSystemOptions["CompileOptions" -> {"TableCompileLength" -> 1}];
compiled = Map[
   Function[x, Timing[Do[With[{y = RandomReal[]},
          Table[
           Abs[i - y]/(Exp@Sin[y*i]*i^2 + 1 - 0.5*(i + y)^23), {i, x}]
          ], {1000}];][[1]]],
    Range[1, 50]
   ];

ListLinePlot[{compiled, uncompiled}]

Mathematica graphics

SetSystemOptions["CompileOptions" -> {"TableCompileLength" -> \[Infinity]}];
uncompiled = Map[
    Function[x, Timing[Do[
        With[{y = RandomReal[]}, Table[i + y, {i, x}]],
        {5000}];][[1]]],
   Range[60, 180]
   ];

SetSystemOptions["CompileOptions" -> {"TableCompileLength" -> 1}];
compiled = Map[
   Function[x, Timing[Do[
        With[{y = RandomReal[]}, Table[i + y, {i, x}]],
        {5000}];][[1]]],
   Range[60, 180]
  ];

ListLinePlot[{compiled, uncompiled}]

Mathematica graphics

If you compare the two plots you will see that for these two cases the optimal compile length is very different.

To get most out of your system, you would need to adopt these settings to the problem at hand (and of course change them for another).

This of course assumes that you are talking about runtime efficiency, although array packing is just as well (or even in the first place) about memory efficiency.

$\endgroup$
6
  • $\begingroup$ I'll do an edit with some additional information/clarification. $\endgroup$ Jan 19, 2012 at 23:27
  • $\begingroup$ I have some thoughts on an answer but firstly I am not sure I am understanding what is happening correctly and even if I am my solution to measure this is probably not the best way to do it, so i am interested in what others think. $\endgroup$ Jan 19, 2012 at 23:40
  • $\begingroup$ Seeing your clarification I tried to give examples for two extreme cases to make clearer why I think it is the problem (body) more than the system that the breakeven depends on. Unfortunately it turned out that the breakeven is usually at such small runtimes that measuring the runtimes becomes unreliable. It's late now, probably I'll find an example when I'm less tired... $\endgroup$ Jan 20, 2012 at 0:20
  • $\begingroup$ BTW Albert in your example the list is not being compiled. ReplaceAll seems to prevent compilation -- so you are correct about the body of the table being important. My question relates only to cases when compilation occurs because when it doesn't compile then it doesn't really matter what the default settings are. $\endgroup$ Jan 20, 2012 at 3:01
  • $\begingroup$ @MikeHoneychurch: it was the purpose of the first example to not be compiled. I have now added two more examples which do compile and show what I meant to say in the second paragraph, but I have seen your own answer which shows the dependence on the tables boy much more detailed. $\endgroup$ Jan 20, 2012 at 10:49
5
$\begingroup$

Here is what I am doing using Table as an example but the same applies for Map, Fold, etc. To examine Table I map numbers onto it so to avoid any autocompilation issues with Map overlapping I set

SetSystemOptions["CompileOptions" -> "MapCompileLength" -> \[Infinity]];

First of all have a look at memory:

tmp1 = (SetSystemOptions["CompileOptions" -> "TableCompileLength" -> #];
     ByteCount[Table[i, {i, 1, #}]]) & /@ Range[1, 300];

SetSystemOptions["CompileOptions" -> "TableCompileLength" -> 250];
tmp2 = ByteCount[Table[i, {i, 1, #}]] & /@ Range[1, 300];

ListLinePlot[{tmp1, tmp2}]

enter image description here

So that looks as you'd expect. Now check timings:

tmp3 = ((SetSystemOptions["CompileOptions" -> "TableCompileLength" -> #1]; 
      Timing[Table[i, {i, 1, #1}];]) &) /@ Range[1, 500];

SetSystemOptions["CompileOptions" -> "TableCompileLength" -> \[Infinity]];
tmp4 = (Timing[Table[i, {i, 1, #1}];] &) /@ Range[1, 500];

ListLinePlot[{tmp3[[All, 1]], tmp4[[All, 1]]}]

enter image description here

On my system -- which fortuitously is a 5 year old slow computer -- these lines intersect somewhere between 280 and 290. I had considered adding a Do loop but a problem (for this analysis) arises:

tmp5 = (SetSystemOptions["CompileOptions" -> "TableCompileLength" -> #];
     Timing[Do[Table[i, {i, 1, #}];, {10}]]) & /@ Range[1, 500];

SetSystemOptions["CompileOptions" -> "TableCompileLength" -> \[Infinity]];
tmp6 = Timing[Do[Table[i, {i, 1, #}];, {10}]] & /@ Range[1, 500];

ListLinePlot[{tmp5[[All, 1]], tmp6[[All, 1]]}]

enter image description here

So looping 10 times reduces the point of intersection by ~10. I couldn't figure out a way around this so have not used Do.

The table is creating a list integers, i.e. returning the is. You would normally use Range for something like this. So the next test is to compare the timings when you do something with the is.

tmp7 = (SetSystemOptions["CompileOptions" -> "TableCompileLength" -> #];
     Timing[Table[i // N, {i, 1, #}];]) & /@ Range[1, 500];

SetSystemOptions["CompileOptions" -> "TableCompileLength" -> \[Infinity]];
tmp8 = Timing[Table[i // N, {i, 1, #}];] & /@ Range[1, 500];

ListLinePlot[{tmp7[[All, 1]], tmp8[[All, 1]]}]

enter image description here

We see now that the optimal length seems to be just over 120. After doing some other calculation with i in other tests, the "optimal" length seemed to vary from 50 through to 120. So it seems that there is no "exact" list length that is optimal, it is dependent on what is being done to the table iterator, however, on my system at least, the default autocompilation length can probably be set much lower for Table. (ditto Map etc.)

Some operations prevent compilation, e.g. Albert's example of a rule replacement:

tmp9 = ((SetSystemOptions["CompileOptions" -> "TableCompileLength" -> #1]; 
      Timing[Table[i /. x_ -> 1, {i, 1, #1}];]) &) /@ Range[1, 500];

SetSystemOptions["CompileOptions" -> "TableCompileLength" -> \[Infinity]];
tmp10 = (Timing[Table[i /. x_ -> 1, {i, 1, #1}];] &) /@ Range[1, 500];

ListLinePlot[{tmp9[[All, 1]], tmp10[[All, 1]]}]

enter image description here

But by definition the default value for the list lengths only has meaning if compilation takes place.

So this is one way of determining what value to use for list lengths for autocompilations (that is all based on what I think the autocompilation number represents). There may be other ways of doing this.

$\endgroup$
3
  • $\begingroup$ I wanted to mention that I think that the strange results you see when using the Do-loop are probably because of the system cache. Using a random number within your calculation avoids that. An alternative would be to use ClearSystemCache, but that might well be expensive enough to spoil the time measuring. I think that this is relevant because without such repetitions you won't be able to get reasonable results on faster machines. $\endgroup$ Jan 21, 2012 at 17:54
  • $\begingroup$ @AlbertRetey on my system using a random number makes no difference, e.g. Table[i+RandomReal[], {i, 1, #}] instead of the example for Do above made no difference. So I guess this test is limited to slower machines. I wonder how Wolfram determines the defaults settings -- possibly they did it just once many years ago? $\endgroup$ Jan 21, 2012 at 22:30
  • $\begingroup$ I just have updated my examples again, I found that there was still something unexpected going on, probably because the compiled code had to step back to evaluate the non localized y. Anyway I think the examples now do what they are supposed to do. If you replace the RandomReal[] with just a constant in the second one you will see how that messes up the measuring. I might be wrong with my guess that this has something to do with the system cache, but I have seen it often to ruin time measures so that it stays my main suspect. $\endgroup$ Jan 21, 2012 at 23:48

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.