8
$\begingroup$
In[1]  AA = RandomInteger[10, 1000000]; BB = AA;

In[2]  Do[BB = AA;, 10000] // Timing

Out[2]  {0., Null}

In[3]  Do[BB[[77]] = i;, {i, 1, 10000}] // Timing

Out[3]  {0., Null}

In[4]  Do[BB[[i]] = i;, {i, 1, 10000}] // Timing

Out[4]  {0., Null}

From Out[2], we see setting a variable to a large list takes no time.

From Out[3],Out[4], we see setting an element of a list to a number takes no time.

But

In[5]  Do[BB = AA; BB[[77]] = i;, {i, 1, 10000}] // Timing

Out[5]  {3.04688, Null}

alternately setting a variable to a large list + setting an element of a list to a number takes long time.

Q1) How can we explain it ?

Q2) In fact, mathematica reported it took 3.04688 seconds, but in fact it took about 20 seconds (physical watch) to get Out[5]. Personaly there have been some differences in the past, but this is the first time I've seen such a big difference.

$\endgroup$
3
  • 12
    $\begingroup$ Line [5] is the only one where a deep copy of the full AA→BB is done in every loop iteration. Line [2] can be done with a shallow (lazy) copy because BB is not being edited and so no actual data copying is required (only some reference counts need to be updated); but in line [5] the shallow copy BB=AA is followed by a write access BB[[77]]=i, which triggers copy-on-write and which takes substantial amounts of time. $\endgroup$
    – Roman
    Jun 22 at 4:54
  • $\begingroup$ Thank you, didn't know there is a concept like shallow (lazy) copy. $\endgroup$
    – imida k
    Jun 22 at 10:47
  • 3
    $\begingroup$ @Roman I found your comment very insightful. Would you consider turning it into an answer? $\endgroup$
    – MarcoB
    Jun 22 at 11:49

1 Answer 1

5
$\begingroup$

I assume that, like all modern software, Mathematica implements copy-on-write. From the Wikipedia:

Copy-on-write (COW), sometimes referred to as implicit sharing or shadowing, is a resource-management technique used in computer programming to efficiently implement a "duplicate" or "copy" operation on modifiable resources. If a resource is duplicated but not modified, it is not necessary to create a new resource; the resource can be shared between the copy and the original. Modifications must still create a copy, hence the technique: the copy operation is deferred until the first write. By sharing resources in this way, it is possible to significantly reduce the resource consumption of unmodified copies, while adding a small overhead to resource-modifying operations.

Translating this explanation to the examples given by the OP:

  • In[2]: The statement BB = AA makes a shallow (lazy) copy of AA and "stores" it in BB. This is a very quick operation: the only thing to do is to write down that BB points to AA. BB is not an independent array; it depends on AA.
  • In[3] and In[4]: The first statement (for $i=1$) sets BB[[77]] = 1, which triggers copy-on-write and prepares a deep (non-lazy) copy of AA in the space of BB, then modifies BB[[77]]. BB is now fully independent of AA. The subsequent 19999 assignments to elements of BB no not re-trigger copy-on-write because BB is not related to AA anymore.
  • In[5]: In every loop iteration, the first statement BB = AA erases the old contents of BB, then establishes a fresh shallow (lazy) copy of AA just like in In[2]. The second statement in the loop then makes an assignment to BB[[77]], which triggers copy-on-write, making BB a deep copy that can be modified independently of AA. It is this copy-on-write operation, which has to make a true copy of one million integer numbers (about 8 megabytes of data), that takes a significant amount of time.

A bit more profiling: a shallow copy seems to take about 190 nanoseconds (a good fraction of which may be the profiling overhead),

AA = RandomInteger[10, 1000000];
RepeatedTiming[BB = AA;] // First
(*    1.93599*10^-7    *)

whereas a deep copy of an array of $10^6$ integers takes about 340 microseconds,

RepeatedTiming[BB = AA; BB[[77]] = 5;] // First
(*    0.000340914    *)
$\endgroup$

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.