Eric Snow added the comment: It turns out the problem was that the odict resize mechanism was not getting triggered in all the cases that it should have been. dict resizes after a certain number of insertions, whether or not previous deletions have cleared out space. odict only resizes its fast lookup table when it needs to do a fast node lookup and only when the current dict keys size does not match the current size of the odict fast lookup table.
This bug is the consequence of a corner case which odict did not handle correctly. When you delete an item and then insert another, the resulting size of the dict keys is the same as the it was before the deletion. However, the insertion may have triggered a resize. This matters because when a resize happens the keys are re-inserted into the hash table. If it so happens that they key you just removed was in a slot that would have otherwise been occupied by another key (i.e. there was an earlier collision) then upon resizing that other key will be moved to its preferred slot. Here's a patch that changes odict to rely on the pointer value of dict's ma_keys (rather than on ma_keys.dk_size) to indicate the need for a resize. This works because dict creates a new keys struct every time it resizes. I'll point out that one alternative would be to track a "state" counter on dict that increments each time there's a resize. Then odict could check that rather than the ma_keys pointer value. ---------- keywords: +patch stage: -> patch review type: -> behavior Added file: http://bugs.python.org/file40126/odict-correct-resize.diff _______________________________________ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue24667> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
