Weak Dictionary Iteration Behavior in Python 3
Hi everybody, In Python 2.x when iterating over a weak key dictionary for example, the common idom for doing that was calling dictionary.keys() to ensure that a list of all objects is returned it was safe to iterate over as a weak reference could stop existing during dict iteration which of course raises a runtime error by the dict iterator. This was documented behavior and worked pretty well, with the small problem that suddenly all references in the dict wouldn't die until iteration is over because the list holds references to the object. This no longer works in Python 3 because .keys() on the weak key dictionary returns a generator over the key view of the internal dict which of course has the same problem as iterkeys in Python 2.x. The following code shows the problem:: from weakref import WeakKeyDictionary f1 = Foo() f2 = Foo() d = WeakKeyDictionary() d[f1] = 42 d[f2] = 23 i = iter(d.keys()) # or use d.keyrefs() here which has the same problem print(next(i)) del f2 print(next(i)) This example essentially dies with "RuntimeError: dictionary changed size during iteration" as soon as f2 is deleted. Iterating over weak key dictionaries might not be the most common task but I know some situations where this is necessary. Unfortunately I can't see a way to achieve that in Python 3. Regards, Armin
On Sat, Sep 13, 2008 at 1:20 PM, Armin Ronacher <armin.ronacher@active-4.com> wrote:
Hi everybody,
In Python 2.x when iterating over a weak key dictionary for example, the common idom for doing that was calling dictionary.keys() to ensure that a list of all objects is returned it was safe to iterate over as a weak reference could stop existing during dict iteration which of course raises a runtime error by the dict iterator.
This was documented behavior and worked pretty well, with the small problem that suddenly all references in the dict wouldn't die until iteration is over because the list holds references to the object.
This no longer works in Python 3 because .keys() on the weak key dictionary returns a generator over the key view of the internal dict which of course has the same problem as iterkeys in Python 2.x.
The following code shows the problem::
from weakref import WeakKeyDictionary
f1 = Foo() f2 = Foo() d = WeakKeyDictionary() d[f1] = 42 d[f2] = 23
i = iter(d.keys()) # or use d.keyrefs() here which has the same problem print(next(i)) del f2 print(next(i))
This example essentially dies with "RuntimeError: dictionary changed size during iteration" as soon as f2 is deleted.
Iterating over weak key dictionaries might not be the most common task but I know some situations where this is necessary. Unfortunately I can't see a way to achieve that in Python 3.
i = list(d.keys()) - Josiah
Josiah Carlson wrote:
On Sat, Sep 13, 2008 at 1:20 PM, Armin Ronacher wrote:
Iterating over weak key dictionaries might not be the most common task but I know some situations where this is necessary. Unfortunately I can't see a way to achieve that in Python 3.
i = list(d.keys())
Surely i = list(d) is a more reasonable way to do this. I seldom find a reason to use .keys --Scott David Daniels Scott.Daniels@Acm.Org
On Sat, Sep 13, 2008 at 5:21 PM, Scott David Daniels <Scott.Daniels@acm.org> wrote:
Josiah Carlson wrote:
On Sat, Sep 13, 2008 at 1:20 PM, Armin Ronacher wrote:
Iterating over weak key dictionaries might not be the most common task but I know some situations where this is necessary. Unfortunately I can't see a way to achieve that in Python 3.
i = list(d.keys())
Surely i = list(d) is a more reasonable way to do this. I seldom find a reason to use .keys
Definitely. I was being lazy in my use of list(d.keys()) ;) - Josiah
i = list(d.keys()) Obviously that doesn't solve the problem. list() consumes the generator one after another, objects can still die when the list is created. Imagine
Hi, Josiah Carlson <josiah.carlson <at> gmail.com> writes: the following example which uses threads:: from time import sleep from weakref import WeakKeyDictionary from threading import Thread class Foo(object): pass d = WeakKeyDictionary() l = [] for x in range(100000): obj = Foo() d[obj] = None l.append(obj) del obj def iterater(): for item in list(d.keys()): pass Thread(target=iterater).start() while True: del l[0] Regards, Armin
On Sat, Sep 13, 2008 at 2:20 PM, Armin Ronacher <armin.ronacher@active-4.com> wrote:
Hi everybody,
In Python 2.x when iterating over a weak key dictionary for example, the common idom for doing that was calling dictionary.keys() to ensure that a list of all objects is returned it was safe to iterate over as a weak reference could stop existing during dict iteration which of course raises a runtime error by the dict iterator.
This was documented behavior and worked pretty well, with the small problem that suddenly all references in the dict wouldn't die until iteration is over because the list holds references to the object.
This no longer works in Python 3 because .keys() on the weak key dictionary returns a generator over the key view of the internal dict which of course has the same problem as iterkeys in Python 2.x.
The following code shows the problem::
from weakref import WeakKeyDictionary
f1 = Foo() f2 = Foo() d = WeakKeyDictionary() d[f1] = 42 d[f2] = 23
i = iter(d.keys()) # or use d.keyrefs() here which has the same problem print(next(i)) del f2 print(next(i))
This example essentially dies with "RuntimeError: dictionary changed size during iteration" as soon as f2 is deleted.
Iterating over weak key dictionaries might not be the most common task but I know some situations where this is necessary. Unfortunately I can't see a way to achieve that in Python 3.
IMO, this is a deeper problem than suggested. As far as I know, python does not (and should not) make promises as to when it'll collect object. We should expect weakrefs to be cleared at random points, and code defensively. One approach I've used before is to enqueue all the cleared weakrefs, then process that queue when the WeakKeyDictionary is modified. -- Adam Olsen, aka Rhamphoryncus
IMO, this is a deeper problem than suggested. As far as I know, python does not (and should not) make promises as to when it'll collect object. We should expect weakrefs to be cleared at random points, and code defensively. It doesn't promise when objects are collected and that's not the problem here. The main problem is that the old solution for weakrefs relayed on
Hi, Adam Olsen <rhamph <at> gmail.com> writes: the fact that .keys() was considered atomic. I don't say it has to become again, but the weak dictionaries have to somehow counter that problem. They could for example only remove items from the internal dict if no dict view to that dict is alive. Speaking of atom keys() / values() / items() operations: I guess we will see more of those problems in threaded situations when people start to convert code over to Python. I've seen quite a few situations where code relays on keys() holding the interpreter lock. Regards, Armin
Armin Ronacher wrote:
Speaking of atom keys() / values() / items() operations: I guess we will see more of those problems in threaded situations when people start to convert code over to Python. I've seen quite a few situations where code relays on keys() holding the interpreter lock.
list(iter) doesn't re-enter the eval loop if the iterator is written in C and hence won't let go of the GIL. As I believe the dict views in 3.0 are all C classes, I'd like to see a failing test case along these lines that doesn't involve a dict subclass and code written in Python. Note that I'm not saying that I know for certain that there aren't any problems with list(d.keys()) that aren't seen with the direct list conversion in 2.x - I'm just saying it may not be as easy to provoke such problems as it initially appears due to the way the list constructor interacts with the supplied iterable, so it is going to take an actual failing test case to convince me. Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia --------------------------------------------------------------- http://www.boredomandlaziness.org
Nick Coghlan schrieb:
Armin Ronacher wrote:
Speaking of atom keys() / values() / items() operations: I guess we will see more of those problems in threaded situations when people start to convert code over to Python. I've seen quite a few situations where code relays on keys() holding the interpreter lock.
list(iter) doesn't re-enter the eval loop if the iterator is written in C and hence won't let go of the GIL. As I believe the dict views in 3.0 are all C classes, I'd like to see a failing test case along these lines that doesn't involve a dict subclass and code written in Python.
WeakKeyDictionary.keys() iterates over its .data dictionary's keys() instead of list(data.keys()). Therefore, the user of WeakKeyDictionary has no chance to do list(keys()) without running Python code. Georg -- Thus spake the Lord: Thou shalt indent with four spaces. No more, no less. Four shall be the number of spaces thou shalt indent, and the number of thy indenting shall be four. Eight shalt thou not indent, nor either indent thou two, excepting that thou then proceed to four. Tabs are right out.
Georg Brandl wrote:
Nick Coghlan schrieb:
Speaking of atom keys() / values() / items() operations: I guess we will see more of those problems in threaded situations when people start to convert code over to Python. I've seen quite a few situations where code relays on keys() holding the interpreter lock.
Armin Ronacher wrote: list(iter) doesn't re-enter the eval loop if the iterator is written in C and hence won't let go of the GIL. As I believe the dict views in 3.0 are all C classes, I'd like to see a failing test case along these lines that doesn't involve a dict subclass and code written in Python.
WeakKeyDictionary.keys() iterates over its .data dictionary's keys() instead of list(data.keys()). Therefore, the user of WeakKeyDictionary has no chance to do list(keys()) without running Python code.
Ouch, there's the dict subclass with Python code that I was asking for before I got concerned (I forgot that the weakref module is only partially implemented in C). I agree this is a problem, but I'm struggling to think of possible solutions that aren't either horrendously complicated or completely contrary to the idea of view-based dicts. Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia --------------------------------------------------------------- http://www.boredomandlaziness.org
Nick Coghlan schrieb:
Georg Brandl wrote:
Nick Coghlan schrieb:
Speaking of atom keys() / values() / items() operations: I guess we will see more of those problems in threaded situations when people start to convert code over to Python. I've seen quite a few situations where code relays on keys() holding the interpreter lock.
Armin Ronacher wrote: list(iter) doesn't re-enter the eval loop if the iterator is written in C and hence won't let go of the GIL. As I believe the dict views in 3.0 are all C classes, I'd like to see a failing test case along these lines that doesn't involve a dict subclass and code written in Python.
WeakKeyDictionary.keys() iterates over its .data dictionary's keys() instead of list(data.keys()). Therefore, the user of WeakKeyDictionary has no chance to do list(keys()) without running Python code.
Ouch, there's the dict subclass with Python code that I was asking for before I got concerned (I forgot that the weakref module is only partially implemented in C).
I agree this is a problem, but I'm struggling to think of possible solutions that aren't either horrendously complicated or completely contrary to the idea of view-based dicts.
In this case, what WeakKeyDictionary.keys() returns is not a view anyway, so using list(self.data.keys()) in the method seems like a good compromise. Georg -- Thus spake the Lord: Thou shalt indent with four spaces. No more, no less. Four shall be the number of spaces thou shalt indent, and the number of thy indenting shall be four. Eight shalt thou not indent, nor either indent thou two, excepting that thou then proceed to four. Tabs are right out.
Georg Brandl wrote:
In this case, what WeakKeyDictionary.keys() returns is not a view anyway, so using list(self.data.keys()) in the method seems like a good compromise.
I don't think that helps, because the implementation has to iterate over that to dereference the weak refs, and if that's done in Python code there's a chance for a weak ref to disappear in the process. -- Greg
Greg Ewing schrieb:
Georg Brandl wrote:
In this case, what WeakKeyDictionary.keys() returns is not a view anyway, so using list(self.data.keys()) in the method seems like a good compromise.
I don't think that helps, because the implementation has to iterate over that to dereference the weak refs, and if that's done in Python code there's a chance for a weak ref to disappear in the process.
Yes, but in that case the ref will simply not be there anymore. It can't be guaranteed anyway which objects will be alive at the precise moment you call keys(). In contrast, iterating over the keys() view of the dictionary one-by-one leads to an exception when one of the refs vanishes while still iterating. See Armin's test case for an example that demonstrates this. Georg -- Thus spake the Lord: Thou shalt indent with four spaces. No more, no less. Four shall be the number of spaces thou shalt indent, and the number of thy indenting shall be four. Eight shalt thou not indent, nor either indent thou two, excepting that thou then proceed to four. Tabs are right out.
Nick Coghlan <ncoghlan <at> gmail.com> writes:
I agree this is a problem, but I'm struggling to think of possible solutions that aren't either horrendously complicated or completely contrary to the idea of view-based dicts.
Keeping a count of the number of views currently alive for a given weak dict doesn't seem "horrendously complicated" (*). Once this count falls to zero, you can purge all the dead weakrefs from the dict (their keys would have been previously queued, so that purging is O(dead weakrefs) and not O(dict length)). (*) the most complicated is probably to write the view classes themselves
My thought on all this is to implement WeakKeyDictionary as a C extension and have it atomically construct and return a list for keys(). While this would not be exactly the same behaviour as an ordinary dict, I don't expect that much code would notice the difference. -- Greg
I would also like to point out that I submitted a patch related to that a couple of months ago in: http://bugs.python.org/issue839159 But it never got any attention :( I'm not sure if it is still relevant. Virgil On 13-Sep-08, at 10:20 PM, Armin Ronacher wrote:
Hi everybody,
In Python 2.x when iterating over a weak key dictionary for example, the common idom for doing that was calling dictionary.keys() to ensure that a list of all objects is returned it was safe to iterate over as a weak reference could stop existing during dict iteration which of course raises a runtime error by the dict iterator.
This was documented behavior and worked pretty well, with the small problem that suddenly all references in the dict wouldn't die until iteration is over because the list holds references to the object.
This no longer works in Python 3 because .keys() on the weak key dictionary returns a generator over the key view of the internal dict which of course has the same problem as iterkeys in Python 2.x.
The following code shows the problem::
from weakref import WeakKeyDictionary
f1 = Foo() f2 = Foo() d = WeakKeyDictionary() d[f1] = 42 d[f2] = 23
i = iter(d.keys()) # or use d.keyrefs() here which has the same problem print(next(i)) del f2 print(next(i))
This example essentially dies with "RuntimeError: dictionary changed size during iteration" as soon as f2 is deleted.
Iterating over weak key dictionaries might not be the most common task but I know some situations where this is necessary. Unfortunately I can't see a way to achieve that in Python 3.
Regards, Armin
_______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/hsoft%40hardcoded.net
participants (9)
-
Adam Olsen -
Antoine Pitrou -
Armin Ronacher -
Georg Brandl -
Greg Ewing -
Josiah Carlson -
Nick Coghlan -
Scott David Daniels -
Virgil Dupras