Unexpected timing result of Total and Part performance of packed array

Question

Define

a = RandomReal[1., {2, 100, 100, 100}];

then

Total[a, Infinity]; // RepeatedTiming
{0.00183727, Null}

and

Total[a[[1]], Infinity]; // RepeatedTiming
{0.00879665, Null}

Why? half work takes much more time?

---

update

This post has envolved into a post about the Part performance of packed array. As we all know, packed arrays stand for better performance and space efficiency over unpacked array, and we try hard not to get into the unpacking process.

However, it is clear now, Part operation of packed array may suffer severe copying issue(as Michael E2 analyzed). So in my case, to store packed sub data inside a unpacked list turns out to be a better choice.

aa = {RandomReal[1., {100, 100, 100}], RandomReal[1., {100, 100, 100}]};
Total[aa[[1]], Infinity]; // RepeatedTiming
{0.000676956, Null}

However, problems remains:

1. Is there direct way to speed up Parting of packed array?
2. Is it inevitable for Mathematica to have this Part behavior on packed array due to its design? (I guess not, because assignment like a[[1,;;,;;,;;]]=1. do not suffer)

Answer 1

[Update: I rewrote most of the text in response to the OP's comments. I suspect what I wrote originally lacked clarity. I hope I have improved it.]

The extra time observed in Total[aa // First, Infinity] comes from copying the data in aa[[1]]. It resembles unpacking in that it adds time to the computation that seems unnecessary. Indeed, in unpacked arrays, the copying of aa[[1]] does not occur. The differences in unpacked and packed arrays are explained below. Since aa // First is evaluated before Total is called, the problem is with Part and not Total. The time it takes to copy the first Part of the array accounts for the difference in timing.

aa = RandomReal[1., {2, 100, 100, 100}];

aa // First; // RepeatedTiming
With[{a1 = aa // First}, Total[a1, Infinity]; // RepeatedTiming]

% + %%
Total[aa // First, Infinity]; // RepeatedTiming

(*
  {0.00184571, Null}   <-- extracting aa[[1]]
  {0.000277292, Null}  <-- Total[]
  
  {0.002123, 2 Null}   <-- sum of preceding two times
  {0.00214796, Null}   <-- Total[aa // First...]
*)

Now I will describe how the difference of a packed array from a regular List array factors into the timing here.

A regular List array lis, constructed by entering lis = {{11, 12, 13}, {21, 22, 23}}, is represented internally by a pointer to a (linked) list of pointers to the expressions {11, 12, 13} and {21, 22, 23}. The part l1 = lis[[1]] is a pointer to an expression. There is no need to copy the expression unless it is changed in either lis or l1, and Mathematica will not copy it until such a change occurs. This is one of the efficiencies implemented in the everything-is-an-expression approach that WRI initially adopted for Mathematica.

A packed array pa is represented internally by an MTensor, which is a pointer to a structure st_MNumericArray, whose definitions can be found in the $InstallationDirectory in "SystemFiles/IncludeFiles/WolframLibrary.h" and ".../WolframCompileLibrary.h" respectively. This structure includes information about the type, rank, and dimensions of the array, a pointer to the numeric data, plus some other bookkeeping information. The numeric data is stored as a flat list of numbers (the same way as in C). The parts of the array are not stored as separate expressions, as in the regular List array. In order to maintain the everything-is-an-expression approach, when a part p1 = pa[[1]] is evaluated, a new expression must be constructed and part of the numeric data is copied into the new packed array. (One imagines one could implement a "subarray" structure that would need only a pointer to the numeric data in pa plus information defining the subarray and whatever additional bookkeeping might be needed. Whether this would be worth it is a design choice, and I cannot evaluate the trade-offs.)

When a packed array is converted to a List array, the process is called "unpacking." It involves constructing expressions and copying the data. It can be expensive. A packed array can be unpacked down to any level. The further down the unpacking goes, the more expensive it is. Taking a part of a packed array also involves constructing an expression and copying data, but it is not called "unpacking." It can still be expensive in way that makes long-time users suspect unpacking.

To test the foregoing, we check the timing in an unpacked array. And we see that totaling the first part is faster than totaling the whole array:

up = Developer`FromPackedArray[aa, 1]; (* unpacks to level 1 only *)
Total[up // First, Infinity]; // RepeatedTiming
Total[aa, Infinity]; // RepeatedTiming

(*
  {0.000276366, Null}  *)
  {0.000793719, Null}  *)
*)

Answer 2

Included in your timing is the Part operation. Try:

b = a[[1]];
Total[b, Infinity]; // RepeatedTiming