[issue29476] Simplify set_add_entry()

Change by Raymond Hettinger : -- resolution: -> fixed stage: patch review -> resolved status: open -> closed ___ Python tracker ___

[issue29476] Simplify set_add_entry()

Raymond Hettinger added the comment: New changeset 3329992e31bd0494a7d7312853f7ffd054737e27 by Raymond Hettinger in branch 'master': bpo-29476: Simplify set_add_entry() (#5175) https://github.com/python/cpython/commit/3329992e31bd0494a7d7312853f7ffd054737e27 -- _

[issue29476] Simplify set_add_entry()

Change by Raymond Hettinger : Added file: https://bugs.python.org/file47383/inner_loop_analysis.s ___ Python tracker ___ ___ Python-bugs-list

[issue29476] Simplify set_add_entry()

Raymond Hettinger added the comment: What I've decided for now is to keep the freeslot reuse logic but in a simpler form. Currently there are two optimizations for rare cases. The first is reusing a dummy entry -- we'll keep that. And the second is detecting multiple dummies in a lookup cha

[issue29476] Simplify set_add_entry()

Change by Raymond Hettinger : -- pull_requests: +5027 stage: -> patch review ___ Python tracker ___ ___ Python-bugs-list mailing lis

[issue29476] Simplify set_add_entry()

Serhiy Storchaka added the comment: I don't downvote, no. I am just unsure. I don't have enough information to say that the net benefit is positive neither that it is negative. In the face of hesitance the status quo wins. But it looks to me that in dominant cases set_add_entry() is used with

[issue29476] Simplify set_add_entry()

Raymond Hettinger added the comment: The problem with posting an idea here on the tracker while it is still in the research phase is that it will be prematurely downvoted without have fully thought it through. What I'm working on now is that opposite question. Was it ever worthwhile to add t

[issue29476] Simplify set_add_entry()

STINNER Victor added the comment: I vote -1 on set_no_dummy_reuse.diff since it doesn't show any significant speedup (3 ns on 130 ns with a std dev of 8 ns is not something significant), and makes the set type 2x slower on some corner cases. -- ___

[issue29476] Simplify set_add_entry()

Changes by STINNER Victor : -- nosy: +haypo ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python

[issue29476] Simplify set_add_entry()

INADA Naoki added the comment: I think it violates O(1). "s.add(x); s.discard(x);" loop creates dummy chain. Average chain length is determined by size of the set. So it is O(len(s)) rather than amortized O(1). -- ___ Python tracker

[issue29476] Simplify set_add_entry()

Serhiy Storchaka added the comment: I don't have good real-world example. Actually dict is used more often than set in such cases. I agree with your arguments Raymond, in particular about your ranging of cases. But even if the bad case is hundreds times more rare than the good case, the total

[issue29476] Simplify set_add_entry()

Raymond Hettinger added the comment: Serhiy, can you post your recurse() code with some sample data so that we can run some timings and get a sense of the effect on the extreme case. -- ___ Python tracker

[issue29476] Simplify set_add_entry()

Serhiy Storchaka added the comment: For the worst case the drawback is significant: $ ./python -m perf timeit -s "s = set('a%s' % i for i in range(100))" -- "s.add('test'); s.discard('test')" Unpatched: Median +- std dev: 861 ns +- 82 ns Patched:Median +- std dev: 2.81 us +- 0.18 us How l

[issue29476] Simplify set_add_entry()

Raymond Hettinger added the comment: > How this change affects this case? I would expect to see a tiny net benefit. The set.add() would be microscopically faster (because of less work finding and going back to a free slot). The set.discard() would do the same work (locating a value and marki

[issue29476] Simplify set_add_entry()

Serhiy Storchaka added the comment: Sets often are used in following pattern: def recurse(obj): if subobj not in proceeding: proceeding.add(obj) for subobj in links(obj): recurse(subobj) proceeding.discard(obj) In this case items a

[issue29476] Simplify set_add_entry()

INADA Naoki added the comment: I like this idea. -- nosy: +inada.naoki ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubs

[issue29476] Simplify set_add_entry()

New submission from Raymond Hettinger: Dummy entries created by deletions are currently handled in two places. The code in set_add_entry() tracks a freeslot to allow dummy slots to be reused when new elements are inserted. The dummies are also eliminated during resizing. The freeslot checks a