New submission from Raymond Hettinger: First draft of patch to switch from a table[(i+j)&mask] style of entry calculation to an entry++ style. The entry computation simplifies from add/shl4/and/lea to a single add16. To do this, the linear probes are limited to the length of table rather than wrapping-around.
I haven't timed this one yet (have just looked at the assembly) or worked through the implications. The new approach is a little less attractive but may be easier to reason about than the mask wrap-around. Also, it disadvantages small sets where the wrap-around property assured that the linear probes would always fine a hit without any entry being checked more than once. There is a extra setup time before the linear probes to compute the limit. Also, since the loop size is now variable instead of fixed, the inner loop for set_insert_clean() no longer gets unrolled by either GCC or CLANG. With the change, the inner loop of set_insert_clean() is very tight: L436: addq $16, %rax #, entry entry < limit cmpq %rdx, %rax # limit, entry ja L399 #, entry->key == NULL cmpq $0, (%rax) #,* entry jne L436 The code for lookkey() is also tight (though I can't tell why the entry->key gets loaded from memory twice): L102: cmpq %r15, %r13 # tmp170, D.12706 entry->key == dummy jne L103 #, testq %r12, %r12 # freeslot cmove %r14, %r12 # entry -> freeslot L103: addq $16, %r14 #, entry entry++ cmpq %r14, %rbx # entry, limit jb L146 #, movq (%r14), %r13 # MEM[base: entry_65, offset: 0B], D.12706 testq %r13, %r13 # D.12706 entry->key == NULL je L147 #, cmpq %rbp, 8(%r14) # hash, MEM[base: entry_104, offset: 8B] je L148 #, entry->hash == hash ? movq (%r14), %r13 # MEM[base: entry_104, offset: 0B], D.12706 jmp L102 # ---------- assignee: rhettinger components: Interpreter Core files: limit.diff keywords: patch messages: 234308 nosy: rhettinger priority: low severity: normal stage: patch review status: open title: Tighten-up search loops in sets type: performance versions: Python 3.5 Added file: http://bugs.python.org/file37773/limit.diff _______________________________________ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue23269> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com