New submission from Raymond Hettinger: The lookkey routines in Object/setobject.c have logic to track the first open "freeslot" in a search.
The benefit is that new keys can reuse previously deleted slots. The benefit only occurs in cases where keys are added, then some removed, and then more added with no intervening resizes (which clear all dummy entries) and only when the newly added keys happen to land on previously deleted entries. The cost of the optimization is the extra logic in the inner search loop, an extra freeslot stackframe field that needs to be saved and restored, and extra logic on the loop exit. It also causes dummies to "leak" out of the lookkey routines so that the code in contains(), discard(), and insert() all have to check for the dummy case. This patch removes the freeslot tracking. It saves one field on the stackframe, simplifies the lookkey inner-loop logic, simplifies the lookkey "found_null" logic, it confines knowledge of dummies to just the lookkey functions, and it simplifies the code in the insert(), contains(), and discard() functions. In short, it looks like the freeslot idea was a net negative -- it optimized an uncommon case at the cost of slowing and complicating the common cases. ---------- assignee: rhettinger components: Interpreter Core files: late8.diff keywords: patch messages: 234198 nosy: rhettinger priority: low severity: normal stage: patch review status: open title: Remove dummy reuse optimization from sets type: performance versions: Python 3.5 Added file: http://bugs.python.org/file37750/late8.diff _______________________________________ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue23259> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
