Proof of concept for Copy-on-Write implementation
An experiment to implement one of the proposals discussed in https://github.com/pandas-dev/pandas/issues/36195/, described in more detail in https://docs.google.com/document/d/1ZCQ9mx3LBMy-nhwRl33_jgcvWo9IWdEfxDNQ2thyTb0/edit

This PR adds Copy-on-Write (CoW) functionality to the DataFrame/Series when using ArrayManager. 
It does this by adding a new `.refs` attribute to the `ArrayManager` that, if populated, keeps a list of `weakref` references (one per columns, so `len(mgr.arrays) == len(mgr.refs)` to the array it is viewing. 
This ensures that if we are modifying an array of a child manager, we can check if it is referencing (viewing) another array, and if needed do a copy on write. And also if we are modifying an array of a parent manager, we can check if that array is being referenced by another array and if needed do a copy on write in this parent frame. (of course, a manager can both be parent and child at the same time, so those two checks always happen both)

A very brief summary of the behaviour you get (longer description at https://github.com/pandas-dev/pandas/issues/36195#issuecomment-786654449):

- *Any* subset (so also a slice, single column access, etc) uses CoW (or is already a copy)
- DataFrame methods that return a new DataFrame return shallow copies (using CoW) if applicable (for this POC I implemented that for `reset_index` and `rename` to test, needs to be expanded to other methods)

I added a `test_copy_on_write.py` which already tests a set of cases (which of course needs to be expanded), going through that file should give an idea of the kind of behaviours (and how it changes compared to current master/BlockManager). Link to that file in the diff: [click here](https://github.com/pandas-dev/pandas/pull/41878/files#diff-2abca9577897e44acf7b37c1412c9fc324b0464723cdf1d68a0f1467834a9245)

(I only added new, targeted tests in that file, I didn't yet start updating existing tests, as I imagine there will be quite a lot)

This is a proof-of-concept PR, so the feedback I am looking for / what I want to get out of it:

- A concrete starting point for an implementation, to stir the discussion on this topic https://github.com/pandas-dev/pandas/issues/36195/ (and a concrete implementation you can play with, to get feedback on the proposed semantics)
- Review of the actual implementation using `weakrefs` (it's quite simple at the moment, but not too simple? Will this be robust enough?)
- Other corner cases that should certainly be tested
- ...

And to be clear, not yet everything is covered (there are some `# TODO`'s in `array_manager.py`, but only fixing those while also adding tests that require it)

TODO:

- [ ] Series and DataFrame constructors

cc @pandas-dev/pandas-core 
Does this implementation have the shallow-copies issue discussed here https://github.com/pandas-dev/pandas/issues/36195#issuecomment-830579242 ? Yes or no, depending on how to interpret the question ;) 
It doesn't have the issue, by not allowing shallow copies in the current sense. Or to put it otherwise, a shallow copy (i.e. `copy(deep=False)`) effectively is a "CoW shallow copy" in the PR's implementation, meaning that once you modify it, data gets copied and mutations don't propagate back to the parent dataframe. If you, for some reason, want the same shallow copy semantics as we have now (i.e. mutations will propagate), then of course that's an "issue". But as mentioned in https://github.com/pandas-dev/pandas/issues/36195#issuecomment-830579242, I am not really sure this is a problem that we won't have this anymore. Does writing to the parent trigger a copy in the child?

Update: i see in the [doc](https://docs.google.com/document/d/1ZCQ9mx3LBMy-nhwRl33_jgcvWo9IWdEfxDNQ2thyTb0/edit#heading=h.iexejdstiz8u) it says it does (Propagating Mutation Forwards), but that doesn't appear to be implemented yet in this branch

```
$ hub pr checkout 41878
$ export PANDAS_DATA_MANAGER=array
$ python3

import pandas as pd

ser = pd.Series(range(10))
ser2 = ser.view("m8[ns]")

ser.iloc[0] = 10000

>>> ser2.view("i8")[0]
10000
```

Not sure if this is a bug or just not yet implemented in this branch. Is there any prospect of making this independent of AM/BM?   > Does writing to the parent trigger a copy in the child?

It triggers a copy, but in the current implementation it's always the values that are being modified that get copied. So in this case, it would trigger a copy in the parent (but so still preserving the behaviour that mutations are not propagated). 
(I think this is the easiest, as there can potentially be many children and children of children etc)

> but that doesn't appear to be implemented yet in this branch

Yes, I didn't yet check the `view()` method (which is actually using the Series constructor, which I didn't yet update to track reference to the input array). If you use a viewing indexing method for the example, (eg `s2 = s[:]`, but which of course doesn't change the dtype), it works as expected:

```
In [9]: pd.options.mode.data_manager = "array"

In [10]: ser = pd.Series(range(5))
    ...: ser2 = ser[:]

In [11]: ser.iloc[0] = 10000

In [12]: ser2
Out[12]: 
0    0
1    1
2    2
3    3
4    4
dtype: int64
```

> Is there any prospect of making this independent of AM/BM? 

Yes, I don't think there is anything in the current implementation that makes it tied to the ArrayManager, and it should be possible to write a similar BlockManager version (it could have the logic of checking for weakref references / triggering a copy if needed on the Blocks. I only expect it to be a bit more complicated, at least if we want to ensure that modifying a single column doesn't necessarily triggers a copy of the full dataframe with consolidated blocks). 
Even if we would move to the ArrayManager long term, we would still basically need some implementation of it in the BlockManager anyway, to be able to raise FutureWarnings about when behaviour would change (although in this case, the implementation can be simpler, as it wouldn't need the performance considerations of not copying a full block). 

But, before doing this in practice, I would first want to see 1) more discussion on the actual semantics (and some more explicit agreement on that we want this), 2) more review of the implementation details (using weakrefs etc) to ensure this POC is actually possible (as this would be similar for the BM version) and 3) some discussion on how we would see an upgrade path (what kind of version bump, how do we want to provide future warnings etc) > It triggers a copy, but in the current implementation it's always the values that are being modified that get copied. So in this case, it would trigger a copy in the parent [...] (I think this is the easiest

Thanks, that makes sense.  Will have to give some thought to the implications of this.

> it should be possible to write a similar BlockManager version [...] But, before doing this in practice, I would first want to see [...]

Make sense.

 How does this behave w/r/t `frame.values`?  for consolidated (1 column for AM) cases this will be a view on the underlying array, but a different object.

(also `Series.to_frame`, but that already behaves differently for ArrayManager xref #42512) was the as_mutable_view idea intended to be part of this?  IIUC this would mean that basically nothing is ever "just a view"? > was the as_mutable_view idea intended to be part of this? 

No, that was part of the original proposal / discussion, but I didn't include it in my updated proposal focusing on Copy-on-Write. I also don't directly see how it could be implemented with reliable semantics across all corner cases (or at least without a complex implementation).  

For example, let's assume you have a `df` and two viewing "child" objects `df_child1` and `df_child2`. If you would now make `df_child1` in a "mutable view", how does that affect `df_child2` ? Mutating `df_child1` is then supposed to also mutate the parent `df`, but still not `df_child2`, in which case a mutation of `df_child1` would need to trigger a copy of the internal data stored in `df_child2`. So then you need to recursively check children of children etc to update those ...

> IIUC this would mean that basically nothing is ever "just a view"?

Indeed. Either you have identical objects (`df1 is df2`) and then obviously mutating the one is reflected in the other (since it are just two names pointing to the same object, eg from doing `df2 = df1`), or either it are not identical objects and then it always uses copy-on-write in case the data are views (meaning it will never act as a view for the user). Makes sense, thanks.

Does any of this change if either the parent or child is a Series?  i.e. does the "never a view" also apply to selecting a single column from a DataFrame?  or to `series[::-1]`?

How are arrays that live inside Indexes treated?  Could any of this be adapted (not here, just spitballing) to prevent modifying arrays that live inside Indexes? > Does any of this change if either the parent or child is a Series? i.e. does the "never a view" also apply to selecting a single column from a DataFrame? or to `series[::-1]`?

Yes, it applies to "any" indexing operation, so including accessing a column as a Series or slicing a Series. 
(the column-as-Series case is explicitly mentioned in the google doc ([here](https://docs.google.com/document/d/1ZCQ9mx3LBMy-nhwRl33_jgcvWo9IWdEfxDNQ2thyTb0/edit#heading=h.e0p3ua7pd2a1)) since it's a typical case that now always is a view, but I should probably also explicitly call out that case in the summary at the top).

> How are arrays that live inside Indexes treated? Could any of this be adapted (not here, just spitballing) to prevent modifying arrays that live inside Indexes?

I don't think this is relevant for Index (which simply disallows to mutate, so you never run into those questions?). But, it *will* be used when converting an Index into a column, in which case we no longer need a copy without having to worry about accidentally modifying the Index (which we don't allow) by modifying the Series.
 > I don't think this is relevant for Index (which simply disallows to mutate, so you never run into those questions?)

The situation I'm thinking of is (this is in master)

```
ser = pd.Series(range(5))
idx = pd.Index(ser)
ser[0] = 10
>>> idx[0]
10
```

With CoW we could trigger a copy in `ser` to avoid accidentally mutating `idx` here.

Thinking back on the `.values` topic, will we will `ser2 = pd.Series(ser.values)` be treated the same as `ser2 = ser[:]`?  What about `ser3 = pd.Series(ser2.values[:])`? shower thought: will _item_cache cause repeated lookups e.g. `ser1 = frame["a"]; ser2 = frame["a"]` to have unexpected semantics? OT: what happened to the shim to preserve .values for sklearn? > I don't think this is relevant for Index (which simply disallows to mutate, so you never run into those questions?)
>
> The situation I'm thinking of is (this is in master)

Ah, that's a nice example. I would say that we should actually consider that a bug in current pandas .. (will open a separate issue about that -> https://github.com/pandas-dev/pandas/issues/42934). But yes, in this case, we should ensure that constructing an Index from a Series creates a reference to that array. And then with the CoW mechanism in this PR, mutating the Series would trigger a copy of its data, since the array is being referenced from elsewhere.

> Thinking back on the `.values` topic, will we will `ser2 = pd.Series(ser.values)` be treated the same as `ser2 = ser[:]`? What about `ser3 = pd.Series(ser2.values[:])`?

It will be similar yes. The plan is to let constructors like `pd.Series(ser.values)` store a reference to the array it is created from, so it also uses copy-on-write (and thus mutating the original `ser` will also trigger a copy-on-write). Updating the DataFrame/Series constructors to do this is still a TODO.  
For `ser3 = pd.Series(ser2.values[:])`, that becomes a bit more tricky to keep track of. That's a good corner case to consider for when implementing this part. A similar issue will arise even with something like `ser2 = pd.Series(ser[1:3])`. In both cases, we need to ensure that the original series knows that there is another Series viewing part of the data

> will _item_cache cause repeated lookups e.g. `ser1 = frame["a"]; ser2 = frame["a"]` to have unexpected semantics?

Good question. We should probably stop using `_item_cache` here. With the item cache, it means that `ser1 is ser2`, i.e. it are identical objects. And for identical objects, mutating one of course also reflects in the "other" (since there is no other ;)). 
I assume the item cache was added for performance (avoiding the overhead of the Series creation each time). Based on a quick profile, there seems to be some low-hanging room for improvement in the column-as-Series construction, but that's something we should then further validate and check performance.

> OT: what happened to the shim to preserve .values for sklearn?

I think that's indeed off-topic, that's something that came in the ArrayManager discussion (a Manager "shim" that stores the 2D array until an actual operation needs a full-blown Array/BlockManager), and not relevant for the CoW discussion (in general the behaviour of `DataFrame(ndarray)` is relevant of course, where we can also try to ensure CoW. But as mentioned above, I didn't yet implement the constructors).

 (reverted the putmask changes for now, making the diff easier to parse)

@jbrockmendel @jreback could I get some review of the implementation here? 
 I'll find some time this week.  Are you looking for high-level review or detailed? I would like to move towards merging this PR, so both. (note there are currently a few failing tests because there were some recent changes in master about when SettingWithCopyWarnings are raised or not, still need to look into that, but it shouldn't influence any reviewing) this will need some review - i personally have not looked at it yet but will soon @jbrockmendel thanks for the review! Thanks for the review!

> * you are hijacking the `deep=None` semantics to do this. we really don't like this keyword anyhow, but either can you add a new value, idk, maybe `deep='cow'` (not sure this is better) but maybe more obvious and readable. or I think @jbrockmendel suggested an enum (let's make it internal atm to signal this).

I don't think that `deep="cow"` is any better or different, both are a new value that can be passed to `deep`. Given that eventually, the `deep=None` could become `deep=False` again (now the `deep=None` is only meant as a keyword that means False for ArrayManager and True for BlockManager, to preserve the BlockManager behaviour on master), I would prefer to keep the `None` instead of some other sentinel (we generally use `None` elsewhere in cases the default depends on some other context) 

> * this is pretty convoluted when you have a method like `.reset_index()` that _only_ has an `inplace` keyword (and not `copy`). i would say we should either: deprecate `inplace` and replace with `copy` first.

What do you mean exactly with "convoluted" in this case? For the case the user doesn't specify `inplace=True` manually (i.e. for the default usage of `reset_index()`), it is easy to add CoW behaviour to `reset_index()` without it having a `copy` keyword. 
For the `inplace=True` case, it's a bit less clear, but short term we can probably continue what we do now: modify the object in place (i.e. equivalent as one would have done a setitem `df["index"] = ..`)

> * this is adding an enormous amount of complexitly to the code (likely hiding lots of cases).. not sure what to do about this, just noting it.

I think it's actually quite little code for such a big feature :) (the majority of the diff here are new/adapated tests). Now there are still many cases not covered, so it will of course still grow a bit. 
 @jorisvandenbossche closable? Yeah since CoW is in 1.5, albeit only for blockmanger, I think we can close this for now until Arraymanager work is picked back up. Closing