2
$\begingroup$

This post is related to my previous post, since that post is ended. I start a new here. Because there is still something I don't understand.

define

packq=Developer`PackedArrayQ
aa=Range[300]

I retested 8 cases below

nested iterator

Table[i j, {i, 1, Length@aa}, {j, 1, Length@aa}] // packq (*False*)
Table[i j, {i, 1, 300}, {j, 1, Length@aa}] // packq (*False*)
Table[i j, {i, 1, Length@aa}, {j, 1, 300}] // packq (*True*)
Table[i j, {i, 1, 300}, {j, 1, 300}] // packq (*True*)

double Table

Table[Table[i j, {i, 1, Length@aa}], {j, 1, 
   Length@aa}] // packq (*False*)
Table[Table[i j, {i, 1, 300}], {j, 1, Length@aa}] // packq (*True*)
Table[Table[i j, {i, 1, Length@aa}], {j, 1, 300}] // packq (*False*)
Table[Table[i j, {i, 1, 300}], {j, 1, 300}] // packq (*True*)

From the above result. It seems that the unpacking behaviour of "nested iterator" and "double table" is somewhat opposite.

  1. for "nested iterator". If outer iterator is explicit, then result is packed.
  2. for "double table". If inner table iterator is explicit, the result is packed.

I thought I understand the "nested iterator" case, because if the outer iterator is an expression, then it may depend on inner loop. So for each inner loop, outer iterator is recalculated. This can be seen from

Table[i j, {i, 1, 2}, {j, 1, Length@Range[2]}] // Trace // Column    
(*Table[i j,{i,1,2},{j,1,Length[Range[2]]}]
{{Range[2],{1,2}},Length[{1,2}],2}
{{i,1},{j,1},1 1,1}
{{i,1},{j,2},1 2,2}
{{Range[2],{1,2}},Length[{1,2}],2}
{{i,2},{j,1},2 1,2}
{{i,2},{j,2},2 2,4}
{{1,2},{2,4}}*)

But I don't understand the "double table" case, why some are unpacked? It seems to be not consistent with below result

Table[i j, {i, Range[300]}, {j, Range[300]}] // packq (*False*)
Table[i j, {i, 1, 300}, {j, Range[300]}] // packq(*False*)
Table[i j, {i, Range[300]}, {j, 1, 300}] // packq(*True*)
Table[i j, {i, 1, 300}, {j, 1, 300}] // packq(*True*)
Table[Table[i j, {i, Range[300]}], {j, Range[300]}] // packq (*True*)
Table[Table[i j, {i, 1, 300}], {j, Range[300]}] // packq(*True*)
Table[Table[i j, {i, Range[300]}], {j, 1, 300}] // packq(*True*)
Table[Table[i j, {i, 1, 300}], {j, 1, 300}] // packq(*True*)

They are all packed except the first two case.

How to explain it?

$\endgroup$
  • 1
    $\begingroup$ Shouldn't one expect the behavior to be opposite for 'nested iterators' vs 'double tables'? E.g., Table[{i, j}, {i, Range@200}, {j, Range@300}] === Table[Table[{i, j}, {j, Range@300}], {i, Range@200}] (* True *)? $\endgroup$ – jjc385 Nov 4 '17 at 16:26
  • $\begingroup$ You're right -- it seems odd that Table[Table[i j, {i, 1, 300}], {j, Range[300]}] is packed while Table[i j, {j, 1, 300}, {i, Range[300]}] is not packed. It seems like the 'double table' is able to auto-compile the Range[300] but the 'nested iterator' case is not. $\endgroup$ – jjc385 Nov 4 '17 at 16:40
6
$\begingroup$

The confusion here may arise from the fact that we must reverse the iterators when converting between the "nested" and "double" table constructions. The Details section of the Table documentation states:

Table[expr, spec1, spec2] is effectively equivalent to Table[Table[expr, spec2], spec1].

Note how spec1 and spec2 are reversed between the two forms. In "nested" form, the leftmost iterator defines the outer loop. In "double" form, the rightmost iterator defines the outer loop. If we take this into account, then we find we get the same results for both nested and double forms:

packq @ Table[i j,       {i, 1, Length@aa},  {j, 1, Length@aa}] (*False*)
packq @ Table[i j,       {i, 1, 300},        {j, 1, Length@aa}] (*False*)
packq @ Table[i j,       {i, 1, Length@aa},  {j, 1, 300}]       (*True*)
packq @ Table[i j,       {i, 1, 300},        {j, 1, 300}]       (*True*)

packq @ Table[Table[i j, {j, 1, Length@aa}], {i, 1, Length@aa}] (*False*)
packq @ Table[Table[i j, {j, 1, Length@aa}], {i, 1, 300}]       (*False*)
packq @ Table[Table[i j, {j, 1, 300}],       {i, 1, Length@aa}] (*True*)
packq @ Table[Table[i j, {j, 1, 300}],       {i, 1, 300}]       (*True*)

Armed with this insight, we observe that the packed optimization is only sensitive to the iterator that defines the inner loop. If that iterator is manifestly constant, then the optimization is applied. If the inner iterator needs to be computed during each outer iteration, then the result is not packed.

What Triggers The Optimization?

The optimizer considers more than just the table bounds. It also takes the data type of the element expressions into account. For example, if we change the element expression from i j to ToString[i j] then we no longer see the single table invocation (since packed arrays can presently only hold simple numeric types).

Furthermore, this optimization only occurs if the table size is large enough to trigger auto-compilation. Here is the relevant system option showing the default compilation threshold of 250 elements:

SystemOptions["CompileOptions" -> "TableCompileLength"]
(* {"CompileOptions" -> {"TableCompileLength" -> 250}} *)

If we change the outer iterator upper bounds in the examples from 300 to 249, then the result is not a packed array.

Observing Auto-Compilation

We can directly observe the effects of table auto-compilation by means of On[Table]. Here, with constant bounds:

On[Table]
Table[Table[i j, {i, 300}], {j, 300}] // Developer`PackedArrayForm
Off[]

single invocation of table

We see only a single invocation of Table. The nested calls have been compiled out. By contrast, if the bounds of the inner Table expression are not manifestly constant then the trace shows 301 invocations of Table (300 inner + 1 outer):

On[Table]
n = 300;
Table[Table[i j, {i, 1, n}], {j, 1, 300}] // Developer`PackedArrayForm
Off[]

301 invocations of Table

Additional Optimization Performed By "Double" Tables

In the updated question, it is observed that sometimes a non-constant (Range) bound on the inner iterator of a double table expression can still yield a packed array even when the (so-called) equivalent nested table expression does not. For example:

Table[i j, {i, 300}, {j, Range[300]}] // packq
(* False *)

but:

Table[Table[i j, {j, Range[300]}], {i, 300}] // packq
(* True *)

To help us investigate this behaviour, we will define a helper function that forces auto-compilation even for small lists, and shows the results in packed array form:

SetAttributes[table, HoldAll]
table[expr_] :=
  Module[{opts = SystemOptions["CompileOptions"]}
  , Internal`WithLocalSettings[
      SetSystemOptions["CompileOptions" -> "TableCompileLength" -> 1]
    , expr // Developer`PackedArrayForm
  , SetSystemOptions[opts]
  ]
]

So then:

Table[i j, {i, 3}, {j, Range[3]}] // table
(* {{1, 2, 3}, {2, 4, 6}, {3, 6, 9}} *)

Table[Table[i j, {j, Range[3]}], {i, 3}] // table
(* PackedArray[Integer,<3,3>] *)

Experimentation reveals that this optimization is not unique to Range. Packing occurs for other list construction expressions as well:

Table[Table[i j, {j, Join[{1}, {2}, {3}]}], {i, 3}] // table
(* PackedArray[Integer,<3,3>] *)

Table[Table[i j, {j, Union[{3, 2}, {1}]}], {i, 3}] // table
(* PackedArray[Integer,<3,3>] *)

Table[Table[i j, {j, Union@RandomInteger[{1, 3}, 100]}], {i, 3}] // table
(* PackedArray[Integer,<3,3>] *)

An interesting result occurs if the expression has side effects:

Table[Table[i j, {j, Echo@Range[3]}], {i, 3}] // table
(* >> {1, 2, 3}
   >> {1, 2, 3}
   >> {1, 2, 3}
   {PackedArray[Integer,<3>],PackedArray[Integer,3>],PackedArray[Integer,<3>]}
*)

These results suggest that there is a post-processing optimization that examines the elements of the final outer list and conditionally packs it. To test that theory, let's perform many evaluations of an expression that yields random results:

Do[
  Table[Table[i j, {j, Union[RandomInteger[{1, 3}, 4]]}], {i, 3}] // table // Print
, 8
]

(* PackedArray[Integer,<3,3>]
   {{1,2,3},{2,4,6},{3,6,9}}
   {{1,3},{4,6},{3,6,9}}
   {{1,2},{2,4},{3,6}}
   PackedArray[Integer,<3,2>]
   PackedArray[Integer,<3,2>]
   {{2,3},{4,6},{3,6}}
   {{1,3},{2,4,6},{3,6,9}}
 *)

Clearly, the optimization is not being determined statically up front. The resulting list is packed as a post-processing step that is sensitive to the exact shapes of the inner lists. The strange result we saw when we added Echo into the mix suggests that there is heuristic at work rather than a hard-and-fast rule.

For whatever reason, this optimization is only applied for the double table case and not for nested tables. Since we have no access to the source code for Table, it is difficult to assess the reason for this difference. It might be a simple oversight, or perhaps different sets of optimization heuristics that are hard to unify across the two patterns. Optimizations such as these are not documented and there are no guarantees about there presence or absence. As a result, it is difficult to characterize differences like these as bugs unless the results are manifestly incorrect (which is not the case here).

$\endgroup$
  • $\begingroup$ This is great. Could you do a quick rundown on the performance characteristics of each form? (unless it’s already been done somewhere) I’m assuming the 301 call version is much less efficient than the single call one. $\endgroup$ – b3m2a1 Nov 4 '17 at 20:13
  • $\begingroup$ @b3m2a1 As you surmise, for these exact expressions there is a ~100x runtime difference. But I have learned that the Mathematica performance model is quite opaque and often surprising -- small changes in data size, data type or operator choice (or Mma version) can cause radical changes in time and space usage. So I hesitate to make a general statement about the performance characteristics. $\endgroup$ – WReach Nov 5 '17 at 0:17
  • 1
    $\begingroup$ Thank you very much, @WReach. It is quite embarrassing that I messed up inner and outer iterator, I am totally stupid when I post yesterday : ). Your explanation makes sense. But it seems that it still can not explain Range behaviour. I updated my post about Range. How could you explain the two False case If as you said range is considered constant bound? $\endgroup$ – matheorem Nov 5 '17 at 13:41
  • $\begingroup$ I have the same question as @matheorem. See my comment above. $\endgroup$ – jjc385 Nov 5 '17 at 14:06
  • 1
    $\begingroup$ @jjc385 I have added a new section that talks about this case. $\endgroup$ – WReach Nov 5 '17 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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