3 ms·

I don't think copy on write would work in Python because you wouldn't know which variables to update to point to the copied list x = [] y = [] y2 =

I don't think copy on write would work in Python because you wouldn't know which variables to update to point to the copied list x = [] y = [] y2 = y y.append(1) # Should also update y2, but not x

viraptor 8y ago
The implementation would have to change, but it's doable. x and y would have to have different IDs, but they could point to a shared location with a cow marker set. It would likely use more memory then the current empty list, but it could potentially improve x[:] of arbitrary list where the result doesn't actually need to change later.
- quietbritishjim 8y ago
  Where would these unique IDs be stored? In Python, variables are just references to objects (as are entries in lists, dictionaries, etc.). So you would need some sort of intermediate object that kept the id and reference to the underlying list; the underlying list would be shared but there would be a separate stub object for every (distinct) variable. In the case of an empty list, this probably wouldn't be any smaller than the current system of having a totally separate list. Copy-on-write might make a difference in the case of large non-empty lists, but then there's another problem: you would need to trigger the copy even if something contained nested within the list changed e.g. if `x=[[1,2],3]` and you change `x[0][0]`. One way around this would be to only allow copy on write for lists of immutable things (excluding immutable things containing mutable things e.g. `x=[([1, 2], 3), 4]`). This is all a really significant change from the current object model.
  - viraptor 8y ago
    The first part is pretty much what I meant. I don't see a problem with nested lists though. They don't need any special treatment. Let's say you use variable->metadata->listdata scheme where listdata is prefixed with a "user counter" similar to refcount but for metadata pointers. You can modify x[0][0] then, which may or may not need to decrement the counter and make a copy of [1,2], but [a,3] doesn't have to change - it points at the same list metadata.
    - quietbritishjim 8y ago
      What I meant was what if the outer list had a ref count of two, like if x and y in the following code sample were automatically elided into a single list with a distinct ref count of 2: x = [[1, 2], 3] y = [[1, 2], 3] x[0][0] = 9 # the nested list needs to notify its owner(s) Now I think about it, I realise that this could be a harder situation to get into than I had thought at first. As the snippet above shows, it can happen if you have a a compiler/interpreter that interns entire nested lists at once. But assuming that COW lists are only formed by trying to copy existing lists, I'm not sure it's possible to end up in this situation. In real Python, if y=list(x) then changing x[0][0] should change y[0][0], as you said.
saagarjha 8y ago
A possible implementation would be to keep track of a reference count and changing behavior once the object is known to be nonunique.

I don't think copy on write would work in Python because you wouldn't know which variables to update to point to the copied list x = [] y = [] y2 = y y.append(1) # Should also update y2, but not x

viraptor 8y ago

The implementation would have to change, but it's doable. x and y would have to have different IDs, but they could point to a shared location with a cow marker set. It would likely use more memory then the current empty list, but it could potentially improve x[:] of arbitrary list where the result doesn't actually need to change later.

quietbritishjim 8y ago
Where would these unique IDs be stored? In Python, variables are just references to objects (as are entries in lists, dictionaries, etc.). So you would need some sort of intermediate object that kept the id and reference to the underlying list; the underlying list would be shared but there would be a separate stub object for every (distinct) variable. In the case of an empty list, this probably wouldn't be any smaller than the current system of having a totally separate list. Copy-on-write might make a difference in the case of large non-empty lists, but then there's another problem: you would need to trigger the copy even if something contained nested within the list changed e.g. if `x=[[1,2],3]` and you change `x[0][0]`. One way around this would be to only allow copy on write for lists of immutable things (excluding immutable things containing mutable things e.g. `x=[([1, 2], 3), 4]`). This is all a really significant change from the current object model.
- viraptor 8y ago
  The first part is pretty much what I meant. I don't see a problem with nested lists though. They don't need any special treatment. Let's say you use variable->metadata->listdata scheme where listdata is prefixed with a "user counter" similar to refcount but for metadata pointers. You can modify x[0][0] then, which may or may not need to decrement the counter and make a copy of [1,2], but [a,3] doesn't have to change - it points at the same list metadata.
  - quietbritishjim 8y ago
    What I meant was what if the outer list had a ref count of two, like if x and y in the following code sample were automatically elided into a single list with a distinct ref count of 2: x = [[1, 2], 3] y = [[1, 2], 3] x[0][0] = 9 # the nested list needs to notify its owner(s) Now I think about it, I realise that this could be a harder situation to get into than I had thought at first. As the snippet above shows, it can happen if you have a a compiler/interpreter that interns entire nested lists at once. But assuming that COW lists are only formed by trying to copy existing lists, I'm not sure it's possible to end up in this situation. In real Python, if y=list(x) then changing x[0][0] should change y[0][0], as you said.

saagarjha 8y ago

A possible implementation would be to keep track of a reference count and changing behavior once the object is known to be nonunique.