Hmm. Here's a naughty, and maybe dangerous, theory. Obtain a "memory deallocation lock". While it is held (by any thread - it's a guard, more than a lock), Py_DECREF will not actually deallocate memory - objects can fall to zero references without being wiped. Once the lock/guard is freed/cleared, anything that had fallen to zero is now deallocated. This probably would mean stuffing them onto a list of "doomed objects", and upon release of the guard, any doomed objects that still have no refs would get deallocated.