Динамические и статические массивы

Я собираюсь рассказать об одном нетривиальном эффекте, заключающемся в существенном замедлении работы программ при переходе от статических массивов к динамическим в некоторых ситуациях. С этим эффектом можно столкнуться при программировании на многих компилируемых языках (в том числе в C++ или Delphi) для архитектуры IA-32. Весь софт еще не скоро перейдет на 64 бита, так что заметка будет актуальной продолжительное время.

Обычно, когда программа должна принимать входные данные меняющегося размера, новички используют статический массив с заведомо большим размером. Более опытные используют динамическое выделение памяти, например, функцией malloc. С идеологической точки зрения всё ясно — метод со статическим массивом некорректен. Однако с сегодняшними компьютерами на памяти можно особенно не экономить. Рассмотрим оба метода с другой точки зрения — сравним их быстродействие.

Я писал программу, моделирующую движение системы материальных точек. Каждая точка имела несколько характеристик: массу, заряд, три координаты, три проекции скорости. Сначала, на этапе отладки, все данные хранились в статическом массиве. Потом, когда я перешел к динамическим массивам, быстродействие программы упало примерно на треть. Я подумал, что использовал не самый лучший вариант организации массивов. Перепробовал все имевшиеся методы. Скорость не увеличилась — терялись те же 30% производительности.

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

На уровне процессора обращение к элементам статического массива a происходит так. Адрес начала массива известен еще при компиляции. Чтобы получить адрес элемента массива a[i], к адресу начала прибавляется индекс i, умноженный на размер одного элемента в байтах. Затем по вычисленному адресу идет обращение в память.

К элементам динамического массива получить доступ сложнее. На этапе компиляции адрес начала массива не известен. После выделения памяти он хранится в специальной переменной — указателе. Чтобы получить адрес элемента массива a[i], нужно сначала обратиться к памяти (взять значение указателя) и получить адрес начала массива. Потом к нему прибавить индекс, умноженный на размер элемента, и по вычисленному адресу элемента массива снова обратиться к памяти. Как видим, получается два обращения к памяти против одного у статических массивов.

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

А что произойдет, например, при переборе всех элементов массива в цикле? Если цикл оперирует с маленьким набором данных, адреса массивов и используемые переменные можно хранить в регистрах. С расширением набора количество свободных регистров уменьшается, и на каком-то этапе в теле цикла появится дополнительное обращение к памяти (прочитайте про такую вещь, как latency, если вы не видите в этом ничего плохого). Понятно, что это произойдет тогда, когда все доступные регистры будут использованы. Именно в этих условиях переход от статического массива к динамическому может привести к существенному замедлению программы.

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

Умение программировать на ассемблере позволяет писать более оптимизированный и оптимизируемый код и на языках высокого уровня. Например, можно дать такой совет: лучше использовать массив структур, а не несколько разных массивов. Такой совет оправдан не только описанной логикой освобождения регистров и уменьшения количества обращений к памяти, но и логикой работы процессорного кеша. Да и в файл сохранять такие данные проще. Или еще один совет: лучше использовать локальные переменные, а не глобальные. Это оправдано не только идеологически; компилятор может разместить локальные переменные не в памяти, а в регистрах.

Относительно архитектуры x64 можно заметить следующее. Хоть в ней появилось 8 новых регистров, теоретически описанная ситуация не исключена. Было бы интересно проверить на практике, появляется ли такой эффект в программах, компилируемых под 64 бита, и на сколько падает быстродействие.

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