Новые словари в Python 3.6

Вероятно вы знаете, что словари в Питоне играют огромную роль, можно даже назвать их одной из основополагающих структур, без которых интерпретатор даже собрать не получится, не то что запустить. А коли так, то вы понимаете, что любая модификация данной структуры должна: 1. быть чётко обоснована; 2. проводиться с чрезвычайной осторожностью, ведь в противном случае, если в фундаменте будет трещина, то и весь дом может развалиться.

Судя по всему, у нас уже есть обоснование, а работы по поиску возможных трещин в полном разгаре и выпуск 3.6, намеченный на 16 декабря 2016, уже будет содержать модифицированную реализацию словарей.

Давайте в общих чертах разберёмся, что и как может измениться.

Заплатка, вносящая изменения, зарегистрирована в запросе 27350. Её автор — Инада Наоки — реализовал сжатый упорядоченный словарь, базируясь на концепции, введённой в PyPy ещё в январе 2015-го. Идея не нова и в рассылке python-dev о ней в 2012-м говорил Реймонд Хеттинджер, который даже создал прототип на Питоне.

Если переложить структуры двух видов словарей с Си на Питон, максимально упрощая, то получим примерно следующее:

    # my_dict = {'python': 'value1', 'schema': 'value2', 'c++': 'value3'}
    
    dict_classic = {
        'items_count': 3,
        'items': [
            # (hash, key, value)
            ('--', '--', '--'),
            (-9095698888683775416, 'python', 'value1'),
            ('--', '--', '--'),
            ('--', '--', '--'),
            ('--', '--', '--'),
            ('--', '--', '--'),
            (-799031295762617234, 'c++', 'value3'),
            (-4226706071475375297, 'schema', 'value2'),
        ]
    }   
    
    dict_compact = {
        'items_count': 3,
        'items_index': [0, 1, 0, 0, 0, 0, 1, 1],
        'items': [
            (-9095698888683775416, 'python', 'value1'),
            (-4226706071475375297, 'schema', 'value2'),
            (-799031295762617234, 'c++', 'value3'),
        ]
    }

Здесь dict_classic — текущее представление объекта словаря и используемой им хеш-таблицы (items), а dict_compact — новое предлагаемое. Видно, что items в первом случае содержит пустые слоты и элементы здесь не следуют в том порядке, в каком были заданы изначально (см. my_dict из первой строки). Во втором случае items не только упорядочен, но и компактен. А для упрощения адресации элементов здесь предусмотрен items_index.

Итак новая реализация позволит: 1. снизить количество выделяемой под словари памяти; 2. сохранять порядок элементов, фактически сводя на нет необходимость в отдельном OrderedDict. Это, конечно, неплохо, но что на счёт быстродействия? Судя по опубликованным в упомянутом выше запросе данным, она останется примерно на том же уровне.

В данный момент заплатка шлифуется, что будет дальше — покажет время.

Наблюдайте, участвуйте.