cpython-lru_cache-weakref: Objects/dictnotes.txt annotate

annotate Objects/dictnotes.txt @ 79675:c0a2294de787 2.7

Issue #16199: Backport 2to3 typo fix from 3.2.

author	Chris Jerdonek <chris.jerdonek@gmail.com>
date	Thu, 11 Oct 2012 16:15:46 -0700
parents	48b6d015340a
children	6e5855854a2e

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

Mercurial > cpython-lru_cache-weakref

annotate Objects/dictnotes.txt @ 79675:c0a2294de787 2.7