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