Алгоритмическая сложность и память

Удивительное дело.

Мы оцениваем алгоритмы при помощи O-нотации. Мы абстрагируемся от низкоуровневых операций во имя сравнения алгоритмов по сложности. Выбираем сложные структуры данных для того, чтобы в их обработке задействовать минимальное количество операций.

Но иногда используются оптимизации, которые ухудшают сложность алгоритма с O(1) до O(n) и эти решения работают быстрее. 

Сложность алгоритма и O-нотация (на бумаге)

Изучая любой алгоритм можно абстрагироваться до набора элементарных операций.

Сложность алгоритма это зависимость количества элементарных операций от размера входных данных.

Константная сложность O(1) - это когда количество операций алгоритма не зависит от размера входящих данных. 

Получение значения в массиве по индексу, поиск в словаре по ключу. 

Логарифмическая сложность O(log n) - это когда количество операций растет, но не так быстро, как растет размер входящих данных. 

Отсортируем массив и уже не нужно перебирать его весь - достаточно рекурсивно проверять его середину и отбрасывать ту его половину, в которой значения точно нет, пока не найдем значение. 

Или строим дерево и не нужно перебирать все элементы, достаточно пройти от корня до нужного листа. Другими словами, количество операций - это высота дерева, а не общий его размер.

Линейная сложность O(n) - количество операций растет пропорционально размеру входящих данных. 

Поиск в массиве полным перебором, простой цикл. Сколько элементов - столько и операций сравнения.

Более высокие сложности - это обычно "цикл в цикле", "цикл в цикле в цикле", сложные рекурсии, порождающие дополнительные вызовы, пробег несколько раз по всему графу для каждого элемента этого графа и прочие. 

Детали в статье.

Считается, что алгоритмы с более низкой сложностью работают быстрее. Но почему же тогда...

Возьмем Redis. Для маленких элементов-хэшей используются не хэш-таблицы, а упакованный бинарный формат. Автор пишет в блоге:

Maybe you remember that in the implementation of the Hash data type I did a trick: instead of saving small hashes (hashes composed of a few tens of elements, where every element is not too big) as hash tables, I encoded them in a special way. What I did was creating a simple special encoding that was suited for _string to string maps_, something like a unique blob of data with prefixed length, so if you have an hash that is "name => foo, surname => bar", this is stored in a unique string like
4:name3:foo7:surname3:bar

This is just an example, the actual format is different (and binary).

Это позволяет экономить память, понятно, структура лучше упакована. Но это еще и ускоряет получение значения, но как? Ведь перебор ключей-значений в такой структуре - это линейный O(n) алгоритм. Зачем отказываться от O(1) в пользу O(n)?

Доступ к памяти (овраги)

В обычной хэш таблице происходит вычисление хэш функции и затем поиск в "случайном" месте в памяти. А если таких небольших хэш таблиц очень много?

В интернете и в книгах распространены таблицы вида "задержки, которые должен знать каждый программист"

L1 cache reference ......................... 0.5 ns
Branch mispredict ............................ 5 ns
L2 cache reference ........................... 7 ns
Mutex lock/unlock ........................... 25 ns
Main memory reference ...................... 100 ns   
...

Скорость работы программы сильно зависит от того, есть ли нужный фрагмент данных в кэше.

А это в свою очередь сильно зависит от размера кэша. Размеры кэша очень малы. Смотрите на эту тему эпичное 32 kilobytes!!! видео.

Значит необходимо максимизировать объем полезных данных в кэше и минимизировать объем бесполезных. 

• Сжимать данные - чем меньше места занимает полезная информация, тем больше места для другой полезной информации.
• Дефрагментировать данные, чтобы вместе с полезной информацией в кэш не пролезала бесполезная. 
• Локализовать данные чтобы повысить вероятность попадания в кэш полезной информации.

И другие пункты, для этого придумано целое направление Data Oriented Design.

Крайне желательно, чтобы все операции алгоритма обращались только к кэшу. 

Не "все данные должны быть в кэше". Скорее "к тому моменту, когда произойдет любая операция, нужные ей данные должны быть в кэше".

С этой точки зрения самый оптимальный паттерн доступа к данным - это обычный цикл с проходом по массиву.

В идеале, в этом массиве должна быть только та информация, которая нужна алгоритму. 

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

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

Но это алгоритм O(n) сложности!

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

Большие объемы и диски

С базами данных эта история тоже работает.

Казалось бы, давно уже изобрели реляционные базы на основе B-Tree.

Строим на диске и отражаем в памяти дерево и балансируем его так, чтобы каждый узел был пропорционален размеру блока на диске (для префетчинга) и высота дерева была как можно ниже (чтобы обеспечить лучший логарифм в O(log n)). Что может пойти не так?

Во-первых, доступ к случайному месту на диске работает еще медленнее, а дерево - это структура, которая заставляет нас обращаться к случайным местам на диске.

Во-вторых, в строковых базах мы вынуждены читать блоки, содержащие значения столбцов, которые не нужны в конкретном запросе.

Оказывается, если хранить данные в колонках, OLAP-нагрузки работают на порядок лучше.

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

Источник изображения

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

Источник изображения

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

В итоге, снова жертвуем O(log n) в пользу O(n) и получаем превосходную производительность на определенном профиле нагрузки.