Автор: (c)Крис Касперски ака мыщъх
Прожорливость современных программ обгоняет темпы роста объемов оперативной памяти бюджетных компьютеров и потому все вокруг тормозит и высаживается на конкретную измену. Как уменьшить потребность программ в памяти, увеличив их в размерах? Шутки в сторону! Чем больше "весит" программа, тем меньше памяти она потребляет. Вот такая, с позволения сказать, практическая магия программирования.
Имеем цикл, вызывающий 10h функций, каждая из которых имеет размер 100h байт. Вопрос: сколько памяти мы потребляем (за вычетом стека, кучи и кода самого цикла)? Очевидный ответ: 10h x 100h = 1.000h далек от истины, как Гонконг от Гондураса. А все потому, что память выделяется дискретным образом и величина кванта адресного пространства равна одной странице (1.000h байт). Допустим, каждая из функций расположена в "своей" странице, тогда операционной системе придется держать в памяти 10h страниц (10h * 1.000h = 10.000h = 65.536 байт памяти).
Но это еще нам повезло. Если же одна или более функций пересекают страничную границу, потребности в памяти пропорционально возрастают и в худшем случае удваиваются. То есть, десять 100h-байтовых функций реально "отъедают" 20.000h = 131.072 байт памяти.
Отсюда следует, что большое количество крохотных функций приносит больше вреда, чем пользы и серьезно напрягает подсистему памяти. Как оптимизировать программу? Очень просто. Группировать часто употребляемые функции так, чтобы они располагались как можно ближе друг к другу. Другими словами, необходимо стремиться, к наиболее плотному заполнению страниц, не оставляя в них "дыр", заполненных посторонним кодом.
Компиляторы располагают функции в порядке их объявления (если речь идет об одном .c файле), а сами .c файлы транслируются в .obj, собираемые линкером слегка более сложным образом. Линкер может объединять файлы в порядке их перечисления в командной строке или же сортировать их по алфавиту. Словом, полагаться на него нельзя и прежде чем нашпиговать библиотеку ворохом крохотных функций, следует хорошо задуматься: а нужно ли нам это или нет? Быть может, функции лучше реализовать по месту их использования?
А как быть, если разные части программы используют разные наборы функций и сгруппировать их оптимальным образом никак не получается? Очень просто - достаточно продублировать некоторые функции так, чтобы получилось несколько независимых компактных групп. И хотя совокупные потребности в памяти при этом возрастут, количество страниц, находящихся в каждый момент в оперативной памяти, сократится, а остальные будут вытеснены на диск.
Аналогичным образом обстоят дела и с ветвлениями. Рассмотрим следующий, кстати сказать, вполне типичный код:
Листинг 1. Пример типичного ветвления.
Допустим, ветка K (неважно, какая из двух) выполняется намного чаще другой. Что это означает?! А то, что значительная часть кода будет бесцельно болтаться в оперативной памяти и операционная система не сможет вытеснить ее на диск, поскольку она находится в тех же страницах, что и полезный код. Ситуация разрешается очень просто - ветка K выносится в отдельную функцию, расположенную совершенно в другом месте, но рядом с теми функциями, которые она вызывает.
Довольно простой трюк, не так ли?! Но при катастрофической нехватке оперативной памяти он увеличивает производительность в сотни(!) раз. Диск практически перестает дергать файлом подкачки и код исполняется на крейсерской скорости, хотя на системах с избытком памяти за счет дублирования функций для создания локальных изолированных групп, ситуация будет обратной и потребности в памяти все-таки возрастут (за счет дублирования!), но производительность ничуть не упадет - ведь свободная память есть, так с какого же перепугу ей падать?!
Чем данные отличаются от кода? С точки зрения менеджера памяти - ничем. Следовательно, они также должны группироваться по правилу: данные, используемые рядом (в коде), следует располагать в пределах одной страницы памяти.
Рассмотрим ситуацию: мы имеем цикл, использующий три переменные типа int: k, m и n, но волею судьбы они оказались расположенными в трех разных страницах памяти, а между ними находятся редко используемые буферы данных. И что же?! Вместо 3 * sizeof(int) наша программа потребляет 3 * sizeof(PAGE) = 12 Кбайт памяти! Над таким КПД посмеялся бы и паровой двигатель!!!
К сожалению, наши возможности по расположению переменных в памяти намного более ограничены. Компиляторы имеют тенденцию размещать локальные переменные в стеке в порядке обращения к ним, а не объявления их в программе, и потому следующий код просто ужасен (и вовсе не потому, что в нем используется "опасная" с точки зрения переполнения функция gets):
Листинг 2. Пример кода, потребляющего вдвое больше стековой памяти, чем ожидалось.
Забудем об оптимизирующих компиляторах (которые в данном конкретном случае разместят переменные a и sum в регистрах) и будем рассуждать - что происходит в общем случае? А происходит следующее: компилятор видит первую используемую переменную sum и кладет ее на стек, затем он видит обращение к buf и располагает ее за sum, после чего очередь доходит и до переменной а. Поскольку размер буфера равен 4 Кб, то переменные a и sum гарантированно попадают в разные страницы и цикл for требует целых 8 Кб стековой памяти, что вдвое превышает фактический размер кадра стека, выделенный под локальные переменные.
Вот так ситуация... Причем никакая перегруппировка переменных ситуации не изменяет, т.к. их порядок определяется самим компилятором. Кстати говоря, ранние версии MS VC предпочитают размещать сначала массивы, а затем скалярные переменные (т.е. в нашем случае переменные a и sum окажутся рядом, что очень хорошо, но никаких гарантий, что это действительно произойдет, у нас нет, к тому же переменные могут оказаться рассечены границей страницы так, что одна попадет в одну страницу, а другая - в другую). Последние версии MS VC и GCC для борьбы с переполнениями изменили тактику и стали размещать буфера за скалярными переменными, предотвращая затирание указателей. Короче, бардак сплошной. Каждый компилятор поступает, как ему захочется, и управы на них нет никакой.
А как же структуры?! Вот ключ к вратам оптимизации! Порядок членов структуры компилятор изменять не имеет права и потому если нам нужно, чтобы переменные a и sum располагались рядом, имеет смысл создать специальную структуру, куда их и положить.
То же самое относится и к динамической памяти. Вместо того, чтобы выделять 10h блоков по 100h байт, рискуя, что менеджер кучи разбросает их по всему адресному пространству, лучше запросить 1.000h байт одним куском и сложить туда наши блоки памяти. Теперь они гарантированно будут рядом!!!
Динамические библиотеки никогда не знают, по какому адресу они будут загружены и потому должны сохранять свою работоспособность независимо от базового адреса загрузки. Существовало два пути решения проблемы: базирование (то есть создание перемещаемого кода, вычисляющего все адреса относительно базового адреса, обычно сохраняемого в некотором регистре общего назначения) и fix up'ы (они же перемещаемые элементы) - это когда все абсолютные адреса корректируются системой в процессе загрузки файла в память, что, конечно, занимает некоторое время и требует места для размещения таблицы fix up'ов, но... эффективная реализация позиционно-независимого кода на x86-процессорах невозможна и такой код будет тормозить всегда, в отличие от fix up'ов, тормозящих лишь на стадии загрузки файла в память. Microsoft выбрала второй путь. Создатели UNIX-систем, кстати говоря, тоже.
Тоже мне, открытие Африки, хмыкнет иной читатель. Это же в любом учебнике по программированию написано. А вот что там не написано, так это то, что при совместном использовании динамических библиотек разными программами все они должны быть загружены по одним и тем же адресам, в противном случае модификация перемещаемых элементов задействует механизм copy-on-write, "расщепляющий" все модифицируемые страницы и предоставляющий каждому процессу, использующему данную DLL, "свою" копию, что вполне логично, но... слишком расточительно с точки зрения использования памяти.
UNIX-компиляторы выносят все перемещаемые элементы в специальную секцию, предотвращая модификацию основного кода. Действительно, если у нас есть программа с 100h перемещаемыми элементами и все эти элементы находятся в различных страницах, то каждый процесс потребует sizeof(PAGE) x 100h = 1.000h x 100h = 100.000h = 1.048.576 байт памяти, то есть целый мегабайт, а ведь в реальной динамической библиотеке количество перемещаемых элементов намного больше 100h.
Как быть?! Да очень просто! Не использовать перемещаемых элементов, то есть - никаких абсолютных адресов. Только относительные. Вызов функции в Си практически всегда происходит по относительным адресам (если только программист принудительно не получил ее адрес и не записал его в указатель на функцию) и потому 99% перемещаемых элементов составляют глобальные и статические переменные. Как избавиться от них? Да проще просто - достаточно использовать API-функции локальной памяти потока (поиск TLS по MSDN). Потребность в памяти тут же сокращается на много мегабайт!