Кажется, поиск в map дороже чем O(1)

Перевод статьи "Go Maps Don’t Appear to be O(1)".

Поправка для вновь прибывших. Некто bboozoo(пользователь с Reddit) сделал замечательный анализ приведенного примера. Похоже, что производительность зависит от кеширования в памяти. Map менее эффективно кешируется, в отличие от slice. И чем больше размер map, тем сложнее его кешировать.

Я учусь на втором курсе университета в Торонто. На нашем курсе структур данных мы, как и многие из вас, изучаем асимптотическую эффективность различных структур данных. Это и бинарный поиск в сортированном списке, который по времени занимает O(log(N)), и поиск в хеш таблице, который занимает O(1).

Для одной из задач, с которой я столкнулся в своем приложении, мне был необходим список некоторых чисел(и Bloom filter мне не подходил). К тому же, мне были необходимы индексы ассоциированные с необходимыми числами. Как наивный студент, я ожидал что для большого набора данных эффективней использовать map[int]uint, а не сортированный slice. Ожидалось что поиск в map будет работать с постоянным показателем по времени. Но, на самом деле, для Go это не так.

Я стараюсь не заниматься преждевременной оптимизацией, но я постоянно делаю бенчмарки своего кода. Для описанных алгоритмов(поиск в хеш таблице vs бинарный поиск) я тоже сделал бенчмарки. И тут всплыло кое что странное.

Не знаю что вы думаете об этом, но для меня это не выглядит как O(1).

Исходники и набор данных вы можете найти в моем репозитории на Github. Тесты запускались на Go 1.4 и Windows машине. В бенчмарках я не учитываю время генерации первоначальных данных и время на GC паузы(GC отключен и вызывается в ручную до вызова таймера).

Через некоторое время после обнаружения этого феномена у меня появилась возможность поспрашивать знающих людей. Я предположил, что причиной может стать большое количество коллизий в большом map. Еще мне подсказали, что проблема может быть в оптимизации. Ясно, что ничего не ясно. Давайте ковырять исходники!

Почему так происходит?

Исходники хеш таблицы занимают не много места и с ними довольно быстро разобраться. Комментарии в коде объемные и очень помогают понять как все устроено и как использовать этот код на более высоком уровне. Но, для начала, давайте разберемся как работает сама хеш таблица. Если вы не гофер, то вы, вероятно, использовали хеш таблицы в других языках программирования, таких как Python (словари), JavaScript (объекты), Lua (таблицы) и т.д.

Данные в хеш таблице сохраняются с уникальным ключом. Почти все реализации позволяют использовать в качестве ключей строки. Предположим, у нас есть телефонная книга и мне нужно связать имена людей(ключи) с номерами телефонов(значения).

Когда я добавляю новый элемент в таблицу, то имя пропускается через функцию хеширования, которая создает уникальный ключ в виде беззнакового инта. Этот инт связан с бакетом в памяти - это такое место, в котором сохраняются записи. Это позволяет программе добраться сразу до нужного места в памяти по адресу, без сканирования и сравнения всех записей. Такой алгоритм работает как O(1) в отличии от простого перебора, который работает O(N).

К сожалению, мир не совершенен. Когда вы хешируете имя, то некоторые данные теряются, так как хеш, как правило, короче исходной строки. Таким образом, в любой реализации хеш таблицы неизбежны коллизии когда по двум ключам получаются одинаковые хеши.

Картинка, иллюстрирующая работа хеш таблицы. Тут видны коллизии для хеша 152, таким образом, значение можно рассматривать как список из двух элементов.

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

Давайте теперь окунемся в исходники Go и посмотрим как там реализована хеш таблица. Для начала взглянем на mapaccess1.

Каждый тип хранит множество дополнительной информации, в том числе и структуру typeAlg, которая определяет как следует хешировать элемент этого типа. Все, кроме функций, slice и map может быть использовано в качестве ключа.

Прежде всего, мы рассчитываем позицию для бакета с использованием хеша нашего ключа:

b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))

В каждом бакете статически аллоцированы 8 предварительных(top) хешей. Они маленькие, так как для быстрого сравнения(еще до сравнения полного хеша всех ключей) используется всего 8 бит. Go перебирает все предварительные хеши в бакете. Если находится совпадение, вычисляется полный адрес пары ключ-значение в памяти.

for i := uintptr(0); i < bucketCnt; i++ {
    // быстрое сравнение
    if b.tophash[i] != top {
        continue
    }
    // готовим полный ключ
    k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
    if t.indirectkey {
        k = *((*unsafe.Pointer)(k))
    }
    // полное сравнение
    if alg.equal(key, k) {
        v := add(unsafe.Pointer(b), dataOffset
                +bucketCnt*uintptr(t.keysize)
                +i*uintptr(t.valuesize))

        if t.indirectvalue {
            v = *((*unsafe.Pointer)(v))
        }
        return v
    }
}

Если полный ключ найден, то возвращается значение(строка 310). Мы обходим только 8 вершин в бакете просто выгружая старые бакеты когда map разрастается и копируем память, если это необходимо.

Заключение

И так, в чем же проблема? Честно говоря, я так и не понимаю этого до конца. Нигде нет явной ошибки, в Go действительно очень хорошо реализованна работа с хеш таблицами и поиском в map(в счет времени вставки и добавления).

Возможно, проблема возникает когда в map попадает очень много элементов в которых совпадают предварительные хеши и приходиться делать очень много полных проверок. Если это так, то должно быть некоторое плато в графике поиска по времени, правда у меня не получилось сделать бенч на более чем 10⁸ элементов(закончилась память). Возможно, мне верно посоветовали, что проблемы связаны с оптимизацией компилятора. Если у кого-то будут какие либо мысли по поводу этой проблемы, то свяжитесь со мной @ConnorPeet.

Обновление: @dgryski предполагает, что проблемы работы алгоритма связаны с кешем процессора. Чтобы как-то подтвердить или опровергнуть это я попытался протестировать поиск с рандомизацией индексов. Это приводит к деградации результатов поиска в map, но по отношению к поиску в слайсе все остается также.

Обновление2: Эта статья вызвала бурю обсуждения на Reddit. Большинство склоняется, что все дело в кеши процессора. Но я, вероятно, не совсем так понял что именно Gryski имеет ввиду под этим понятием.