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

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?

• We do not know the details of implementation, but we can safely assume that something as basic as lists is implemented as efficiently as possible, possibly using optimized internal representations exactly to avoid what you feared. However, since the details of the implementation are not public, I am not sure what you would consider an appropriate answer to this question. It seems to me, conversely, that your hypothesis that "more highly nested lists, being deeper and more complex, to take up more space" was simply disproved by experiment. Jul 8, 2020 at 19:25
• @ MarcoB An appropriate answer in my mind would be an explanation as to why more highly nested lists are not more memory and time-intensive, or why my original assumption that they would be is not reasonable. I do not believe the assumption that more highly nested structures would be more computationally expensive is unreasonable. A flat list of small integers is an incredibly simple structure. Jul 8, 2020 at 20:01

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[DeveloperPackedArrayQ, h[a1], {2}]


and

Map[DeveloperPackedArrayQ, 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[DeveloperToPackedArray[h[a1]]]
`

68192