| NOTES ON DICTIONARIES |
| ================================ |
| |
| Principal Use Cases for Dictionaries |
| ------------------------------------ |
| |
| Passing keyword arguments |
| Typically, one read and one write for 1 to 3 elements. |
| Occurs frequently in normal python code. |
| |
| Class method lookup |
| Dictionaries vary in size with 8 to 16 elements being common. |
| Usually written once with many lookups. |
| When base classes are used, there are many failed lookups |
| followed by a lookup in a base class. |
| |
| Instance attribute lookup and Global variables |
| Dictionaries vary in size. 4 to 10 elements are common. |
| Both reads and writes are common. |
| |
| Builtins |
| Frequent reads. Almost never written. |
| About 150 interned strings (as of Py3.3). |
| A few keys are accessed much more frequently than others. |
| |
| Uniquification |
| Dictionaries of any size. Bulk of work is in creation. |
| Repeated writes to a smaller set of keys. |
| Single read of each key. |
| Some use cases have two consecutive accesses to the same key. |
| |
| * Removing duplicates from a sequence. |
| dict.fromkeys(seqn).keys() |
| |
| * Counting elements in a sequence. |
| for e in seqn: |
| d[e] = d.get(e,0) + 1 |
| |
| * Accumulating references in a dictionary of lists: |
| |
| for pagenumber, page in enumerate(pages): |
| for word in page: |
| d.setdefault(word, []).append(pagenumber) |
| |
| Note, the second example is a use case characterized by a get and set |
| to the same key. There are similar use cases with a __contains__ |
| followed by a get, set, or del to the same key. Part of the |
| justification for d.setdefault is combining the two lookups into one. |
| |
| Membership Testing |
| Dictionaries of any size. Created once and then rarely changes. |
| Single write to each key. |
| Many calls to __contains__() or has_key(). |
| Similar access patterns occur with replacement dictionaries |
| such as with the % formatting operator. |
| |
| Dynamic Mappings |
| Characterized by deletions interspersed with adds and replacements. |
| Performance benefits greatly from the re-use of dummy entries. |
| |
| Data Layout |
| ----------- |
| |
| Dictionaries are composed of 3 components: |
| The dictobject struct itself |
| A dict-keys object (keys & hashes) |
| A values array |
| |
| |
| Tunable Dictionary Parameters |
| ----------------------------- |
| |
| See comments for PyDict_MINSIZE, USABLE_FRACTION and GROWTH_RATE in |
| dictobject.c |
| |
| Tune-ups should be measured across a broad range of applications and |
| use cases. A change to any parameter will help in some situations and |
| hurt in others. The key is to find settings that help the most common |
| cases and do the least damage to the less common cases. Results will |
| vary dramatically depending on the exact number of keys, whether the |
| 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(). |
| Also, every dictionary iterates at least twice, once for the memset() |
| when it is created and once by dealloc(). |
| |
| Dictionary operations involving only a single key can be O(1) unless |
| resizing is possible. By checking for a resize only when the |
| dictionary can grow (and may *require* resizing), other operations |
| remain O(1), and the odds of resize thrashing or memory fragmentation |
| are reduced. In particular, an algorithm that empties a dictionary |
| by repeatedly invoking .pop will see no resizing, which might |
| not be necessary at all because the dictionary is eventually |
| discarded entirely. |
| |
| The key differences between this implementation and earlier versions are: |
| 1. The table can be split into two parts, the keys and the values. |
| |
| 2. There is an additional key-value combination: (key, NULL). |
| Unlike (<dummy>, NULL) which represents a deleted value, (key, NULL) |
| represented a yet to be inserted value. This combination can only occur |
| when the table is split. |
| |
| 3. No small table embedded in the dict, |
| as this would make sharing of key-tables impossible. |
| |
| |
| These changes have the following consequences. |
| 1. General dictionaries are slightly larger. |
| |
| 2. All object dictionaries of a single class can share a single key-table, |
| saving about 60% memory for such cases. |
| |
| Results of Cache Locality Experiments |
| -------------------------------------- |
| |
| Experiments on an earlier design of dictionary, in which all tables were |
| combined, showed the following: |
| |
| When an entry is retrieved from memory, several adjacent entries are also |
| retrieved into a cache line. Since accessing items in cache is *much* |
| cheaper than a cache miss, an enticing idea is to probe the adjacent |
| entries as a first step in collision resolution. Unfortunately, the |
| introduction of any regularity into collision searches results in more |
| collisions than the current random chaining approach. |
| |
| Exploiting cache locality at the expense of additional collisions fails |
| to payoff when the entries are already loaded in cache (the expense |
| is paid with no compensating benefit). This occurs in small dictionaries |
| where the whole dictionary fits into a pair of cache lines. It also |
| occurs frequently in large dictionaries which have a common access pattern |
| where some keys are accessed much more frequently than others. The |
| more popular entries *and* their collision chains tend to remain in cache. |
| |
| To exploit cache locality, change the collision resolution section |
| in lookdict() and lookdict_string(). Set i^=1 at the top of the |
| loop and move the i = (i << 2) + i + perturb + 1 to an unrolled |
| version of the loop. |
| |
| For split tables, the above will apply to the keys, but the value will |
| always be in a different cache line from the key. |
| |
| |