Why are more highly nested lists often not more memory and time-intensive?

Question

I would expect more highly nested lists, being deeper and more complex than flatter lists, to take up more space (bytecount) and take more time and memory to operate on in general. Consider the following.

---

Let's make a highly nested list of integers and a list with the same elements but flatter.

a1 = RandomInteger[9, {20, 30, 40, 50}];
a2 = Flatten[a1, {{1}, {2}, {3, 4}}];

Both are packed arrays.

a1 // PackedArrayQ
a2 // PackedArrayQ

(*True*)
(*True*)

They have nearly the same bytecount.

a1 // ByteCount
a2 // ByteCount

(*9600224*)
(*9600216*)

Let's perform a nesting operation on both. The time taken and memory involved is nearly the same (the timing was even closer in different trials).

h[a_] := Outer[Append, a, Last /@ a, 1]

h[a1] // MaxMemoryUsed // AbsoluteTiming
h[a2] // MaxMemoryUsed // AbsoluteTiming

(*{0.097976, 208425704}*)
(*{0.089271, 208422184}*)

The output lists have nearly the same bytecount as well, but neither is packed.

h[a1] // ByteCount
h[a2] // ByteCount

(*198490600*)
(*198487400*)

h[a1] // PackedArrayQ
h[a2] // PackedArrayQ

(*False*)
(*False*)

---

Even if we vastly change how deeply nested the original list a1 is and the number of elements each level has, and then compare it to more flattened versions a2 and a3, we get similar results. For example, the same conclusions can be seen from the following.

a1 = RandomInteger[9, {150, 100, 80}];
a2 = Flatten[a1, {{1}, {2, 3}}];
a3 = Flatten[a1];



a1 // ByteCount
a2 // ByteCount
a3 // ByteCount

(*9600216*)
(*9600208*)
(*9600200*)



h[a1] // MaxMemoryUsed // AbsoluteTiming
h[a2] // MaxMemoryUsed // AbsoluteTiming

(*{0.928319, 1487693704}*)
(*{0.916964, 1487305936}*)



h[a1] // ByteCount
h[a2] // ByteCount

(*1477273280*)
(*1477093280*)

---

Why is this?

Answer 1

A packed arrays (or a MTensor on the C++ side of Mathematica) consists of a linear array containing all entries plus the information needed for storing of the Dimensions of the packed array. That is 1 mreal=double/mint=long long int = 64 bit = 8 byte per entry + a few bytes for storing the array of the Dimension of the packed array (again probably a mint/long long int = 64 bit = 8 byte for each entry and an additional mint/long long int = 64 bit = 8 byte for storing the size of the Dimensions array). That means that the bulk of memory is used only for storing the entries.

For complex numbers (mcomplex), just multiply the size of the linear array by two (1 mcomplex = 2 mreal a.k.a. double).

Arrays that are not packed can often be represented by some array of pointers to packed arrays. Each point has to store only a memory address, which is probably a 64-bit unsigned integer. For example, both

Map[Developer`PackedArrayQ, h[a1], {2}]

and

Map[Developer`PackedArrayQ, h[a2], {2}]

reveal that both are stored as $20 \times 20$ array of packed arrays. The entries of those array $20 \times 20$ arrays differ only by an additional dimension. So by the reasoning above, their storage costs should differ by only 8 byte. Let's see:

h[a1][[1,1]] // ByteCount
h[a2][[1,1]] // ByteCount

496160

496152

Aha, this seems to be right. In total, that would be $20 \times 20 \times 8$ byte = $3200$ byte. And indeed:

ByteCount[h[a1]] - ByteCount[h[a2]]

3200

However, the $20 \times 20$ array of pointers is stored as a ragged list, which is a much more complicated data structure (ragged lists can store basically everything and that comes at a cost). Accordingly, that requires a bit more memory than the corresponding packed array:

ByteCount[h[a1]] - ByteCount[Developer`ToPackedArray[h[a1]]]

68192