[Python-checkins] Fix terminology in comment and add more design rationale. (#3335)
Raymond Hettinger
webhook-mailer at python.org
Mon Sep 4 21:54:19 EDT 2017
https://github.com/python/cpython/commit/64263dfd182da4984c51ea33ebd597369d4196f3
commit: 64263dfd182da4984c51ea33ebd597369d4196f3
branch: master
author: Raymond Hettinger <rhettinger at users.noreply.github.com>
committer: GitHub <noreply at github.com>
date: 2017-09-04T18:54:16-07:00
summary:
Fix terminology in comment and add more design rationale. (#3335)
* Fix terminology in comment and add more design rationale.
* Fix extra space
files:
M Objects/setobject.c
diff --git a/Objects/setobject.c b/Objects/setobject.c
index 5c61bc71795..219e81d0baf 100644
--- a/Objects/setobject.c
+++ b/Objects/setobject.c
@@ -12,16 +12,23 @@
To improve cache locality, each probe inspects a series of consecutive
nearby entries before moving on to probes elsewhere in memory. This leaves
- us with a hybrid of linear probing and open addressing. The linear probing
+ us with a hybrid of linear probing and randomized probing. The linear probing
reduces the cost of hash collisions because consecutive memory accesses
tend to be much cheaper than scattered probes. After LINEAR_PROBES steps,
- we then use open addressing with the upper bits from the hash value. This
- helps break-up long chains of collisions.
+ we then use more of the upper bits from the hash value and apply a simple
+ linear congruential random number genearator. This helps break-up long
+ chains of collisions.
All arithmetic on hash should ignore overflow.
Unlike the dictionary implementation, the lookkey function can return
NULL if the rich comparison returns an error.
+
+ Use cases for sets differ considerably from dictionaries where looked-up
+ keys are more likely to be present. In contrast, sets are primarily
+ about membership testing where the presence of an element is not known in
+ advance. Accordingly, the set implementation needs to optimize for both
+ the found and not-found case.
*/
#include "Python.h"
More information about the Python-checkins
mailing list