Move items implemented after a2 into the new a3 section
[python.git] / Objects / dictnotes.txt
blobcb46cb120bd82feeb7134f10d3f6bc45c600d5f0
1 NOTES ON OPTIMIZING DICTIONARIES
2 ================================
5 Principal Use Cases for Dictionaries
6 ------------------------------------
8 Passing keyword arguments
9     Typically, one read and one write for 1 to 3 elements.
10     Occurs frequently in normal python code.
12 Class method lookup
13     Dictionaries vary in size with 8 to 16 elements being common.
14     Usually written once with many lookups.
15     When base classes are used, there are many failed lookups
16         followed by a lookup in a base class.
18 Instance attribute lookup and Global variables
19     Dictionaries vary in size.  4 to 10 elements are common.
20     Both reads and writes are common.
22 Builtins
23     Frequent reads.  Almost never written.
24     Size 126 interned strings (as of Py2.3b1).
25     A few keys are accessed much more frequently than others.
27 Uniquification
28     Dictionaries of any size.  Bulk of work is in creation.
29     Repeated writes to a smaller set of keys.
30     Single read of each key.
31     Some use cases have two consecutive accesses to the same key.
33     * Removing duplicates from a sequence.
34         dict.fromkeys(seqn).keys()
36     * Counting elements in a sequence.
37         for e in seqn:
38           d[e] = d.get(e,0) + 1
40     * Accumulating references in a dictionary of lists:
42         for pagenumber, page in enumerate(pages):
43           for word in page:
44             d.setdefault(word, []).append(pagenumber)
46     Note, the second example is a use case characterized by a get and set
47     to the same key.  There are similar used cases with a __contains__
48     followed by a get, set, or del to the same key.  Part of the
49     justification for d.setdefault is combining the two lookups into one.
51 Membership Testing
52     Dictionaries of any size.  Created once and then rarely changes.
53     Single write to each key.
54     Many calls to __contains__() or has_key().
55     Similar access patterns occur with replacement dictionaries
56         such as with the % formatting operator.
58 Dynamic Mappings
59     Characterized by deletions interspersed with adds and replacements.
60     Performance benefits greatly from the re-use of dummy entries.
63 Data Layout (assuming a 32-bit box with 64 bytes per cache line)
64 ----------------------------------------------------------------
66 Smalldicts (8 entries) are attached to the dictobject structure
67 and the whole group nearly fills two consecutive cache lines.
69 Larger dicts use the first half of the dictobject structure (one cache
70 line) and a separate, continuous block of entries (at 12 bytes each
71 for a total of 5.333 entries per cache line).
74 Tunable Dictionary Parameters
75 -----------------------------
77 * PyDict_MINSIZE.  Currently set to 8.
78     Must be a power of two.  New dicts have to zero-out every cell.
79     Each additional 8 consumes 1.5 cache lines.  Increasing improves
80     the sparseness of small dictionaries but costs time to read in
81     the additional cache lines if they are not already in cache.
82     That case is common when keyword arguments are passed.
84 * Maximum dictionary load in PyDict_SetItem.  Currently set to 2/3.
85     Increasing this ratio makes dictionaries more dense resulting
86     in more collisions.  Decreasing it improves sparseness at the
87     expense of spreading entries over more cache lines and at the
88     cost of total memory consumed.
90     The load test occurs in highly time sensitive code.  Efforts
91     to make the test more complex (for example, varying the load
92     for different sizes) have degraded performance.
94 * Growth rate upon hitting maximum load.  Currently set to *2.
95     Raising this to *4 results in half the number of resizes,
96     less effort to resize, better sparseness for some (but not
97     all dict sizes), and potentially doubles memory consumption
98     depending on the size of the dictionary.  Setting to *4
99     eliminates every other resize step.
101 Tune-ups should be measured across a broad range of applications and
102 use cases.  A change to any parameter will help in some situations and
103 hurt in others.  The key is to find settings that help the most common
104 cases and do the least damage to the less common cases.  Results will
105 vary dramatically depending on the exact number of keys, whether the
106 keys are all strings, whether reads or writes dominate, the exact
107 hash values of the keys (some sets of values have fewer collisions than
108 others).  Any one test or benchmark is likely to prove misleading.
110 While making a dictionary more sparse reduces collisions, it impairs
111 iteration and key listing.  Those methods loop over every potential
112 entry.  Doubling the size of dictionary results in twice as many
113 non-overlapping memory accesses for keys(), items(), values(),
114 __iter__(), iterkeys(), iteritems(), itervalues(), and update().
115 Also, every dictionary iterates at least twice, once for the memset()
116 when it is created and once by dealloc().
119 Results of Cache Locality Experiments
120 -------------------------------------
122 When an entry is retrieved from memory, 4.333 adjacent entries are also
123 retrieved into a cache line.  Since accessing items in cache is *much*
124 cheaper than a cache miss, an enticing idea is to probe the adjacent
125 entries as a first step in collision resolution.  Unfortunately, the
126 introduction of any regularity into collision searches results in more
127 collisions than the current random chaining approach.
129 Exploiting cache locality at the expense of additional collisions fails
130 to payoff when the entries are already loaded in cache (the expense
131 is paid with no compensating benefit).  This occurs in small dictionaries
132 where the whole dictionary fits into a pair of cache lines.  It also
133 occurs frequently in large dictionaries which have a common access pattern
134 where some keys are accessed much more frequently than others.  The
135 more popular entries *and* their collision chains tend to remain in cache.
137 To exploit cache locality, change the collision resolution section
138 in lookdict() and lookdict_string().  Set i^=1 at the top of the
139 loop and move the  i = (i << 2) + i + perturb + 1 to an unrolled
140 version of the loop.
142 This optimization strategy can be leveraged in several ways:
144 * If the dictionary is kept sparse (through the tunable parameters),
145 then the occurrence of additional collisions is lessened.
147 * If lookdict() and lookdict_string() are specialized for small dicts
148 and for largedicts, then the versions for large_dicts can be given
149 an alternate search strategy without increasing collisions in small dicts
150 which already have the maximum benefit of cache locality.
152 * If the use case for a dictionary is known to have a random key
153 access pattern (as opposed to a more common pattern with a Zipf's law
154 distribution), then there will be more benefit for large dictionaries
155 because any given key is no more likely than another to already be
156 in cache.
158 * In use cases with paired accesses to the same key, the second access
159 is always in cache and gets no benefit from efforts to further improve
160 cache locality.
162 Optimizing the Search of Small Dictionaries
163 -------------------------------------------
165 If lookdict() and lookdict_string() are specialized for smaller dictionaries,
166 then a custom search approach can be implemented that exploits the small
167 search space and cache locality.
169 * The simplest example is a linear search of contiguous entries.  This is
170   simple to implement, guaranteed to terminate rapidly, never searches
171   the same entry twice, and precludes the need to check for dummy entries.
173 * A more advanced example is a self-organizing search so that the most
174   frequently accessed entries get probed first.  The organization
175   adapts if the access pattern changes over time.  Treaps are ideally
176   suited for self-organization with the most common entries at the
177   top of the heap and a rapid binary search pattern.  Most probes and
178   results are all located at the top of the tree allowing them all to
179   be located in one or two cache lines.
181 * Also, small dictionaries may be made more dense, perhaps filling all
182   eight cells to take the maximum advantage of two cache lines.
185 Strategy Pattern
186 ----------------
188 Consider allowing the user to set the tunable parameters or to select a
189 particular search method.  Since some dictionary use cases have known
190 sizes and access patterns, the user may be able to provide useful hints.
192 1) For example, if membership testing or lookups dominate runtime and memory
193    is not at a premium, the user may benefit from setting the maximum load
194    ratio at 5% or 10% instead of the usual 66.7%.  This will sharply
195    curtail the number of collisions but will increase iteration time.
196    The builtin namespace is a prime example of a dictionary that can
197    benefit from being highly sparse.
199 2) Dictionary creation time can be shortened in cases where the ultimate
200    size of the dictionary is known in advance.  The dictionary can be
201    pre-sized so that no resize operations are required during creation.
202    Not only does this save resizes, but the key insertion will go
203    more quickly because the first half of the keys will be inserted into
204    a more sparse environment than before.  The preconditions for this
205    strategy arise whenever a dictionary is created from a key or item
206    sequence and the number of *unique* keys is known.
208 3) If the key space is large and the access pattern is known to be random,
209    then search strategies exploiting cache locality can be fruitful.
210    The preconditions for this strategy arise in simulations and
211    numerical analysis.
213 4) If the keys are fixed and the access pattern strongly favors some of
214    the keys, then the entries can be stored contiguously and accessed
215    with a linear search or treap.  This exploits knowledge of the data,
216    cache locality, and a simplified search routine.  It also eliminates
217    the need to test for dummy entries on each probe.  The preconditions
218    for this strategy arise in symbol tables and in the builtin dictionary.
221 Readonly Dictionaries
222 ---------------------
223 Some dictionary use cases pass through a build stage and then move to a
224 more heavily exercised lookup stage with no further changes to the
225 dictionary.
227 An idea that emerged on python-dev is to be able to convert a dictionary
228 to a read-only state.  This can help prevent programming errors and also
229 provide knowledge that can be exploited for lookup optimization.
231 The dictionary can be immediately rebuilt (eliminating dummy entries),
232 resized (to an appropriate level of sparseness), and the keys can be
233 jostled (to minimize collisions).  The lookdict() routine can then
234 eliminate the test for dummy entries (saving about 1/4 of the time
235 spent in the collision resolution loop).
237 An additional possibility is to insert links into the empty spaces
238 so that dictionary iteration can proceed in len(d) steps instead of
239 (mp->mask + 1) steps.  Alternatively, a separate tuple of keys can be
240 kept just for iteration.
243 Caching Lookups
244 ---------------
245 The idea is to exploit key access patterns by anticipating future lookups
246 based of previous lookups.
248 The simplest incarnation is to save the most recently accessed entry.
249 This gives optimal performance for use cases where every get is followed
250 by a set or del to the same key.