Very simple, unexpected Low Performance of set(=)

Question

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.

Answer 1

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    *)