From 258dfebfb4286afe176cce1d6f6245d53112fc1a Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Sun, 4 May 2003 21:25:19 +0000 Subject: * Note how dummy entry re-use benefits use cases with interspersed deletes and adds. * Note that dictionary iteration is negatively impacted by additional sparseness. --- Objects/dictnotes.txt | 12 +++++++++++- 1 file changed, 11 insertions(+), 1 deletion(-) diff --git a/Objects/dictnotes.txt b/Objects/dictnotes.txt index dcfb7a0..46dabb7 100644 --- a/Objects/dictnotes.txt +++ b/Objects/dictnotes.txt @@ -43,6 +43,10 @@ Membership Testing Similar access patterns occur with replacement dictionaries such as with the % formatting operator. +Dynamic Mappings + Characterized by deletions interspersed with adds and replacments. + Performance benefits greatly from the re-use of dummy entries. + Data Layout (assuming a 32-bit box with 64 bytes per cache line) ---------------------------------------------------------------- @@ -91,6 +95,12 @@ keys are all strings, whether reads or writes dominate, the exact hash values of the keys (some sets of values have fewer collisions than others). Any one test or benchmark is likely to prove misleading. +While making a dictionary more sparse reduces collisions, it impairs +iteration and key listing. Those methods loop over every potential +entry. Doubling the size of dictionary results in twice as many +non-overlapping memory accesses for keys(), items(), values(), +__iter__(), iterkeys(), iteritems(), itervalues(), and update(). + Results of Cache Locality Experiments ------------------------------------- @@ -165,7 +175,7 @@ sizes and access patterns, the user may be able to provide useful hints. 1) For example, if membership testing or lookups dominate runtime and memory is not at a premium, the user may benefit from setting the maximum load ratio at 5% or 10% instead of the usual 66.7%. This will sharply - curtail the number of collisions. + curtail the number of collisions but will increase iteration time. 2) Dictionary creation time can be shortened in cases where the ultimate size of the dictionary is known in advance. The dictionary can be -- cgit v0.12