8 ms·

> With this scheme, the reference count in each object is split in two, with one "local" count for the owner (creator) of the object and a shared count for all

by a1369209993 5y ago

> With this scheme, the reference count in each object is split in two, with one "local" count for the owner (creator) of the object and a shared count for all other threads. Since the owner has exclusive access to its count, increments and decrements can be done with fast, non-atomic instructions. Any other thread accessing the object will use atomic operations on the shared reference count. > Whenever the owning thread drops a reference to an object, it checks both reference counts against zero. If both the local and the shared count are zero, the object can be freed, since no other references exist. If the local count is zero but the shared count is not, []a special bit is set to indicate that the owning thread has dropped the object[]; any subsequent decrements of the shared count will then free the object if that count goes to zero. This seems... off. Wouldn't it work better for the owning thread to hold (exactly) one atomic reference, which is released (using the same decref code as other threads) when the local reference count goes to zero? Edit: I probably should have explicitly noted that, as jetrink points out, the object is initialized with a atomic refcount of one (the "local refcount is nonzero" reference), and destroyed when the atomic refcount is one and to-be-decremented, so a purely local object never has atomic writes.

cogman10 5y ago
Yeah, I'm not exactly getting all the complexity here. I'm digging the 2 reference counters, that makes sense to me, but I don't know why it isn't something more like: "every time a new thread takes a reference, atomic +1, every time a new thread's local count hits 0, atomic -1. If the shared reference is 0, free". IDK what special purpose the flags are serving here.
- deleted 5y ago
  [deleted]
- jeremyjh 5y ago
  Most objects are never shared so there would be a performance impact from incrementing (and decrementing) an atomic counter even just once.
  - jetrink 5y ago
    That is true, but what if the shared count were initialized to one and the creator thread frees an object when the shared count is equal to one and the local count is decremented zero? (Since it knows it holds one shared reference.) Then the increment and decrement would be avoided for non-shared objects.
    - a1369209993 5y ago
      I probably should have mentioned that explicitly; edited.
- kzrdude 5y ago
  To have one local count per thread would add memory overhead, I think? In his solution there are only two counters per object, local and shared. Any other thread can't know if it's the first time or not it's taking a reference to an object.
kccqzy 5y ago
I like this idea. In fact another possibility is to have a thread-local reference count for each thread that uses the object which can use fast non-atomic operations, and then each thread can use a shared atomic reference count, that counts how many threads use the object. When each thread-local count goes to zero, the shared count is decremented by one. This way, if an object is created in one thread and transferred to another, the other thread wouldn't even need to do a lot of atomic reference count manipulations. There wouldn't be surprising behavior in which different threads run the same code with different speed, just by virtue of whether they created the objects or not.
- Fronzie 5y ago
  Good point. Windows COM did not follow your suggestion, leading to all sorts of awkwardness in applications that have compute- and ui-threads and share objects between the two. Object destruction becomes non-predictable and can hold up a UI thread.
- twic 5y ago
  How would the storage be laid out? With the proposed scheme, there are two counters (and, i assume, the ID of the owning thread), so a small fixed-size structure, which can sit directly in the object header. With your scheme, you need a variable and unbounded number of counters. Where would they go?
  - wishawa 5y ago
    Maybe each thread could have a mapping storing the number of references held (in that thread) for each object? This way only the atomic refcount has to be in the object header. Also I don’t think there would be an owning thread at all with this idea, so no ID needed.
dennisafa 5y ago
I think that idea was mentioned earlier in the article: > The simplest change would be to replace non-atomic reference count operations with their atomic equivalents. However, atomic instructions are more expensive than their non-atomic counterparts. Replacing Py_INCREF and Py_DECREF with atomic variants would result in a 60% average slowdown on the pyperformance benchmark suite.
- a1369209993 5y ago
  > to replace non-atomic reference count operations with their atomic equivalents. Nope, my proposal still uses two reference counts (one atomic, one local); it just avoids having a seperate flag bit to indicate that the owning thread is done.
  - bonzini 5y ago
    Adding one shared reference doesn't work because the number of shared references can be negative (if non-owning threads end up removing more references than they add: think of the owner storing objects in a collection and a bunch of consumers that pick them and replace them with None). The meaning of the extra bit is "the object doesn't have an owning thread anymore, and the local refcount will always be zero; and the shared refcount cannot go negative anymore so a zero really means the object can be freed". A second bit is used if a non-owning thread notices local+shared=0. In that case the object is placed on a list that the owning thread will go through every now and then. For all objects in the list, the owning thread transfers the local references to the shared refcount, disowns the object (by setting the first special bit). Then, according to the rules for the first social bit, if the resulting shared refcount is still zero the object can be freed.
jeremyjh 5y ago
Threads don’t hold references - other objects do and we have to know how many do. If threads held a reference it might never be released. Since most objects are never shared we wouldn’t want to increment an atomic counter even once for those.
- a1369209993 5y ago
  I don't think the objection you're actually making is valid (the extra atomic reference is just a representation of the fact that the local refcount is nonzero), but come to think of it, even in the original version, how the heck does a thread know whether a reference held by (say) a dictionary that is itself accesible to multiple threads was increfed by the owning thread or another thread?
- kccqzy 5y ago
  I think you have misunderstood GP. GP is trying to say, the thread that created the object has a remote (atomic) reference count of 1, in addition to a local reference count of 1. the remote reference count is simply initialized to be 1. During this initialization operation no atomic operation is used. The only atomic operation is during destruction: the local reference count is decremented non-atomically, and then if it is zero, we need an atomic memory_order_release decrement for the remote reference count.
  - a1369209993 5y ago
    > and then if it is zero, we need an atomic memory_order_release decrement for the remote reference count. Actually, we don't. We need a atomic load, but if the results of that load indicate that we're destroying the last reference to the object (which does need to be more complicated than just a extra remote reference; see [0] and [1]), we can just destroy the object as-is without actually doing a atomic store, because by definition there is no reference to the object through which another thread could inspect the remote refcount. (If there was, our reference wouldn't be the last one.) 0: https://news.ycombinator.com/item?id=28883218 https://news.ycombinator.com/item?id=28883218 1: https://sci-hub.se/https://dl.acm.org/doi/10.1145/3243176.3243195 https://sci-hub.se/https://dl.acm.org/doi/10.1145/3243176.32...
deleted 5y ago
[deleted]
morelisp 5y ago
This seems like it would be less efficient if most objects don't escape their owning thread (you would need one atomic inc/dec versus zero), which is probably true of most objects.
- a1369209993 5y ago
  Sorry, should have been more clear; edited.
Someone 5y ago
> which is released (using the same decref code as other threads) when the local reference count goes to zero? (I may misunderstand your remark, as ‘releasing’ is a bit ambiguous. It could mean decreasing reference count and freeing the memory if the count goes to zero or just plain freeing the memory) The local ref count can go to zero while other threads still have references to the object (e.g. when the allocating thread sends an object as a message to another thread and, knowing the message arrived, releases it), so freeing the memory when it does would be a serious bug. Also, the shared ref count can go negative. From the paper: > As an example, consider two threads T1 and T2. Thread T1 creates an object and sets itself as the owner of it. It points a global pointer to the object, setting the biased counter to one. Then, T2 overwrites the global pointer, decrementing the shared counter of the object. As a result, the shared counter becomes negative. That can’t happen with the biased counter because, when it would end up going negative, the object gets unbiased, and the shared counter gets decreased instead. That asymmetry is what ensures that only a single thread updates the biased counter, so that no locks are needed to do that.
- a1369209993 5y ago
  > I may misunderstand your remark, as 'releasing' is a bit ambiguous. The reference is released; ie the (atomic) reference count is decremented (and the object is only freed if that caused the atomic reference count to go to zero). > From the paper I missed that there was a paper and was referring to the proposed implementation in python that was described in TFA. IIUC, biased refcount (in paper) is local (in my description), and shared is atomic, correct? > the shared ref count can go negative And that makes sense. Thanks. (And also explains how to deal with references added by one thread and removed by another, when one of those threads is the object owner.)
AgentME 5y ago
>Edit: I probably should have explicitly noted that, as jetrink points out, the object is initialized with a atomic refcount of one (the "local refcount is nonzero" reference), and destroyed when the atomic refcount is one and to-be-decremented, so a purely local object never has atomic writes. I think you're under the impression that the refcount would only ever need to be incremented if the object was shared to another thread, but that's not the case. The refcount isn't a count of how many threads have a reference to the object; it's a count of how many objects and closures have a reference to the object. Even objects that never leave their creator thread will be likely to have their reference count incremented and decremented a few times over their life.
- a1369209993 5y ago
  > Even objects that never leave their creator thread will be likely to have their reference count incremented and decremented a few times over their life. I think you're under the impression that there's only one refcount. The point of the original design (and this one) is that there are two refcounts: one that's updated only by the thread that created the object, and therefor doesn't need to use slow atomic accesses, and one that's updated atomically, and therefor can be adjusted by arbitrary threads.
  - AgentME 5y ago
    Oh, I misunderstood you then. I thought you were trying to get rid of the local refcount and make the atomic one handle its job too, but what you're suggesting is a possible simplification of the logic that detects when it's time to destroy the object. That makes sense, just seems more minor than I thought you were going at and I guess I missed it.
    - a1369209993 5y ago
      I was also under the impression that the creator-thread-is-done-with-the-object bit was in a seperate word (TFA describes it as a "special" bit, but according to the paper[0] it's actually in the same word as the atomic refcount), and was trying to eliminate that. 0: https://sci-hub.se/https://dl.acm.org/doi/10.1145/3243176.3243195 https://sci-hub.se/https://dl.acm.org/doi/10.1145/3243176.32...
johntb86 5y ago
Suppose thread A (the owner) keeps a reference, but also puts another reference in a global variable. This would increment its local refcount to 1 and have a shared refcount of 1. Then thread B clears the global variable. With your scheme the local refcount would be 1 but the shared refcount would be 0, so thread B would destroy the object even though it's referenced by thread A.
wishawa 5y ago
I think yours is a much cleaner design. In the original plan, if the owning thread just set the special bit, but before that set is propagated, another thread drops the shared refcount to zero, the object would never be released, would it? EDIT: never mind the question, I just read that the special bit is atomic.
- a1369209993 5y ago
  Having been pointed to the actual paper[0] by Someone[1], the special bit (effectivly a local-refcount-is-nonzero flag) is in the same atomic word as the shared refcount, which I missed from the description of the python implementation. The shared refcount can go negative, but the (shared refcount,local-is-nonzero) tuple can never be (0,false) while the object is referenced. 0: https://sci-hub.se/https://dl.acm.org/doi/10.1145/3243176.3243195 https://sci-hub.se/https://dl.acm.org/doi/10.1145/3243176.32... 1: https://news.ycombinator.com/item?id=28883218 https://news.ycombinator.com/item?id=28883218 (seriously, upvote this; it should be higher in the list of responses, since it actually properly refutes my original comment)

cogman10 5y ago

Yeah, I'm not exactly getting all the complexity here. I'm digging the 2 reference counters, that makes sense to me, but I don't know why it isn't something more like: "every time a new thread takes a reference, atomic +1, every time a new thread's local count hits 0, atomic -1. If the shared reference is 0, free". IDK what special purpose the flags are serving here.

deleted 5y ago
[deleted]
jeremyjh 5y ago
Most objects are never shared so there would be a performance impact from incrementing (and decrementing) an atomic counter even just once.
- jetrink 5y ago
  That is true, but what if the shared count were initialized to one and the creator thread frees an object when the shared count is equal to one and the local count is decremented zero? (Since it knows it holds one shared reference.) Then the increment and decrement would be avoided for non-shared objects.
  - a1369209993 5y ago
    I probably should have mentioned that explicitly; edited.
kzrdude 5y ago
To have one local count per thread would add memory overhead, I think? In his solution there are only two counters per object, local and shared. Any other thread can't know if it's the first time or not it's taking a reference to an object.

kccqzy 5y ago

I like this idea. In fact another possibility is to have a thread-local reference count for each thread that uses the object which can use fast non-atomic operations, and then each thread can use a shared atomic reference count, that counts how many threads use the object. When each thread-local count goes to zero, the shared count is decremented by one. This way, if an object is created in one thread and transferred to another, the other thread wouldn't even need to do a lot of atomic reference count manipulations. There wouldn't be surprising behavior in which different threads run the same code with different speed, just by virtue of whether they created the objects or not.

Fronzie 5y ago
Good point. Windows COM did not follow your suggestion, leading to all sorts of awkwardness in applications that have compute- and ui-threads and share objects between the two. Object destruction becomes non-predictable and can hold up a UI thread.
twic 5y ago
How would the storage be laid out? With the proposed scheme, there are two counters (and, i assume, the ID of the owning thread), so a small fixed-size structure, which can sit directly in the object header. With your scheme, you need a variable and unbounded number of counters. Where would they go?
- wishawa 5y ago
  Maybe each thread could have a mapping storing the number of references held (in that thread) for each object? This way only the atomic refcount has to be in the object header. Also I don’t think there would be an owning thread at all with this idea, so no ID needed.

dennisafa 5y ago

I think that idea was mentioned earlier in the article: > The simplest change would be to replace non-atomic reference count operations with their atomic equivalents. However, atomic instructions are more expensive than their non-atomic counterparts. Replacing Py_INCREF and Py_DECREF with atomic variants would result in a 60% average slowdown on the pyperformance benchmark suite.

a1369209993 5y ago
> to replace non-atomic reference count operations with their atomic equivalents. Nope, my proposal still uses two reference counts (one atomic, one local); it just avoids having a seperate flag bit to indicate that the owning thread is done.
- bonzini 5y ago
  Adding one shared reference doesn't work because the number of shared references can be negative (if non-owning threads end up removing more references than they add: think of the owner storing objects in a collection and a bunch of consumers that pick them and replace them with None). The meaning of the extra bit is "the object doesn't have an owning thread anymore, and the local refcount will always be zero; and the shared refcount cannot go negative anymore so a zero really means the object can be freed". A second bit is used if a non-owning thread notices local+shared=0. In that case the object is placed on a list that the owning thread will go through every now and then. For all objects in the list, the owning thread transfers the local references to the shared refcount, disowns the object (by setting the first special bit). Then, according to the rules for the first social bit, if the resulting shared refcount is still zero the object can be freed.

jeremyjh 5y ago

Threads don’t hold references - other objects do and we have to know how many do. If threads held a reference it might never be released. Since most objects are never shared we wouldn’t want to increment an atomic counter even once for those.

a1369209993 5y ago
I don't think the objection you're actually making is valid (the extra atomic reference is just a representation of the fact that the local refcount is nonzero), but come to think of it, even in the original version, how the heck does a thread know whether a reference held by (say) a dictionary that is itself accesible to multiple threads was increfed by the owning thread or another thread?
kccqzy 5y ago
I think you have misunderstood GP. GP is trying to say, the thread that created the object has a remote (atomic) reference count of 1, in addition to a local reference count of 1. the remote reference count is simply initialized to be 1. During this initialization operation no atomic operation is used. The only atomic operation is during destruction: the local reference count is decremented non-atomically, and then if it is zero, we need an atomic memory_order_release decrement for the remote reference count.
- a1369209993 5y ago
  > and then if it is zero, we need an atomic memory_order_release decrement for the remote reference count. Actually, we don't. We need a atomic load, but if the results of that load indicate that we're destroying the last reference to the object (which does need to be more complicated than just a extra remote reference; see [0] and [1]), we can just destroy the object as-is without actually doing a atomic store, because by definition there is no reference to the object through which another thread could inspect the remote refcount. (If there was, our reference wouldn't be the last one.) 0: https://news.ycombinator.com/item?id=28883218 https://news.ycombinator.com/item?id=28883218 1: https://sci-hub.se/https://dl.acm.org/doi/10.1145/3243176.3243195 https://sci-hub.se/https://dl.acm.org/doi/10.1145/3243176.32...

deleted 5y ago

[deleted]

morelisp 5y ago

This seems like it would be less efficient if most objects don't escape their owning thread (you would need one atomic inc/dec versus zero), which is probably true of most objects.

a1369209993 5y ago
Sorry, should have been more clear; edited.

Someone 5y ago

> which is released (using the same decref code as other threads) when the local reference count goes to zero? (I may misunderstand your remark, as ‘releasing’ is a bit ambiguous. It could mean decreasing reference count and freeing the memory if the count goes to zero or just plain freeing the memory) The local ref count can go to zero while other threads still have references to the object (e.g. when the allocating thread sends an object as a message to another thread and, knowing the message arrived, releases it), so freeing the memory when it does would be a serious bug. Also, the shared ref count can go negative. From the paper: > As an example, consider two threads T1 and T2. Thread T1 creates an object and sets itself as the owner of it. It points a global pointer to the object, setting the biased counter to one. Then, T2 overwrites the global pointer, decrementing the shared counter of the object. As a result, the shared counter becomes negative. That can’t happen with the biased counter because, when it would end up going negative, the object gets unbiased, and the shared counter gets decreased instead. That asymmetry is what ensures that only a single thread updates the biased counter, so that no locks are needed to do that.

a1369209993 5y ago
> I may misunderstand your remark, as 'releasing' is a bit ambiguous. The reference is released; ie the (atomic) reference count is decremented (and the object is only freed if that caused the atomic reference count to go to zero). > From the paper I missed that there was a paper and was referring to the proposed implementation in python that was described in TFA. IIUC, biased refcount (in paper) is local (in my description), and shared is atomic, correct? > the shared ref count can go negative And that makes sense. Thanks. (And also explains how to deal with references added by one thread and removed by another, when one of those threads is the object owner.)

AgentME 5y ago

>Edit: I probably should have explicitly noted that, as jetrink points out, the object is initialized with a atomic refcount of one (the "local refcount is nonzero" reference), and destroyed when the atomic refcount is one and to-be-decremented, so a purely local object never has atomic writes. I think you're under the impression that the refcount would only ever need to be incremented if the object was shared to another thread, but that's not the case. The refcount isn't a count of how many threads have a reference to the object; it's a count of how many objects and closures have a reference to the object. Even objects that never leave their creator thread will be likely to have their reference count incremented and decremented a few times over their life.

a1369209993 5y ago
> Even objects that never leave their creator thread will be likely to have their reference count incremented and decremented a few times over their life. I think you're under the impression that there's only one refcount. The point of the original design (and this one) is that there are two refcounts: one that's updated only by the thread that created the object, and therefor doesn't need to use slow atomic accesses, and one that's updated atomically, and therefor can be adjusted by arbitrary threads.
- AgentME 5y ago
  Oh, I misunderstood you then. I thought you were trying to get rid of the local refcount and make the atomic one handle its job too, but what you're suggesting is a possible simplification of the logic that detects when it's time to destroy the object. That makes sense, just seems more minor than I thought you were going at and I guess I missed it.
  - a1369209993 5y ago
    I was also under the impression that the creator-thread-is-done-with-the-object bit was in a seperate word (TFA describes it as a "special" bit, but according to the paper[0] it's actually in the same word as the atomic refcount), and was trying to eliminate that. 0: https://sci-hub.se/https://dl.acm.org/doi/10.1145/3243176.3243195 https://sci-hub.se/https://dl.acm.org/doi/10.1145/3243176.32...

johntb86 5y ago

Suppose thread A (the owner) keeps a reference, but also puts another reference in a global variable. This would increment its local refcount to 1 and have a shared refcount of 1. Then thread B clears the global variable. With your scheme the local refcount would be 1 but the shared refcount would be 0, so thread B would destroy the object even though it's referenced by thread A.

wishawa 5y ago

I think yours is a much cleaner design. In the original plan, if the owning thread just set the special bit, but before that set is propagated, another thread drops the shared refcount to zero, the object would never be released, would it? EDIT: never mind the question, I just read that the special bit is atomic.

a1369209993 5y ago
Having been pointed to the actual paper[0] by Someone[1], the special bit (effectivly a local-refcount-is-nonzero flag) is in the same atomic word as the shared refcount, which I missed from the description of the python implementation. The shared refcount can go negative, but the (shared refcount,local-is-nonzero) tuple can never be (0,false) while the object is referenced. 0: https://sci-hub.se/https://dl.acm.org/doi/10.1145/3243176.3243195 https://sci-hub.se/https://dl.acm.org/doi/10.1145/3243176.32... 1: https://news.ycombinator.com/item?id=28883218 https://news.ycombinator.com/item?id=28883218 (seriously, upvote this; it should be higher in the list of responses, since it actually properly refutes my original comment)