Yu1709$!%yuyu!$%wutu!5=126+

                
____  ___       .__                 
\   \/  /  _____|  |   ______  _  __
 \     /  /  ___/  |  /  _ \ \/ \/ /
 /     \  \___ \|  |_(  <_> )     / 
/___/\  \/____  >____/\____/ \/\_/  
      \_/     \/    @ligmakokz

Editing: dictnotes.txt

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.

Name	Type	Actions
clinic	Directory
stringlib	Directory
README	File
abstract.c	File
abstract.gcda	File
abstract.o	File
boolobject.c	File
boolobject.gcda	File
boolobject.o	File
bytearrayobject.c	File
bytearrayobject.gcda	File
bytearrayobject.o	File
bytes_methods.c	File
bytes_methods.gcda	File
bytes_methods.o	File
bytesobject.c	File
bytesobject.gcda	File
bytesobject.o	File
call.c	File
call.gcda	File
call.o	File
capsule.c	File
capsule.gcda	File
capsule.o	File
cellobject.c	File
cellobject.gcda	File
cellobject.o	File
classobject.c	File
classobject.gcda	File
classobject.o	File
codeobject.c	File
codeobject.gcda	File
codeobject.o	File
complexobject.c	File
complexobject.gcda	File
complexobject.o	File
descrobject.c	File
descrobject.gcda	File
descrobject.o	File
dictnotes.txt	File
dictobject.c	File
dictobject.gcda	File
dictobject.o	File
enumobject.c	File
enumobject.gcda	File
enumobject.o	File
exception_handling_notes.txt	File
exceptions.c	File
exceptions.gcda	File
exceptions.o	File
fileobject.c	File
fileobject.gcda	File
fileobject.o	File
floatobject.c	File
floatobject.gcda	File
floatobject.o	File
frame_layout.md	File
frameobject.c	File
frameobject.gcda	File
frameobject.o	File
funcobject.c	File
funcobject.gcda	File
funcobject.o	File
genericaliasobject.c	File
genericaliasobject.gcda	File
genericaliasobject.o	File
genobject.c	File
genobject.gcda	File
genobject.o	File
interpreteridobject.c	File
interpreteridobject.gcda	File
interpreteridobject.o	File
iterobject.c	File
iterobject.gcda	File
iterobject.o	File
listobject.c	File
listobject.gcda	File
listobject.o	File
listsort.txt	File
lnotab_notes.txt	File
locations.md	File
longobject.c	File
longobject.gcda	File
longobject.o	File
memoryobject.c	File
memoryobject.gcda	File
memoryobject.o	File
methodobject.c	File
methodobject.gcda	File
methodobject.o	File
moduleobject.c	File
moduleobject.gcda	File
moduleobject.o	File
namespaceobject.c	File
namespaceobject.gcda	File
namespaceobject.o	File
object.c	File
object.gcda	File
object.o	File
object_layout.md	File
object_layout_312.gv	File
object_layout_312.png	File
object_layout_full_312.gv	File
object_layout_full_312.png	File
obmalloc.c	File
obmalloc.gcda	File
obmalloc.o	File
odictobject.c	File
odictobject.gcda	File
odictobject.o	File
picklebufobject.c	File
picklebufobject.gcda	File
picklebufobject.o	File
rangeobject.c	File
rangeobject.gcda	File
rangeobject.o	File
setobject.c	File
setobject.gcda	File
setobject.o	File
sliceobject.c	File
sliceobject.gcda	File
sliceobject.o	File
structseq.c	File
structseq.gcda	File
structseq.o	File
tupleobject.c	File
tupleobject.gcda	File
tupleobject.o	File
typeobject.c	File
typeobject.gcda	File
typeobject.o	File
typeslots.inc	File
typeslots.py	File
typevarobject.c	File
typevarobject.gcda	File
typevarobject.o	File
unicodectype.c	File
unicodectype.gcda	File
unicodectype.o	File
unicodeobject.c	File
unicodeobject.gcda	File
unicodeobject.o	File
unicodetype_db.h	File
unionobject.c	File
unionobject.gcda	File
unionobject.o	File
weakrefobject.c	File
weakrefobject.gcda	File
weakrefobject.o	File