Agreed about fixing the other issues.  I'm still unclear that we need anything more than just the _remove_dead_weakref function to do that, but also, I don't see a particular problem with adding self._commit_removals() a bit everywhere.

About the O(1) expectation for len(): it's still unclear if it is better to give a precise answer or if an over-estimate is usually enough.  I can see of no reasonable use for a precise answer---e.g. code like this

    while len(d) > 0:
        do_stuff(d.popitem())

is broken anyway, because a weakref might really die between len(d) and d.popitem().  But on the other hand it makes tests behave strangely.  Maybe the correct answer is that such tests are wrong---then I'd be happy to revert the PyPy-specific change to __len__() and fix the test instead.  Or maybe weakdicts should always raise in __len__(), and instead have a method .length_upper_bound().