A VOL D'OISEAU

На этом вводную часть книги можно считать законченной.

AMD Code Analyst

Рисунок 4 0x007 Логотип профилировщика AMD Code Analyst

AMD Code Analyst на два порядка уступает своему прямому конкуренту VTune, и я бы ни за что не порекомендовал использовать его в качестве вашего основного профилировщика. Опасаясь быть побитым агрессивными поклонниками AMD, я все же позволю перечислить основные недостатки Code Analyst'a:

Во-первых, он требует обязательно наличия отладочной информации в профилируемой программе. Программу без отладочной информации он просто откажется загружать! Компиляторы же, в подавляющем своем большинстве, никогда не помещают отладочную информацию в оптимизированные программы. Это объясняется тем, что оптимизация, внося значительные изменения в исходный код, уничтожает прямое соответствие между номерами строк программы и сгенерированными машинными инструкциями. Фактически, оптимизированная и не оптимизированная программа – это две разные программы, имеющие различные, пусть и пересекающиеся, подмножества горячих точек. Профилировка не оптимизированного варианта программы принципиально не позволяет найти и устранить все узкие места настоящего приложения. (При отключенной оптимизации узкие места могут быть найдены там, где их нет).

Во-вторых, разрешающая способность его диаграмм ограничивается строками исходного текста программы, но, увы, не машинными командами (как у VTune). И хотя в принципе Code Analyst позволяет засекать время выполнения каждой инструкции, он не предоставляет никаких механизмов выделения "горячих" точек на этом уровне. Всю работу по выявлению "тяжеловесных" машинных команд нам приходится выполнять самостоятельно, "вручную" просматривая столбик цифр колонки CPI (Cycle per Instruction). Надо ли говорить, что даже в относительно небольшом участке программе количество машинных команд может достигать нескольких тысяч и подобный "кустарный" анализ их температур может растянуться черт знает на сколько времени.

В-третьих, Code Analyst не дает никаких советов по ликвидации выявленных узких мест программы, что не очень-то обрадует программистов-новичков (а таковых, как показывает практика, большинство и лишь очень немногие из нас поднаторели в оптимизации).

В-четвертых, Code Analyst просто неудобен в работе. Неразвитая система контекстных меню, крайне не конфигурабельный и вообще аскетичный интерфейс, отсутствие возможности сохранения "хронологии" профилировки… все это придает ему черты незаконченной утилиты, написанной на скорую руку.

Тем не менее, Code Analyst весьма компактен (его последняя на данный момент версия 1.1.0 занимает всего 16 мегабайт, что на порядок меньше VTune), стабилен и устойчив в работе и главное – он содержит полноценный эмулятор процессоров K6-II, Athlon

(с внешним и интегрированным кэшем), Duron, включая и их мобильные реализации. Причем, возможно вручную выбирать частоту шины и ядра. Это полезно хотя бы для оценки влияния частоты шины на производительность, что особенно актуально для приложений интенсивно работающих с основной оперативной памятью (жалко, но VTune лишен этой возможности). Наконец, Code Analyst содержит толковую справку, сжато и внятно описывающую узкие места процессора. И – самое приятное – он, в отличии от VTune, абсолютно бесплатен!

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

Аннотация

Хотите заглянуть внутрь черного ящика подсистемы оперативной памяти? Хотите узнать: что чувствует, чем дышит и какими мыслями живет каждая микросхема вашего компьютера? Хотите научиться минимальными усилиями создавать эффективный программный код, исполняющийся вдвое – втрое быстрее обычного? Хотите использовать возможности современного оборудования на полную мощь? Тогда – вы не ошиблись в выборе книги!

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

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

Здесь вы найдете и оригинальные приемы программирования, и недокументированные секреты, существование которых Intel и Microsoft хотели бы скрыть, и разъяснение туманных пунктов фирменной документации (включая указания на многочисленные ошибки и неточности!), и перечень типовых ошибок программистов, снижающих производительность системы, и вполне готовые к использованию решения, и…

Основной упор сделан на процессоры AMD Athlon, Intel Pentium-III и Intel Pentium-4 и языки программирования Си/Си ++ (впрочем, описываемые техники не привязаны ни к какому конкретному языку, и знание Си требуется лишь для чтения исходных текстов примеров, приведенных в книге).

Аппаратная оптимизация

На мгновение отвлечемся от компьютеров и зададимся вопросом: можно ли с помощью обычной ученической линейки измерить толщину листа принтерной бумаги? На первый взгляд, тут без штангенциркуля ну никак не обойтись… Но, если взять с полсотни листов бумаги и плотно сложить их друг с другом… вы уже поняли куда я клоню? Пусть погрешность измерения толщины образовавшегося "кирпича" составит ±1 мм, тогда – точность определения толщины каждого отдельно взятого листа будет не хуже чем ±0,02 мм, что вполне достаточно для большинства повседневных целей!

Почему бы не применить эту технику для измерения времени выполнения машинных команд? В самом деле, время выполнения одной команды так мало, что ничем его не измерять (см. "Неточность измерений"), но если мы возьмем сто или даже сто тысяч таких команд, то… Увы! Машинные команды – ведут себя совсем не так, как листы бумаги. Неоднородность конвейера приводит к тому, что зависимость между количеством и временем выполнения команд носит ярко выраженный нелинейный характер.

К тому же, современные процессоры слишком умы, чтобы воспринимать переданный им на выполнение код буквально. Нет! Они подходят к этому делу весьма творчески. Вот допустим встретится им последовательность команд MOV EAX, 1; MOV EAX, 1; MOV EAX, 1, каждая из которых помещает в регистр EAX значение "1". Думаете, процессор как полный идиот, исполнит все три команды? Да как бы не так! Поскольку, результат двух первых присвоений никак не используется, процессор отбросит эти команды как ненужные, затратив время лишь на их декодирование, и ощутимо сэкономит на выполнении!

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

означает сказать лишь половину правды.

Сказать, что AMD опередила Intel с поддержкой программной предвыборки, – означает сказать лишь половину правды. Предвыборка отнюдь не является оригинальным изобретением AMD и в мире не-PC компьютеров она достаточно широко распространена. Поскольку, непосредственное управление кэшем не может осуществляться без учета характеристик подсистемы памяти с одной стороны, и архитектуры процессора с другой, – оно всегда аппаратно – зависимо. В мире "больших" компьютеров, конфигурации которых более или менее предсказуемы, "заточка" оптимизации программы под конкретное оборудование – явление вполне нормальное.

Но вот PC – дело другое. Оптимальная стратегия предвыборки зависит и от типа оперативной памяти, и от времени доступа к ней, и от ее латентности, и от характеристик чипсета, и от разрядности и тактовой частоты системной шины, и от частоты и архитектуры ядра процессора, и от политики кэширования, и от длины кэш-линеек, и от разрядности и частоты внутренней шины, и от латентности кэш-памяти… Многообразие конфигураций персональных компьютеров приводит к тому, что программная предвыборка создает проблем больше, чем их решает.

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

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

Алгоритм предсказаний недокументирован, но, тем не менее, суть его (по крайней мере, в общих чертах) понять несложно. Пусть, например, процессор фиксирует ряд кэш-промахов при обращении к линейкам N, N+3, N+6, N+9… Не нужно быть ясновидящим, чтобы с высокой степенью достоверности предположить, что следующей на очереди стоит N+12 линейка.
Т.е. P- 4 умеет распознавать арифметическую прогрессию и вычислять ее члены. Насчет же распознавания геометрической прогрессии в документации ничего не сказано, а проверить экспериментально – под рукой процессора нет.

Определить шаг арифметической прогрессии по нескольким ее элементам – не проблема! Вот выделить прогрессию из произвольной последовательности – куда сложнее. Справляется ли с этим P-4? Нет! Его разработки честно признаются в документации, что "Follows only one stream per 4K page (load or store)". Т.е. в пределах одной страницы доступ к данным, обрабатываемых в цикле, должен происходить по одному регулярному шаблону, в противном случае механизм предсказаний "ослепнет" и аппаратная предвыборка осуществляться не будет. Если же такая необходимость все же возникает (а практически всегда она и возникает), обрабатываемые данные следует разбить на несколько блоков (числом не более восьми) и расположить их в различных четырех килобайтовых регионах. Восьми – потому что P-4 умеет одновременно отслеживать не более восьми регулярных шаблонов (в терминологии разработчиков: потоков данных – data stream). Причем, упреждающая загрузка осуществляется только в пределах одного четырех килобайтового блока памяти – при выходе за его пределы механизм предсказаний дезактивируется и отслеживание шаблона обращений начинается сначала. Т.е. процессор вновь дожидается нескольких кэш-промахов, определяет шаг прогрессии и только после этого приступает к очередному сеансу предвыборки. Вследствие этого ячейки памяти, читаемые с большим шагом (порядка 1Кб), никогда не предвыбираются и потому обрабатываются крайне неэффективно.

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

Аппаратное непостоянство

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

Почему оно – аппаратное непостоянство – вообще возникает? Ну, тут много разных причин. Вот, например, одна из них: если частота системной шины не совпадает с частотой модулей оперативной памяти, чипсету придется каждый раз выжидать случайный промежуток времени до прихода следующего фронта тактового импульса. Исходя из того, что один цикл пакетного обмена в зависимости от типа установленных микросхем памяти занимает от 5 до 9тактов, а синхронизовать приходится и его начало, и его конец, нетрудно подсчитать, что в худшем случае мы получаем неоднозначность в 25% –40%.

Самое интересное, что аппаратный разброс в чрезвычайно высокой степени разниться от системы к системе. Я, к сожалению, так и не смог определить кто именно здесь виноват, но могу сказать, что, к примеру, на P-III 733/133/100/I815EP не смотря на разницу в частотах памяти и системной шины, аппаратный разброс весьма невелик и едва ли превышает 1% – 2%, на что можно вообще закрыть глаза.

Вот AMD Athlon 1050/100/100/VIA KT133 – совсем другое дело! У него наблюдается просто ошеломляюще аппаратное непостоянство, в частности, в операциях с основной памятью доходящее аж до двух раз! Непонятно, как на такой системе вообще можно профилировать программы!!! В, частности, последовательные замеры времени копирования 16-мегабайтного блока памяти после предварительной обработки (т.е. откидывания заведомо пограничных значений) могут выглядеть так:

Прогон № 01: 84445103 тактов

Прогон № 02: 83966665 тактов

Прогон № 03: 73795939 тактов

Прогон № 04: 80323626 тактов

       Прогон № 05: 84381967 тактов

       Прогон № 06: 85262076 тактов

       Прогон № 07: 85151531 тактов

       Прогон № 08: 91520360 тактов

       Прогон № 09: 92603591 тактов

       Прогон № 10: 100651353 тактов

       Прогон № 11: 93811801 тактов

       Прогон № 12: 84993464 тактов

       Прогон № 13: 92927920 тактов

Смотрите, расхождение между минимальным и максимальным времени выполнения составляет не много, не мало – 36%! А это значит, что вы не сможете обнаруживать "горячие" точки меньшей величины. Более того, вы не сможете оценивать степень влияния тех или иных оптимизирующих алгоритмов, если только они не дают по меньшей мере двукратного прироста производительности!

Отсюда правило: I) не всякая система пригодна для профилировки и оптимизации приложений

и II) если последовательные замеры дают значительный временной разброс, просто смените систему. (Под "системой" подразумевается не операционная система, а аппаратное обеспечение).

Архиерей – царство MS-DOS

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

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

Вскоре появился целый "пантеон" упаковщиков (их тогда писали все кому не лень) – AINEXE, DIET, EXEPACK, LZEXE, PKLITE и масса других – всех не перечислись! И не удивительно: процессоры день ото дня становились все производительнее и производительнее – уже на "тройке" распаковка занимала столь незначительное время, что им было можно полностью пренебречь. К тому же приятным побочным эффектом оказалась защита от дизассемблирования.

Действительно, непосредственно дизассемблировать упакованный файл невозможно, - прежде его необходимо распаковать. Конечно, на каждый щит найдется свой меч – из под пера хакеров вышло немало замечательных универсальных распаковщиков (UNP, Intruder, UUP, а вершиной всему стал CPU386 со встроенным эмулятором реального режима 80386 процессора), но качество автоматической распаковки оставляло желать лучшего (порой распакованные файлы зависали при запуске или в процессе работы), а ручной трассировкой владели далеко не все.

Словом, при всех своих достоинствах, упаковка исполняемых файлов не имела никаких недостатков и не собиралась сдавать позиций даже с приходом емких (по тем временам!) одно – двух гигабайтных жестких дисков и лазерных накопителей на CD-ROM.

Архитектура и характеристики кэшей современных микропроцессоров

Перечислять технические характеристики кэшей всех современных микропроцессоров – занятие неблагодарное, однако, крайне необходимое! Ведь код, оптимальный для одного процессора, может оказаться крайне неоптимальным для другого!

Важнейшей характеристикой является размер

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

и уж в самом крайнем случае "вылетать" в оперативную память (подробнее см. "Оптимизация обращения к памяти и кэшу. Влияние размера обрабатываемых данных на производительность")

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

Вторая по значимости характеристика – степень ассоциативности и размер банков кэша. Если степень ассоциативности окажется хотя бы на единицу меньшей, чем это вам необходимо, кэш будет работать вхолостую, под час в десятки раз снижая производительность. Чтобы этого не произошло, программист должен следить, чтобы интенсивно используемые данные по возможности не располагались по адресам, кратным размерам банков кэша. А это требование очень трудно обеспечить – размеры банков кэша варьируются в очень широких пределах, да и их ассоциативность тоже. Чтобы быть уверенным в отсутствии коллизий, необходимо тестировать программу на всех доступных процессорах и при необходимости, корректировать размещение структур данных. (подробнее см. "Оптимизация обращения к памяти и кэшу. Учет ограниченной ассоциативности кэша")

Третье – политика записи. От нее зависит: насколько эффективно выполняется операция записи в память. Все кэши современных процессоров поддерживают режим прямой записи с буферизацией и обратную запись, но количество буферов непостоянно и варьируется от процессора к процессору – от двух 64-битных буфера младших моделей Intel Pentium до двенадцати у Pentium?III (подробнее см. "Оптимизация обращения к памяти и кэшу. Особенности буферизации записи").

Четвертое – длина кэш-линий. В последних процессорах от Intel и AMD она расширена до 64 байт. Но больше – еще не значит лучше. Упреждающая загрузка наиболее эффективна именно при последовательной обработке данных, иначе кэш будет работать вхолостую.

Помимо перечисленных существует еще и масса других факторов, но и без того уже ясно: оптимизация кода под все микропроцессоры сразу – занятие не для слабонервных.

В приведенной ниже таблице (см. табл. 2) перечислены основные характеристики кэшей распространенных процессоров.

процессор

характеристика

Pentium II

CELERON

Pentium III

CELERON

Pentium 4

Athlon

размер (полный)

32 Кб

н/д

128 Кб

тип

раздельный

К

О

Д

размер

16 Кб

12K ops

64 Кб

протокол

ассоциативность

4-way

размер линеек

32 байта

6 mOPs

64 байт

банков в линии *1

н/д

размер банка *2

4 Кб

н/д

32 Кб

кол-во портов

алгоритм замещения

LRU

политика записи

–

блокировка

не блок.?

частота

1.0 x ядра

время доступа

нормальное

1 такт

line-splint

6 – 12 тактов

н/д

Д

А

Н

Н

Ы

Е

размер

16 Кб

8 Кб

64 Кб

протокол

MESI

MOESI

ассоциативность

4-way

2-way

размер линеек

32 байта

64 байта

банков в линии *1

размер банка *2

4 Кб

2 Кб

32 Кб

кол-во портов

алгоритм замещения

LRU

политика записи

блокировка

не блок.

не блок. +4

не блок.

частота

1.0 x ядра

время доступа

размещение

unified

on-die

unified

on-die

размер, Кб

128, 256, 512, >

512,1024,2048

тип *3

inclusive

exclusive

inclusive

exclusive

протокол

MESI

ассоциативность

4-way

размер кэш-линий

32 байта

64x2

64?

размер банка, Кб

32, 64, 128

128

кол-во портов

алгоритм замещения

LRU *3

LRU

политика записи

блокировка

не блок.

не блок.?

частота

0.5x

1.0x

0.5x

1.0x

1.0х

время доступа

10 тактов?

4 такта?

2 такта?

формула

2-1-1-1

1-1-1-1

ROB, входов

RS, входов

Read Buffer

4x32 байт?

Write Buffer

32 байт?

6 x 64 байт

частота системной шины, MHz

100

133

100x4

133x4

100х2

разрядность шины

L2 ßà L1

256

L2 ßà DRAM

64 / 128?

Таблица 2 Основные характеристики L1 и L2 кэшей современных процессоров

Архитектура памяти Windows

Создание самомодифицирующегося кода требует знания некоторых тонкостей архитектуры Windows, не очень-то хорошо освященных в документации. Точнее, совсем не освященных, но от этого отнюдь не приобретающих статус "недокументированных особенностей", поскольку, во-первых, они одинаково реализованы на всех Windows-платформах, а во-вторых, их активно использует компилятор VisualC++ от Microsoft. Отсюда следует, что никаких изменений даже в отдаленном будущем компания не планирует; в противном случае код, сгенерированный этим компилятором, откажет в работе, а на это Microsoft не пойдет (вернее, не должна пойти, если верить здравому смыслу).

Для адресации четырех гигабайт виртуальной памяти, выделенной в распоряжение процесса, Windows используют два селектора, один из которых загружается в сегментный регистр CS, а другой – в регистры DS, ES и SS. Оба селектора ссылаются на один и тот же базовый адрес памяти, равный нулю, и имеют идентичные лимиты, равные четырем гигабайтам. (Замечание: помимо перечисленных сегментных регистров, Windows еще использует и регистр FS, в который загружает селектор сегмента, содержащего информационный блок потока – TIB).

Фактически существует всего один

сегмент, вмещающий в себя и код, и данные, и стек процесса. Благодаря этому передача управления коду, расположенному в стеке, осуществляется близким (near) вызовом или переходом, и для доступа к содержимому стека использование префикса "SS" совершенно необязательно. Несмотря на то, что значение регистра CS не равно значению регистров DS, ES и SS, команды MOV dest,CS:[src]; MOV dest,DS:[src] и MOV dest,SS:[src]

в действительности обращаются к одной и той же ячейке памяти.

Отличия между регионами кода, стека и данных заключаются в атрибутах принадлежащих им страниц – страницы кода допускают чтение и исполнение, страницы данных – чтение и запись, а стека – чтение, запись и исполнение

одновременно.

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

Манипулировать атрибутами страниц, равно как и ассоциировать страницы с линейными адресами, может только операционная система или код, исполняющийся в нулевом кольце. В защите Windows 95\Windows 98 имеются люки, позволяющие прикладному коду повысить свои привилегии до супервизора, но выгода от их использования сомнительна, поскольку "привязывает" пользователя к этой операционной системе и не дает возможности проделать тот же трюк на Windows NT\Windows 2000.

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

Асинхронная статическая память

Асинхронная статическая память работает независимо от контроллера и потому, контроллер не может быть уверен, что окончание цикла обмена совпадет с началом очередного тактового импульса. В результате, цикл обмена удлиняется по крайней мере на один такт, снижая тем самым эффективную производительность. "Благодаря" последнему обстоятельству, в настоящее время асинхронная память практически нигде не применяется (последними компьютерами, на которых она еще использовались в качестве кэша второго уровня, стали "трешки" – машины, построенные на базе процессора Intel80386).

Балансировка логического древа

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

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

Но, задумайтесь: чем собственно занимается оператор switch? Если отвлечься от устоявшейся идиомы "оператор SWITCH дает специальный способ выбора одного из многих вариантов, который заключается в проверке совпадения значения данного выражения с одной из заданных констант в соответствующем ветвлении", то можно сказать, что switch – оператор поиска соответствующего значения. В таком случае линейное switch - дерево представляет собой тривиальный алгоритм последовательного поиска – самый неэффективный алгоритм из всех.

Пусть, например, исходный текст программы выглядел так:

switch (a)

{

case 98 : …;

case 4 : …;

case 3 : …;

case 9 : …;

case 22 : …;

case 0 : …;

case 11 : …;

case 666: …;

case 096: …;

case 777: …;

case 7 : …;

}

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

Исправить "перекос" можно разрезав одну ветку на две и "привив" образовавшиеся половинки к новому гнезду, содержащему условие, определяющее: в какой из веток следует искать сравниваемую переменную. Например, левая ветка может содержать гнезда с четными значениями, а правая – с нечетными. Но это плохой критерий: четных и нечетных значений редко бывает поровну и вновь образуется перекос (тем не менее никакого произвола нет и для балансировки можно использовать любой подходящий алгоритм).
Гораздо надежнее поступить так: берем наименьшее из всех значений и бросаем его в кучу А, затем берем наибольшее из всех значений и бросаем его в кучу B. Так повторяем до тех пор, пока не рассортируем все, имеющиеся значения.

Поскольку, оператор множественного выбора требует уникальности каждого значения, т.е. каждое число может встречаться в наборе (диапазоне) значений лишь однажды, легко показать, что: а) в обеих кучах будет содержаться равное количество чисел (в худшем случае – в одной куче окажется на одно число больше); б) все числа кучи A меньше наименьшего из чисел кучи B. Следовательно, достаточно выполнить только одно сравнение, чтобы определить: в какой из двух куч следует искать сравниваемое значения.

Высота нового дерева будет равна , где N – количество гнезд старого дерева. Действительно, мы же делим ветвь дерева надвое и добавляем новое гнездо – отсюда и берется и +1, а (N+1) необходимо для округления результата деления в большую сторону. Т.е. если высота не оптимизированного дерева достигала 100 гнезд, то теперь она уменьшилась до 51. Что? Говорите, 51 все равно много? А что нам мешает разбить каждую из двух ветвей еще на две? Это уменьшит высоту дерева до 27 гнезд! Аналогично, последующее уплотнение даст 16 à

12 à

11 à

9 à

8… и все! Более плотная упаковка дерева невозможна (подумайте почему – на худой конец постройте само дерево). Но, согласитесь, восемь гнезд – это не сто! Полное прохождение оптимизированного дерева потребует менее девяти сравнений!

Рисунок 1 0х001 Логическое дерево до утрамбовки (слева) и после (справа)

Из всех трех рассматриваемых компиляторов "трамбовать" switch-и не умеет один лишь WATCOM, а Visual C++ и Borland C++ сполна справляются с этой задачей.

BEDO (Burst EDO) – пакетная EDO RAM

Двукратное увеличение производительности было достигнуто лишь в BEDO-DRAM (Burst EDO – пакетная EDO RAM). Добавив в микросхему генератор номера столбца, конструкторы ликвидировали задержку CASDelay, сократив время цикла до 15 нс. После обращения к произвольной ячейке микросхема BEDO автоматически, без указаний со стороны контроллера, увеличивает номер столбца на единицу, не требуя его явной передачи. По причине ограниченной разрядности адресного счетчика (конструкторы отвели под него всего лишь два бита) максимальная длина пакета не могла превышать четырех ячеек (22=4).

Забегая вперед, отметим, что процессоры Intel 80486 и Pentium в силу пакетного режима обмена с памятью никогда не обрабатывают менее четырех смежных ячеек за раз (подробнее см. "Взаимодействие памяти и процессора"). Поэтому, независимо от порядка обращения к данным, BEDO всегда работает на максимально возможной скорости и для частоты 66 Мгц ее формула выглядит так: 5-1-1-1, что на ~40% быстрее EDO-DRAM!

Все же, несмотря на свои скоростные показатели, BEDO оказалась не конкурентоспособной и не получила практически никакого распространения. Просчет состоял в том, что BEDO, как и все ее предшественники, оставалась асинхронной

памятью. Это накладывало жесткие ограничения на максимально достижимую тактовую частоту, ограниченную 60 – 66 (75) мегагерцами. Действительно, пусть время рабочего цикла составляет 15 нс. (1 такт в 66 MHz системе). Однако поскольку "часы" контроллера памяти и самой микросхемы памяти не синхронизованы, нет никаких гарантий, что начало рабочего цикла микросхемы памяти совпадет с началом такового импульса контроллера, вследствие чего минимальное время ожидания составляет два такта.

Вернее, если быть совсем точным, рабочий цикл никогда не совпадает с началом тактового импульса. Несколько наносекунд уходит на формирование контроллером управляющего сигнала RAS или CAS, за счет чего он уже не совпадет с началом тактирующего импульса. Еще несколько наносекунд требуется для стабилизации сигнала и "осмысления" его микросхемой, причем, сколько именно времени потребуется заранее определить невозможно, т.к. на результат влияет и температура, и длина проводников, и помехи на линии, и… еще миллион факторов!

Блокируемая и не блокируемая кэш память

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

Блокируемая кэш память, как и следует из ее названия, блокирует доступ к кэшу после всякого кэш-промаха. Независимо от того, присутствуют ли запрашиваемые данные в сверхоперативной памяти или нет, до тех пор, пока кэш-строка, вызвавшая промах не будет целиком загружена (выгружена), кэш не сможет обрабатывать никаких других запросов ("…a read hit or miss after a read miss waits until the prior miss fills the cache", – как говорят англичане). В настоящее время блокируемая кэш память практически не используется, поскольку при частных кэш-промахах, она работает крайне непроизводительно.

Не блокируемая кэш память, напротив, позволяет работать с кэшем параллельно с загрузкой (выгрузкой) кэш-строк. То есть, кэш-промахи не препятствует кэш-попаданиям. И это – хорошо! Несмотря на то, что не блокируемая кэш память имеет значительно большую аппаратную сложность (а, значит, и стоимость), в силу своей привлекательности, она широко используется в старших процессорах семейства x86, как, впрочем, и во многих других современных процессорах.

Brief

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

a) разворачивайте циклы, читающие память

b) устраняйте зависимости по данным

c) отправляйте контроллеру памяти несколько запросов одновременно

d) запрашивайте данные на чтение с шагом не меньшим 32 байт

e) группируйте операции чтения памяти с операциями записи

f) используйте все страницы к которым обращаетесь целиком

g) обрабатывать данные с шагом, исключающим попадание на ту же самую страницу.

h) виртуализуйте потоки данных

i) обрабатывайте данные двойными словами

j) выравнивание адреса источников данных

k) комбинируйте вычисления с доступом к памяти

l) обращайтесь к памяти только тогда когда это действительно необходимо

m) никогда не оптимизируйте программу на отдельно взятой машине

Буфера записи

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

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

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

В частности, процессоры AMD K6 и Athlon всегда выгружают содержимое буферов записи в кэш первого уровня, благодаря чему скорость их опорожнения весьма велика (при благоприятном стечении обстоятельств каждый 32/64? байтовый буфер выгружается за один такт), а выгруженные данные вплоть до вытеснения их из L1-кэша доступны на чтение практически мгновенно!

Процессоры P6 и P-4, напротив, направляют содержимое буферов записи в кэш второго, а не первого уровня. (Конечно, если записываемые данные уже содержаться в L1-кэше они помещаются именно туда). Эффективность такой стратегии не бесспорна. С одной стороны: это приводит к тому, что процессор переносит значительно меньшую интенсивность промахов записи, а с другой: выгрузка записываемых данных в кэш второго уровня не загрязняет кэш первого уровня, в конечном итоге увеличивая его эффективную емкость.

Кстати, нетривиальным следствием такой политики выгрузки буферов, становится искажение политики кэш-записи. Несмотря на то, что кэш первого уровня формально построен по Write Back архитектуре, фактически он работает по схеме Write True, поскольку промах записи приводит к непосредственному обновлению кэш?памяти более высокой иерархии без загрузки модифицируемых данных в кэш.
Забавно, но Intel впервые "проговорилась" об этом факте лишь в документации по процессору Pentium-4, где в графе " политика записи кэша первого уровня" честно указано "Write True", а не "Write Back", как это утверждалось в документации по процессорам предыдущего поколения.

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

перегрузки, когда несколько промахов возникают одновременно (или идут с минимальным отрывом друг от друга), а затем вновь наступает "тишина".

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

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

·         при выполнении инструкции с префиксом монопольного захвата шины (LOCK);

·         при выполнении инструкции упорядоченного выполнения (например, CPUID);

·         при выполнении инструкции выгрузки буферов SFNCE (Pentium III и выше);

·         при выполнении инструкции выгрузки буферов MFENCE (Pentium-4)

·         при возникновении исключения или вызове прерывания;

·         при записи или чтении в/из порта ввода-вывода;

·         при выполнении инструкции BINIT;

Упорядочивание записи. Помимо всего прочего, на буфера еще возложена и функция упорядочивания записи. Старшие представители семейства x86 разбивают машинные инструкции на микрооперации, выполняя их в наиболее предпочтительном с точки зрения RISC-ядра процессора, порядке. Но ведь нарушение очередности операций чтения/записи в память (кэш) может запросто нарушить нормальную работу программы!

Задумайтесь, что произойдет если в следующем блоке кода "a = *p; *p = b;" запись ячейки *p завершится раньше ее чтения? Спрашивайте, а почему такое вообще может случиться? Да мало ли почему! Допустим, блок чтения данных занят обработкой предыдущей инструкции и команда a = *p

вынуждена терпеливо дожидаться свой очереди, в то время как команда *p = b

захватывается бездельничающим в этот момент блоком записи.

Конечно, блок записи можно до завершения чтения и притормозить, но производительности такая мера не добавит – это уж точно. Выход?! Выход: временно сохранить записываемые данные не в кэше (основной памяти), а в некотором промежуточном буфере. Чтобы не захламлять архитектуру микроядра и не вводить еще один буфер, конструкторы решили для этих целей использовать все те же буфера записи. Политика выгрузки данных из буфера гарантирует, что данные, помещенные в буфер, покинут его "застенки" не раньше, чем завершаться все, предшествующие им инструкции. Таким образом, с буфера данные сходят уже упорядоченными и потому никаких конфликтов не возникает.

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

Реализация и характеристики буферов записи.

Младшие модели Pentium имели всего два буфера записи (write buffers) – по одному на каждую U- и V-трубу, но уже в Pentium MMX количество буферов возросло до четырех, а в Pentium II их и вовсе насчитывается двенадцать! Причем, начиная с Pentium II буфера записи переименованы в Складские Буфера (store buffers), однако, во избежании путаницы, здесь и далее мы будем пользоваться исключительно прежним термином. Все равно "store" и "write" в русском переводе – синонимы (во всяком случае, в рамках данного контекста)

Учитывая, что размер каждого из буферов составляет 32 байт, можно безболезненно сохранять до 384 байт (96 двойных слов) за раз, не беспокоясь за кэш-промахи. Но помните, что попытки записи в некэшируемую память при полностью заполненный буферах приводят к неустранимым кэш-промахам и вытекающих отсюда штрафным задержкам.

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

Цели и задачи кэш-памяти

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

В задачи кэша входит:

а) обеспечение быстрого доступа к интенсивно используемым данным;

b) согласование интерфейсов процессора и контроллера памяти;

с) упреждающая загрузка данных;

d) отложенная запись данных.

Обеспечение быстрого доступа к интенсивно используемым данным. Архитектурно кэш-память расположена между процессором основной оперативной памятью (см. рис. 0x009) и охватывает все (реже часть) адресного пространства. Перехватывая запросы к основной памяти, кэш-контроллер смотрит: есть ли действительная (валидная от английского valid) копия затребованных данных в кэше. Если такая копия там действительно есть, то данные наскоро извлекаются из сверхоперативной памяти и происходит так называемое кэш-попадание (cache hit). В противном случае говорят о промахе

– (cache miss), и тогда запрос данных переадресуется к основной оперативной памяти.

Рисунок 9 0х009 Расположение кэша в иерархии оперативной памяти

Для достижения наивысшей производительности кэш-промахи должны происходить как можно реже (а в идеале – не происходить вообще). Учитывая, что емкость сверхоперативной памяти намного меньше емкости основной оперативной памяти, добиться этого не так-то просто! И в служебные обязанности кэш-контроллера в первую очередь входит накопление в сверхоперативной памяти действительно нужных данных и своевременное удаление оттуда всякого "мусора", – данных, которые более не понадобятся. Поскольку, кэш-контроллер не имеет абсолютно никакого представления о назначении обрабатываемых данных, эта задача требует нехилого искусственного интеллекта. Но, увы, кэш-контроллеры персональных процессоров интеллектом не обременены и слепо действуют по одному из нескольких шаблонов, называемых стратегиями кэширования.

Стратегия помещения данных в кэш- память представляет собой алгоритм, определяющий: стоит ли помещать копию запрошенных данных в сверхоперативную память или нет? Процессоры класса Intel Pentium (и совместимые с ними процессоры AMD) не мудрствуя лукаво, помещают в кэш все данные, к которым хотя бы однократно происходит обращение.

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

Поиск вот таких наименее нужных данных и называется стратегия замещения. Можно принимать решение, основываясь на количестве обращений к каждой порции данных (частотный анализ), можно – на времени последнего обращения, выбрав ту, к которой дольше всего не обращались (алгоритм LRU – Least Recently Used), можно – на времени загрузки из основной памяти, вытеснив ту, которая была загружена раньше всех (алгоритм FIFO – First Input First Output), а можно просто подкинуть монетку (randomize-алгоритм)– на кого судьба ляжет, – ту и вытеснять (кстати, именно такая стратегия замещения использовалась в процессорах AMD K5).

В современных процессорах семейства x86 встречаются исключительно стратегии FIFO и LRU, частотный же анализ ввиду сложности его реализации в них не используется.

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

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

Естественно, до той поры, пока остальные карандаши не будут реально востребованы (конечно, если они вообще будут востребованы), их необходимо где-то хранить. Решение: извлечь один-единственный карандаш из упаковки и выбросить остатки, – слишком нерационально, поэтому здесь не рассматривается. Тем более, что подходящее хранилище для пакетов данных у нас есть – это кэш. Получив пакет данных со склада, пардон, загрузив их из основной оперативной памяти, кэш позволяет процессору обрабатывать эти данные с любой разрядностью. Именно этим, кстати, объясняется выбранная стратегия загрузки данных (см. "Стратегия помещения данных"). Кэш-контроллер вынужден помещать в сверхоперативную памяти все ячейки, к которым происходит обращение, уже хотя бы потому, что выкидывать их, как карандаши, в приведенном выше примере, было бы крайне нерационально.

Упреждающая загрузка данных. Существует несколько стратегий загрузки данных из основной оперативной памяти в кэш-память. Простейший алгоритм загрузки, называемый загрузкой по требованию (on demand), предписывает обращаться к основной памяти только после того, как затребованных процессором данные не окажется в кэше (то есть, попросту говоря, после возникновения кэш-промаха). В результате, в кэше окажутся действительно именно те данные, которые нам нужны (и это плюс!), однако, при первом обращении к ячейке, процессору придется очень долго ждать – приблизительно 20 тактов системной шины, если не дольше, – а вот это минус!

Стратегия спекулятивной (speculative) загрузки, напротив, предписывает помещать данные в кэш задолго то того, как к ним произойдет реальное обращение. Откуда же кэш-контроллер может знать, какие именно ячейки памяти потребуется процессору в ближайшем будущем? Ну… наверняка знать этого он этого, конечно, не может, но почему бы ему не попробовать просто угадать?

Алгоритмы угадывания делятся на интеллектуальные и неинтеллектуальные. Типичный пример неинтеллектуального алгоритма – опережающая загрузка.

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

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

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

До недавнего прошлого интеллектуальные кэш-контроллеры использовались разве что в суперкомпьютерах и высокопроизводительных рабочих станциях, но теперь они реализованы в процессорах P-4 и AMD Athlon XP (см. "Оптимизация обращения к памяти и кэшу. Управление кэшированием в x86 процессорах старших поколений. Аппаратная предвыборка в микропроцессоре P-4")

Стратегии поиска данных. В соответствии с выбранной стратегией загрузка данных из памяти может начинаться либо после фиксации кэш-промаха (стратегия Look Through), либо осуществляться параллельно с проверкой наличия соответствующей копии данных в сверхоперативной памяти и прерываться в случае кэш-попадания (стратегия Look aside). Последнее сокращает накладные расходы на кэш-промахи, уменьшая тем самым латентность загрузки данных, но зато увеличивает энергопотребление, что в ряде случаев оказывается неприемлемо большой платой за в общем-то довольно незначительную прибавку производительности.

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

Механизм отложенной записи в x86 процессорах, реализован начиная с Pentium и AMD K6. Более ранние модели были вынужденные непосредственно записывать в основную память каждую модифицируемую ячейку, что серьезно ограничивало их быстродействие. К счастью, сегодня такие процессоры практически не встречаются и об этой проблеме уже можно забыть.

Цели и задачи профилировки

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

Большинство современных профилировщиков поддерживают следующий набор базовых операций:

определение общего времени исполнения каждой точки программы (total [spots] timing)

определение удельного времени исполнения каждой точки программы ([spots] timing)

определение причины и/или источника конфликтов и пенальти (penalty information)

определение количества вызовов той или иной точки программы ([spots] count)

определение степени покрытия программы ([spots] covering)

Часть 0 Профилировка программ

Профилировкой

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

(HotSpots), – тех участков программы, на выполнение которых расходуется наибольше количество времени.

Согласно правилу "10/90", десять процентов кода съедают девяносто процентов производительности системы (равно как и десять процентов людей выпивают девяносто процентов всего пива). Если время, потраченное на выполнение каждой машинной инструкции, изобразить графически в порядке возрастания их линейных адресов, на полученной диаграмме мы обнаружим несколько высоченных пиков, горделиво возвышающихся над практически пустой равниной, усеянной множеством низеньких холмиков (см. рис. 0x001) Вот эти самые пики – "горячие" точки и есть.

Почему "температура" различных участков программы столь неодинакова? Причина в том, что подавляющее большинство вычислительных алгоритмов так или иначе сводятся к циклам, – т.е. многократным повторениям одного фрагмента кода, причем зачастую циклы обрабатываются не последовательно, а образуют более или менее глубокие иерархии, организованные по типу "матрешки". В результате, львиную долю всего времени выполнения, программа проводит в циклах с наибольшим уровнем вложения и именно их оптимизация дает наилучший прирост производительности!

Громоздкие и тормозные, но редко вызываемые функции оптимизировать нет какой нужды, – это практически не увеличит быстродействия приложения (ну разве что они совсем уж криво будет написаны).

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

Профилировщик

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

Правило номер один: ликвидация не самых горячих точке программы, практически не увеличивает ее быстродействия.

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

Часть I Оперативная память

Оперативная память персональных компьютеров сегодня, как и десять лет тому назад, строится на базе относительно дешевой динамической памяти – DRAM (Dynamic Random Access Memory). Множество поколений интерфейсной логики, соединяющей ядро памяти с "внешним миром", сменилось за это время. Эволюция носила ярко выраженный преемственный характер – каждое новое поколение памяти практически полностью наследовало архитектуру предыдущего, включая и свойственные ему ограничения. Ядро же памяти (за исключением совершенствования проектных норм таких, например, как степень интеграции) и вовсе не претерпевало никаких принципиальных изменений! Даже "революционный" Rambus DirectRDRAM ничего подлинного революционного в себе не несет и хорошо вписывается в общее "генеалогическое" древо развития памяти.

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

Стоит заметить: в этой главе приводятся лишь необходимый минимум сведений об устройстве оперативной памяти, без которых грамотная оптимизация программ просто немыслима. Настоятельно рекомендуется не ограничиваться "необходимым минимумом", а познакомится с микросхемами памяти во всех подробностях, обратившись к спецификациями и технической документации, распространяемой производителями. Наилучшей (на взгляд автора) документацией можно разжиться на серверах www.IBM.com, www.SAMSUNG.com, www.INTEL.com и www.AMD.com. Много полезной информации можно найти и на сайте www.iXBT.com (и других, подобных ему).

Часть II Подсистема кэш-памяти

"Тогда мы поняли настоящую цену учебникам типа "Язык XXX за двадцать один день" или "YYY - это просто!".

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

"Редкая профессия" Евгений Зуев

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

Я искренне надеюсь, что вы сочтете настоящее описание кэш-подсистемы лучшим из имеющихся, но даже оно не освещает и доли тайн кэш-памяти! Перед вами – лишь небольшая часть того, что мне удалось нарыть. Увы! Сжатые временные сроки не позволили рассказать обо всем и пришлось ограничится только самой необходимой информацией…

Часть III Машинная оптимизация

"Лучший способ оптимизации - не оптимизировать вообще, а изначально производить хороший код"

Джон Спрей

Часть IV Приложение I Программистская копилка

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

Данная приложение представляет собой сборник некоторых статей автора, которые прямо или косвенно относятся к подсистеме оперативной памяти, оптимизации, эффективным приемам кодирования и т.д.

Conventional DRAM (Page Mode DRAM) – "обычная" DRAM

Разобравшись с устройством и работой ядра памяти, перейдем к рассмотрению ее интерфейса. Физически микросхема памяти (не путать с модулями памяти, – о них речь еще впереди) представляет собой прямоугольный кусок керамики (или пластика) "ощетинившийся" с двух (реже – с четырех) сторон множеством ножек. Что это за ножки?

В первую очередь выделим среди них линии адреса

и линии данных. Линии адреса, как и следует из их названия, служат для выбора конкретной ячейки памяти, а линии данных – для чтения и для записи ее содержимого. Необходимый режим работы определяется состоянием специального вывода Write Enable (Разрешение Записи).

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

Такой трюк значительно сокращает количество выводов микросхемы, что в свою очередь уменьшает ее габариты. А, чем меньше габариты, тем выше предельно допустимая тактовая частота. Почему? О, тут замешен целый ряд физических явлений и эффектов. Во-первых, в силу ограниченной скорости распространения электрических сигналов, длины проводников, подведенных к различным ножкам микросхемы, должны не сильно отличаться друг от друга, иначе сигнал от одного вывода будет опережать сигнал от другого. Во-вторых, эти самые длины не должны быть очень велики – в противном случае задержка распространения сигнала "съест" все быстродействие. В-третьих, любой проводник действует как приемная и как передающая антенна, причем это воздействие резко усиливается с ростом тактовой частоты. Паразитному антенному эффекту можно противостоять множеством способов (например, путем перекашивания сигналов в соседних разрядах), но самой радикальной мерой было и до сих пор остается сокращение длин и количества проводников. Наконец, в-четвертых, всякий проводник обладает электрической емкостью. А емкость и скорость передачи данных – несовместимы! Вот только один пример: "…первый трансатлантический кабель для телеграфа был успешно проложен в 1858 году,… когда напряжение прикладывалось к одному концу кабеля, оно не появлялось немедленно на другом конце и вместо скачкообразного нарастания достигало стабильного значения после некоторого периода времени.
Когда снимали напряжение, напряжение приемного конца не падало резко, а медленно снижалось. Кабель вел себя как губка, накапливая электричество. Это свойство мы теперь называем емкостью".

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

Столбцы

и строки матрицы памяти тем же самым способом совмещаются в единых адресных линиях. В случае квадратной матрицы количество адресных линий сокращается вдвое, но и выбор конкретной ячейки памяти отнимает вдвое больше тактов, ведь номера столбца и строки приходится передавать последовательно. Причем, возникает неоднозначность, что именно в данный момент находится на адресной линии: номер строки или номер столбца? А, быть может, и вовсе не находится ничего? Решение этой проблемы потребовало двух дополнительных выводов, сигнализирующих о наличии столбца или строки на адресных линиях и окрещенных RAS (от row address strobe – строб адреса строки) и CAS (от column address strobe – строб адреса столбца) соответственно. В спокойном состоянии на обоих выводах поддерживается высокий уровень сигнала, что говорит микросхеме: никакой информации на адресных линиях нет и никаких действий предпринимать не требуется.

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

Чувствительный усилитель декодирует всю строку, преобразуя ее в последовательность нулей и единиц, и сохраняет полученную информацию в специальном буфере. Все это (в зависимости от конструктивных особенностей и качества изготовления микросхемы) занимает от двадцати до сотни наносекунд, в течение которых контроллер памяти выдерживает терпеливую паузу. Наконец, когда микросхема завершает чтение строки и вновь готова к приему информации, контроллер подает на адресные линии номер колонки и, дав сигналу стабилизироваться, сбрасывает CAS в низкое состояние. "Ага!", говорит микросхема и преобразует номер колонки в смещение ячейки внутри буфера. Остается прочесть ее содержимое и выдать его на линии данных. Это занимает еще какое-то время, в течение которого контроллер ждет запрошенную информацию. На финальной стадии цикла обмена контроллер считывает состояние линий данных, дезактивирует сигналы RAS и CAS, устанавливая их в высокое состояние, а микросхема берет определенный тайм-аут на перезарядку внутренних цепей и восстановительную перезапись строки (если, конечно, восстановительная перезапись выполняется самой микросхемой).

Задержка между подачей номера строки и номера столбца на техническом жаргоне называется "RAS to CAS delay" (на сухом официальном языке – tRCD). Задержка между подачей номера столбца и получением содержимого ячейки на выходе – "CAS delay" (или tCAC), а задержка между чтением последней ячейки и подачей номера новой строки – "RAS precharge" (tRP). Здесь и ниже будут использоваться исключительно жаргонизмы – они более наглядны и к тому же созвучны соответствующим настойкам BIOS, что упрощает восприятие материала.

Рисунок 5 0х12 Схематическое изображение модуля оперативной памяти (1); микросхемы памяти (2); матрицы (3) и отдельной ячейки памяти (4)

Рисунок 6 scm.dram Устройство ячейки современной микросхемы динамической памяти

DDR SDRAM, SDRAM II (Double Data Rate SDRAM) SDRAM с удвоенной скоростью передачи данных

Дальнейшее совершенствование синхронной памяти привело к появлению DDR?SDRAM – Double Data Rate SDRAM (SDRAM удвоенной скорости передачи данных). Удвоение скорости достигается за счет передачи данных и по фронту, и по спаду тактового импульса (в SDRAM передача данных осуществляется только по фронту). Благодаря этому эффективная частота увеличивается в два раза – 100MHz DDR-SDRAM по своей производительности эквивалента 200 MHz SDRAM (на самом деле, это не совсем так, см. "Вычисление полного времени доступа"). Правда, по маркетинговым соображениям, производители DDR-микросхем стали маркировать их не тактовой /* рабочей */ частой, а максимально достижимой пропускной способностью, измеряемой в мегабайтах в секунду. Т.е. DDR-1600 работает вовсе не на 1.6 GHz (что пока является недостижимым идеалом), а всего лишь на 100 MHz. Соответственно, DDR?2100 работает на частоте 133 MHz.

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

Деление

Деление – очень "дорогостоящая" операция, даже на старших моделях процессоров Intel Pentium занимающая до сорока и более тактов. Кошмар! К счастью процесс деления поддается оптимизации.

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

К сожалению, компиляторы Borland C++ и WATCOM не настолько "умны", чтобы заменять деление умножением – на это способен один лишь Microsoft Visual C++, за что честь ему и хвала! Битовые же сдвиги используют все три рассматриваемых компилятора.

Двухуровневая организация кэша

Предельно достижимая емкость кэш-памяти ограничена не только ее ценой, но и электромагнитной интерференцией (см. "Часть I Оперативная память. Устройство и принципы функционирования оперативной памяти. RDRAM Rambus DRAM – Rambus-память"), налагающей жесткие ограничения на максимально возможное количество адресных линий, а значит – на непосредственно адресуемый объем памяти. В принципе, мы можем прибегнуть к мультиплексированию выводов или последовательной передаче адресов (как, например, поступили разработчики Rambus RDRAM), но это неизбежно снизит производительность и доступ к ячейке кэш-памяти потребует более одного такта, что не есть хорошо.

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

Естественный выход состоит в создании многоуровневой кэш-иерархии (см. рис. 0х013). Большинство современных систем имеют как минимум два уровня кэш памяти. Первый, наиболее "близкий" к процессору (условно обозначаемый Level 1

или сокращенно L1), обычно реализуется на быстрой двух портовой синхронной статической памяти, работающей на полной частоте ядра процессора. Объем L1-кэша весьма не велик и редко превышает 32 Кб, поэтому он должен хранить только самые-самые необходимые данные. Зато на обработку двух полно разрядных ячеек уходит всего один такт. (Внимание: процессоры x86 оснащаются не истинно двух портовой памятью! Двух портовый у нее лишь интерфейс, а ядро памяти состоит из нескольких независимых банков, – обычно восьми, реализованных на одно-портовый матрицах, и параллельный доступ возможен лишь к ячейкам разных банков. см. "Оптимизация обращения к памяти и кэшу. Стратегия распределения данных по кэш-банкам.")

Между кэшем первого уровня и оперативной памятью расположен кэш второго уровня (условно обозначаемый Level 2

или сокращенно L2). Он реализуется на одно-портовой конвейерной статической памяти (BSRAM) и зачастую работает на пониженной тактовой частоте.
Поскольку одно- портовая память значительно дешевле, объем L2 кэша составляет сотни килобайт, а зачастую достигает и нескольких мегабайт! Между тем скорость доступа к нему относительно невелика (хотя, естественно, многократно превосходит скорость доступа к основной памяти).

Во-первых, минимальной порцией обмена между L1 и L2 кэшем является отнюдь не байт, а целая кэш-линейка, на чтение которой уходит в среднем 5 тактов частоты кэша второго уровня (напоминаем, что формула BSRAM памяти выглядит так: 2-1-1-1). Если L2-кэш работает на половинной частоте процессора, то обращение к одной ячейке займет целых 10 тактов. Разумеется, эту величину можно сократить. В серверах и высокопроизводительных рабочих станциях кэш второго уровня чаще всего работает на полной частоте ядра процессора и зачастую имеет учетверенную разрядность шины данных, благодаря чему пакетный цикл обмена завершается всего за один такт. Однако и стоимость таких систем соответствующая.

Рисунок 12 0х013 Двух уровневая кэш-иерархия

Включающая (inclusive) архитектура.

Кэш второго уровня, построенный по inclusive-архитектуре, всегда дублирует содержимое кэша первого уровня, а потому эффективная емкость сверхоперативной памяти обоих иерархий равна: L2.CACHE_SIZE – L1.CACHE.SIZE + L1.CACHE.SIZE == L2.CACHE.SIZE.

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

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

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

Между тем, практически все современные процессоры (AMD K6, P-II, P-III) построенные именно по включающей архитектуре.

Рисунок 13 0х014 0х015 inclusive- (слева) и exclusive- (справа) архитектуры

Исключающая (exclusive) архитектура.

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

размеров сверхоперативной памяти всех иерархий.

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

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

На сегодняшний день эксклюзивная кэш-подсистема реализована в одном лишь процессоре AMD Athlon, да и то не с первых моделей (см. так же. "Оптимизация обращения к памяти и кэшу. Влияние размера обрабатываемых данных на производительность. Особенности кэш-подсистемы процессора AMD Athlon")

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

EDO-DRAM (Extended Data Out) память с усовершенствованным выходом

Изобретение FPM-DRAM не решило проблему производительности, но дало короткую передышку – ведь тактовые частоты микропроцессоров не стояли на месте, а стремительно росли, вплотную приближаясь к рубежу в 200 МГц. Рынок требовал качественного нового решения, а не изнуряющей борьбы за каждую наносекунду. Инженеров вновь отправили к чертежным доскам, где (году эдак в 1996) их осенила очередная гениальная идея. Если оснастить микросхему специальным триггером-защелкой, удерживающим линии данных после исчезновения сигнала CAS, станет возможным дезактивировать CAS до окончания чтения данных, подготавливая в это время микросхему к приему номера следующего столбца.

Взгляните на диаграмму рис. 0х23: видите, у FPM низкое состояние CAS удерживается вплоть до окончания считывания данных, затем CAS дезактивируется, выдерживается небольшая пауза на перезарядку внутренних цепей, и только после этого на адресную шину подается номер колонки следующей ячейки. В новом типе памяти, получившем название EDO?DRAM (Extend Data Output – память с усовершенствованным выходом), напротив, CAS дезактивируется в процессе чтения данных параллельно с перезарядкой внутренних цепей, благодаря чему номер следующего столбца может подаваться до завершения считывания линий данных. Продолжительность рабочего цикла EDO-DRAM (в зависимости от качества микросхемы) составляла 30-, 25- и 20 нс., что соответствовало всего двум тактам в 66 МГц системе. Совершенствование производственных технологий сократило и полное время доступа. На частоте 66 МГц формула лучших микросхем выглядела так: 5?2?x?x. Простой расчет позволяет установить, что пиковый прирост производительности составил около 30%, однако, во многих компьютерных журналах тех лет фигурировала совершенно немыслимая цифра 50%, – якобы настолько увеличивалась скорость компьютера при переходе с FPM на EDO. Это могло быть лишь при сравнении худшей FMP- с самой "крутой" EDO-памятью, т.е. фактически сравнивались не технологии, а старые и новые микросхемы.

Рисунок 7 0x23 Временная диаграмма, иллюстрирующая работу некоторых типов памяти

Елей и деготь оптимизирующих компиляторов

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

Так происходит потому, что на чистом

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

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

В частности, программа, приведенная в листинге 3, молчаливо полагает, что указатель на функцию совпадает с точкой входа в эту функцию, а все тело функции расположено непосредственно за точкой входа. Именно такой код (наиболее очевидный с точки зрения здравого смысла) и генерирует подавляющее большинство компиляторов. Большинство, но не все! Тот же MicrosoftVisual C++ в режиме отладки вместо функций вставляет "переходники", а сами функции размешает совсем в другом месте. В результате, в стек копируется содержимое "переходника", но не само тело функции! Заставить Microsoft Visual C++ генерировать "правильный" код можно сбросом флажка "Link incrementally". У других компиляторов название этой опции может значительно отличаться, а в худшем случае – вообще отсутствовать. Если это так – придется отказаться либо от самомодифицирующегося кода, либо от данного компилятора.

Естественное (natural) выравнивание данных

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

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

размер данных	степень выравнивания
P-Plain, P MMX	P Pro, P-II, P-III	Athlon
1 байт (8 битов)	Произвольная	Произвольная	Произвольная
2 байта (16 битов)	Кратная 2 байтам	Кратная 2 байтам	Кратная 2 байтам
4 байта (32 бита)	Кратная 4 байтам	Кратная 4 байтам	Кратная 4 байтам
6 байт (48 бит)	Кратная 4 байтам	Кратная 8 байтам	Кратная 8 байтам
8 байтов (64 бита)	Кратная 8 байтам	Кратная 8 байтам	Кратная 8 байтам
10 байтов (80 битов)	Кратная 16 байтам	Кратная 16 байтам	Кратная 16 байтам
16 байтов (128 битов)	Кратная 16 байтам	Кратная 16 байтам	Кратная 16 байтам

Таблица 4 Предпочтительная степень выравнивания для различных типов данных

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

Рисунок 24 0х26 Естественное выравнивание данных

FECI QUOD POTUI, FACIANT MELIORA POTENTES

Хочу закончить свою книгу. Вот и все. Я меняю себя на нее. Мне кажется, что она вцепилась в меня, как якорь.

Антуан де Сент-Экзюпери. Цитадель

Фоновое копирование памяти

Фактически, фоновое копирование памяти, – есть ни что иное, как прозрачное комбинирование вычислительных операций с загрузкой ячеек из оперативной памяти. Возвращаясь к предыдущей задаче (загрузить N ячеек памяти и k раз вычислить синус угла), – а что если поместить цикл загрузки ячеек в один, а цикл вычисления синуса в другой поток? И пусть процессор сам разбирается в какой концентрации их лучше всего смешивать. Э, нет! Все не так просто! Потоки (в том виде, в котором они поддерживаются операционной системой) для решения этой задачи абсолютно непригодны. В течение кванта времени, выделяемого потоку, процессор успевает загрузить из памяти десятки мегабайт данных, что явно не входит в наши планы, поскольку мы хотим выполнять оба потока параллельно. Что ж, приходится эмулировать много поточность самостоятельно. Самый простой путь решения

Формула памяти

К середине девяностых среднее значение RASto CAS Delay составляло порядка 30 нс., CAS Delay – 40 нс., а RAS precharge – менее 30 нс. (наносекунд). Таким образом, при частоте системной шины в 60 МГц (т.е. ~17 нс.) на открытие и доступ к первой ячейки страницы уходило около 6 тактов, а на доступ к остальным ячейкам открытой страницы – около 3 тактов. Схематически это записывается как 6-3-x-x и называется формулой памяти.

Формула памяти упрощает сравнение различных микросхем друг с другом, однако для достоверного сравнения необходимо знать преобладающий тип обращений к памяти: последовательный или хаотичный. Например, как узнать, какая из двух микросхем лучше: 5?4?x?x или 6?3?x?x? В данной постановке вопрос вообще лишен смысла. Лучше для чего? Для потоковых алгоритмов с последовательной обработкой данных, бесспорно, предпочтительнее последний тип памяти, в противном случае сравнение бессмысленно, т.к. чтение двух несмежных ячеек займет не 5-5-х-х и, соответственно, 6?6?х?х тактов, а 5+RAS Precharge?5+RAS Precharge?x?x и 6+RAS prechange-6+RAS prechange?x?x. Поскольку время регенерации обоих микросхем не обязательно должно совпадать, может сложиться так, что микросхема 6?3?x?x окажется быстрее и для последовательного, и для хаотичного доступа. Поэтому, практическое значение имеет сравнение лишь вторых цифр – времени рабочего цикла. Совершенствуя ядро памяти, производители сократили его сначала до 35, а затем и до 30 нс., достигнув практически семикратного превосходства над микросхемами прошлого поколения.

FPM DRAM (Fast Page Mode DRAM) быстрая страничная память

Первой ласточкой стала FPM-DRAM – Fast-Page Mode DRAM (Память быстрого страничного режима), разработанная в 1995 году. Основным отличием от памяти предыдущего поколения стала поддержка сокращенных адресов. Если очередная запрашиваемая ячейка находится в той же самой строке, что и предыдущая, ее адрес однозначно определяется одним лишь номером столбца и передача номера строки уже не требуется. За счет чего это достигается? Обратимся к диаграмме, изображенной на рис 0x23. Смотрите, в то время как при работе с обычной DRAM (верхняя диаграмма) после считывания данных сигнал RAS дезактивируется, подготавливая микросхему к новому циклу обмена, контроллер FPM-DRAM удерживает RAS в низком состоянии, избавляясь от повторной пересылки номера строки.

При последовательном чтении ячеек памяти, равно как и обработке компактных одно?двух килобайтовых структур, время доступа сокращается на 40%, а то и больше, ведь обрабатываемая строка находится во внутреннем буфере микросхемы, и обращаться к матрице памяти нет никакой необходимости!

Правда, хаотичное обращение к памяти, равно как и перекрестные запросы ячеек из различных страниц, со всей очевидностью не могут воспользоваться преимуществами передачи сокращенных адресов и работают с FPM-DRAM в режиме обычной DRAM. Если очередная запрашиваемая ячейка лежит вне текущей (так называемой, открытой) строки, контроллер вынужден дезактивировать RAS, выдержать паузу RAS precharge на перезарядку микросхемы, передать номер строки, выдержать паузу RAS to CAS delay и лишь затем он сможет приступить к передаче номера столбца.

Ситуация, когда запрашиваемая ячейка находится в открытой строке, называется "попаданием на страницу" (Page Hit), в противном случае говорят, что произошел промах (Page Miss). Поскольку, на промах налагаются штрафные задержки, критические к быстродействию программные модули приходится разрабатывать с учетом особенностей архитектуры FPM-DRAM и абстрагироваться от ее устройства уже не получается. (Вот он ключевой момент истории, начиная с которого оперативная память утратила свою однородность!)

Возникла и другая проблема: непостоянство времени доступа затрудняет измерение производительности микросхем памяти и их сравнение результатов друг с другом. В худшем случае обращение к ячейке составляет RAS to CAS Delay + CAS Delay + RAS precharge нс., а в лучшем: CAS Delay. Хаотичное, но не слишком интенсивное обращение к памяти (так, чтобы она успевала перезарядиться) требует не более чем RAS to CAS Delay + CAS Delay нс.

Поскольку, величины RAS to CAS Delay, CAS Delay и RAS precharge непосредственно не связаны друг с другом и в принципе могут принимать любые значения, достоверная оценка производительности микросхемы требует для своего выражения как минимум трех чисел. Однако производители микросхем в стремлении приукрасить реальные показатели, обычно проводят только два: RAS to CAS Delay + CAS Delay и CAS Delay. Первое (называемое так же "временем [полного] доступа") характеризует время доступа к произвольной ячейке, а второе (называемое так же "временем рабочего цикла") – время доступа к последующим ячейкам из уже открытой строки. Время, необходимое для регенерации микросхемы (т.е. RAS precharge), из полного времени доступа исключено. (Вообще-то, в технической документации, кстати, свободно доступной по Интернету, приводятся все значения и тайминги, так что никакого произвола в конечном счете нет).

Фундаментальные проблемы профилировки "в большом"

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

Профилировке "в большом" присущи свои проблемы. Это и непостоянство времени выполнения, и проблема "второго прохода", и необходимость учета наведенных эффектов… Словом, здесь есть над чем поработать!

Фундаментальные проблемы профилировки "в малом"

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

Функции с аргументами по умолчанию – из Си++ в классический Си

Язык Си++ выгодно отличается от своего предшественника тем, что поддерживает функции с аргументами по умолчанию. Для чего они нужны? Переставим себе такую ситуацию. Пусть у нас имеется активно используемая функция plot(int x, int y, int color), рисующая в заданных координатах точку заданного цвета. Допустим, в один прекрасный момент мы осознаем, что помимо координат и цвета нам жизненно необходим, скажем, атрибут прозрачности. Как быть? Реализовать еще одну функцию, практически повторяющую первую (ау, метод "copy-and-paste")? Не слишком-то удачное решение! Помимо неоправданного увеличения размеров программы возникнет проблема синхронизации обеих функций – при исправлении ошибок в первой функции, их придется "отлавливать" и во второй. (Вообще же, в грамотно спроектированной программе не должно присутствовать хотя бы двух идентичных блоков).

Но почему бы просто не добавить еще один аргумент к функции? Дело в том, что это потребует внесения изменений во все остальные функции, использующие данную. А всякое изменение уже отлаженного кода чревато появлением ошибок в самых непредсказуемых местах. Еще хуже если такая функция вынесена в библиотеку – тогда ее модификация "срубит" множество программ, что весьма нежелательно.

А давайте объявим атрибут прозрачности аргументом по умолчанию! Тогда, ранее написанные фрагменты кода без какой либо адоптации смогут вызывать эту функцию по "старинке", даже подозревая об изменении ее прототипа. Благодаря этому, мы сможем наращивать функциональность кода без потери обратной совместимости. К тому же такая методика если не избавляет от необходимости проектирования прототипов функций, то, во всяком случае, значительно упрощает эту задачу, зачастую позволяя решать ее "на лету".

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

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

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

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

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

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

Впрочем, величина снижения производительности на практике не превышает 0,5%-1% и ей вполне можно пренебречь. Другой минус – загромождение листинга структурами, что затрудняет его понимание. Однако к такому стилю очень быстро привыкаешь, и дискомфорт исчезает сам собой.

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

Конечно, данный метод, уже хотя бы в силу присущих ему недостатков, не претендует на радикальное изменение идеологии программирования и вовсе не намеривается вытеснять (и даже потеснясь) классический механизм передачи аргументов, но в некоторых случаях он все же бывает чрезвычайно полезен. Сам автор этой статьи использовал его в нескольких крупных проектах и полученным результатам остался доволен. Благодаря нему кардинальные нововведения новых версий и даже перенос из среды MS-DOS в операционную систему Windows обошлись практически без модификации уже отлаженного кода.

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

Группировка операций чтения с операциями записи

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

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

/* -----------------------------------------------------------------------

перекрытия транзакций не происходит

----------------------------------------------------------------------- */

for (a = 0; a < BLOCK_SIZE; a += 4)

{

*(int *)((int)p1 + a) = x;

}

for (a = 0; a < BLOCK_SIZE; a += 4)

{

x += *(int *)((int)p1 + a);

}

/* -----------------------------------------------------------------------

перекрытия транзакций происходят постоянно

----------------------------------------------------------------------- */

for (a = 0; a < BLOCK_SIZE; a+= 32)

{

x += *(int *)((int)p1 + a);

*(int *)((int)p2 + a) =x;

}

Листинг 28 [Memory/read.write.c] Фрагмент программы, демонстрирующий влияние перекрытия транзакций чтения/записи на производительность

Опля! Вот уж чего мы вряд ли ожидали, – так это увеличения

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

Чтобы компенсировать побочное влияние разворота, давайте развернем два непрерывающихся цикла на N итераций, а "гибридный" цикл – на N/2, причем, N должно быть достаточно велико, чтобы разворот в N/2 итерации был не сильно хуже, чем N (ведь на время прохождения трассы, как мы помним, влияет не только количество поворотов, но и протяженность прямых участков см. "Разворачивание циклов"). Достаточно точный результат достигается уже при N равном 16, вот его-то мы и возьмем (фрагмент программы с развернутыми циклами здесь не приводится, т.к. эту операцию вы должны уметь осуществлять и самостоятельно).

Ага, оказывается, что перекрытие транзакций все же уменьшает производительность. Правда, совсем не на много, всего лишь на ~5% на системе P-III 733/133/100/I815EP. Эта величина настолько мала, что в подавляющем большинстве случаев ей можно абсолютно безболезненно пренебречь. Правда, на AMD Athlon 1050/100/100/VIA KT133 проигрыш достигает аж ~25%, чем будет достаточно большой жертвой, но все-таки на нее можно закрыть глаза ради упрощения реализации вычислительного алгоритма.

Рисунок 42 graph 31 Демонстрация влияния перекрытия транзакций чтения/записи на время обработки больших блоков данных с учета разворота цикла и без. Если на P-III перекрытие транзакций практически не влияет на производительность, то на AMD Athlon проигрыш уже становится ощутим, хотя и не так велик, что бы перечеркивать все выше написанное

Идеология – как средство конкурентной борьбы

Воины-смертники, готовые умереть за идею, не слишком отличаются от приверженцев движения "Open Source" – и те, и другие служат на благо того, против чего борются.

Только глупцы верят, что "Open Source" несет в себе свободу. И пока они в это верят, многие используют их в качестве тарана против монополизма Microsoft. Компании IBM и HP поддерживает LINUX отнюдь не потому, что вдавились в старческую филантропию. Под шумком идей "свободы", "открытости" и "братства" они подсаживает миллионы пользователей на LINUX, отрывая жирный кусок рынка от Microsoft. Подавляющее большинство выбирают LINUX не из-за его технических и потребительских достоинств (которым там фактически нету), а потому, что это круто. От кривого (да не запинают меня его поклонники) LINUX к коммерческим AIX- и HP-UNIX всего лишь один шаг. Немного рекламы, скидок, консалтинга и клиент его сделает! Вот истинная

причина поддержки LINUX компаниями HP и IBM.

Самой же Microsoft "открытые исходники" выгодны вот по каким причинам:

а) конкурент в лице LINUX разбивает в пух и прах все обвинения компании в монополизме;

б) позволяет чужими руками забесплатно создавать и обкатывать новые технологии;

в) способствует обучению и профессиональному росту молодых программистов, а это – кадры;

г) и так далее…

Увлеченные борьбой с монополиями, члены движения "Open Source" не заметили, как стали работать на благо этих же монополий, превратившись в мощный инструмент в их руках.

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

Иерархия оперативной памяти

Оперативная память… что это? Объект материального мира или абстракция, не соответствующая никакой физической действительности? Не спешите отвечать. Давайте рассуждать логически. Если, вооружившись отверткой, открутить несколько болтов, удерживающих корпус компьютера, то, среди прочего семейства микросхем, на материнской плате обнаружатся один, два или три вертикально установленных прямоугольных модуля. Это и есть оперативная память или, говоря по-английски, RAM – Random Access Memory (Память с Произвольным Доступом). Значит, оперативная память – это некоторое физическое устройство (какое – уже неважно). Так?

А вот попробуйте подойти с этим вопросом к любому программисту. Если наш программист не будет пьян или вусмерть укурен, то, скорее всего, он определит память как совокупность ячеек, причем не хаотично разбросанных точно пшено на асфальте, а объединенных адресным пространством с наперед заданными свойствами. Слышите? Ни слова об устройстве! Причем, это был явно системный программист, который, если захочет, может без труда положить значение 0x666 в ячейку под "номером" 0x999, а спустя некоторое время извлечь его оттуда. Прикладные же программисты имеют крайне смутное представление о том как нумеруются ячейки (и нумеруются ли они вообще). Языки высокого уровня приучают оперировать не ячейками, а переменными. Считается, что переменные располагаются в памяти, вернее каждое переменной соответствует одна или более ячеек памяти. На самом же деле это не совсем так (или даже совсем не так)! Компилятору может взбрести в голову разместить переменных в регистрах или же вовсе не размещать их нигде, если он обнаружит, что значение переменной в программе не используется или же его можно вычислить еще на этапе компиляции.

Так что же все-таки представляет собой оперативная память? С точки зрения сборщика компьютеров, память – это микросхема. С точки зрения программиста – абстрактное хранилище данных. И бессмысленно спрашивать кто из них прав! Они оба… не правы.
Оперативная память – не микросхема и не абстракция. Это целая подсистема

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

>>>>> врезка

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

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

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

<<<<<

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

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

Стоп! Мы слишком увлеклись! Если мы не будет протирать звезды, пардон, учитывать особенности физического оборудования, то кто же тогда их будет учитывать?! Навряд ли этим займутся уровни абстракций и уж тем более – не само оборудование! Эмуляция и производительность – понятия несовместимые…

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

Маленькая деталь. Сказанное вовсе не означает, что вам придется программировать на ассемблере и взаимодействовать с "железом" напрямую. Достаточно лишь планировать запросы к памяти с учетом характера этого железа, а эффективно программировать можно на любом языке. Если Вам направиться Си/С++, Паскаль или даже Perl, – я не буду ни в чем вас ограничивать.

Можно провести такую аналогию. Допустим, выемка писем из почтового ящика осуществляется каждое утро ровно в девять часов. Следовательно, для ускорения переписки мы должны обязательно отправлять наши письма до девяти. Даже незначительное опоздание увеличит срок доставки письма на целые сутки! Надеюсь, это вас убедит, что снять крышку с черного ящика с надписью "подсистема оперативной памяти IBM PC" все таки полезно. ОК, снимаем… (тяжелая зараза!) Еще одна секунда и мы узнаем, что же находится там…

На вершине иерархии (см. рис. sx1) находятся прикладные библиотеки управления памятью, реализующие унифицированный интерфейс к сервисам менеджера куч (heap manager) операционной системы. (Вообще-то, некоторые операционные системы, в частности MS-DOS, не имеют полноценного менеджера куч, и в этом случае его обязанности целиком ложатся на плечи прикладной библиотеки, но о таких "операционных системах" мы говорить не будем, поскольку это совершенно другая тема).

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

Уровнем ниже лежит менеджер виртуальной памяти (virtual memory manager), который в тесной координации с процессором реализует:

a) виртуальные адресные пространства, т.е. абстрагируется от реальных физических адресов и позволяет назначать ячейкам памяти произвольные адреса. Благодаря этому, множество одновременно запущенных приложений могут быть загружены по одним и тем же логическим (виртуальным) адресам, причем адресные пространства этих приложений не будет пересекаться! Приложения, словно жители параллельных миров, при всем желании не "увидят" друг друга, конечно, если не воспользуются специально созданными для этой цели разделяемыми регионами памяти или другими средствами межпроцессорного взаимодействия, но это – разговор особый.

b) виртуальную память, представляющую собой дальнейшее развитие идей виртуальных адресных пространств. Любая ячейка виртуальной памяти может находиться как в оперативной памяти, так и на дисковом накопителе. Это позволяет выделять практически неограниченные объемы памяти, вплоть до десятков гигабайт (на самом деле, ОС семейства Windows предоставляют в распоряжение каждого процесса максимум два гигабайта, разве что Windows NT Server Enterprise не накладывает на аппетит программиста никаких ограничений, см. описание "Very Large Memory" в Platform SDK).

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

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

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

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

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

Управление сверхоперативной памятью осуществляется не процессором, а кэш-контроллером

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

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

Поэтому, воспринимайте схему sx1 не более чем наброском, грубо очерчивающим наш дальнейший маршрут путешествия по подсистеме памяти…

Рисунок 3 sx1.doc 0х22 Иерархия памяти в операционных системах Windows 9x/NT/2000 и UNIX (грубо)

Игры не для всех

– А пыли, пыли-то, сколько батюшки! – изумился Сергей и неуверенно чихнул. Он наполовину высунулся из разобранного сервера и, словно ожидая увидеть хотя бы на одном лице раскаяние, примирительно пробурчал "Ладно, тащите пылесос".

"Вот уже и электроника стала считаться грязной работой", – подумал он, – "прогресс, мать его! Нет, надо драть отсюда когти по добру, по здорову. Наблюдал бы он по-прежнему звезды. Точная оптика, хромированные маховички, белые халатики. Так, нет же, потянуло к компьютерам. То ли интересно стало, а может, просто заработать хотел. А вышло, что ни там, ни там не платят. То есть прожить, конечно, можно.… Но стоит ли ради этого жить? Что бы вот так копаться в современных, супернавороченных компьютерах, которые сегодня обрастают пылью, а уже завтра оказываются на свалке. И кто вспомнит трудягу-техника, лелеющего всю эту груду микросхем?"

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

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

Неуверенно потянувшись к рубильнику, он включил питание. Сервер тут же ожил, замигал огоньками и затарахтел всеми своими вентиляторами. А на экране монитора под надрывные хрипы жесткого диска вспыхнул логотип "Microsoft Windows NT Server"…

"Уххх…" пронесся вздох облегчения "работает".

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

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

Дул пронизывающий ветер, быстро неслись разлохмаченные облака, подсвечиваемые огнями большого города. Иногда сквозь разрывы удавалось заметить тускло светящие в задымлено – белом небе съежившиеся звезды. Видимость была настолько плохой, что различить контуры созвездий не мог даже тренированный глаз Сергея.

Да и тренированный ли теперь? Столько же воды утекло с тех пор, как он ушел с обсерватории? Три года? Пять лет? Или целая вечность? Но ничего, он к ним еще вернется. Вот только закончатся все намеченные проекты, истечет срок контрактов… И тогда – назад, в горы, к звездам! А к компьютерам – больше ни пальцем, ни ногой.

А как все хорошо начиналось! Быстрый успех, феноменальный взлет, заказы со всего мира.… Потом восторг заказчиков немного поутих, навалились конкуренты, и теперь чтобы удержаться на гребне популярности приходилось прикладывать титанические усилия, порой работая по двадцать и больше часов в день, создавая программы, которые устаревали порой быстрее, чем была поставлена последняя точка в листинге. Этот бешенный тем бессмысленной круговерти затягивал, словно омут, лишая всякой ориентации, цели и смысла жизни.

"И зачем я вообще живу?", – подумал Сергей, усаживаясь за свой любимый столик, в глубине "Трех поросят". "Что бы работать как проклятый, так что даже не остается времени поваляться на диване с любимой книжкой? Или просто поваляться, не думая ни о чем. Оставлю ли за собой след в истории, или так и рассеюсь в ее песке, среди тысяч таких же, молодых преуспевающих программистов, строящих окружающий нас кибернетический мир, струящийся и ускользающий из рук?"

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

"…так, двадцать семь множим, десять на ум кладем", – считал Сергей свои расходы "итого выходит недостаток в пятьдесят семь долларов, которые нужно найти к завтрему на квартиру.

То есть уже к сегодняшнему", – поправился он, глядя на светлеющее небо, на котором сквозь узкую щель между двумя небоскребами светила такая далекая сейчас Венера.

Нет, деньги не были проблемой, – и домовладельцы могли подождать, и ничего не стоило подписать новый контракт, вытребовав ощутимый процент предоплаты. Включится в очередной проект хотя бы ради того, чтобы разогнать накатившую депрессию, вновь отложить решение вопросов "Зачем?", "Для чего?" на неопределенный срок.

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

"...А вечером надо спать", – едва не обронил вслух Сергей, от чего внезапно смутился и без видимой для окружающих причины заспешил к выходу. "Спать, спать", – повторил про себя он, – "а то точно крыша поедет".

На улице семенил мелкий противный дождь, больно ударяющий порывами ветра в лицо. Ждать общественного транспорта по такой погоде ужасно не хотелось, но денег на такси уже не оставалось и приходилось покоряться судьбе.

"Стоило ли ехать в Москву только ради того, что бы оказаться под дождем, и пересчитывать мятые бумажки, которых как ни считай, все равно не хватит на такси?", – выругался Серей. Впрочем, тут же успокоил себя: "Раскис он. Деньги, говорит, у него кончились. Так работать надо, а не заниматься черт знает чем… Жизнью он не доволен. Квартира собственная есть? Есть! Интернет у него есть? Есть! Любимый компьютер? А как же! Возможность заниматься любимым делом? Ррразумется!"

"Но все что у тебя есть – лишь средства работы, ну и существования", – донесся внутренний голос. – "Что впрочем, для тебя одно и то же. Когда другие работают, что бы жить, ты живешь что бы работать…"

Сергей, зябко поежился. И впрямь, у него не было ничего, кроме работы. Ни семьи, ни даже любимой девушки. Друзья? Конечно, были и поклонники, и деловые партнеры и даже приятели, но ни с одним из них он ни разу просто так беспричинно не встретился, просто, что бы поболтать или тяпнуть пивка… Даже окружающий мир перестал замечать.

А ведь когда- то часами мог любоваться красотой заката, радоваться дождю, булыжнику, что валяется под ногой. Компьютеры подмяли собой весь остальной мир. Цветной монитор окрасил жизнь в тона оттенков серого. Собственно, жизнь вне компьютера стала для Сергея чужим, агрессивным, непонятным пространством. Слишком скучным и неинтересным, чтобы его можно было воспринимать всерьез. Компьютер – это не только целая Вселенная, это возможность видеть мир таким, как ты хочешь. Сергея ничуть не смущало, что мир этот виртуален. Какая, в сущности, разница? Реальная Вселенная – ничто иное, как совокупность сильных, слабых, гравитационных и электромагнитных излучений. Восприятие мира – это уже привилегия мозга, а если он не в состоянии отличить грань призрачного от реального, стоит ли искать различия?

"Брр", – пробормотал Сергей, нахохливаясь, словно воробей, под потоками усиливающегося дождя. – "Вот и вся вам разница между мирами, – идет дождь, и никакое мое восприятие действительности не в силах прекратить его, или хотя бы вызвать трамвай, или что там может прийти мне на помощь? Еще минута и насморк мне обеспечен"

От нечего делать он стал изучать содержимое своих карманов. Три метрошных карточки, начатая пачка сигарет, пара дискет неизвестного происхождения, купленная вчера авторучка. А зажигалка куда-то запропастилась. Выронил он ее что ли? Или забыл в сервере? Похоже, что забыл… "Вот будет для кого-то сюрприз", – усмехнулся Сергей, представляя себе, наладчика, открывающего сервер, в недрах которого среди прочих потрохов, лежит новенькая, почти не использованная газовая зажигалка. "Нет", – вздохнул Сергей. – "Юмор вряд ли поймут, если еще короткого замыкания, не будет", – подумал он.

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

"За ногу", – простонал Сергей.

– "Кажется, начинается сезон неприятностей. Хорошо, хоть вовремя успел спохватиться" Теперь оставалось только придумать благовидный повод, требующий немедленного вскрытия сервера. Но, чтобы он ни сказал, ярости шефа не избежать. Попробуй, объясни ему, почему это нельзя было сделать вчера ночью, когда нагрузка на сервер минимальна, а именно сегодня утром, когда каждая минута простоя сервера это прямые убытки для компании, продающей через Интернет свой товар.

"Впрочем", – подумал Сергей, – "зачем придумывать повод, если его можно сделать?" Вытащив из кармана пару долларов, он направился к ближайшему Интернет-кафе. Идея была до безобразия проста. Вешаем сервер и.… Хм, и если это раскроется, то мало не покажется. Впрочем, зачем усложнять себе жизнь? Зачем атаковать сервер, если это можно придумать? Создать видимость атаки!

*                              *                              *

Оторвавшись от терминала, Сергей направился к охраннику, сидевшему у входа и, старясь вложить в свой тон максимум уверенности, произнес: "Мне от вас требуется позвонить. Как я могу это сделать?"

"А по какому поводу?", – хмыкнул охранник, явно не настроенный предоставлять телефон первому ощипанному проходимцу.

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

"А, ну раз такое дело, то, конечно, звоните", – смилостивился охранник, доставая из-за спины телефон.

"Евгений Петрович? Доброе утро! Сергей Потапов беспокоит. Знаете ли, я задержался в Интернет кафе. Так вот, к делу. Решил проверить, работает ли наш серверочек. Да, тот, что вчера настраивал. И представьте мое удивление, когда я попал на сайт порнографического содержания. Что? Так я только и хотел сказать, что это значит, что атаковали вас, - изменили таблицу роуминга… Что? Совершенно с Вами согласен, черт побери этих хакеров и мать их за ногу так! Что? Технические аспекты вас не интересуют? Ах, что бы работало через пять минут? Пожалуйста, еще раз загляните в контракт и уточните мои обязанности! Конечно же, за доплату дело другое.

Ну да, выписывайте пропуск, я буду через пять- десять минут. Нет, ремонт займет минут десять от силы тридцать…. Конечно, черт побери!. О кей, о кей. Еду"

"Неплохо", – подумал Сергей, окунаясь в сплошную стену дождя. – "Удивительно, как невыгодное положение порой оборачивается на пользу тебе. Конечно, это нечестно, но что такое честность? Кому дано судить о добре и зле? О пороке и добродетели? Как правило, все эти ярлыки навешиваются не лучшими представителями человечества, которые едва ли сами верят в них. Да, собственно, это не вопрос веры. Мораль – всего лишь сумма взглядов на мир, точнее один из вариантов представления мира. В чистом виде никаких понятий нет, - есть лишь субъективные оценки и проблемы выживания. Умереть голодным, но честным, означает лишь признать поражение честности – ее неспособность сопротивляться реалиям окружающей действительности. Ложь всегда побеждает. Потому, что предоставляет большую свободу действий. Да, собственно, что мы понимаем под ложью? Противоположность истине? Конечно же, нет. Тогда бы все было слишком просто и неинтересно. Ложь – это некоторая сложная производная функция от аргумента, который мы называем истиной. Хм, но есть и такая функция, что f(x)==x. То есть, правда – лишь частный случай лжи. Выходит, что лжи достаточно для описания всех человеческих отношений, а вот правды бы, увы, оказалось не достаточно.… Впрочем, в дискретике…."

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

"Серж, закурить не найдется?", – окликнул его сидевший в машине водитель. – "Каким ветром занесло к нам? Вот твоя зажигалка, кстати. Ты ее вчера на сервере забыл"

"Зажигалка?" – нервно усмехнулся Сергей. – "Вправду моя! Ну что ж, давай, сядем, покурим, раз погода на то располагает!"

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

И Сергей решился на очередную наглость.

"Слушай, шеф, у тебя телефона не будет? Позвонить надобно", – попросил он.

"Да как же не будет", – доброжелательно отозвался тот, – "в такой машине все есть! Сотовый Вас устоит?" лукаво улыбнулся он, но тут же поспешно добавил: "только не долго, ок?"

"Ну, о чем разговор", – согласился Сергей. – "Евгений Петрович?.. Переключайте, переключайте барышня. Добрый день Евгений Петрович!… Конечно же, я в курсе, что прошло уже… да, тридцать четыре минуты. Так я звоню, сообщить, что таблица роуминга уже как десять минуть назад восстановлена и сейчас тестируется… Нетехническим языком? Нетехническим языком – все в ажуре… Да, прямо справился не выходя из кафе… Нет, приятное с полезным совместить не удалось, Вы же сами просили работать как загнанная лошадь… Нет, я еще не готов выставить счет… Да, пятьсот долларов превосходно устроят. Всегда готов помочь. Всего доброго, до свидания"

"Серж, а ты где живешь-то? Может тебя довезти?", – предложил свои услуги водитель.

"Спасибо большое, но я вряд ли смогу расплатится", – честно признался Сергей, доставая из карманов последние и уже порядком промокшие бумажки.

"Да, что там! Жизнь длинная – сочтемся", – философски изрек шеф. "Ну так куда ехать?"

*              *              *

"…Хороший человек этот шофер", – размышлял Сергей, не отрывавший взгляд от дворников, тщетно пытающихся отвоевать хотя бы кусочек пространства у дождя. "А, впрочем, скорее расчетливый, чем хороший. Что помогает нам выжить в этой жизни? Связи, контакты, другими словами, друзья. Чем больше у тебя друзей, тем спокойнее в бушующем море жизни. Ничто ни страшно, если в трудную минуту кто-то успевает протянуть руку"

Пелена за окном замедляла движение транспорта до скорости табуна черепах, ползущих вверх по кромке дюны. Такими темпами до дому можно было добираться и час, и два, что явно не входило в планы, Сергея, мечтающего в этот момент только об одном – доползти до своей кровати и упасть в нее без задних ног.

" Находятся же глупцы, что ищут наркотики", – усмехнулся про себя Сергей. "Зачем? Внутри нас целая фабрика по их производству, - достаточно лишь систематически не досыпать, и мозг сам начет вырабатывать их. Впрочем, о чем это я? Там же совсем другой механизм, правда, с идентичными проявлениями. И с худшими последствиями", – зло усмехнулся он. "Однажды заставив работать уставший от бессонницы мозг, спустя какое-то время с ужасом обнаруживаешь, что ни в какое другое время, кроме бессонницы он наотрез отказывается работать. Но стоит только смириться, как мозг ставит новый барьер. – Порой Сергею приходилось не спасть по пять ночей кряду, чтобы довести свое создание до того волшебного состояния, когда окружающая действительность теряет очертания и, словно проваливаясь в какую-то пустоту, оставляет перед тобой лишь поставленную накануне задачу. Не важно формула это, или не поддающаяся отладке злостная процедура в программе, - и то и другое материализуется, становится осязаемым. К нему можно подойти, пнуть ногой. Попробовать на вкус, растереть на ладони… Конечно же, это всего лишь искаженная работа неправильно функционирующего мозга, и удачные решения – всего лишь следствие данной мозгу возможности получить нетривиальный результат. Беспорядочные возбуждения и торможения нейронов могут что угодно решить методом тривиального перебора. Но есть ли смысл в таких решениях? В некотором смысле – это действительно, ответы упавшие "свыше", но не дающие никаких навыков для решения аналогичных задач"

Горящая буква "М" едва просматривалась сквозь заплывшее стекло. – "Останови, шеф, я выйду", – попросил Сергей. – "На метро, оно быстрее будет", – объяснился он, выходя из машины, и бросил напоследок, уже закрывая дверь: "Да, нервные клетки не восстанавливаются. Они отмирают. Но их место сменяют новые, - это естественный процесс, протекающий всю жизнь".

"Вот так часть истины становится ложью", – подумал Сергей. "Ведь что такое ложь, как не искусство умолчания?".

"Нет, меня определенно мучает совесть", – подумал он, спускаясь вниз по эскалатору. "Все эти рассуждения – лишь попытки убедить себя в собственной же правоте. Странное существо человек. Мы не находим себе места от мелких прегрешений, не замечая при этом, что само наше существование уже является преступлением".

Если на эскалаторе еще удавалось отдаться собственным мыслям, то в переполненном вагоне метро ни о чем другом, кроме как поскорее доехать думать было невозможно. Москвичи ехали на работу. "Зеркальный мир", – усмехнулся Сергей, только и думающий о том, как сейчас завалится спать. "Я смотрю на мир сквозь зеркало, но почему я не вижу себя? Может быть, я в зазеркалье? И смотрю на мир оттуда? Как же тогда направлен ход лучей?", – понимая, что он дремлет наяву, Сергей машинально продолжал рассуждать: "наверно свойства фотона быть одновременно в двух точках как раз и объясняются тем, что одна из них – отражение. А может быть и вторая тоже? И весь наш мир это лишь отражение себя в себе самом?" Внезапно Сергей вспомнил, что перед тем как сесть в поезд, он даже не обратил внимания, куда тот едет. Или обратил? Судя по карте, он ехал верным направлением, и через остановку ожидалась его станция. "Только если я не засну эту остановку", – пробурчал про себя Сергей, протискиваясь сквозь толпу поближе к выходу.

*              *              *

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

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

Обстановка являлось как бы продолжением внутреннего мира Сергея, мира который замыкался в этих четырех стенах. Здесь, отрезанный от остальной цивилизации, он и проводил большую часть своей жизни. Шелест дождя, мурлыкавший сквозь стекло, неудержимо клонил ко сну, и спустя минуту – другую Сергей тихонечко посапывал, утомленный ночной вылазкой в город.

Долго спать ему, впрочем, не пришлось. В дверь звонили протяжно и настойчиво. "Мммать", – пробурчал Сергей, на ходу натягивая штаны, – "давно я этот звонок снести хотел! Нет, ну кто это так звонит?"

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

"Заходи", – только и бросил Сергей, исчезая в темноте глубины комнаты. Шурик был одним из тех его приятелей, которых и шугнуть, вроде бы, повода нет, но и встречаться не хочется.

"У тебя закусь, надеюсь найдется?", – затараторил Шурик, едва только вошел. "Я посмотрю, в холодильнике ладно?", – не дожидаясь ответа он полез в холодильник. "Я, как-то неожиданно к тебе зашел. Ехал мимо и подумал, а почему бы мне зайти к моему другу Сергею?"

"Ну и ехал бы себе мимо", – буркнул Сергей вполголоса. Он знал, что Шурик на такие высказывания не обижается.

"Нет, в самом деле", – воскликнул Шурик, – "у тебя есть закуска или нет? Одни консервы и полуфабрикаты. Хоть бы хлеба корочку что-ли…"

"Хлеба ему…", – проворчал, едва сдерживая зевоту, Сергей, – "кто ж так пьет?" фыркнул он уже громче, – "в чем весь смысл? Бухнуть в рот не весть чего, а потом сразу тянуться к закуске. Нет! Пить надо так, что бы почувствовать вкус того, что пьешь, ощутить аромат, почувствовать терпкость на языке…". Широко зевнув, он продолжил, – "но какой у водки аромат? Так что выкинь ты ее, или с собой забери. Если хочешь пить, там, в холодильнике, вино, коньяк"

"Ну, коньяк, так коньяк", – согласился Шурик.

"Я вот, что хотел спросить", – сказал он, расставляя на полу перед диваном бокалы. "Могу я вернуть свой долг не деньгами, а один очень интересным заказом?"

"Заказом!", – недовольно хмыкнул Сергей. "Хватит с меня этих заказов! И так живу как в берлоге, что некогда личной жизнью заняться…"

"Личная жизнь – это неплохо", – согласился Шурик, – "но, прежде чем ее заняться, нужно иметь, на что жить. А ты вот перебиваешься от случая к случаю. Сутками напролет работаешь, а все что имеешь – так это полный холодильник концентратов…"

"Чья бы корова…", – лениво отозвался Сергей, не желая включаться в спор. "Уговорил, я не правильно живу. Ну а смысл? Ты не задавался вопросом, что все эти наши рассуждения о правильности жизни, как и поиски в ней смысла – просто бред собачий. Человек живет не для, а потому что. Биохимические реакции в его теле протекают – не зависимо от воли и сознания. Точно так идет дождь не для того, что бы оросить траву в жаркий полдень, а потому что вода испаряется, конденсируется и падает". Сергей кивнул в сторону зашторенного окна, по которому барабанил дождь.

"Все поиски смысла жизни заранее обречены на провал", – после некоторой паузы добавил он. "Оглянись назад. За тобой остались тысячелетия этих самых поисков, рассветы и падения цивилизаций. Какими же далекими и незначительными они нам кажутся сейчас. Величайшие мудрецы истории едва ли изменили ее ход. В лучшем случае мы помним их имена, и изучаем чудом уцелевшие труды. В чем смысл их жизни? У них была цель, это верно, но смысла не было".

"Но общая цель каждого из нас выжить", – заметил Шурик, важно поднимая бокал. "Так выпьем же за то, что бы мы умели выживать в этом мире".

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

"Это ничего не меняет", – возразил Шурик. "Деньги, все равно никто не отменял, и залогом выживания в наше время становятся именно они".

"Ну, так к делу", – зевнув, оборвал его Сергей.

"К делу", – согласился Шурик, делая большой глоток. "Надобно одну программу взломать…"

"Взломать, это можно", – серьезным видом согласился Сергей. – "Тюк топориком – и она готова".

"Приколись", – фыркнул Шурик

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

"Какие же они теперь твои?", – ухмыльнулся Шурик, "когда ты своими руками мне их отдал…"

"Дохлый номер", – парировал Сергей. "Не хочешь отдавать – так и скажи. Только нечего меня во всякие темные дела впутывать".

"Ситуация следующая", – протянул Шурик. "С деньгами у меня кранты. В том, смысле, что сухо, как в Сахаре. Отдать долг я смогу не раньше, чем хоть что-то заработаю. А по этому поводу расклад следующий. Взялся я одну программку подломать, да уперся в одну хитрую функцию, что никак не могу обратить".

"Понятно…", – зевнул еще раз Сергей. "Обращу, если обратима. Во всяком случае, сведу к системе линейных уравнений, а дальше уж – по твоему усмотрению".

"Это же надо обмыть!", – воскликнул Шурик.

"Идея хорошая, но не правильная", – буркнул Сергей.

"Тогда я пойду, наверное", – замялся Шурик.

"Ну, заходи еще", – машинально отозвался Сергей, поднимаясь с пола, что бы проводить гостя.

"Я тебе функцию мылом кину", – бросил напоследок Шурик, скрываясь за дверью.

"Мылом, – это хорошо", – подумал Сергей, размышляя, чем бы сейчас заняться в первую очередь. После принятого натощак конька ужасно хотелось есть. Вытащив из холодильника свой любимый пакетный суп от "Галина Бланка", куриный суп с рисом, Сергей в ожидании пока закипит чайник, наводил порядок в своей комнате.

Смести пыль, поставить на место диски, собрать рассыпанные книжки, протереть пыль со стола – стало своеобразным утренним ритуалом, вошедшим в жизнь Сергея еще с детства, когда он терпеть не мог учить уроки в беспорядке. Если каждый день уделять уборке по пять минут, то надобность в генеральных уборках отпадает.

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

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

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

Информация о пенальти

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

Возвращаясь к предыдущему вопросу: почему указатель pswd загружается так долго? И при каких именно обстоятельствах загрузка y "подскакивает" со своих обычных семи до восьмидесяти тактов? Судя по всему, процессору что-то не понравилось и он обложил эти две машинные команды штрафом (penalty), на время притормозив их исполнение. Можем ли мы узнать когда и за какой проступок это произошло? Не прибегая к полной эмуляции процессора– навряд ли (хотя современные x86 с некоторыми ограничениями позволяют получить эту информацию и так).

Гранды компьютерной индустрии – Intel и AMD уже давно выпустили свои профилировщики, содержащие полноценные эмуляторы выпускаемых ими процессоров, позволяющие визуализировать нюансы выполнения каждой машинной инструкции.

Просто щелкните по строке "mov ecx, DWORD PTR [ebp-28]" и VTune выдаст всю, имеющуюся у него информацию:

Decoder Minimum Clocks

= 1 ; Минимальное время декодирования – 1 такт

Decoder Average Clocks

= 8.7 ; Эффективное время декодирования – 8,7 тактов

Decoder Maximum Clocks

= 86 ; Максимальное время декодирования – 86 тактов

Retirement Minimum Clocks

= 0, ; Минимальное время завершения – 0 тактов

Retirement Average Clocks

= 7.3 ; Эффективное время завершения – 7,3 такта

Retirement Maximum Clocks

= 80 ; Максимальное время завершения – 80 тактов

Total Cycles

= 80 (00,65%) ; Всего времени исполнения – 80 тактов

Micro-Ops for this instruction = 1 ; Кол-во микроопераций в инструкции – 1

The instruction had to wait 0 cycles for it's sources to be ready

("Инструкция ждала 0 тактов пока подготавливались ее операнды, т.е. попросту она их не ждала совсем")

Dynamic Penalty:     IC_miss

The instruction was not in the instruction cache, so the processor loads the instruction from the L2 cache or main memory.

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

Occurances

= 1                   ; Такое случалось 1 раз

Dynamic Penalty:     L2instr_miss

The instruction was not in the L2 cache, so the processor loads the instruction from main memory.

("Инструкция отсутствовала в кэше второго уровня и процессор был вынужден загружать ее из основной оперативной памяти")

Occurances

= 1                   ; Такое случалось 1 раз

Dynamic Penalty:     Store_addr_unknown

The load instruction stalls due to the address calculation of the previous store instruction.

("Загружающая инструкция простаивала по той причине, что адрес источника рассчитывался предыдущей инструкцией записи")

Occurances

= 10                  ; Такое случалось 10 раз

Так, кажется, наше расследование превращается в самый настоящий детектив, еще более запутанный, чем у Агаты Кристи. Если приложить к полученному результату даже самый скромный арифметических аппарат, получится полная чепуха и полная расхождение дебита с кредитом. Судите сами. Полное время выполнения инструкции – 80 тактов, причем, известно, что она выполнялась 11 раз (см. колонку count в листинге 1). А наихудшее время выполнения инструкции составило… 80 тактов! А наихудшее время декодирования и вовсе – 86! То есть, худшее время декодирования инструкции превышает общее время ее исполнения и при этом в десяти итерациях она еще ухитряется простаивать как минимум один такт за каждую итерацию по причине занятости блока расчета адресов.

Да… тут есть от чего поехать крышей!

Причина такого несоответствия заключается в относительности самого понятия времени. Вы думаете время относительно только у Эйнштейна? Отнюдь! В конвейерных процессорах (в частности процессорах Pentium и AMD K6/Athlon) понятие "времени выполнения инструкции" вообще не существует в принципе (см. "Фундаментальные проблемы профилировки в малом. Конвейеризация или пропускная способность vs латентность"). В силу того, что несколько инструкций могут выполняться параллельно, простое алгебраическое суммирование времени их исполнения даст значительно больший результат, нежели исполнение занимает в действительности.

Ладно, оставим разборки с относительностью до более поздних времен, а пока обратим внимание на тот факт, что в силу отсутствия нашей инструкции в кэше (она как раз находится на границе двух кэш линеек) и вытекающей отсюда необходимости загружать ее из основной памяти, в первой итерации цикла она выполняется значительно медленнее, чем во всех последующих. Отсюда, собственно, и берутся эти пресловутые восемьдесят тактов. При большом количестве итераций (а при "живом" исполнении программы оно и впрямь велико) временем начальной загрузки можно и пренебречь, но… Стоп! Ведь профилировщик исполнил тело данного цикла всего 11 раз, в результате чего среднее время выполнения этой инструкции составило 7,6 тактов, что совершенно не соответствует реальной действительности! Ой! Оказывается, это вовсе не горячая точка! И тут совершенного нечего оптимизировать. Если мы увеличим количество прогонов профилировщика хотя бы в четыре раза, среднее время выполнения нашей инструкции понизится до 1,8 тактов и она окажется одним из самых холодных мест программы! Точнее – это вообще абсолютный ноль, поскольку эффективное время исполнения данной инструкции – ноль тактов (т.е. она завершается одновременно с предыдущей машинной командой). Словом, мы навернулись по полной программе.

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

Короткое лирическое отступление на тему: почему же все так произошло. По умолчанию VTune прогоняет профилируемый фрагмент 1.000 раз. Много? Не спешите с ответом. Наш хитрый цикл устроен так, что его тело получает управление лишь каждые 'z' ? '!' == 0x59 итераций. Таким образом, за все время анализа тело цикла будет исполнено всего лишь 1.000/89 == 11 раз!!! Причем, ни в коем случае нельзя сказать, что это надуманный пример. Напротив! В программном коде такое встречается сплошь и рядом.

       while((++pswd[p])>'z')     // ß

данный цикл прогоняется профилировщиком 1.000 раз

          {

              pswd[p] = '!';       // ß

данная инструкция прогоняется всего 11 раз

              …

          }

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

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

Впрочем нет, постойте. Нам еще предстоит разобраться со второй "горячей" точкой и на удивление тормозной скоростью загрузки указателя pswd. Опытные программисты, вероятно, уже догадались в чем тут дело. Действительно, – строка pswd[p] = '!'

– это первая строка тела цикла, получающая управление каждые 0x59 итераций, что намного превосходит "проницательность" динамического алгоритма предсказания ветвлений, используемого процессором для предотвращения остановки вычислительного конвейера. Следовательно, данное ветвление всегда предсказывается ошибочно и выполнение это инструкции процессору приходится начинать с нуля. А процессорный конвейер – длинный. Пока он заполниться… Собственно, тут виновата вовсе не команда "mov edx, DWORD PTR [ebp+0ch]"

– любая другая команда на ее месте исполнялась бы столь же непроизводительно! "Паяльная грелка", до красна нагревающая эту точку программы, находится совсем в другом месте!

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

Decoder Minimum Clocks

= 0        ; Минимальное время декодирования – 0 тактов

Decoder Average Clocks

= 0        ; Эффективное время декодирования – 0 тактов

Decoder Maximum Clocks

= 4        ; Максимальное время декодирования – 4 такта

Retirement Average Clocks

= 1    ; Эффективное время завершения – 1 такт

Total Cycles

= 1011 (08,20%)             ; Всего времени исполнения – 1010 тактов (8,2%)

Micro-Ops for this instruction = 1 ; Кол-во микроопераций в инструкции – 1

The instruction had to wait (8,11.1,113) cycles for it's sources to be ready

("Эта инструкция ждала минимально 8, максимально 113, а в основном 11,1 тактов пока ее операнды не были готовы")

Dynamic Penalty: BTB_Miss_Penalty ; Штраф типа BTB_Miss_Penalty

This instruction stalls because the branch was mispredicted.

("Эта инструкция простаивала потому что ветвление не было предсказано")

Occurances = 13                  ; Такое случалось 13 раз

Наша гипотеза полностью подтверждается. Это ветвление тринадцать

раз предсказывалась неправильно, о чем VTune и свидетельствует! Постой, как тринадцать?! Ведь тело цикла исполняется только одиннадцать! Да, правильно, одиннадцать. Но ведь процессор наперед этого не знал, и дважды пытался передать на него управление, и лишь затем, увидев, что ни одно из двух предсказаний не сбылось, плюнул и поклялся, что никогда – никогда не поставит свои фишки на эту ветку.

ОК. Когда загадки разрешаются – это приятно. Но главный вопрос несколько в другом: как именно их разрешать? Хорошо, что в нашем случае непредсказуемый условный переход находился так близко к "горячей" точке, но ведь в некоторых (и не таких уж редких) случаях "виновник" бывает расположен даже в других модулях программы! Ну что на это сказать… Подходите к профилировке комплексно и всегда думайте головой.Пожалуй, ничего более действенного я не смогу посоветовать…

Intel VTune

Рисунок 3 0x006 Логотип профилировщика VTune

Бесспорно, что VTune – самый мощный из когда-либо существовавших профилировщиков (ну, во всяком случае, на IBM PC). Собственно, его и профилировщиком язык называть не поворачивается. VTune – это высокоинтеллектуальный инструмент, не только выявляющий "горячие" точки, но еще и дающий вполне конкретные советы по их устранению. В дополнении к этому, VTune содержит весьма не хилый оптимизатор кода, увеличивающий скорость программ, откомпилированных Microsoft Visual C++ 6.0 в среднем на 20%, – согласительно, такая прибавка производительности никогда не бывает лишней!

В общем, у VTune столько достоинств, что писать о них становится даже как-то и не интересно. Просто воспринимайте его как безальтернативный профилировщик и все! А в настоящем обзоре мы лучше поговорим о его недостатках (ну какая же программа обходится без недостатков?):

Основной недостаток VTune его чрезмерная "тяжелость" (дистрибьютив шестой версии – последней на момент написания этих строк – весит аж 150 мегабайт) и весьма впечатляющая стоимость, помноженная на тот факт, что даже имея деньги, VTune не так-то просто приобрести из России. Правда, Intel предлагает бесплатную полнофункциональную версию, которая ни чем не уступает коммерческой, но работает всего лишь 30 дней. Качать такую тяжесть ради какого-то месяца работы? Извините, это несерьезно! (Особенно, если у вас dial-up).

Другой минус – VTune не очень стабилен в работе и частенько вешает систему (например, у меня при попытке активизации некоторых счетчиков производительности он загоняет операционную систему в синий экран смерти с надписью "IRQL_NOT_LESS_OR_EQUAL" и хорошо если при этом еще не грохает активный Рабочий Стол!). Впрочем, если не лезть "куда не надо" и вообще перед выполнением каждого действия думать головой, то ужиться с VTune все-таки можно (а что делать – ведь достойной альтернативы все равно нет).

Еще VTune получает много нареканий за свою ужасающую сложность. Кажется, что вообще не возможно освоить его и досконально во всем разобраться. Один встроенный "хелп", занимающий свыше трех тысяч страниц формата A4 чего стоит! Попробуйте его прочесть (только прочесть) – даже если вы хорошо владеете английским это у вас отнимет по меньшей мере целый месяц! Но давайте рассмотрим проблему под другим углом. Вам нужен Инструмент или бирюлька? Чем мощнее и гибче инструмент, – тем он сложнее по определению. С моей точки зрения VTune ничуть не сложнее чем тот же Visual C++ или DELPHI и проблема заключается не в самой сложности, а в отсутствии литературы по профилировке вообще и данному продукту в частности. Поэтому, в данную книгу включен короткий самоучитель по VTune, который вы найдете в главе "Практический сеанс работы с VTune", – надеюсь это вам поможет.

Исходные тексты

void __cdecl c_cpy(int *src, int *dst, int n)

{

int a; int t;

if (n<1) return; // нечего копировать!

// поэлементное копирование массива

for (a=0;a<n;a++) dst[a]=src[a];

return;

}

Листинг 1 Реализация алгоритма копирования памяти на языке Си

_asm_cpy proc

PUSH ESI ; / *

PUSH EDI ; сохраняем регистры

PUSH ECX ; */

MOV ESI,[ESP+4+3*4] ; src

MOV EDI,[ESP+8+3*4] ; dst

MOV ECX,[ESP+8+4+3*4] ; n

REP MVSD ; копируем одной командой!

POP ECX ; /*

POP EDI ; восстанавливаем регистры

POP ESI ; */

ret ; выходим

_asm_cpy endp

Листинг 2 Ассемблерная реализация алгоритма копирования памяти

int __cdecl c_min(int *src, int n)

{

int a; int t;

if (n<2) return -1; // Не среди чего искать минимум!

// Присваиваем первому элементу массива статус

// "условно наименьшего"

t=src[0];

// Если такой, кто будет меньше нашего "меньшего"?

// есть да, то предать статус ему.

for(a=1;a<n;a++) if (t>src[a]) t=src[a];

return t;

}

Листинг 3 Реализация алгоритма поиска минимума на языке Си

_asm_min proc

PUSH ESI ; сохраняем

PUSH EDI ; регистры

MOV ESI,[ESP+8+4] ; src

MOV EDX,[ESP+8+8] ; n

CMP EDX,2 ; есть среди чего искать?

JB @exit ; нет элементов для поиска

MOV EAX, [ESI] ; присваиваем первому элементу

; статус "условно наименьшего"

@for: ; начало цикла

MOV EDI, [ESI] ; в EDI – очередной элемент

CMP EAX, EDI ; если кто еще меньше?

JB @next ; если нет, - следующий элемент

MOV EAX, EDI ; передать статус

@next:

ADD ESI, 4 ; перейти к следующему элементу

DEC EDX ; уменьшить счетчик цикла на 1

JNZ   @for              ; повторять цикл пока EDX > 0

@exit:

POP   EDI               ; восстанавливаем

POP   ESI                                 регистры

ret

_asm_min endp

Листинг 4 Ассемблерная реализация алгоритма поиска минимума

void __cdecl c_sort(int *src, int n)

{

int a; int t; int f;

if (n<2)

return;     // Меньше двух элементов сортировать нельзя!

do{

f=0; // устанавливаем флаг сортировки в нуль

// Перебираем все элементы один за другим

for (a=1; a<n; a++)

// если следующий элемент меньше предыдущего

// меняем их местами и устанавливаем флаг

// сортировки в единицу

if (src[a-1]>src[a])

{

t=src[a-1];

src[a-1]=src[a];

src[a]=t;

f=1;

}

// повторять сортировку до тех пор, пока не дождемся

// первого "чистого" прохода, т.е. прохода без изменений

} while(f);

}

Листинг 5 Реализация алгоритма пузырьковой сортировки на языке Си

_asm_sort   proc

MOV   EDX,[ESP+8]       ; n

CMP   EDX,2             ; есть что сортировать?

JB    @exit             ; сортировать нечего, на выход

PUSH ESI               ; /*

PUSH EBP               ;     сохраняем   регистры

PUSH EBX               ; */

@while:                       ; основной цикл сортировки

MOV   ESI,[ESP+4+4*3]   ; src

MOV   EDX,[ESP+8+4*3]   ; n

XOR   EBP,EBP           ; f := 0

@for:                         ; цикл перебора элементов

MOV   EAX, [ESI]        ; EAX := src

MOV   EBX, [ESI+4]      ; EBX := src+1

CMP   EAX, EBX          ; Сравнить EAX и EBX

JAE   @next_for         ; Если EAX > EBX перейти к

; следующему элементу

; иначе обменять элементы местами

MOV   EBP, EBX          ; взвести флаг изменений

MOV   [ESI+4], EAX      ; "не чистый" проход

MOV   [ESI],EBX

@next_for:

ADD   ESI, 4            ; src+=1;

DEC   EDX               ; уменьшить счетчик цикла

JNZ   @for              ; перебирать элементы, пока

; счетчик не равен нулю

OR    EBP,EBP           ; dirty-флаг взведен?

JNZ   @while            : сортировать пока не будет чисто

POP   EBX               ; /*

POP   EBP               ;     Восстановить регистры

POP   ESI               ; */

@exit:

ret                     ; Выход

_asm_sort endp

Листинг 6 Ассемблерная реализация алгоритма пузырьковой сортировки

[1] некоторые процессоры (в частности Alpha) вообще не поддерживают констант, заставляя их ложить в память

[2] такое удаление удаляет и побочные эффекты типа деления на ноль

Использование кучи для создания массивов

От использования статических массивов рекомендуется вообще отказаться (за исключением тех случаев, когда их переполнение заведомо невозможно). Вместо этот следует выделять память из кучи (heap), преобразуя указатель, возвращенный функцией malloc к указателю на соответствующий тип данных (char, int), после чего с ним можно обращаться точно так, как с указателем на обычный массив.

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

В этом случае передавая функции, читающей строку с клавиатуры, указатель на буфер, не придется мучительно соображать: какой именно величиной следует ограничить его размер, – об этом позаботиться сама вызываемая функция, и программисту не придется добавлять еще одну константу в свою программу!

Использование преимуществ синхронного чтения

Использование собственных тактовых генераторов в микросхемах памяти типа SDRAM позволяет осуществлять обмен с памятью без участия процессора – действительно, если процессор точно знает: когда закончится цикл чтения (записи) зачем ему постоянно опрашивать контроллер памяти?

Поэтому, при загрузке 32-байтной строки из оперативной памяти ее первые 64-бита (четверное слово) доступны сразу же в момент их получения! Отсюда следует, что чтение массива по колонкам должно происходить заметно быстрее его чтения по столбцам. Достаточно лишь выровнять массив по адресу, кратному 32 и позаботится, чтобы он полностью умещался в кэш второго уровня. Тогда – пока ожидается поступление первых 64-битов ячейки очередной линейки столбца, три оставшихся 64-битных ячейки предыдущей линейки загружаются в "фоновом" режиме! Благодаря этому скорость обработки массива возрастает практически вдвое. Единственное условие – массив должен целиком вмещаться в кэш второго уровня.

Использование WriteProcessMemory

Если требуется изменить некоторое количество байт своего (или чужого) процесса, самый простой способ сделать это – вызвать функцию WriteProcessMemory. Она позволяет модифицировать существующие страницы памяти, чей флаг супервизора не взведен, т.е., все страницы, доступные из кольца 3, в котором выполняются прикладные приложения. Совершенно бесполезно с помощью WriteProcessMemory пытаться изменить критические структуры данных операционной системы (например, page directory или page table) – они доступны лишь из нулевого кольца. Поэтому, эта функция не представляет никакой угрозы для безопасности системы и успешно вызывается независимо от уровня привилегий пользователя (автору этих строк доводилось слышать утверждение, дескать, WriteProcessMemory требует прав отладки приложений, но это не так).

Процесс, в память которого происходит запись, должен быть предварительно открыт функцией OpenProcess с атрибутами доступа "PROCESS_VM_OPERATION" и "PROCESS_VM_WRITE". Часто программисты, ленивые от природы, идут более коротким путем, устанавливая все атрибуты – "PROCESS_ALL_ACCESS". И это вполне законно, хотя справедливо считается дурным стилем программирования.

Простейший пример использования функции WriteProcessMemory для создания самомодифицирующегося кода, приведен в листинге 1. Она заменяет инструкцию бесконечного цикла "JMP short $-2" на условный переход "JZ $-2", который продолжает нормальное выполнение программы. Неплохой способ затруднить взломщику изучение программы, не правда ли? (Особенно, если вызов WriteMe расположен не возле изменяемого кода, а помещен в отдельный поток; будет еще лучше, если модифицируемый код вполне естественен сам по себе и внешне не вызывает никаких подозрений – в этом случае хакер может долго блуждать в той ветке кода, которая при выполнении программы вообще не получает управления).

int WriteMe(void *addr, int wb)

{

HANDLE h=OpenProcess(PROCESS_VM_OPERATION|PROCESS_VM_WRITE,

                                         true,GetCurrentProcessId());

       return WriteProcessMemory(h, addr,&wb,1,NULL);

}

int main(int argc, char* argv[])

{

       _asm {

              push 0x74            ; JMP --> > JZ

              push offset Here

              call WriteMe

              add esp,8

Here:         JMP short here

       }



       printf("#JMP SHORT $-2 was changed to JZ $-2\n");

       return

0;

}

Листинг 2 Пример, иллюстрирующий использования функции WriteProcessMemory для создания самомодифицирующегося кода

Поскольку Windows для экономии оперативной памяти разделяет код между процессами, возникает вопрос: а что произойдет, если запустить вторую копию самомодифицирующейся программы? Создаст ли операционная система новые страницы или отошлет приложение к уже модифицируемому коду? В документации на Windows NT и Windows 2000 сказано, что они поддерживают копирование при записи (copy on write), т.е. автоматически дублируют страницы кода при попытке их модификации. Напротив, Windows 95 и Windows 98 не поддерживают такую возможность. Означает ли это то, что все копии самомодифицирующегося приложения будут вынуждены работать с одними и теми же страницами кода, что неизбежно приведет к конфликтам и сбоям?

Нет, и вот почему – несмотря на то, что копирование при записи в Windows 95 и Windows 98 не реализовано, эту заботу берет на себя сама функция WriteProcessMemory, создавая копии всех модифицируемых страниц, распределенных между процессами. Благодаря этому, самомодифицирующийся код одинаково хорошо работает как под Windows 95\Windows 98\Windows Me, так и под Windows NT\Windows 2000. Однако следует учитывать, что все копии приложения, модифицируемые любым иным путем (например, командой mov нулевого кольца) будучи запущенными под Windows 95\Windows 98 будут разделять одни и те же страницы кода со всеми вытекающими отсюда последствиями.

Теперь об ограничениях. Во-первых, использовать WriteProcessMemory разумно только в компиляторах, компилирующих в память или распаковщиках исполняемых файлов, а в защитах – несколько наивно. Мало-мальски опытный взломщик быстро обнаружит подвох, обнаружив эту функцию в таблице импорта. Затем он установит точку останова на вызов WriteProcessMemory, и будет контролировать каждую операцию записи в память. А это никак не входит в планы разработчика защиты!

Другое ограничение WriteProcessMemory заключается в невозможности создания новых страниц – ей доступны лишь уже существующие страницы. А как быть в том случае, если требуется выделить некоторое количество памяти, например, для кода, динамически генерируемого "на лету"? Вызов функций, управления кучей, таких как malloc, не поможет, поскольку в куче выполнение кода запрещено. И вот тогда-то на помощь приходит возможность выполнения кода в стеке…

Истоки

Итак, динамическая оперативная память относительно дешева, но по сегодняшним меркам недостаточно производительна. Статическая оперативная память на всех, достигнутых ныне частотах, имеет скорость доступа в один такт, но стоит чрезвычайно дорого и потому не может использоваться в качестве основной оперативной памяти ПК.

Так может, хотя бы часть памяти реализовать на SRAM? Знаете, а это мысль! Ведь что по сути представляет собой оперативная память? Правильно, – временное хранилище данных, загруженных с внешней, так называемой, дисковой памяти. Диски слишком медленны и интенсивная работа с ними крайне непроизводительна. Поэтому, разместив многократно используемые данные в оперативной памяти, мы резко сокращаем время доступа к ним, а, значит,– и время их обработки.

На первый взгляд, выигрыш в производительности достигается в тех, и только в тех случаях, когда загруженные данные используются многократно. А вот и нет! Допустим, потребовалось нам перекодировать содержимое некоторого файла. Поскольку, к каждому байту обращение происходит лишь однократно, – какой смысл загружать его в оперативную память? Тем не менее смысл все-таки есть, – дисковод в силу своих конструктивных особенностей просто "не хочет" считывать один-единственный байт и как минимум требует обработать весь сектор целиком. А раз так, – прочитанный сектор надо где-то хранить. К тому же, обмен данными можно значительно ускорить, есть обрабатывать не один, а сразу несколько секторов за раз. В этом случае, дисководу не придется тратить время на позиционирование головки при обращении к каждому сектору. Наконец, хранение данных в оперативной памяти позволяет отложить их немедленную запись до тех времен, пока это не будет "удобно" дисководу.

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

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

Так родился кэш…

История

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

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

Итоги и прогнозы

Теперь самое время подвести итоги. Если откинуть первый неудачный вариант программы с постоянным вызовом функции printf, можно сказать, что мы увеличили скорость оптимизируемой программы с полутора до восьмидесяти четырех миллионов паролей в секунду, то есть без малого на два порядка! И у нас есть все основания этим гордиться! Пускай, мы далеко от теоретического предела и до исчерпания резерва производительности еще далеко (вот скажем, можно перебирать несколько паролей одновременно, используемые векторные MMX-команды) профилировка приложений несомненно лучшее средство избежать неоправданного снижения производительности!

Любопытно, но каждый шаг оптимизации приводил к экспоненциальному росту производительности (см. рис. graph 0x001). Конечно, экспоненциальный рост наблюдается далеко не во всех случаях (можно сказать, что тут нам просто повезло), но тем не менее общая тенденция профилировки такова, что самые крупные "камни преткновения" по обыкновению находится на глубине и разглядеть их, не "окунувшись в воду" (в смысле в дебри кода) в общем-то невозможно.

В этой главе ### статье мы рассмотрели лишь самые базовые средства профилировщика VTune (да и то мельком), но его возможности этим отнюдь не исчерпаются! Собственно это целый мир, содержащий помимо прочего собственный язык программирования и даже имеющий собственное API, позволяющие вызывать функции VTune из своих программ (читай: клепать к профилировщику собственные плагины)…

Но, как бы то ни было, первый шаг в изучении VTune уже сделан и в дальнейшем вы постепенно сможете осваивать его и самостоятельно. А напоследок рискну дать вам один совет. Пользоваться контекстовой помощью VTune крайне неудобно и множество разделов при этом так и остаются неохваченными. Поэтому, лучше воспользоваться любым help-декомпилятором и перегнать hlp-файл в rtf, который затем можно открыть с помощью того же Ворда и распечатать. Или – читать с экрана, ибо помощь занимает свыше трех тысяч страниц – бумаги не напасешься!

Рисунок 11 graph 0x001

Измерения падения производительности от сжатия программ (DLL)

В заключении поговорим об измерении падения производительности от упаковки файлов. Казалось бы, что тут сложного – берем неупакованный файл, запускаем его, замеряв время загрузки, записываем результат на бумажке, упаковываем, запускаем еще раз, и… Первый камень преткновения – что понимать под "временем загрузки"? Если проецирование, - так оно выполняется практически мгновенно, и им можно вообще пренебречь. Моментом времени, начиная с которого с приложением можно полноценно работать? Так это от самого приложения зависит больше, чем от его упаковки. К тому же на время загрузки упакованных файлов очень сильно влияет количество свободной на момент запуска физической оперативной памяти (не путать с общим объемом памяти, установленной на машине). Если перед запуском упакованного файла мы завершим одно-два "монстроузных" приложения, то занятая ими память теперь окажется свободна, и сможет беспрепятственно использоваться распаковщиком. Напротив, если свободной памяти нет, ее придется по крохам отрывать от остальных приложений…

Хорошо, даже если мы оценим изменение времени загрузки (что, кстати, сделать весьма проблематично – серия замеров на одной и той же машине, с одним и тем же набором приложений дает разброс результатов более чем на порядок!), как измерять падение производительности остальных приложений? Ведь, при нехватке памяти Windows в первую очередь избавляется от не модифицированных страниц, которые незачем сохранять на диске! В результате упаковка файла несколько повышает производительность самого этого файла, но значительного ухудшает положение остальных, неупакованных приложений!

Поэтому, никаких конкретных цифр здесь не приводится. Приблизительные оценки, выполненные "на глаз", показывают, что при наличии практически неограниченного количества оперативной памяти потери производительности составляют менее 10%, но при ее нехватке, скорость всех приложений падает от двух до десяти раз! (Для справки: в эксперименте участвовали исполняемые файлы Microsoft Word 2000, Visual Studio 6.0, Free Pascal 1.04, IDA Pro 4.17, Adobe Acrobat Reader ¾, машина с процессором CLERION-300A, оснащенная 256 мегабайтами ОЗУ, для имитации нехватки памяти ее объем уменьшался до 64 мегабайт; использовались операционные системы –Windows 2000 и Windows 98).