difference of speed in making a Table

I was reading a useful post at WRI blog on improving speed of code, and I need help in understanding this one.

Compare these speeds

Timing[
 tbl = Table[i + j, {i, 1, 1000}, {j, 1, 1000}];     
]

{0.031, Null}

and

Timing[
 a = 1000;
 tbl = Table[i + j, {i, 1, a}, {j, 1, a}];
 ]

{0.422, Null}

So it is much faster when putting the actual value for the limit inside the table itself vs outside. The explanation for this, which I am sure it is correct, but I need help in understanding, is that Table is compiled if its limit are numeric vs. not, this is because its Attributes is HoldAll.

But my question is: How would the above actually work, because the limits to Table must, at one point, become numeric anyway? I can't write

Clear[a]
tbl = Table[i + j, {i, 1, a}, {j, 1, a}]

The above gives an error.

So, for me, writing a=1000 outside Table vs. inside, should have made no difference, since without a having a numerical value, Table[] can't do anything. So the replacing of a by the number 1000 must occur at one point of time by evaluator before Table[] can do anything useful, would it not?

In other words, what Table should see, eventually, is {i, 1, 1000}, {j, 1, 1000} in both cases.

So, the way I thought this would happen is this:

Evaluator replaces a by 1000 in the arguments of table
Evaluator calls Table with the result, which is now all numeric.
Table Compiles, and runs faster now.

But what seems to happen is something else. (due to HoldAll ?)

Table takes its arguments, a

wolfram-mathematica

Edit Report

1 Answer

So this is what I think is happening. The reason why you see the slow down between a numeric and a symbolic limit on Table is due to the fact that you do a double index. Each sub-table (e.g. going over all indices j for a fixed index i) is constructed separately and when the limit is symbolic there is an extra step involved in figuring out that limit before constructing each sub table. You can see this by examining, e.g.

Trace[a = 3;
      tbl = Table[i + j, {i, 1, a}, {j, 1, a}];
     ]

David gives a good example for why you would want to do this check for every sub list. As to why Mathematica cannot figure out when this check is not needed I have no clue. If you only have one index to sum over there is no difference in speed between the symbolic and numeric version

Timing[tbl = Table[i + j, {j, 1, 1000}];]
{0.0012, Null}

Timing[a = 1000;
       tbl = Table[i + j, {j, 1, a}];
      ]
{0.0013, Null}

To answer your follow up regarding speed; making tbl a function is faster for both numeric and symbolic limits.

Timing[a = 1000;
       tblFunc[a_] := Table[i + j, {i, 1, a}, {j, 1, a}];
       tblFunc[a];
      ]

{0.045171, Null}

vs.

Timing[tbl = Table[i + j, {i, 1, 1000}, {j, 1, 1000}];]
{0.066864, Null}

Timing[a = 1000;
       tbl = Table[i + j, {i, 1, a}, {j, 1, a}];
      ]
{0.632128, Null}

You gain even more speed if you intend to reuse the tbl construction.

b=1000;
Timing[tblFunc[b];]
{0.000013, Null}

answered 2012-01-03T08:00:51.840

difference of speed in making a Table

1 Answer

Your Answer