Table and memory efficiency

Question

Consider these two types of creating matrices:

Table[Table[i*j,{i,1,10}],{j,1,10}]

Table[i*j,{i,1,10},{j,1,10}]

I want to know if there is any difference between these two in terms of memory efficiency.

N@(ByteCount[Table[Table[i*j, {i, 1, 10}], {j, 1, 10}]]/ByteCount[Table[i*j, {i, 1, 10}, {j, 1, 10}]])

If the size of the matrix is 10by10 both methods use the same amount of memory, for 100by100 the first method uses more memory, and for 1000by1000 case both use the same amount of memory.

1. Why aren't both method memory efficient equally?

2. Why the second method has advantage just over a limited range of matrix size?

The second part is comparing these two codes:

n = 100;
ByteCount[Table[i*j, {i, 1, n}, {j, 1, n}]]
(*250496*)

and

ByteCount[Table[i*j, {i, 1, 100}, {j, 1, 100}]]
(*80152*)

Why does setting the limits of the table by n make it less memory efficient?

I use Mathematica 9.

Edit

If I make a table of matrices, there isn't significant difference in size between packed and unpacked arrays:

<< Developer`
id = IdentityMatrix[100];
a = Table[{id[[i]]}\[Transpose].{id[[i]]}, {i, 1, 100}];
b = ToPackedArray[Table[{id[[i]]}\[Transpose].{id[[i]]}, {i, 1, 100}]];
PackedArrayQ[a]
PackedArrayQ[b]
ByteCount[a]/(1.0*ByteCount[b])

Answer 1

Part 1:

It has to do with packed arrays. Packed arrays occupy around 1/3 to 1/4 the size of unpacked arrays, giving the results you see. You can verify this as follows:

<< Developer`
PackedArrayQ[Table[Table[i*j, {i, 1, 10}], {j, 1, 10}]]
PackedArrayQ[Table[i*j, {i, 1, 10}, {j, 1, 10}]]
PackedArrayQ[Table[Table[i*j, {i, 1, 100}], {j, 1, 100}]]
PackedArrayQ[Table[i*j, {i, 1, 100}, {j, 1, 100}]]
PackedArrayQ[Table[Table[i*j, {i, 1, 1000}], {j, 1, 1000}]]
PackedArrayQ[Table[i*j, {i, 1, 1000}, {j, 1, 1000}]]

producing

False
False
False
True
True
True

Explanation: Mathematica tries to pack an array when the number of elements exceeds a certain threshold (250). In your nested Table of Table version for the 100-by-100 case, 100 is below this threshold, generating an unpacked array of unpacked arrays whose overall size (10000 elements) exceeds the packed array limit. In contrast, the single-Table version realizes that 10000 is over the threshold, and produces a single packed array.

Likewise, in the 10-by-10 case, both cases fall under the threshold, and in the 1000-by-1000 case, both exceed the threshold, so they both are equally efficient.

Incidentally, you can determine the threshold by the following:

PackedArrayQ[Table[i, {i, 249}]]
PackedArrayQ[Table[i, {i, 250}]]

which produces

False
True

This explains the behavior you see.

Part 2:

The first case doesn't pack your array:

n = 100;
PackedArrayQ[Table[i*j, {i, 1, n}, {j, 1, n}]]
PackedArrayQ[Table[i*j, {i, 1, 100}, {j, 1, 100}]]
(*False*)
(*True*)

I'm not sure why that's the case, though. Anyone know why? In any case, you can convert an array to a packed array using ToPackedArray:

PackedArrayQ[ToPackedArray@Table[i*j, {i, 1, n}, {j, 1, n}]]
(*True*)

Part 3 (addressing your Edit)

IdentityMatrix by default returns packed arrays. The product of two packed arrays is a packed array. As a result, a is an unpacked vector of packed matrices. Since the unpacked coarseness is at the top level, the size difference between the "unpacked" array a and the packed array b is very small.

You can confirm this by the following:

PackedArrayQ[a]
PackedArrayQ[a[[1]]] 
(*False*)
(*True*)

So in fact, you really are getting a factor of 3 size reduction from the packing, but it's not immediately apparent from a ByteCount comparison with the "unpacked" array.