Two strange efficiency problems in Mathematica

Question

FIRST PROBLEM

I have timed how long it takes to compute the following statements (where V[x] is a time-intensive function call):

Alice     = Table[V[i],{i,1,300},{1000}];
Bob       = Table[Table[V[i],{i,1,300}],{1000}]^tr;
Chris_pre = Table[V[i],{i,1,300}];
Chris     = Table[Chris_pre,{1000}]^tr;

Alice, Bob, and Chris are identical matricies computed 3 slightly different ways. I find that Chris is computed 1000 times faster than Alice and Bob.

It is not surprising that Alice is computed 1000 times slower because, naively, the function V must be called 1000 more times than when Chris is computed. But it is very surprising that Bob is so slow, since he is computed identically to Chris except that Chris stores the intermediate step Chris_pre.

Why does Bob evaluate so slowly?

---

SECOND PROBLEM

Suppose I want to compile a function in Mathematica of the form

f(x)=x+y

where "y" is a constant fixed at compile time (but which I prefer not to directly replace in the code with its numerical because I want to be able to easily change it). If y's actual value is y=7.3, and I define

f1=Compile[{x},x+y]
f2=Compile[{x},x+7.3]

then f1 runs 50% slower than f2. How do I make Mathematica replace "y" with "7.3" when f1 is compiled, so that f1 runs as fast as f2?

---

EDIT:

I found an ugly workaround for the second problem:

f1=ReleaseHold[Hold[Compile[{x},x+z]]/.{z->y}]

There must be a better way...

Answer 1

You probably should've posted these as separate questions, but no worries!

Problem one

The problem with Alice is of course what you expect. The problem with Bob is that the inner Table is evaluated once per iteration of the outer Table. This is clearly visible with Trace:

Trace[Table[Table[i, {i, 1, 3}], {3}]]

{
Table[Table[i,{i,1,2}],{2}],
{Table[i,{i,1,2}],{i,1},{i,2},{1,2}},{Table[i,{i,1,2}],{i,1},{i,2},{1,2}},
{{1,2},{1,2}}
}

Line breaks added for emphasis, and yeah, the output of Trace on Table is a little weird, but you can see it. Clearly Mathematica could optimize this better, knowing that the outside table has no iterator, but for whatever reason, it doesn't take that into account. Only Chris does what you want, though you could modify Bob:

Transpose[Table[Evaluate[Table[V[i],{i,1,300}]],{1000}]]

This looks like it actually outperforms Chris by a factor of two or so, because it doesn't have to store the intermediate result.

Problem two

There's a simpler solution with Evaluate, though I expect it won't work with all possible functions to be compiled (i.e. ones that really should be Held):

f1 = Compile[{x}, Evaluate[x + y]];

You could also use a With:

With[{y=7.3},
    f1 = Compile[{x}, x + y];
]

Or if y is defined elsewhere, use a temporary:

y = 7.3;
With[{z = y},
    f1 = Compile[{x}, x + z];
]

I'm not an expert on Mathematica's scoping and evaluation mechanisms, so there could easily be a much better way, but hopefully one of those does it for you!

Answer 2

Your first problem has already been explained, but I want to point out that ConstantArray was introduced in Mathematica 6 to address this issue. Prior to that time Table[expr, {50}] was used for both fixed and changing expressions.

Since the introduction of ConstantArray there is clear separation between iteration with reevaluation, and simple duplication of an expression. You can see the behavior using this:

ConstantArray[Table[Pause[1]; i, {i, 5}], {50}] ~Monitor~ i

It takes five seconds to loop through Table because of Pause[1], but after that loop is complete it is not reevaluated and the 50 copies are immediately printed.

Answer 3

First problem Have you checked the output of the Chris_pre computation? You will find that it is not a large matrix at all, since you're trying to store an intermediate result in a pattern, rather than a Variable. Try ChrisPre, instead. Then all the timings are comparable.

Second problem Compile has a number of tricky restrictions on it's use. One issue is that you cannot refer to global variables. The With construct that was already suggested is the suggested way around this. If you want to learn more about Compile, check out Ted Ersek's tricks: http://www.verbeia.com/mathematica/tips/Tricks.html