5
$\begingroup$

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)
$\endgroup$
14
  • 1
    $\begingroup$ Did you check packing? $\endgroup$ – J. M.'s torpor Feb 14 at 14:34
  • 1
    $\begingroup$ @J.M. On["Packing"] shows nothing $\endgroup$ – matheorem Feb 14 at 14:50
  • 4
    $\begingroup$ Extract the part separately and you'll see that the timing difference has nothing to do with Total: part = a[[1]]; RepeatedTiming[Total[part, Infinity];] $\endgroup$ – MarcoB Feb 14 at 15:12
  • $\begingroup$ Obvious workaround that does too much work but is fast: Total[a, {2, Infinity}][[1]] $\endgroup$ – Roman Feb 14 at 15:14
  • 1
    $\begingroup$ @MichaelE2 That is even more wierd. Which version do you use? I use mma 12. on windows. What on earth happend to Part? Does Part make a copy? Why is it not the case on your system? $\endgroup$ – matheorem Feb 15 at 2:17
7
$\begingroup$

Included in your timing is the Part operation. Try:

b = a[[1]];
Total[b, Infinity]; // RepeatedTiming
$\endgroup$
0
3
$\begingroup$

[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}  *)
*)
$\endgroup$
7
  • $\begingroup$ Thank you so much, Michael E2. Acutally I was just about to update my post to talk about that unpacked list of packed array is a better choice in this case :) I still got questions. First, what are those punpack1 and punpack11 messages? I never saw these message. $\endgroup$ – matheorem Feb 15 at 15:43
  • $\begingroup$ You said "Mathematica copies a structure only when a program tries to change (part of) its value ". But in assignment case a[[1, ;; , ;; , ;;]] = 1., the a is gonna changing, but I guess no copy happened, it is an inplace update, because it is indeed much faster. So I am wondering if Part of packed array really has to be copied due to mathematica's maybe immutability design principle? $\endgroup$ – matheorem Feb 15 at 15:53
  • 1
    $\begingroup$ After all, for built-in functions like Total and basic arithmetics, there should be special branches to prevent this kind of copy. If not, that is a shame for packed array to be the common choice of faster and more efficient over unpacked array. $\endgroup$ – matheorem Feb 15 at 15:53
  • 1
    $\begingroup$ The messages are what you get with On["Packing"]. -- Try b = a; a[[1, ;; , ;; , ;;]] = 1.. Then the array a pointed to will be copied to preserve the value of b. Time this with a 1GB+ array for a and it will be obvious. Mathematica must keep a table of references to an expression. -- I disagree with your last comment. Total does not hold its arguments. a[[1]] is copied before Total is called; see my example aa // First above. The fault, if you want to call it that, is with Part, which I alluded to in my second-to-last paragraph ("I don't know enough..."). $\endgroup$ – Michael E2 Feb 15 at 17:04
  • $\begingroup$ Hi, Michael E2. But I didn't see any message generated with On["Packing"] when evaluating Total[aa // First, Infinity]; $\endgroup$ – matheorem Feb 16 at 7:41

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.