3 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 twic 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.
So in this program:
import threading
def produce():
global global_foo
local_foo = "potato"
global_foo = local_foo
def consume():
global global_foo
local_foo = global_foo
global_foo = None
if __name__ == '__main__':
produce()
thread = threading.Thread(target=consume)
thread.start()
thread.join()
What happens to the counts on the string "potato"?
In produce, the main thread creates it and puts it in a local, and increments the local count. It assigns it to a global, and increments the local count. It then drops the local when produce returns, and decrements the local count. In consume, the second thread copies the global to a local, and increments the shared count. It clears out the global, and decrements the shared count. It then drops the local when consume returns, and decrements the shared count.
That leaves the local count at 1 and the shared count at -1!
You might think that there must be special handling around globals, but that doesn't fix it. Wrap the string in a perfectly ordinary list, and put the list in the global, and you have the same problem.
I imagine this is explained in the paper by Choi et al, but i have not read it!
- Jtsummers 5y agoTwo spaces in front of each line of the code block. As written, right now, your comment is hard to parse: import threading def produce(): global global_foo local_foo = "potato" global_foo = local_foo def consume(): global global_foo local_foo = global_foo global_foo = None if __name__ == '__main__': produce() thread = threading.Thread(target=consume) thread.start() thread.join()
- ameixaseca 5y agoI couldn't find this in the design document but the only obvious solution is to track globals via the shared count. Since a global reference is part of all threads simultaneously, it cannot be treated as local. If you follow this reasoning, the operations above result in local=0/shared=0 after the last assignment.
- twic 5y agoAs i said in the comment, that doesn't work. Put a list in the global, and then push and pop the string on the list. Even better, push the string into a local list, then put that list in another local list, then put that in a global, etc. You would need to dynamically keep every object reachable from a global marked as such, and that's a non-starter.
- ameixaseca 5y agoSorry, you're right - I missed that part. I had a few assumptions in mind that obviously break down with a bit of reasoning. The algorithm from the paper you posted in another comment indeed looks more complicated than it needs to be and prone to bad performance. Judging by the design, it appears they were trying to avoid the local thread to touch the shared counter in any circumstance on the hot path, but I wonder if it would not be much simpler for the owner thread to just check a flag set by the non-owner thread and perform the unbiasing/freeing right away without going through all the queuing mechanism.
- twic 5y agoThe paper: > When the shared counter for an object becomes negative for the first time, the non-owner thread updating the counter also sets the object’s Queued flag. In addition, it puts the object in a linked list belonging to the object’s owner thread called QueuedObjects. Without any special action, this object would leak. This is because, even after all the references to the object are removed, the biased counter will not reach zero — since the shared counter is negative. As a result, the owner would trigger neither a counter merge nor a potential subsequent object deallocation. > To handle this case, BRC provides a path for the owner thread to explicitly merge the counters called the ExplicitMerge operation. Specifically, each thread has its own thread-safe QueuedObjects list. The thread owns the objects in the list. At regular intervals, a thread examines its list. For each queued object, the thread merges the object’s counters by accumulating the biased counter into the shared counter. If the sum is zero, the thread deallocates the object. Otherwise, the thread unbiases the object, and sets the Merged flag. Then, when a thread sets the shared counter to zero, it will deallocate the object. Overall, as shown in invariant I4, an owner only gives up ownership when it merges the counters. Well, that works, but it's a bit naff.