I have attached a new patch, that changes the way how references are being kept track of.
First of all, as I have explained in my long post today, it is important for speed that the buckets of TripleDict only keep track of the memory locations of the keys. Hence, references (weak or strong, depending on the type of keys) need to be stored somewhere else.
Previously, there was a global dictionary, that was shared by all TripleDicts. That probably was a bad idea, for the reasons you pointed out. Now, the references are stored in a dictionary that is an attribute of each TripleDict.
That has several advantages: In a single TripleDict, each key triple only occurs once. Hence, we don't need to store the references in a list addressed by a triple of memory locations, that are popped off the list when being garbage collected.
Instead, each triple of memory locations points to exactly one triple of references. The triple of references is popped off the dictionary as soon as any weak-refed member of the key triple was garbage collected. Note that the if len(L)==0: bit is not needed.
Another advantage: If the TripleDict is deallocated, then the strong references associated with the TripleDict will vanish as well, which wouldn't have been the case with the old code.
Currently, there is only one bad situation I can think of: Let P be an object that can not be weak-refed, has a TripleDict T as an attribute, is used as a key in T, and has a __del__ method. Then the reference cycle P->T->T._refcache->P will keep P alive. However, if any of the four assumptions does not hold, then P can be garbage collected. I think we can take that risk.
Is there any question of yours that I forgot to address?
I didn't do timings, but I've successfully run the doc tests.
Apply trac_715_combined.patch trac_715_local_refcache.patch #11521
