[issue10408] Denser dicts and linear probing

Raymond Hettinger added the comment: Agreed. This doesn't make sense for the compact dict implementation. -- resolution: -> out of date stage: -> resolved status: pending -> closed ___ Python tracker ___

[issue10408] Denser dicts and linear probing

Serhiy Storchaka added the comment: I think this issue is outdated. Liner probing doesn't make much sense for current dict implementation. -- status: open -> pending ___ Python tracker

[issue10408] Denser dicts and linear probing

INADA Naoki added the comment: > - make dicts denser by making the resize factor 2 instead of 4 for small dicts This had been implemented already when I start compact dict. > - improve cache locality on collisions by using linear probing set does this. But dict doesn't do it for now. In case

[issue10408] Denser dicts and linear probing

Serhiy Storchaka added the comment: What is the status of this issue in the light of compact dict implementation? -- nosy: +inada.naoki ___ Python tracker ___ ___

[issue10408] Denser dicts and linear probing

Jim Jewett added the comment: FWIW, doing a linear probe only within a cache line (changing the 1's bit) before applying perturb might also be useful -- and the results may change if the size of a dictentry were reduced. (Mark Shannon's now-integrated patch doesn't actually do that for the k

[issue10408] Denser dicts and linear probing

Changes by Serhiy Storchaka : -- nosy: +storchaka ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.p

[issue10408] Denser dicts and linear probing

Charles-François Natali added the comment: This paper might be of interest: http://www.siam.org/meetings/alenex05/papers/13gheileman.pdf Basically, it concludes that most of the time, there's no speedup to be gained from the increased cached locality incurred by linear probing when the input

[issue10408] Denser dicts and linear probing

Changes by John O'Connor : -- nosy: +jcon ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.or

[issue10408] Denser dicts and linear probing

Antoine Pitrou added the comment: > See Objects/dictnotes.txt for some of the results. > I spent about full month trying to optimize dict > performance either by tuning parameters or using > different algorithms. Well, I've seen those results. I'm asking about which workloads or benchmarks were

[issue10408] Denser dicts and linear probing

Raymond Hettinger added the comment: See Objects/dictnotes.txt for some of the results. I spent about full month trying to optimize dict performance either by tuning parameters or using different algorithms. There were a couple wins that were not implemented. 1) Allowing users to control insert

[issue10408] Denser dicts and linear probing

Antoine Pitrou added the comment: > FWIW, one way to make a dict denser without increasing the number of > probes is to use Brent's Variation of Algorithm D in Knuth. That > optimizes the insertion order to minimize the number of collisions and > lets you pack well over two-thirds full without

[issue10408] Denser dicts and linear probing

Raymond Hettinger added the comment: FWIW, one way to make a dict denser without increasing the number of probes is to use Brent's Variation of Algorithm D in Knuth. That optimizes the insertion order to minimize the number of collisions and lets you pack well over two-thirds full without de

[issue10408] Denser dicts and linear probing

Antoine Pitrou added the comment: > My previous experiments along these lines showed it was a dead-end. > The number of probes was the most important factor and beat-out any > effort to improve cache utilization from increased density. Can you describe your experiments? What workloads or benc

[issue10408] Denser dicts and linear probing

Raymond Hettinger added the comment: My previous experiments along these lines showed it was a dead-end. The number of probes was the most important factor and beat-out any effort to improve cache utilization from increased density. Doing extra work (more probes) in order to improve cache

[issue10408] Denser dicts and linear probing

Antoine Pitrou added the comment: Here is a benchmark adapted from another bug entry (I merely adapted the dict sizes in order to better exhibit the performance degradation when the CPU cache becomes too small to hold the whole dict). Results without the patch: 1 words (9092 keys)

[issue10408] Denser dicts and linear probing

New submission from Antoine Pitrou : This is a patch experiment which does two things: - make dicts denser by making the resize factor 2 instead of 4 for small dicts - improve cache locality on collisions by using linear probing It should be noted that these two changes are not independent. Impr