Асимптотика случайного доступа к памяти = O(√N + logN)

Я нашёл вчера статью о том, что в современных компьютерах случайный доступ к памяти O(√N), а не O(1), как вы (скорее всего) думали. Причём N — это количество байт, а не элементов. Это асимптотику не меняет, но усиливает значимость констант.

Мы уже, вроде как и раньше знали, что чтение с жёсткого диска медленнее чем чтение из оперативки. Но теперь назревает паттерн довольно глобальный и имеющий множество последствий.

В комментариях к этой статье я нашёл другую статью (но уже на arxiv.org) с утверждением, что доступ к памяти O(logN).

Но прикол заключается в том, что обе статьи отталкиваются от двух разных вещей, которые с друг другом не связаны, но при этом совместимы с друг другом. И значит стоит говорить о том, что асимптотика доступа к памяти на самом деле где-то O(√N+logN), только константы правильные подобрать.


Первая статья “The Myth of RAM” (на самом деле серия из четырех статей) основывается на том, что у нас есть следующие уровни хранения данных:

  • регистры;
  • L1-кэш;
  • L2-кэш;
  • L3-кэш;
  • RAM + SWAP;
  • SSD;
  • HDD;
  • сетевые кэши;
  • внешние сетевые хранилища.

Каждый следующий уровень хранения данных объемнее предыдущего, но при этом более медленнее (см. статью “Числа, которые должен знать каждый программист” / “Numbers everyone should know”, если вы хотите узнать эти числа). Если начать бродить по данным в стиле Random Access, то с увеличением количества элементов мы будем постепенно выходить за пределы каждого уровня. В итоге среднее амортизированное время доступа к элементу будет меняться. Человек не поленился и нарисовал график (но только от L1 до RAM+SWAP), после чего натянул на него график O(√N).

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

Модель в основном вписывается на точках близких к каждому уровню. Между уровнями есть еще куча всяких прикольных эффектов, типа выпуклых загогулин, которые скорее всего появляются от cache miss. График в итоге получается не такой гладкий как хотелось бы. Не стоит также забывать о том, что разные ядра процессора шарят кэши L2, чем могут портить стройную картину. В общем, натянулось со скрипом, но в целом тенденцию отражает — иерархия хранилищ памяти действительно вписывается в этот паттерн.

В общем, если смотреть на индустрию сейчас, то эта тенденция никуда не денется в ближайшем будущем. В статье там ещё пространные рассуждения о том, что O(√N) это ещё и теоретический предел доступа к памяти, но выкладки нужно бы проверить. Также там есть советы по поводу того, как в некоторых случаях можно избавляться от random-access.


Вторая статья “The Cost of Address Translation” основывается на том, что вообще-то у нас есть такая штука как виртуальная память, с которой мы работаем и которая отображается на физическую. И, соответственно, есть магическая операция трансляции виртуальных адресов в реальные. Начиная с 64-битных систем мы можем гарантировать, что эта операция занимает O(logN) от общего количества памяти, которое у нас есть на машине. А все потому, что трансляция адресов реализована в виде древовидных таблиц.

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


Теперь собственно говоря я могу рассказать о последствиях, которые появляются из этих двух статей. Два основных вывода, о которых вы, наверняка, догадались:
 — Чем меньше памяти вы используете, тем быстрее ваш код;
 — Последовательный доступ к памяти более выгоден, чем random access (в добавок, у нас вообще-то каждый уровень иерархии памяти имеет prefetch, который тоже вносит сильную лепту).

Если вам интересно почитать про prefecth и вообще кэши процессора, могу порекомендовать статью “Галерея эффектов кэшей процессоров”.


Но это не все выводы. Если посмотреть на текущее состояние дел индустрии, то мы заметим такую ситуацию:

  • языки программирования уходят от unmanaged кода к managed-коду, в подарок даря безопасность при программировании;
  • каждый язык тянет за собой довольно избыточный рантайм;
  • количество объектов начинает увеличиваться благодаря развитию теории типов (ФП сейчас вообще не умеет в структуры);
  • каждый объект имеет константный оверхед просто на себя любимого. Так у Java и C# этот оверхед равен 8 байт, причём вы бы на них посмотрели — это же целая эпопея о том, почему дебилов нельзя пускать к компиляторам. За деталями зачем нужны дополнительные 8 байт на объект см. статью “Знакомство с внутренним устройством .NET Framework. Посмотрим, как CLR создаёт объекты” и почему это плохо — см. статью “Object Overhead: The Hidden .NET Memory Allocation Cost”;
  • у нас есть волшебное понятие выравнивания данных, чтобы их можно было располагать с интервалом кратным 8/16 байт от начала одного до конца другого, потому что процессор плохо умеет работать с некратными адресами, подробнее см. статью “Что такое выравнивание, и как оно влияет на работу ваших программ”;
  • у нас есть практика протаскивания объектов через цепочки методов (причём тот же Rust даже гордится этим), что приводит к тому, что у нас возникает множество объектов, которые нарушают принцип локальности и находятся далеко друг от друга (это нормально, пока таких объектов одновременно мало, но их то бывает много — особенно во всяких персистентных структурах);
  • несмотря на все заявления ФП-адептов о потенциально более простом анализе ФП-программ и возможностях автоматической оптимизации — увы, нет реальных подвижек в эту сторону;
  • программирование движется в сторону continuation-passing, что только усугубляет ситуацию нелокальности данных;
  • теория правильной упаковки данных полностью забыта вместе с C/C++;
  • у нас есть GC, причём он ленивый и работает во время исполнения, поэтому мы вообще не можем предсказать, как будут лежать объекты в памяти (к чести GC он умеет двигать объекты для обеспечения малой фрагментации, но это не то);
  • про альтернативные аллокаторы памяти вообще никто не слышал из-за волшебного GC;
  • малые объекты невыгодно делать из-за выравнивания объектов. Большие объекты невыгодно делать из-за GC, который не умеет отслеживать, что какое-то ссылочное поле большого объекта больше не потребуется. Из-за этого сборка мусора задерживает лишние объекты в памяти;
  • GC плохо работает, когда количество свободной памяти меньше, чем четыре объема занятой памяти. См. раздел “сборщик мусора не настолько хорош” из статьи “Почему веб-приложения на мобильных платформах работают медленно”;
  • для сериализации в основном используются json и xml (потому что удобно и распространено), а про бинарные протоколы только слышали, из-за чего у нас появляется адский расход памяти и не очень то последовательный доступ к памяти;
  • объемы данных, с которыми нужно работать постепенно растут;
  • а вот характеристики железа не показывают устойчивого роста.

И финальным выводом является тот факт, что мы вообще не умеем работать с памятью. В целом, если посмотреть на то, как работает софт, это довольно очевидно — он занимает адские объемы оперативки не делая ничего. А значит рано или поздно индустрия упрется в современные подходы разработки.

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

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.