How Does Python 3.6 Dictionary Implementation Improve Memory Usage and Preserve Insertion Order?

Python 3.6 : Dictionaries Preserve Insertion Order

As of Python 3.6, dictionaries in CPython implementations exhibit insertion ordering, a significant departure from previous versions. This feature is now a guaranteed language feature in Python 3.7.

Improved Memory Usage and Performance

The new dictionary implementation significantly reduces memory usage by 20-25% compared to Python 3.5. This improvement stems from the implementation's use of separate arrays:

• dk_entries: Stores entries (PyDictKeyEntry) in insertion order.
• dk_indices: Stores indices for entries in dk_entries, acting as a hash table.

Previously, a sparse array of type PyDictKeyEntry had to be allocated, resulting in wasted space due to performance considerations. The new approach allocates only the necessary entries and employs a sparse array of type intX_t, which consumes less memory.

Data Structures Used

Originally, dictionaries were stored as [keyhash, key, value] in a sparse array with empty entries denoted by '--'. The new approach organizes the data as:

• indices: [None, 1, None, None, None, 0, None, 2]

• entries: [[-9092791511155847987, 'timmy', 'red'],

          [-8522787127447073495, 'barry', 'green'],
          [-6480567542315338377, 'guido', 'blue']]
  

This revised structure significantly reduces memory overhead.

Benefits of Insertion Ordering

While the new dictionary implementation primarily focuses on memory optimization, the insertion ordering feature has convenient applications:

• Preserving the order of objects in which they were added to the dictionary.
• Customizing the display or iteration order of dictionary contents.

It's important to note that insertion ordering is not guaranteed across different Python implementations or future language versions. However, in Python 3.7 and beyond, it is a guaranteed feature that you can rely on.

The above is the detailed content of How Does Python 3.6 Dictionary Implementation Improve Memory Usage and Preserve Insertion Order?. For more information, please follow other related articles on the PHP Chinese website!