Considerations when determining efficiency of Mathematica code

Question

I have two segments of code that do the same thing and I want to determine the which is more efficient.

What are the considerations when determining efficiency of Mathematica code?

• Correctness/Equality of code segments
• AbsoluteTiming vs Timing ... Why?
• Clearing the cache
• Memory footprint (speed vs size) ... Any suggestions on how to measure this?
• More?

Any useful packages out there to assist in this?

---

Hypothetical Code Segment 1

numbers = {}; For[i = 0, i < 100, i++, AppendTo[numbers, i]]; numbers

---

Hypothetical Code Segment 2

Range[0, 99]

---

Testing Code

(* Test Equality *)
Print["Equality: ", 
    numbers = {}; For[i = 0, i < 100, i++, AppendTo[numbers, i]]; numbers == 
    Range[0, 99]]

(* Timing Comparison *)
iterations = 10000;

times = Map[{
      AbsoluteTiming[
       numbers = {}; For[i = 0, i < 100, i++, AppendTo[numbers, i]]; numbers
       ][[1]],
     AbsoluteTiming[
       Range[0, 99]
       ][[1]]
     } &, Range[1, iterations]];
{times1, times2}  = Transpose[times];

PrintStats[times_] :=

 Print["Sum: ", Fold[Plus, 0., times], "  Min: ", Min[times], 
  "  Max: ", Max[times], "  Mean: ", Mean[times], "  StdDev: ", 
  StandardDeviation[times]]

PrintStats[times1];
ListPlot[times1, PlotRange -> All]
Histogram[times1]

PrintStats[times2];
ListPlot[times2, PlotRange -> All]
Histogram[times2]

Results:

Answer 1

First off, Timing isn't as accurate as AbsoluteTiming because it has a tendency to ignore various things. Here is a paticularly telling example. Keep in mind that neither will keep track of rendering time or formatting of output, this is purely time spent computing in the kernel.

AbsoluteTiming[x = Accumulate[Range[10^6]]; Pause[x[[1]]]; resA = x + 3;]

==> {1.045213, Null}

Timing[x = Accumulate[Range[10^6]]; Pause[x[[1]]]; resB = x + 3;]

==> {0.031200, Null}

These are identical calculations but Timing ignores Pause so it is way off.

Now lets set up a toy example. Your tests for timings are what I would typically do first when looking for efficiency.

f[x_Integer?Positive] := Accumulate[Range[x]]

g[x_Integer?Positive] := 
   Block[{result = Array[0, x]},
    result[[1]] = 1;
    For[i = 2, i <= x, i++, result[[i]] = result[[i - 1]] + i];
    result
   ]

The AbsoluteTiming is quite different for these two approaches. Clearly the built in function is preferable in this case.

AbsoluteTiming[resf = f[10^6];]

==> {0.015600, Null}

AbsoluteTiming[resg = g[10^6];]

==> {3.432044, Null}

And of course, we should test that these produce equivalent results..

resf == resg

==> True

Now I will mention that there are times when Equal will return False. This may be acceptable in some situations if say we are only really interested in very low precision, ball-park results.

As for memory consumption, I hope someone else might elaborate on this part. One way to test it is with MemoryInUse.

m1 = MemoryInUse[];
f[10^6];
MemoryInUse[] - m1

==> 8001424

m1 = MemoryInUse[];
g[10^6];
MemoryInUse[] - m1

==> 24000656

Again, the system function wins hands down.

Edit:

The reason the second method showed such a substantial increase in MemoryInUse is because it doesn't produce a packed array. If we pack the output, it uses the same memory as the first. This tells me that MemoryInUse only tells us how much memory the result uses and nothing about the amount of memory used in intermediate computations.

m1 = MemoryInUse[];
Developer`ToPackedArray@g[10^6];
MemoryInUse[] - m1

==> 8001472

Edit 2: Here is a function I put together that I'm sure can be made more effective and efficient. It uses a binary search technique with MemoryConstrained to find the amount of memory requested when evaluating an expression.

SetAttributes[memBinarySearch, HoldFirst]

memBinarySearch[expr_, min_, max_] :=
 Block[{med = IntegerPart[(max - min)/2], low = min, high = max, 
   i = 1},
  While[True,
   If[MemoryConstrained[expr, med] === $Aborted,
    low = med;
    ,
    high = med;
    ];
   med = IntegerPart[low + (high - low)/2];
   If[Equal @@ Round[{low, med, high}, 2], Break[]];
   ];
  med
  ]

Here it is applied to f and g from above...

memBinarySearch[f[10^6], 1, 10^9]

==> 16000295

memBinarySearch[g[10^6], 1, 10^9]

==> 62499999

Note that memBinarySearch is only accurate to 2 bytes. For some reason (probably related to IntegerPart) it doesn't like to find the exact byte count requested.

Answer 2

I think it is worth highlighting the difference in behavior between Timing and AbsoluteTiming as they relate to parallel computation.

---

FactorInteger is an example of a function that runs on a single thread.

LaunchKernels[];
lst = Table[2^149 - 1, {12}];

Map[FactorInteger, lst]; // AbsoluteTiming
Map[FactorInteger, lst]; // Timing

{4.7302705, Null}

{4.711, Null}

Timings are about the same, as one would expect.

ParallelMap[FactorInteger, lst]; // AbsoluteTiming
ParallelMap[FactorInteger, lst]; // Timing

{1.2420710, Null}

{0., Null}

With AbsoluteTiming we see the expected reduction in computation time. With Timing we get zero, presumably because it only measures time in the master kernel and not the workers.

---

Dot is an example of a function that, when applied to arrays of machine-size real numbers, automatically uses parallel computation.

LaunchKernels[];
$HistoryLength = 0;
sets = RandomReal[99, {12, 2, 1000, 1000}];

Map[Dot @@ # &, sets]; // AbsoluteTiming
Map[Dot @@ # &, sets]; // Timing

{0.5060290, Null}

{0.421, Null}

Now attempting ParallelMap on an already parallel operation:

ParallelMap[Dot @@ # &, sets]; // AbsoluteTiming
ParallelMap[Dot @@ # &, sets]; // Timing

{0.9880565, Null}

{0.436, Null}

AbsoluteTiming shows correctly that this slows down computation rather than speeding it up. Here Timing appears to show approximately the extra time spent.

Answer 3

Andy gave some good hints, here are a few additions:

1. Yes, of course correct code is the most important. The question is the border cases, sometimes the code is mostly correct, but fixing border cases makes then slower. One idea here is to have a general fully correct procedure and then sub methods that well work for particular cases. I my opinion, the default code should always be the fully correct one.
2. Timing vs. AbsoluteTiming: Here is another example of a shortcoming of Timing. You might want to look at the Workbench profiler.
3. Concerning cache and memory, I find $HistoryLength=0 and also MaxMemoryUsed[] very valuable.