Удаление неиспользуемых присвоений

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

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

int *p=0;

int a=sizeof(int);

p=malloc(a*1024)

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

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

int *p=0;

int a=sizeof(int);

p=malloc(a*1024)

С этой задачей сполна справляются все три рассматриваемых компилятора – Microsoft Visual C++, Borland C++ и WATCOM.

Удаление текста

В первую очередь хотелось бы обратить внимание на команду "CutAppendNext", позволяющую добавлять вырезаемые фрагменты в конец буфера обмена без затирания его содержимого. По умолчанию она не связана ни с какой "горячей" клавишей и назначить ее вы должны самостоятельно ("Tools à Customize à Keyboard à Category Edit à CutAppendNext"). В работе с ней есть одна хитрость – сама CutAppendNext не вырезает текст в буфер, но говорит редактору, что следующая операция вырезания (Cutting) текста должна не перезаписывать (overwrite) содержимое буфера, а дописываться (append) к нему.

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

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

"Горячая" клавиша <Ctrl-L> вырезает в буфер обмена текущую строку целиком, а ее "сестра" – <Shift-Ctrl-L> просто удаляет строку, сохраняя содержимое буфера обмена неизменным.

Две других команды "LineDeleteToEnd" и "LineDeleteToStart" удаляют "хвост" строки справа и слева от курсора соответственно.

Удаление ветвлений

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

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

Рассмотрим типичный цикл с условием в середине:

do

{

printf("1й оператор\n");

if (--a<0) break;

printf("2й оператор\n");

}while(1);

Компилятор Microsoft Visual C++ не долго думая транслирует его в цикл с постусловием, удаляя тем самым оператор break.

printf("1й оператор\n");

a--;

if

(a>=0)

{

a++;

do

{

printf("1й оператор\n");

printf("2й оператор\n");

} while(–-a<0);

       }

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

Заметим еще раз –из всех трех рассматриваемых компиляторов удалять внутрицикловые ветвления умеет один лишь Microsoft Visual C++ – ни Borland C++, ни WATCOM на это не способны.

__циклы которые никогда не выполняются

Удаление заведомо ложных условий

Иногда программисты допускают ошибки, создавая заведомо ложные условия, как, например, это:

if (a!=0 && a==0) …

Ясно, что если 'a' не равно нулю, то равно нулю оно быть никак не может, - вот компилятор Microsoft Visual C++ и не генерирует для него код, опуская всю ветку "IF – THEN", правда, почему-то не выдавая никаких предупреждений. А зря! Ведь ясно, что это – программистская ошибка. Компиляторы же Borland C++ и WATCOM вообще не оптимизируют такой код, понимая его буквально – как есть.

Впрочем, и Microsoft Visual C++ не всегда распознает заведомую ложность условий. В частности, со следующим примером он уже не справляется:

if (a<0 && a>0x666) …

Удельное время выполнения

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

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

 Line       Instructions                      Dyn-Retirement Cycles              

 107 pswd[p] = '!';  

 107       mov    edx,    DWORD PTR [ebp+0ch]       13 ************

 107 ;     ^ загрузить в регистр EDX указатель pswd

 107       add    edx,   DWORD PTR [ebp-4]          2  **

 107 ;     ^ сложить регистр EDX с переменной p

 107       mov    BYTE PTR [edx],    021h           3  ***

 107 ;     ^ записать в *(pswd+p) значение '!'

 109 y = y | y << 8;

 109       mov    eax,    DWORD PTR [ebp-28]        2  **

 109 ;     ^ загрузить в регистр EAX переменную y

 109       shl    eax,    08h                       1  *

 109 ;     ^ сдвинуть EAX на 8 позиций влево

 109       mov      ecx, DWORD PTR [ebp-28]         (0,7.3,80)

 109 ;     ^ загрузить в регистр ECX переменную y      *******

 109       or       ecx, eax                        1  *

 109 ;     ^ ECX = ECX | EAX (tmp = y | y)

 109       mov      DWORD PTR [ebp-28], ecx         1  *

 109 ;     ^ записать полученный результат в y

 110 x -= k;

 110       mov      edx, DWORD PTR [ebp-24]         0 

 110 ;     ^ загрузить в регистр EDX переменную x

 110       sub      edx, DWORD PTR [ebp-36]         1  *

 110 ;     ^ вычесть из регистра EDX переменную k

 110       mov      DWORD PTR [ebp-24], edx         1  *

 110 ;     ^ записать полученный результат в x

Листинг 3 Удельное время выполнения машинных команд внутри профилируемого фрагмента программы

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

За исключением команды, загружающей содержимое переменной y в регистр ECX, время выполнения всех остальных команд строго постоянно и не меняется от случая к случаю. Наша же "подопечная" в зависимости от еще не выясненных обстоятельств, может отъедать аж восемьдесят тактов, что на время делает ее самой горячей точкой данного фрагмента программы. Восемьдесят тактов – это вообще полный беспредел! И пускай среднеарифметическое время ее выполнения составляет всего лишь семь тактов, а минимальное – и вовсе ноль, мы не успокоимся пока не выясним: на что и при каких именно обстоятельствах уходит такое количество тактов?

Уменьшение размера структур данных

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

Раздельные (separated) структуры данных.

Вернемся к списку. Классическое представление списка (см. рис. 0х33) – крайне не оптимально с точки зрения подсистемы памяти IBM PC. Почему? Да ведь при трассировке списка (трассировка – операция прохождения по списку без обращения к данным [значениям] его элементов) процессор вынужден загружать все ячейки, а не только ссылки на следующие элементы. Если операция трассировки выполняется неоднократно, – потери производительности могут оказаться весьма значительными.

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

Обратите внимание: как в этом случае изменяется обращение к элементам списка. Если доступ к "классическому" списку осуществляется приблизительно так: _list[element].next=xxx; _list[element].val=xxx; то после его модернизации так: _mylist.next[element]=xxx; _mylist.val[element]=xxx.
Т.е. квадратные скобки сместились на одно слово вправо! Это не создает никаких неудобств (ну разве что с непривычки), но способно запутать начинающих программистов, не имеющих опыта работы с Си.

Рисунок 21 0х33 Устройство "классического" списка. При трассировке процессор вынужден загружать и ссылки, и значения, несмотря на то, что нас интересуют одни лишь ссылки



Рисунок 22 0х40 Устройство оптимизированного списка. Теперь при трассировке процессор загружает лишь те ячейки, к которым происходит реальное обращение, что значительно увеличивает производительность системы

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

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

 

Рисунок 23 0х034. Отводите указателям минимально возможное количество бит, – это здорово сократит объем занимаемой памяти



Совместное использование обоих этих приемов (разделения списка вкупе с усечением разрядности указателей) сокращает размер ссылочного массива в sizeof(struct list)/sizeof(index_next) раз. Т.е. в данном случае – в четыре раза. Неплохо? А во сколько раз это повышает производительность? Давайте проверим! Рассмотрим следующую программу, реализующую "классический" и оптимизированный варианты списков и сравнивающую время их обработки.

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

 *

 *                   обработка классического списка

 *

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

struct list{         // КЛАССИЧЕСКИЙ СПИСОК

struct list   *next; // Указатель на следующий узел

int           val;   // Значение

};

struct list *classic_list,*tmp_list;

// инициализация списка

for (a = 0; a < N_ELEM; a++)

{

       classic_list[a].next= classic_list + a+1;

       classic_list[a].val = a;

} classic_list[N_ELEM-1].next=0;

// трассировка списка

tmp_list=classic_list;

while(tmp_list = tmp_list[0].next);

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

 *

 *            обработка оптимизированного раздельного списка

 *

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

struct mylist{             // ОПТИМИЗИРОВАННЫЙ РАЗДЕЛЬНЫЙ СПИСОК

short int *next;     // Массив указателей на следующий узел

int *val;            // Массив значений

};

struct mylist separated_list;

// инициализация списка

for (a=0;a<N_ELEM;a++)

{

       separated_list.next[a] = a+1;

       /*                 ^^^ обратите внимание где находятся

                              квадратные скобки */

       separated_list.val[a] = a;

} separated_list.next[N_ELEM-1]=0;

// трассировка списка

while(b=separated_list.next[b]);

Листинг 13 [Memory/list.separated] Фрагмент программы, демонстрирующий эффективность трассировки разделенных списков



Результаты ее работы должны быть приблизительно следующими:



Рисунок 24 graph 0x08 Демонстрация эффективности обработки раздельных списков с указателями усеченной разрядности. Как видно, это значительно сокращает время трассировки списков, причем трехкратный выигрыш производительности (достигнутый в данном случае) – далеко не предел!

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

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

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

struct list_of_obj {

struct list_of_obj *next;

int               obj_attr[14];

int               obj_body[8000];

}

Листинг 14. Не оптимизированная структура

Имеет ли смысл помещать элементы такой структуры в раздельные массивы? Давайте подсчитаем. Длина пакетного цикла обмена в подавляющем большинстве случаев составляет 32 (K6/P-II/P-III) или 64 байта (Athlon). Сумма длин полей obj_attr и obj_body – 60 байт. Следовательно, всего лишь ~10% загруженных ячеек остаются невостребованными. Это весьма незначительная потеря и ей, по идее, можно безболезненно пренебречь. Но, прежде чем делать окончательный вывод, не поленимся, а сравним оптимизированный и не оптимизированный варианты на практике.

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

 *

 *                   обработка классического списка



 *

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

struct LIST_OF_OBJ {              // НЕОПТИМИЗИРОВАННЫЙ СПИСОК

       struct   LIST_OF_OBJ *next; // указатель на следующий объект

       int    obj_attr[ATTR_SIZE];      // атрибуты объекта /нечто компактное

       int    obj_body[BODY_SIZE];      // тело объекта     /нечто монстровое

};

struct LIST_OF_OBJ *list_of_obj, *tmp_list_of_obj;

// выделение памяти

list_of_obj = (struct LIST_OF_OBJ*)

              _malloc32(N_ELEM*sizeof(struct LIST_OF_OBJ));

      

// инициализация списка

for (a = 0; a < N_ELEM; a++)

       list_of_obj[a].next = list_of_obj + a + 1; list_of_obj[N_ELEM-1].next = 0;

// трассировка списка

tmp_list_of_obj = list_of_obj;

do{

       for(attr = 0; attr < ATTR_SIZE; attr++)

              x += tmp_list_of_obj[0].obj_attr[attr];

} while(tmp_list_of_obj = tmp_list_of_obj[0].next);

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

 *

 *            Обработка оптимизированного раздельного списка

 *

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

struct LIST_OF_OBJ_OPTIMIZED {           // ОПТИМИЗИРОВАННЫЙ СПИСОК

       struct LIST_OF_OBJ_OPTIMIZED *next;      // указатель на следующий объект

       #ifdef PESSIMIZE

              int    *obj_attr;           // указатель на атрибуты (это плохо!)

       #else               

              int    obj_attr[ATTR_SIZE];      // атрибуты объекта (это хорошо!)

       #endif

       int    *obj_body;                 // указатель на тело объекта

};

struct LIST_OF_OBJ_OPTIMIZED      *list_of_obj_optimized, *tmp_list_of_obj_optimized;

// выделение памяти

list_of_obj_optimized = (struct LIST_OF_OBJ_OPTIMIZED*)

                     _malloc32(N_ELEM*sizeof(struct LIST_OF_OBJ_OPTIMIZED));

// инициализация списка

for

(a = 0; a

< N_ELEM ;a++)

{

       list_of_obj_optimized[a].next = list_of_obj_optimized + a + 1;



      

       #ifdef PESSIMIZE

              list_of_obj_optimized[a].obj_attr = malloc(sizeof(int)*ATTR_SIZE);

       #endif

      

       list_of_obj_optimized[a].obj_body = malloc(sizeof(int)*BODY_SIZE);

}      list_of_obj_optimized[N_ELEM-1].next = 0;

// трассировка списка

tmp_list_of_obj_optimized = list_of_obj_optimized;

do{

       for(attr = 0; attr < ATTR_SIZE; attr++)

       x+ = tmp_list_of_obj_optimized[0].obj_attr[attr];

} while(tmp_list_of_obj_optimized = tmp_list_of_obj_optimized[0].next);

Листинг 15 [Memory/list.obj.c] Фрагмент программы, демонстрирующий эффективность оптимизации структуры (14)

Ого! Оптимизированный вариант обгоняет своего "классического" коллегу в скорости на целых 60% (см. рис. graph 9), – весьма существенный прирост производительности, не так ли? К сожалению, оптимизированный вариант весьма капризен. Если заменить оптимизированную структуру (14):

struct list_of_obj_optimized {

       struct list_of_obj_optimized *next;

       int           obj_attr[ATTR_SIZE];

       int                  *obj_body;

};

на ее ближайший аналог:

struct list_of_obj_optimized {

       struct list_of_obj_optimized      *next;

       int                        *obj_attr;

       int                        *obj_body;

};

…то разница между оптимизированным и не оптимизированным вариантом составит всего лишь 30%!!! (см. рис. graph 9). Совершенно непонятно: чем же int *obj_attr хуже, чем int obj_attr[ATTR_SIZE]?! И тем более непонятно, за счет чего в последнем случае достигается такая производительность. Мистика прям какая-то! Ведь, исходя из самых общих соображений, ясно: количество загруженных ячеек памяти во всех случаях должно быть одинаково!



Рисунок 25 graph 0x09 Демонстрация эффективности различных подходов к оптимизации структуры (14) Учет особенностей станичной организации памяти (см. ниже) позволяет более чем в два раза сократить время обработки списка



Учитывайте станичную организацию памяти. Ненадолго оторвемся от этой маленькой головоломки и исследуем зависимость времени трассировки списка от шага чтения памяти. Казалось бы, какие тут могут быть сюрпризы? А вот попробуйте с ходу объяснить форму кривой, полученной с помощью программы list.step.c.

// перебор различных значений шага чтения памяти

for(a = STEP_FACTOR; a < MAX_STEP_SIZE; a += STEP_FACTOR)

{

       #ifdef UNTLB

       // загрузка страниц в TLB

       for (i=0;i<=BLOCK_SIZE;i+=4*K) x += *(int *)((int)p + i+32);

       #endif

      

       L_BEGIN(0);          // <-- начало замера времени выполнения

              i=0;

              // чтение памяти с шагом a

              for(b = 0; b < MAX_ITER; b++)

              {

                     x += *(int *)((int)p + i);

                     i

+= a;

                    

              }

       L_END(0);            // <-- конец замера времени выполнения

}

Листинг 16 [Memory/list.step.c] Фрагмент программы, демонстрирующий зависимость времени трассировки списка от шага чтения памяти

Кривая (см. рис. graph 0x007) и впрямь ведет себя очень интересно. Время трассировки – вопреки всем прогнозам – не остается постоянным, а увеличивается вместе с шагом! Правда, это увеличение не бесконечно, – при достижении отметки в 32 Кб для P-II\P-III и 64 Кб для AMD Athlon, кривая достигает максимума насыщения и переходит в горизонтальное "плато", превышающее "подножье" по высоте более чем в пять раз! Это слишком большая величина, и мы не можем просто взять и проигнорировать ее, но… чем же, черт побери, вызван рост времени обработки?! Конечно, оперативная память неоднородна и время доступа к ней непостоянно, но чтобы она была настолько

неоднородна.…

Какой физической реальности соответствует отметка в 32 Кб (а на Athlon и вовсе в 64 Кб)? Структур такого размера в памяти (насколько мы знаем память) заведомо нет. Между тем, время обработки при увеличении шага растет.


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

Если немного доработать программу, заставив ее выводить время доступа к каждой ячейке, то обнаружиться (см. [Memory/memory.way.c]), что через каждые четыре килобайта кривая внезапно изгибается в неприступный зубец (см. рис. graph 10), "отъедающий" десятки тысяч тактов процессора! Нет, это не типографская ошибка. Все так и должно быть, – ведь практически все современные операционные системы (и Windows с UNIX в том числе) используют страничную организацию памяти. Не останавливаясь подробно на этом вопросе (см. "Intel Architecture Software Developer's Manual Volume 3 System Programming Guide", §3.6 PAGING") отметим лишь тот факт, что с каждой страницей связана специальная 32?битная структура данных, содержащая атрибуты страницы и ее базовый адрес. При первом обращении к странице процессор считывает эти данные из физической памяти в свой внутренний буфер (именуемый TLB – Translation Look aside Buffer) и последующие обращения к той же самой станице происходят без задержек вплоть до вытеснения этой информации из TLB. Так вот где собака порылась! Оказывается, минимальной порцией обмена с памятью является отнюдь не 32-байтный пакетный цикл, а целая страница! Время задержки, возникающей при первом обращении к странице, лишь в полтора-два раза уступают времени чтения всей этой страницы, – т.е. независимо от количества реально прочитанных байт, обработка страницы занимает столько времени, как если она была прочитана целиком. Отсюда, – потоковые алгоритмы должны обращаться как можно к меньшему количеству страниц, т.е. в пределах одной страницы располагайте данные максимально плотно, не оставляя пустот.

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


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

Дело в том, что атрибуты страниц не разбросаны хаотично по всей памяти, а объединены в особые структуры – Page Table (Страничные Таблицы или Таблицы страниц). Каждый элемент страничной таблицы занимает одно двойное слово, но, так как минимальная порция обмена с памятью превышает эту величину, то при обращении к одной странице процессор загружает из памяти атрибуты еще семи (пятнадцати – в Athlon) страниц, сохраняя эту информацию в сверхоперативной памяти. Вот вам и ответ на вопрос! Умножение восьми (пятнадцати) элементов на четыре (размер одной страницы в килобайтах) как раз и дает те загадочные 32 (64 на Athlon) килобайта, ограничивающие рост кривой.

Теперь становится понятно, почему вынос obj_body в отельный массив значительно ускорил обработку списка, – элементы *next и obj_attr стали располагаться плотнее и уместились в меньшее количество страниц.

Почему вынос obj_attr ухудшил производительность – понять несколько сложнее. Количество страниц, правда, в последнем случае будет несколько больше, но ненамного. Давайте подсчитаем. Первый вариант структуры занимает (sizeof(*next) + sizeof (int) * ATTR_SIZE + sizeof(*obj_body)) * N_ELEM = 64 Кб (16 страниц). Второй вариант: (sizeof(*next) + sizeof(*obj_attr) + sizeof(*obj_body)) * N_ELEM + sizeof(int) * ALIGN_ATTR_SIZE * N_ELEM = 76 Кб (19 страниц). Ну, пусть за счет округления набежит еще пара страниц. Тогда 21/16 = 1.3, в то время как соотношения производительности первого и второго вариантов составляет 1.4 для Athlon и аж 1.8 для P-III. Куда уходят такты?! А вот куда. Стратегия выделения памяти функции malloc такова, что при запросе маленьких блоков каждый последующий выделенный блок имеет меньший адрес, чем предыдущий.


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

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



Рисунок 26 graph 0х007 График, иллюстрирующий время обработки блока данных в зависимости от шага чтения. На P-III насыщение наступает на 32 Кб шаге чтение данных, а на AMD Athlon – на 64 Кб. Причем, на участке (0; 4Кб] происходит резкий "влет" кривой, особенно хорошо заметный на AMD Athlon.



Рисунок 27 graph 10 График, иллюстрирующий зависимость времени доступа к ячейке от адреса этой ячейки при последовательном обращении к данным. Смотрите, – при первом обращении к странице возникает пауза в десятки тысяч тактов!

Умножение

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

Если один из сомножителей представляет собой степень двойки – в ход идут битовые сдвиги. Это очевидно, но не все знают: как быстро выполнить умножение на числа 3, 5, 6, 7, 9, 10 и т.д. Оказывается, в этих случаях на помощь приходит сложение – в самом деле, (a*3) можно записать как: ((a>><<1)+a), что с легкостью укладывается в один такт (LEA может не только складывать, но и умножать один из регистров на числа 2, 4 и 8).

Компиляторы Microsoft Visual C++ и Borland C++ умело заменяют умножение битовыми сдвигами, при необходимости комбинируя их с операцией сложения, а вот WATCOM предпочитает обходиться без LEA, проигрывая своим конкурентам один такт (точнее, с учетом спаривая, даже полтора такта).

Упорядочивание обращения к памяти

Задержки при доступе в память возникают в следующих случаях:

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

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

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

Для предотвращения таких задержек следует:

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

Размещать операции чтения и записи в одну и ту же область памяти как можно дальше друг от друга.

Управление кэшированием в x86 процессорах старших поколений

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

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

Первой этой проблеме бросила вызов фирма AMD, включив в состав набора команд 3D Now! инструкцию prefetch, позволяющую программисту заблаговременно загружать в кэш ячейки памяти, к которым он рассчитывает обратиться в ближайшем будущем. Причем, загрузка данных осуществляется без участия и остановки вычислительного конвейера! Это убивает двух зайцев сразу: во-первых, "ручное" управление кэш-контроллером позволяет выбрать оптимальную стратегию упреждающей загрузки данных, что существенно уменьшает количество кэш-промахов, а, во-вторых, с предвыборкой становится возможным загружать очередную порцию данных параллельно с обработкой предыдущей, маскируя тем самым латентность тормозов оперативной памяти!

Следом за K6, предвыборка (естественно, в усовершенствованном варианте) появилась и в процессоре Pentium-III, да не одна, а с целой свитой команд "ручного" управления кэшированием, – Intel явно не хотела отставать от конкурентов!

Совершенствование управления подсистемой памяти продолжилось и в Pentium-4. Помимо множества новых команд (таких как….), в нем реализован воистину уникальный (с появлением Athlon XP уже, увы, не уникальный) на сегодняшний день механизм аппаратной предвыборки

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

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

Устранение зависимостей по данным

Если запрашиваемые ячейки оперативной памяти имеют адресную зависимость по данным (т.е. попросту говоря, одна ячейка содержит адрес другой), процессор не может обрабатывать их параллельно, и вынужден простаивать в ожидании поступления адресов. Рассмотрим это на следующем примере: while(next=p[next]). До тех пор, пока процессор не узнает значение переменной next, он не сможет приступить к загрузке следующей ячейки, т.к. еще не знает ее адреса. Время выполнения такого цикла определяется в основном латентностью подсистемы памяти и практически не зависит от ее пропускной способности. И SDRAM, и DDR-SDRAM, и даже сверхпроизводительная RDRAM покажут практически одинаковый результат, над которым посмеялась бы и EDO-DRAM, будь одна до сих пор жива. Латентность же подсистемы памяти на современных компьютерах весьма велика и составляет приблизительно 20 тактов системной шины, что соответствует полному времени доступа в 200 нс.

Прямую противоположность этому составляет цикл вида: while(a=p[next++]). Процессор, отправив чипсету запрос на загрузку ячейки p[next], немедленно увеличивает next на единицу и, не дожидаясь ответа (зачем? ведь адрес следующей ячейки известен), посылает чипсету еще один запрос. Потом еще один, и еще.… Так продолжается до тех пор, пока количество необработанных запросов не достигает своего максимально допустимого значения (для P6 – четырех). Поскольку, запросы следуют друг за другом с минимальным интервалом, в первом приближении можно считать, что они обрабатываются параллельно. И это действительно так! Если время загрузки N зависимых ячеек в общем случае равно: t = N(Tch + Tmem), где Tch – латентность чипсета, а Tmem – латентность памяти, то такое же количество независимых ячеек будут загружены за время , где C – пропускная способность подсистемы памяти.

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

Наглядно сравнить скорость обработки зависимых и независимых данных позволяет следующая программа:

/* ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

 *

 *                   цикл чтения зависимых данных

 *                   (не оптимизированный вариант)

 * ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– */

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

{                     /*   ^^^^^ мы разворачиваем цикл для более быстрой обработки */

      

       // читаем ячейку

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

      

       // адрес следующей ячейки вычисляется на основе значения предыдущей

       // поэтому, процессор не может послать очередной запрос чипсету до тех пор,

       // пока не получит эту ячейку в свое распоряжение

       a += x;

      

       // дальше - аналогично...

       y = *(int *)((int)p1 + a + 4);

       a += y;

      

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

       a += x;

      

       y = *(int *)((int)p1 + a + 12);

       a += y;

      

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

       a += x;

      

       y = *(int *)((int)p1 + a + 20);

       a += y;

      

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

       a += x;

      

       y = *(int *)((int)p1 + a + 28);

       a

+= y;

}

/* ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

 *

 *                   цикл чтения независимых данных

 *                     (оптимизированный вариант)

 * ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– */

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

{

       // теперь процессор может посылать очередной запрос чипсету,



       // не дожидаясь завершения предыдущего, т.к. адрес ячейки

       // никак не связан с обрабатываемыми данными

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

       y += *(int *)((int)p1 + a + 4);

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

       y += *(int *)((int)p1 + a + 12);

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

       y += *(int *)((int)p1 + a + 20);

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

       y += *(int *)((int)p1 + a + 28);

}

Листинг 9 [Memory/dependence.c] Фрагмент программы, демонстрирующий эффективность обработки независимых данных

Результат тестирования двух компьютеров, имеющихся в распоряжении автора, представлен на рис. graph 1. Первое, что сразу бросается в глаза – значительный разрыв во времени обработки зависимых и независимых данных. В частности, на P?III/733/133/100 цикл чтения независимых данных выполняется в два с половиной раза быстрее! Несколько худший результат показывает AMD Athlon?1050/100/133/VIA KT 133, что объясняется серьезными конструктивными недоработками этого чипсета (см. "Вычисление полного времени доступа"). Недостаточная пропускная способность канала между контроллером памяти и блоком интерфейса с шиной (оба смонтированы в северном мосте чипсета) приводит к образованию постоянных заторов, и как следствие – ограничению количества одновременно обрабатываемых запросов. Тем не менее, даже в этом случае чтение независимых данных осуществляется намного эффективнее и весь вопрос в том, как именно следует их обрабатывать.

Линейное (оно же – последовательное) чтение ячеек памяти – не самая удачная идея, что и демонстрирует рис. graph 1. На P-III мы не достигли и 60% от расчетной пропускной способности, а на AMD Athlon и того меньше, – всего лишь немногим более 30%. "Потрясающая" производительность, не правда ли? Это что же такое получается?! Неужели архитектура PC настолько крива, что не позволяет справиться даже с такой простой штукой как оперативная память? Кстати, мы не первые, кому эта "здравая" мысль пришла в голову.У большинства прикладных разработчиков существует весьма устойчивое убеждение, что PC – это тормоз. По жизни. Но не спешите пересаживаться на Cray…

Рисунок 18 graph 0x001 Тест пропускной способности оперативной памяти при линейном чтении зависимых и независимых данных. На "правильном" чипсете Intel 815EP независимые данные обрабатываются в два с половиной раза быстрее. На чипсете VIA KT133 (за счет его высокой латентности) различие в производительности намного меньше и составляет всего 1,7 крат. Но, как бы так ни было, на любой системе обрабатывать зависимые данные крайне невыгодно. Обратите также внимание, что при линейном чтении данных заявленная пропускная способность (800 Мб/сек. для данного типа памяти) не достигается

Устройство интерфейсной обвязки

По своему устройству, интерфейсная обвязка матрицы статической памяти, практически ничем не отличается от аналогичной ей обвязки матрицы динамической памяти (см. "Часть I. Оперативная память: устройство и принципы функционирования оперативной памяти. Conventional DRAM Page Mode DRAM – обычная DRAM") Поэтому, не будем подробно останавливаться на этом вопросе и рассмотрим его лишь в общих чертах.

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

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

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

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

Рисунок 7 0х007 Устройство типовой микросхемы SRAM-памяти

Устройство элемента "НЕ" (инвертора)

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

Ниже в качестве примера приведена принципиальная схема простейшего инвертора, сконструированного из двух последовательно соединенных комплементарых /* взаимно дополняемых */ CMOS-транзисторов – p- и n- канального (см. рис. 0х004).

Если на затворы подается нулевой уровень, то открывается только p-канал, а n-канал остается разомкнутым. В результате, на выходе мы имеем питающее напряжение (т.е. высокий уровень). Напротив, если на затворы подается высокий уровень, размыкается n-канал, а p-канал – замыкается. Выход оказывается закорочен на массу и на нем устанавливается нулевое напряжение (т.е. низкий уровень).

Рисунок 3 0х004 Устройство элемента НЕ (инвертора)

Устройство матрицы статической памяти

Подобно ячейкам динамической памяти (см. "ЧастьI. Оперативная память: устройство и принципы функционирования оперативной памяти. Conventional DRAM Page Mode DRAM – "обычная" DRAM"), триггеры объединяются в единую матрицу, состоящую из строк (row) и столбцов (column), последние из которых так же называются битами (bit).

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

Рисунок 4 0х005 Устройство 6-транзистроной одно-портовой ячейки SRAM-памяти

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

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

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

Наиболее часто встречается двух - портовая память, устройство ячейки которой изображено на рис. 0х006. (внимание! это совсем не та память которая, в частности, применяется в кэше первого уровня микропроцессоров Intel Pentium). Нетрудно подсчитать, что для создания одной ячейки двух – портовой памяти расходуется аж восемь транзисторов. Пусть емкость кэш-памяти составляет 32 Кб, тогда только на одно ядро уйдет свыше двух миллионов транзисторов!

Рисунок 5 0х006 Устройство 8-транзистроной двух портовой ячейки SRAM-памяти



Рисунок 6 sram.dev3 sram.top  Ячейка динамической памяти воплощенная в кристалле

Устройство триггера

В основе всех триггеров лежит кольцо из двух логических элементов "НЕ" (инверторов), соединенных по типу "защелки" (см. рис. 0х002). Рассмотрим, как он работает. Если подать на линию Q сигнал, соответствующий единице, то, пройдя сквозь элемент D.D1 он обратится в ноль. Но, поступив на вход следующего элемента, – D.D2 – этот ноль вновь превратится в единицу. Поскольку, выход элемента D.D2 подключен ко входу элемента D.D1, то даже после исчезновения сигнала с линии Q, он будет поддерживать себя самостоятельно, т.е. триггер перейдет в устойчивое состояние. Образно это можно уподобить дракону, кусающему себя за хвост.

Естественно, если на линию Q подать сигнал, соответствующий логическому нулю,– все будет происходить точно так же, но наоборот!

Рисунок 2 0х002, lesiem_cd2.TIF Устройство простейшего триггера (слева). Образно это можно представить драконом, кусающим свой хвост

Увеличение эффективности предвыборки.

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

Рассмотрим следующий пример:

for (a = 0; a < N; a++)

{

for (b = 0; b < BLOCK_SIZE; b+=STEP_SIZE)

{

// Для переноса примера на K6\Athlon замените

// нижеследующую инструкцию на prefetch

_prefetchnta (p[a][b+STEP_SIZE]);

computation (a[a][b]);

}

}

Листинг 24 Пример, демонстрирующий "холостой" ход предвыборки

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

Как, не сильно усложнив алгоритм, увеличить его производительность? Да очень просто – достаточно лишь в последней итерации цикла B осуществить предвыборку следующей обрабатываемой ячейки. В данном случае ею будет ячейка p[a+1][0].

Оптимизированный вариант кода может выглядеть, например, так:

for (a = 0; a < N; a++)

{

for (b = 0; b <BLOCK_SIZE; b+=STEP_SIZE)

{

if (b==(BLOCK_SIZE-STEP-SIZE))

_prefetchnta (p[a+1][0]);

else

_prefetchnta (p[a][b+STEP_SIZE]);

computation (p[a][b]);

}

}

Листинг 25 Черновая демонстрация удаление "холостого" хода предвыборки

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

for (a = 0; a < N; a++)

{

for (b = 0; b <(BLOCK_SIZE-STEP_SIZE); b+=STEP_SIZE)

{

_prefetchnta (p[a][b+STEP_SIZE]);

computation (p[a][b]);

}

_prefetchnta (p[a+1][0]);

computation (p[a][b]);

}

Листинг 26 Финальная демонстрация удаления "холостого" хода предвыборки

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

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

int p[N];

#define computation (x) zzz+=(x)*0x666; zzz+=p[x];

for (a = 0; a < N; a+=sizeof(int))

{

_prefetchnta (p[a + 32*3]);

computation (a);

}

Листинг 27 Демонстрация чрезмерного злоупотребления предвыборкой

Поскольку каждый элемент массива p занимает всего лишь 8 байт, а размер кэш-линеек процессора в зависимости от модели составляет от 32 до 128 байт, в большинстве итераций цикла команда предвыборки будет выполняться вхолостую, т.к. запрошенные данные уже находятся в кэше, и загружать из оперативной памяти их не требуется. В такой ситуации команда предвыборка ведет себя аналогично инструкции NOP, однако накладные расходы на ее выполнение отнюдь не равны нулю! Чрезмерное засорение цикла предвыборкой (overprefetching) не то, что не ускоряет, а даже замедляет



его работу. В частности, пример??? 8 при исключении предвыборки исполняется на 10%-15% быстрее! (см. рис. 0х019). (Следует так же учесть накладные расходы на передачу аргументов функции предвыборки).

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

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

{

_prefetchnta (p[a + 32*3]);

computation (a+0);

computation (a+4);

computation (a+8);

computation (a+12);

computation (a+16);

computation (a+20);

computation (a+24);

computation (a+28);

}

Листинг 28 [cache_prefetch_unroll] Разворачивание цикла для исключения лишних запросов предвыборки



Рисунок 47 graph 0x019 Влияние лишних запросов предвыборки на производительность. За 100% приятно копирование памяти штатной функцией memcpy

Однако этот прием не лишен недостатков: во-первых, многократное дублирование тела цикла приводит к значительному увеличению объема исполняемого кода с вытекающим отсюда риском попросту не влезть в кэш. Во-вторых, величину шага (а, значит, и размер кэш-линеек) допустимо выбирать лишь на этапе создания программы и поменять ее "на лету" практически невозможно. Чем плоха "жесткая" прошивка? Дело в том, что, попав на процессор с иной длиной кэш-линий, программа будет исполняться недостаточно эффективно. Ориентироваться на размер в 32 байта – это хвататься за процессоры уходящего дня, но затачивать свой код под 128 байт – все равно, что бежать впереди паровоза. Рабочие станции на основе P-4 вытеснят P?III не раньше чем через несколько лет, но и тогда доля процессоров с 32 (64) байтными кэш-линейками будет весьма велика. Похоже, ничего не остается, как реализовать все критичные к быстродействию функции в нескольких вариантах и по ходу выполнения программы выбирать одну из них.



Но почему бы ни вставить в цикл тривиальный условный оператор, например, что-то вроде: if ((a % PREFETCH_CACHE_LINE_SIZE) == 0) prefetch(a+psd)? Во?первых, деление крайне

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

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

Рассмотрим следующий пример:

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

{

computation1 (p1[a]);

computation2 (p2[a]);

computation3 (p3[a]);

computation4 (p4[a]);

}

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

При условии, что блоки памяти p1, p2, p3 и p4 расположены достаточно далеко друг от друга, требуется как минимум четыре инструкции предвыборки на каждую итерацию. Возникает вопрос – как лучше всего их расположить: поместить их в начало цикла или перемешать вместе с остальными инструкциями?

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


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

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

Т.е. предвыборку с инструкциями записи должно разделять, по крайней мере, 30-50, а лучше еще большее количество тактов процессора. А что делать, если это невозможно? В таком случае будет лучше сгруппировать все операции предвыборки вместе, чем позволить им перемешаться с операциями записи. Вообще-то оптимальное чередование можно подобрать и экспериментально, только помните о том, что оно системно-зависимо.

В ядре

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

(ROW), а вертикальные – столбцами

(Column) или страницами (Page).

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

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

Чувствительный усилитель (sense amp), подключенный к каждому из столбцов матрицы, реагируя на слабый поток электронов, устремившихся через открытые транзисторы с обкладок конденсаторов, считывает всю страницу целиком. Это обстоятельство настолько важно, что последняя фраза вполне заслуживает быть выделенной курсивом. Именно страница является минимальной порцией обмена с ядром динамической памяти. Чтение/запись отдельно взятой ячейки невозможна! Действительно, открытие одной строки приводит к открытию всех, подключенных к ней транзисторов, а, следовательно, – разряду "закрепленных" за этими транзисторами конденсаторов. Хочешь – не хочешь,– а читай всю строку за раз целиком!

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

"Имею скафандр - готов путешествовать" Роберт Ханлайн

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

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

– периодическому считыванию ячеек с последующей перезаписью. В зависимости от конструктивных особенностей "регенератор" может находиться как в контроллере, так и в самой микросхеме памяти. Например, в компьютерах XT/AT регенерация оперативной памяти осуществлялась по таймерному прерыванию каждые 18 мс через специальный канал DMA (контроллера прямого доступа). И всякая попытка "замораживания" аппаратных прерываний на больший срок приводила к потере и/или искажению оперативных данных, что не очень-то радовало программистов, да к тому же снижало производительность системы, поскольку во время регенерации память была недоступна. Сегодня же регенератор чаще всего встраивается внутрь самой микросхемы, причем перед регенерацией содержимое обновляемой строки копируется в специальный буфер, что предотвращает блокировку доступа к информации.



Рисунок 4 core 1024-битное ядро памяти компьютера UNIVAC-11015. Действительный размер этого ядра составляет 5.5 см. Похожее на грубо обработанную мешковину, оно, в действительности, состоит из многочисленных ферритовых "пончиков", каждый из которых может хранить всего лишь один бит информации. По легенде, намотку ферритовых колец осуществляли… девушки, вооруженные стереоскопическим микроскопом. Мужчины, по всей видимости оказывались слишком неуклюжими и недостаточно усидчивыми для этой тонкой и чрезвычайно кропотливой работы. (Попробовал бы сегодня кто-нибудь намотать 1 гигобит ячеек памяти вручную!). Восемь таких ядер объединялись в стопку, реализуя на пересечении столбцов и колонок целый байт информации (термин "машинное слово" в те годы еще не был изобретен!).

В кэше первого уровня

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

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

Помимо этого, увеличенный масштаб графика (ведь мы собственноручно растянули его в сто раз по вертикали – см. 100*Ax_GET) позволяет безо всякого труда установить, что запись ячеек памяти происходит в три раза быстрее чтения и в четыре раза быстрее чтения, последующим за записью. Виною тому – накладные расходы на организацию цикла. Компилятор Microsoft Visual C++ 6.0, которым транслировалась тестовая программа, сумел распознать цикл записи и заменил его всего одной машинной командой: REP STOSD, в то время как цикл чтения занял несколько машинных команд.

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

процессор		латентность		пропускная способность		макс. операций
K5		чтение		1		2		R+R | R+W
запись		1
K6		чтение		2		1		R + W
запись		1		1
Athlon		чтение		?		2		R+R+W+W
запись		?		2
P-II, P-III		чтение		3		1		R+W
запись		1		1
P-4		чтение		2		1		R+W
запись		2		1

Таблица 3 Основные характеристики кэш памяти некоторых моделей процессоров.

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

Тем не менее, при отсутствии зависимости по данным, процессор может приступать к загрузке следующей ячейке не через два такта, а всего лишь через один, ведь устройство вычисления эффективного адреса уже освободилось и к началу следующего такта вновь готово к работе! Таким образом, N независимых ячеек могут быть прочитаны за N*Throughput + Latency

тактов. Очевидно, что при большом N, величиной латентности можно полностью пренебречь, приняв среднее время доступа к ячейке в 1 такт на K6 и 0.5 таков на Athlon (Athlon способен загружать две 32 битных ячейки за такт).

Правда тут есть одно "но". Параллельное выполнение команд осуществляется как минимум при наличии этих самых команд. В свернутом цикле вида for(a=0; a < BLOCK_SIZE; a++) x+=p[a]; происходит лишь одно обращение к памяти за каждую итерацию (при условии, что переменные a

и x

расположены в регистрах, конечно), поэтому время выполнения данного цикла окажется значительно больше, чем N*Throughput + Latency. Решение проблемы состоит в развороте цикла по крайней мере на две итерации. Подробнее этот вопрос уже рассмотрен в ("Часть I. Оптимизация работы с памятью. Разворачивание циклов") сейчас же нас больше интересует другой аспект, а именно: как изменится производительность при выходе за кэш первого уровня.

В кэше второго уровня

Время загрузки данных из кэша второго уровня составляет порядка тактов процессора в пересчете на одну 32битную ячейку, где F.CACHE – частота работы кэша второго уровня, F.CPU – частота ядра, а N.BUS – разрядность локальной кэш-шины. Латентность кэш-контроллера и блока интерфейсов с шиной здесь не учитывается, т.к. при конвейерной обработке данный ей можно полностью пренебречь.

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

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

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

В ожидании конца света

Это в наше-то время говорить о конце света? Лучше уж о прошлогоднем снеге – все-таки имеет отношение к урожаю. Во всяком случае завтра его не будет, а там… наши потомки что-нибудь да придумают! Который раз объявляют очередной день Концом, но в последний момент вновь переносят исполнение «приговора Господня» на неопределенный срок. Вот и слухи о готовящимся столкновении с астероидом «1999 AN10» в середине нашего века оказались сильно преувеличенными – уточненные расчеты показали, что даже в момент наибольшего сближения нас будут разделять по меньшей мере полмиллиона километров!

А если бы не разделяли – свершились бы самые худшие опасения создателей кинофильмов «Астероид» и «Армагеддон». В момент столкновения вся кинетическая энергия астероида (e=mv2/2) мгновенно высвобождается и происходит чудовищной мощности взрыв. Приняв среднюю плотность астероидов равной 3,5х103 кг/м3, скорость – порядка 104

м/сек, а размер – километр в поперечнике, нетрудно рассчитать энергию взрыва. Но ненаглядно мереть ее джоулями – гораздо практичнее оперировать тротиловым эквивалентом. Астероид, движущийся со скоростью 4 км/сек, в момент столкновения эквивалентен такому же по массе количеству тротила, т.е. в среднем несет в себе заряд порядка 20.000.000 мегатонн. Даже в наш век атомного оружия о такой бомбе ни один полководец не смеет и мечтать (эдак всю Землю разнести недолго)! А ведь поперечник многих астероидов составляет сотни километров, а скорости столкновения доходят до пятнадцати и более километров в секунду…

Какие последствия вызовет взрыв такой силы сказать трудно – ученым до сих пор не представилось возможности проверить свои предположения на практике. Считается – наиболее благоприятно для человечества падение астероида в океан. За исключением «мелких брызг» все дело закончится гигантской морской волной, способной обойти весь Земной Шар и дважды и трижды, поднимаясь при этом на несколько километров! Но будем оптимистами – мы не сахарные, не растаем. Пока волна своим ходом до нас дойдет – переждем ее на вертолетах (только не спрашивайте: «где мы найдем столько вертолетов?»).
Правда, имеются смутные опасения насчет океанской коры, слишком тонкой, чтобы выдержать такие удары судьбы – наверняка астероид пробьет ее насквозь и… точное развитие событий геологи еще прорабатывают, но уже ясно, что по крайне мере в планетарном масштабе это ничем не грозит. А землетрясения и извержения – локальные катастрофы, никак не отражающиеся на судьбе человечества в целом.

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

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

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

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

Строго определения «астероидам» не существует – астрономы относят к ним все, что меньше планеты и в отличие от комет не имеет видимого хвоста, а движется по эллипсу в одном из фокусов которого находится Солнце.


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

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

По общепринятой модели Солнечная система образовалась из газопылевого облака, а все тела в свою очередь сформировались в результате дефекта складки – давным-давно однородный газопылевой шар, окружающий Солнце, по причине осевого вращения сплющился в диск (центробежные силы в плоскости экватора диаметрально противоположны силам гравитации, в то время как у полюсов ничто не могло удержать частички газа и пыли от падения на Солнце). Из курса физики известно – в поле тяжести радиус вращения тела по круговой орбите обратно пропорционален квадрату скорости. Т.е. если бы все пылинки двигались одинаково, они бы собрались на какой-то одной орбите, сформировав одну-единственную планету. Но квадратичная зависимость многократно усиливает даже незначительную дисперсию скоростей, делая протопланетный диск гравитационно-неустойчивым, отчего он распадается на отдельные сгущения. Если коэффициент дисперсии близок к единице, порядка 2/3 всей массы диска сосредотачиваются в одной планете типа Юпитера, а остаток распределяется между всеми остальными. Мощное гравитационное поле гиганта стянуло на себя часть вещества своих соседей, отхватив приличный кусок от того, что впоследствии стало Марсом (вот почему он меньше Земли, хотя исходя из распределения дисперсии скоростей должно быть наоборот) и изрядно поистрепало строительный материал гипотетической планеты Фаэтон, оставив ей горстку мусора, по массе в сотни раз меньшую Луны. Фаэтону просто не из чего было формироваться, но даже если бы он каким-то чудом сумел образовался, тяготение Юпитера в короткие сроки вновь разрушило бы его!



Вместо Фаэтона в этой области пространства мы наблюдаем огромное количество космического щебня – «пояс астероидов». В отличие от всех остальных планет эволюция пояса еще не завершена и в настоящее время там происходят чрезвычайно любопытные процессы.

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

Чем меньше небесное тело, тем оно чувствительнее к гравитационным возмущениям, а его орбита неустойчивее. Юпитер запросто может выдернуть разлетающиеся осколки из пояса астероидов, изменив их орбиту так, что она пересечется с орбитой Земли. К счастью, вероятность столкновения с нами очень мала, но во-первых, из-за дробления астероидов со временем она неумолимо нарастает, а во-вторых, «…слон был один на всю Москву, да и того убило».

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

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


Но даже этого «чуть-чуть» достаточно, чтобы астероид врезался в Землю или наоборот, пролетел далеко от нее!

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

Это только «царям природы» Земля кажется большой – в масштабах Космоса она все равно что пылинка. Нас и Солнце разделяют сто пятьдесят миллионов километров, и приблизительно в полтора раза дальше находится пояс астероидов. Погрешность ±0.01% приводит к неопределенности в расстоянии пятьдесят тысяч километров, что вчетверо больше диаметра нашего «шарика»! Поэтому, если расчетное сближение с Землей составляет менее полумиллиона километров, астрономы всерьез начинают беспокоится о столкновении (прогнозы же типа «астероид … упадает в Атлантический океан в районе острова Мадагаскар» не более чем выдумка журналистам – не верьте им, такую точность расчетов наука, в отличие от гадалок, магов и прорицателей, обеспечить ни сейчас, ни в отдаленном будущем не в состоянии!)

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

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

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

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


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

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

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

Когда же такая теория будет построена, дело станет за малым, – вот «сталкивающийся» астероид обнаружен – как его уничтожить? Пальнуть по нем атомной ракетой? А вдруг не попадет? Подпускать засранца близко к Земле нельзя (рискованно!), а ракет, способных поразить цель на большом удалении от Земли, пока нет и в скором будущем не предвидится.

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

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



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

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

Биосферу Земли, как шутят учение, можно уничтожить разве что вместе с самой Землей. Так что не волнуйтесь, ничего с ней не случиться: как говорил старик Лемм – это не конец мира, это всего лишь конец нашей цивилизации…

* В поисках нуля *

Для комфортной работы всякий прибор следует

Влияние размера исполняемого кода на производительность

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

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

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

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

В результате, у нас получится следующее:

; CODE_SIZE EQU      ?      ; // Макрос CODE_SIZE автоматически генерируется

                           ; // пакетным файлом-транслятором

; /*--------------------------------------------------------------------------

;  *

;  *          МАКРОС, ГЕНЕРИРУЩИЙ N машинных команд "NOP

;  *

;  *                       (команда NOP буквально обозначает "нет операции"

;  *                       и занимает  ровно один байт, т.е. N команд NOP

;  *                       дают N байт исполняемого кода)

;  *

;  -------------------------------------------------------------------------*/

NOPING MACRO N                    ; // НАЧАЛО МАКРОСА //

       _N = N               ; _N := N (получаем переданный макросу аргумент)

       _A = 0               ; _A -- переменная-счетчик цикла

       WHILE _A NE _N             ; while(_A <= _N){

              NOP           ; вставляем в исходный текст "NOP"

              _A = _A + 1   ; _A++;

       ENDM                 ; }

ENDM                       ; // КОНЕЦ МАКРОСА //

; /*--------------------------------------------------------------------------

;  *

;  *          ВЫЗОВ МАКРОСА ДЛЯ СОЗДАНИЯ БЛОКА ИЗ CODE_SIZE KB команд NOP

;  *

; --------------------------------------------------------------------------*/

NOPING CODE_SIZE*1024

Листинг 2 [Cache/ code.cache.size.xm] Ассемблерный листинг программы, генерирующей произвольное количество машинных операций NOP

#include

"code.cache.size.h"             ; ßэтот файл формируется пакетным транслятором

                                  ; и содержит определение CODE_SIZE

#include <DoCPU.h>

main()

{

       int a;

       A_BEGIN(1);                ; ß начало замера времени выполнения

              DoCPU(&a);           ; выполняем блок из CODE_SIZE команд NOP

       A_END(1);                  ; ß конец замера времени выполнения

      

       // вывод результатов замера на экран

       printf("%03d\t %d\n", CODE_SIZE, Ax_GET(1));

}

Листинг 3 [Cache/code.cache.size.c] Пример, демонстрирующий последствия выхода за кэш перового (второго) уровня

@ECHO OFF

IF #%1#==#MAKE_FOR# GOTO make_it

REM MAKE ALL

ECHO

= = = СБОРКА ПРИМЕРА, ДЕМОНСТРУЮЩЕГО ОПРЕДЕЛЕНИЕ РАЗМЕРА КОДОВОГО КЭША = = =

ECHO

Утилита к книге \"Техника  оптимизации  программ"  /* название рабочее */

ECHO @ECHO OFF                                              >  CODE.CACHE.SIZE.RUN.BAT

ECHO ECHO

= = демонстрация определения размера кэша = =     >> CODE.CACHE.SIZE.RUN.BAT



ECHO ECHO

Утилита к книге "Техника  оптимизации  программ"  >> CODE.CACHE.SIZE.RUN.BAT

ECHO ECHO N NOP     ...CLOCK...                             >> CODE.CACHE.SIZE.RUN.BAT

ECHO ECHO ------------------------------------------------- >> CODE.CACHE.SIZE.RUN.BAT

FOR %%A IN (2,4,8,16,32,64,128,256,512,1024,2048) DO CALL  %0 MAKE_FOR %%A

ECHO DEL %%0                                                >> CODE.CACHE.SIZE.RUN.BAT

GOTO end

:make_it

ECHO /%0/%1/%2 *

SHIFT

ECHO CODE_SIZE EQU %1                                       >  CODE.CACHE.SIZE.MOD

ECHO #define CODE_SIZE %1                                   >  CODE.CACHE.SIZE.H

TYPE CODE.CACHE.SIZE.XM                                     >> CODE.CACHE.SIZE.MOD

CALL CLOCK.MAKE.BAT   CODE.CACHE.SIZE.C                     > NUL

DEL  CODE.CACHE.SIZE.MOD

DEL  CODE.CACHE.SIZE.H

IF   NOT EXIST CODE.CACHE.SIZE.EXE  GOTO err

IF   EXIST CODE.CACHE.SIZE.%1.EXE   DEL CODE.CACHE.SIZE.%1.EXE

REN  CODE.CACHE.SIZE.EXE CODE.CACHE.SIZE.%1.EXE

ECHO CODE.CACHE.SIZE.%1.EXE                                 >> CODE.CACHE.SIZE.RUN.BAT

ECHO DEL CODE.CACHE.SIZE.%1.EXE                             >> CODE.CACHE.SIZE.RUN.BAT

GOTO end

:err

ECHO -ERR ошибка

компиляции! подробнее см. CODE.CACHE.SIZE.ERR

TYPE CODE.CACHE.SIZE.ERR

EXIT

:end

Листинг 4 [Cache/code.cache.size.make.bat] Пакетный файл, выполняющий трансляцию тестовой программы

Влияние размера обрабатываемых данных на производительность

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

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

Даже такой авторитет как Agner Fog в свей монографии "How to optimize for the Pentium family of microprocessors" приводит всего лишь ориентировочное количество тактов, требующихся для загрузки ячейки из различных иерархий памяти! Может быть, эта информация и полезна сама по себе, но она не дает общего представления о картине. Ведь "время доступа" как уже было показано в первой части настоящей книги (см. Части I "Оперативная память. Взаимодействие памяти и процессора. Вычисление полного времени доступа") – слишком абстрактное понятие, тесно переплетающееся с конвейером и параллелизмом. К тому же, Fog устарел не на один ледниковый период и сегодня представляет разве что исторический интерес (во всяком случае – часть, касающаяся времени доступа к памяти). Что ж! Ничего не остается как затовариться пивом (или "Напитками из Черноголовки" – это кому как во вкусу) и плотно засесть за компьютер в надежде разобраться во всем самостоятельно.

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

#define       BLOCK_SIZE    (715*K)       // размер обрабатываемого блока памяти

#define STEP_FACTOR  (1*K)  // шаг приращения перебираемого размера

#define X            1      // :'b' - для вычитания линейной составляющей

                           // :'1' - показывать график как есть

// выделяем память

p = malloc(BLOCK_SIZE);

// шапка

printf("---\t");

for (b = 1*K; b < BLOCK_SIZE; b += STEP_FACTOR)

       printf("%d\t",b/K); printf("\n");

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

 *

 *                   ПОСЛЕДОВАТЕЛЬНОЕ ЧТЕНИЕ

 *

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

printf("R\t"); for (b = 1*K; b < BLOCK_SIZE; b += STEP_FACTOR)

{

       PRINT_PROGRESS(25*b/BLOCK_SIZE); VVV;

       A_BEGIN(0)

              for (c = 0; c <= b; c += sizeof(int))

                     tmp += *(int*)((int)p + c);

       A_END(0)

       printf("%d\t", 100*Ax_GET(0)/X);

}

printf("\n");

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

 *

 *                   ПОСЛЕДОВАТЕЛЬНАЯ ЗАПИСЬ

*

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

printf("W\t"); for (b = 1*K; b < BLOCK_SIZE; b += STEP_FACTOR)

{

       PRINT_PROGRESS(25+25*b/BLOCK_SIZE); VVV;



       A_BEGIN(1)

              for (c = 0; c <= b; c += sizeof(int))

                     *(int*)((int)p + c) = tmp;

       A_END(1)

       printf("%d\t", 100*Ax_GET(1)/X);

}

printf("\n");

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

 *

 *            ПОСЛЕДОВАТЕЛЬНОЕ ЧТЕНИЕ потом ЗАПИСЬ

 *

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

printf("RW\t"); for (b = 1*K; b < BLOCK_SIZE; b += STEP_FACTOR)

{

       PRINT_PROGRESS(50+25*b/BLOCK_SIZE); VVV;

       A_BEGIN(2)

       for (c = 0; c <= b; c += sizeof(int))

       {

              tmp += *(int*)((int)p + c);

              *(int*)((int)p + c) = tmp;

       }

       A_END(2)

       printf("%d\t", 100*Ax_GET(2)/X);

}

printf("\n");

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

 *

 *            ПОСЛЕДОВАТЕЛЬНОЕ ЧТЕНИЕ потом ЗАПИСЬ

 *

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

printf("WR\t"); for (b = 1*K; b < BLOCK_SIZE; b += STEP_FACTOR)

{

       PRINT_PROGRESS(75+25*b/BLOCK_SIZE); VVV;

       A_BEGIN(3)

       for (c = 0; c <= b; c += sizeof(int))

       {

              *(int*)((int)p + c) = tmp;

              tmp += *(int*)((int)p + c);

       }

       A_END(3)

       printf("%d\t", 100*Ax_GET(3)/X);

}

printf("\n");

Листинг 1 [Cache/cache.size.c] Пример, демонстрирующий зависимость времени обработки от размера и рода обработки блока данных

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



меняющую крутизну своих склонов.

Если присмотреться повнимательнее (впрочем, вряд ли вы что разглядите на полиграфии такого качества), то можно заметить, что первый подъем расположен в районе ~32 километра, ой, я хотел сказать килобайта. Это и есть размер сверхоперативной памяти кэша данных первого уровня микропроцессора AMD K6 (кстати, неплохого между прочим процессора).

Миновав кэш, график чтения начинает линейное восхождение вверх с коэффициентом пропорциональности близким к единице, т.е. на участке (L1.CACHE.SIE; L2.CACHE.SIZE] – время обработки блока в зависимости от его размера изменяется так: , где T – время обработки. При выходе за пределы кэша первого уровня быстродействие программы резко и значительно сокращается, – действительно, по горам лазать – это вам не по равнине налегке ходить (кэш первого уровня – это равнина).

Наклон графика чтения задирается к верху еще круче и визуально (то бишь субъективно) его коэффициент пропорциональности близко к полутора, а то и двум. Между тем, это – не более чем досадный обман зрения и формула зависимости времени обработки от размеров записываемого блока идентична формуле чтения. Не верите? Так давайте проверим! Смотрите: обработка ~89 Кб блока данных заняла 200.000 тактов процессора, а ( …приложив линейку к монитору…) блок в ~177 Кб обрабатывался бы 400.000 тактов. А теперь – 89 : 177 ==200.000 : 400.000 == 0.5, что и требовалось доказать!



Рисунок 17 graph 0 Зависимость времени обработки от размера блока (AMD K6) без вычета линейной составляющей

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

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

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

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

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



Рисунок 18 graph 1 Зависимость скорости обработки от размера блока на AMD K6

Вместо заключения

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

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

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

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

Волчьи ямы опережающей записи

Начиная с K5 процессоры серии x86 используют прозрачную буферизацию записи (см. "Кэш – принципы функционирования. Буфера записи"), причем, буфера записи доступны не только на запись, но на чтение. То есть, результат работы команды становится доступным сразу же, как только он попадает в буфер,– дожидаться завершения его выгрузки в кэш-память нет никакой нужды! Очевидно, что такой трюк, именуемый разработчиками процессоров опережающий записью (Store-Forwarding), значительно сокращает время доступа к данным.

Рассмотрим это на следующем примере. Пусть у нас имеется цикла вида.

for(a = 0; a < BLOCK_SIZE; a += sizeof(tmp32))

{

       p[a] += tmp_1;

       tmp_2 -= p[a];

}

Вместо того, чтобы гонять данные по "большому кругу кровообращения": вычислительное устройство à

блок записи à

кэш à

блок чтения à

вычислительное устройство, процессор AMD Athlon направляет данные по "малому кругу кровообращения" вычислительное устройство à

буфер записи à

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

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

Продемонстрируем это на следующем примере (см. рис. 0х17 слева):

*(int *)((int)p) = x;         // запись данных в буфер

y = *(int *)((int)p + 2);     // байтов [p+2; p+4] нет в буфере

Грубо говоря, мы записываем в буфер ячейки 0, 1, 2 и 3, а затем запрашиваем ячейки 2, 3, 4 и 5. Легко сообразить, что ячеек 4 и 5 просто нет в буфере и для их загрузки процессору необходимо обратиться к кэшу. Но ведь в кэше еще нет ячеек 2 и 3, – т.к. они не успели покинуть буфер!

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

Но, так или иначе, все это требует дополнительных тактов, снижающих производительность. (На P-III величина пенальти составляет шесть тактов, а на AMD Athlon – десять).



Рисунок 33 0х017 Возникновение задержки при перекрытии областей чтения/записи

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



Рисунок 34 0х018 Возникновение задержки при несоответствии разрядности данных

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

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

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

       *(char *)((int)p + 0) = 'B';

       *(char *)((int)p + 1) = '0';

       *(char *)((int)p + 2) = 'F';

       *(char *)((int)p + 3) = 'H';

       BOFH

= *(int *)((int)p

+ 0);      // ß задержка! читаются не те же самые данные,



                                  // которые только что были записаны

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

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

Если же прочесть небольшую порцию только что записанных данных просто жизненно необходимо, – воспользуйтесь, как и рекомендует Intel, битовыми операциями: "If it is necessary to extract a non-aligned portion of stored data, read out the smallest aligned portion that completely contains the data and shift/mask the data as necessary. The penalty for not doing this is much higher than the cost of the shifts".

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

// не оптимизированный код

for(a = 0; a < BLOCK_SIZE; a += sizeof(int))

{

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

       y += *(char *)((int)p + a + 2));

}

Выделенная жирным шрифтом строка навлекает страшный гнев процессора и становится самым узким местом в цикле.

Попробуем исправить проблему так:

// оптимизированный код

for(a = 0; a < BLOCK_SIZE; a += sizeof(int))

{

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

       tmp = *(int *)((int)p + a);              // читаем во временную переменную те же самые данные

       x += ((tmp & 0x00FF0000) >> 0x10); // "вручную" выкусываем нужный нам ячейку



}

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

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

Рассмотрим следующий пример:

*(int *)((int)p) = x;

*(int *)((int)p + L1_CACHE_SIZE/L1_CACHE_WAY_ASSOCIATIVE) = y;

z = *(int *)((int)p);      // ß задержка

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

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

for(a = sizeof(int); a < BLOCK_SIZE; a += sizeof(int))



{

       x += *(char *)((int)p + a - (sizeof(int)/2));

       *(int *)((int)p + a) += y;

}

И в заключении главы – наш традиционный эксперимент, позволяющий количественно оценить степень падения производительности при неправильном обращении к данным. Для наглядности мы последовательно переберем все шесть комбинаций (см. листинг mem.stail.c), упомянутых в руководстве по оптимизации от Intel (кстати, руководство по оптимизации от AMD крайне поверхностно и туманно освещает эту проблему, поэтому даже если вы убежденный поклонник AMD не побрезгуйте обратится к Intel, тем более, что в этом вопросе оба процессора ведут себя одинаково).

// выделяем

память

p = (int*)_malloc32(BLOCK_SIZE);

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

 *

 *                   ОПТИМИЗИРОВАННЫЙ ВАРИАНТ

 *                 Long Write/Long Read(same addr)

 *

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

for(a = 0; a < BLOCK_SIZE; a += sizeof(tmp32))

{

       *(int *)((int)p + a) = tmp32;

       tmp32 += *(int *)((int)p + a);

}

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

 *

 *                   НЕОПТИМИЗИРОВАННЫЙ ВАРИАНТ

 *                Short Write/Long Read (same addr)

 *

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

for(a = 0; a < BLOCK_SIZE; a += sizeof(tmp32))

{

       *(char *)((int)p + a) = tmp8;

       tmp32 += *(int *)((int)p + a);

}

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

 *

 *                   НЕОПТИМИЗИРОВАННЫЙ ВАРИАНТ

 *                Short Write/Long Read (overlap space)

 *

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

for(a = sizeof(tmp32); a < BLOCK_SIZE; a += sizeof(tmp32))

{

       *(char *)((int)p + a + (sizeof(tmp32)/2)) = tmp8;

       tmp32 += *(int *)((int)p + a);

}

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



 *

 *                   НЕОПТИМИЗИРОВАННЫЙ ВАРИАНТ

 *                Long Write/Short Read (same addr)

 *

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

for(a = 0; a < BLOCK_SIZE; a += sizeof(tmp32))

{

       *(int *)((int)p + a) = tmp32;

       tmp8 += *(char *)((int)p + a);

}

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

 *

 *                   НЕОПТИМИЗИРОВАННЫЙ ВАРИАНТ

 *                Long Write/Short Read (overlap space)

 *

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

for(a = sizeof(tmp32); a < BLOCK_SIZE; a += sizeof(tmp32))

{

       *(int *)((int)p + a) = tmp32;

       tmp8 += *(char *)((int)p + a + (sizeof(tmp32)/2));

}

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

 *

 *                   НЕОПТИМИЗИРОВАННЫЙ ВАРИАНТ

 *                Long Write/Long Read (overlap space)

 *

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

for(a = sizeof(tmp32); a < BLOCK_SIZE; a += sizeof(tmp32))

{

       *(int *)((int)p + a) = tmp32;

       tmp32 += *(int *)((int)p + a - (sizeof(tmp32)/2));

}

Листинг 14 [Cache/mem.stail.c] Демонстрация возникновения задержек памяти при записи/чтении данных         различного размера

Результат прогона этой программы на процессорах AMD Athlon 1050 и P-III 733 представлен ниже. При условии, что обрабатываемый блок не превышает размера кэша первого (второго уровня), попытка чтения отсутствующих в буфера данных приводит к пяти-шести кратному падению производительности (см. рис. graph 05)!

На P-4 (если верить его разработчикам) величина пенальти еще больше. Намного больше, вот цитата из руководства: "The performance penalty from violating store-forwarding restrictions was present in the Pentium II and Pentium III processors, but the penalty is larger on the Pentium 4 processor" и дальше "

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


Если их адреса совпадают, время доступа к ячейке увеличивается "всего" в полтора раза.



Рисунок 35 graph 05 Возникновение задержек при обработке данных различной разрядности (в кэше первого/второго уровня)

Вне кэша. При выходе за пределы кэш-памяти второго уровня картина существенно изменяется. Штрафные санкции снижаются до не таких уж значительных полутора-трех крат, а короткое чтение после длинной записи на P-III (и – предположительно – на P-II и P-4) исполняется и вовсе без издержек! Впрочем, не стоит обольщаться, – AMD Athlon не простит вам подобных вольностей и накажет двух кратным падением производительности.

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

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



Рисунок 36 graph 06 Возникновение задержек при обработке данных различной разрядности, находящихся в основной памяти

Волчьи ямы опережающей записи II

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

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

На P6 и K6 следующий код будет исполняться предельно быстро независимо от того, присутствует ли ячейка *p в сверхоперативной памяти или нет:

*p = a;

b = p*;

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

*p = a;

f = (sin(x) + con(y)) / z;

b = p*;

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

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

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

В данном случае проблемы легко избежать перегруппировкой команд, – переместив вычислительную операцию на одну строчку вверх или вниз, – мы добьемся спаривания команд записи/чтения и гарантировано избежим преждевременного вытеснения буферов. Но такое решение не всегда достижимо. Команды могут иметь зависимость по данным или вообще находится в различных функциях, а то и потоках. Как быть тогда? Откроем, например, уже упомянутое руководство по оптимизации от Ангера Фрога ("How to optimize for the Pentium family of microprocessors" by Agner Fog) и найдем в главе, посвященной кэш-памяти следующие строки:

"When you write to an address which is not in the level 1 cache, then the value will go right through to the level 2 cache or to the RAM (depending on how the level 2 cache is set up) on the PPlain and PMMX. This takes approximately 100 ns. If you write eight or more times to the same 32 byte block of memory without also reading from it, and the block is not in the level one cache, then it may be advantageous to make a dummy read from the block first to load it into a cache line. All subsequent writes to the same block will then go to the cache instead, which takes only one clock cycle. On PPlain and PMMX, there is sometimes a small penalty for writing repeatedly to the same address without reading in between.

On PPro, PII and PIII, a write miss will normally load a cache line, but it is possible to setup an area of memory to perform differently, for example video RAM (See Pentium Pro Family Developer's Manual, vol. 3: Operating System Writer's Guide").



("Когда на Pentium- просто или Pentium MMX вы записываете данные, отсутствующие в кэш-памяти первого уровня, они будут помещены в кэш второго уровня или основную оперативную память (в зависимости от того: наличествует ли кэш второго уровня или нет). Эта операция занимает приблизительно 100 нс. Если вы обращайтесь на запись восемь или более раз (именно раз, а не байт, как сказано в популярном переводе Дмитрия Померанцева) к одному и тому же 32-байтовому блоку памяти без чтения чего бы то ни было оттуда, и данный блок памяти отсутствует в кэше первого уровня, было бы недурственно предварительно прочитать любую ячейку блока, загружая тем самым его в кэш первого уровня. Все последующие операции записи данного блока будут записываться в кэш первого уровня, что займет всего один такт. На Pentium-просто и Pentium MMX при многократной записи данных по одному и тому же адресу иногда возникают небольшие задержки, если эти данные не будут востребованы.

На Pentium Pro, Pentium-II и Pentium-III промах записи обычно загружает соответствующую кэш-линейку, но если это возможно, установите область памяти для предотвращения различий, например видеопамять (см. "Семейство-Pentium Pro Справочник разработчика. Том 3. Руководство создателям операционных систем").

Выделенное курсивом предложение написано довольно неуверенным тоном (похоже Ангер Фрог и сам его не понимал). Итак, начинаем лексический анализ. "Normally load a cache line" – можно перевести двояко. "нормально загружает" (т.е. самостоятельно загружает без дураков) или же "обычно загружает" (т.е. может загрузить, а может нет). Судя по всему, Ангер Фрог подразумевал последний вариант. Действительно, в зависимости от состояния соответствующих атрибутов страницы, кэширование записи может быть как разрешено, так и нет. Вот например, в области видеопамяти оно уж точно запрещено, ведь в противном случае обновление изображения происходило бы не в момент записи, а спустя неопределенное время после вытеснения данных из кэша первого уровня, что вряд ли кого могло устроить.


Вот Фрог и советует: убедитесь, что обрабатываемая область памяти разрешает кэширование…

Между тем, это только часть истины, – Ангер Фрог совсем забыл о буферизации. На самом деле, и на P-Pro, и на P-II, и на P-III промах записи не загружает кэш линейку! (Исключение составляет запись расщепленных данных). На K6/Athlon промах записи так же не приводит к немедленной загрузке кэш-линейки, но поскольку содержимое буферов вытесняется в кэш первого уровня, с некоторой натяжкой можно сказать, что такая загрузка все-таки происходит.

Поэтому, к современным процессорам применимы те же самые рекомендации, что и к Pentium-просто и Pentium MMX. Покажем их живое воплощение на практике:

volatile trash;

trash = *p;

*p = a;

f = (sin(x) + con(y)) / z;

b = *p;

Что изменилось? Обратите внимание на выделенную жирным шрифтом строку, загружающую содержимое записываемой ячейки в неиспользуемую переменную. Такой трюк практически не снижает производительности (т.к. процессоры P6 и K6 могут дожидаться загрузки ячейки из оперативной памяти параллельно с ее записью), но гарантирует, что содержимое буферов к моменту обращения к ним, не будет вытеснено дальше кэша первого уровня. А кэш первого уровня – он всегда под рукой и его чтение не займет много времени.

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

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

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


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

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

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

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


Да-да, не него возложена миссия

___промежуток времени, в течении которого записываемые данные еще можно надеяться обнаружить в буферах, а так же

; N_ITER EQU  ?      ;// <-- !auto gen!

; /*--------------------------------------------------------------------------

;  *

;  *          макрос, автоматически дублирующий свое тело N раз

;  *

; ---------------------------------------------------------------------------*/

STORE_BUFF MACRO N

       _N = N

       _A = 0

       WHILE _A NE _N

              MOV [EBX+32*_A],ECX; <- *(int *)((int)p + 32 * _A) = x;

              _A = _A + 1

       ENDM

ENDM

; /*--------------------------------------------------------------------------

;  *

;  *          ДЕМОНСТРАЦИЯ ВЫГРУЗКИ БУФЕРОВ ВО ВРЕМЕЯ ЗАНЯТОСТИ ШИНЫ

;  *

; ---------------------------------------------------------------------------*/

STORE_BUFF    N_ITER ; *p+00 = a;  <-     заполняем буфера записи, записывая

                     ; *p+32 = a;         каждый раз ячейку  в  новый  буфер

                     ; *p+64 = a;         Буфера  выгружаются  параллельно с

                     ; ..........         записью. Чтобы доказать это мы....

MOV    EDX,   [EBX]  ; b = *p;     <-     ...мы обращаемся к самому  первому

                           ;             записанному  буферу; если  он  еще

                           ;             не   выгружен, -  его   содержимое

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

                           ;             в противном случае возникнет зад.

ADD EBX,      32*N_ITER;           <-     смещаем указатель на след. буфера

Листинг 15 [Cache/store_buf.xm] Ядро программы, демонстрирующей выгрузку одних буферов записи параллельно с заполнением других

; N_ITER EQU  ?      ;// <-- !auto gen!

; /*--------------------------------------------------------------------------

;  *

;  *                 макрос, автоматически дублирующий свое тело N раз



;  *

; ---------------------------------------------------------------------------*/

STORE_BUFF MACRO N

       _N = N

       _A = 0

       WHILE _A NE _N

              NOP                  <-     ТЕЛО МАКРОСА

              _A = _A + 1

       ENDM

ENDM

; /*--------------------------------------------------------------------------

;  *

;  *          ДЕМОНСТРАЦИЯ ВЫГРУЗКИ БУФЕРОВ ВО ВРЕМЕНЯ ПРОСТОЯ ШИНЫ

;  *

; ---------------------------------------------------------------------------*/

MOV    [EBX], ECX    ; *p = a;     <-     тут мы записываем в *p некое  значение

                     ;             <-     записываемое значение в первую очередь

                     ;             <-     попадает в буфер записи (store buffers)

STORE_BUFF    N_ITER ; ...         <-     один или несколько NOP

                     ; ...                параллельно с их выполнением содержимое

                     ; ...                буферов вытесняется в кэш первого (AMD)

                     ; ...                или второго (Intel) уровней

MOV    EDX,   [EBX]  ; b = *p;     <-     читаем содержимое ячейки *p

                     ;                    если к этому моменту  соответствующий ей

                     ;                    буфер еще не вытеснен, то она причтется

                     ;                    максимально  быстро; в  противном  же

                     ;                    случае возникнет задержка

ADD    EBX,   32     ; (int)p+32;  <-     смещаем указатель на след. буфер

Листинг 16 [Cache/store_buf_nop.xm] Ядро программы, демонстрирующей выгрузку буферов во время простоя шины

Результаты прогонов программы на процессорах P-III и AMD Athlon представлены на диаграмме graph 0x013. Наше обсуждение мы начнем с характера кривой зависимости времени загрузки данных от количества команд записи. Кривая P-III изображена жирной линией, выделенной синим цветом. Смотрите, – после семи команд записи время загрузки данных без всяких видимых причин возрастает с ~35 до ~150 тактов, т.е.


в четыре с небольшим раза. Это говорит о том, что первая из записанных ячеек уже покинула буфер и "отлетела" в кэш второго уровня. Она сделала это несмотря на то, что свободные буфера еще не были исчерпаны! Тем самым, мы убедительно доказали, что буфера могут выгружаться и самопроизвольно, а не только при переполнении их. Приняв за время выполнения операции записи один такт, мы сможем оценить приблизительное время выгрузки содержимого перового из буферов. Оно, как нетрудно установить составляет 7±1 тактов.

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

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

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

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


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

Рассмотрим теперь как реализован механизм буферизации записи в процессоре AMD Athlon (коричневая кривая). Сразу же бросается в глаза, что за счет выгрузки содержимого буферов в кэш первого, а не второго (как на P-II/P-III) уровня, Athlon не имеет проблем с обвальным падением производительности. За счет этого сокращено и время выгрузки буферов. Причем, Athlon, судя по всему, не выгружает буфера вплоть до тех пор, пока в этом не возникнет несущей необходимости.

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

Рисунок 37 graph 0x013 Демонстрация выгрузки буферов записи

Вредный совет 1 Используйте табличные вычисления вместо расчетов

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

Рассмотрим пример с вычислением синуса угла. Пусть нам необходимо знать его с точностью до одной угловой минуты, тогда в худшем случае таблица займет: 90*60*sizeof(float) = 21.6 Kb, что совсем немного даже по понятиям восьмидесятых. Используя же простейшие алгоритмы интерполяции мы, не сильно проиграв в производительности и точности, уменьшим этот размер минимум раза в два, а то и в четыре. А теперь вспомним, что вы

не выполнять вычисления каждый раз

 "на лету

Вредные советы и

Временные диаграммы чтения/записи

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

Цикл чтения начинается со сброса сигнала CS

(Chip Select – Выбор Чипа) в низкое состояние, давая понять тем самым микросхеме, что чип "выбран" и сейчас с ним будут работать (и работать будут, и прорабатывать!). К тому моменту, когда сигнал стабилизируется, на адресных линиях должен находиться готовый к употреблению адрес ячейки (т.е. номер строки и номер столбца), а сигнал WE должен быть переведен в высокое состояние (соответствующее операции чтения ячейки). Уровень сигнала OE (Output Enable – разрешение вывода) не играет никакой роли, т.к. на выходе пока ничего не содержится, точнее выходные линии находятся в, так называемом, высоко импедансом состоянии.

Спустя некоторое время (tAddress Access), определяемое быстродействием управляющей логики и быстротечностью переходных процессорах в инверторах, на линиях выхода появляются долгожданные данные, которые вплоть до окончания рабочего цикла (tCycle) могут быть непосредственно считаны. Обычно время доступа к ячейке статической памяти не превышает 1 – 2 нс., а зачастую бывает и меньше того!

Цикл записи происходит в обратном порядке. Сначала мы выставляем на шину адрес записываемой ячейки и одновременно с этим сбрасываем сигнал WE в низкое состояние. Затем, дождавшись, когда наш адрес декодируется, усилиться и поступит на соответствующие битовые линии, сбрасываем CS в низкий уровень, приказывая микросхеме подать сигнал высокого уровня на требуемую линию row. Защелка, удерживающая триггер, откроется и в зависимости от состоянии bit-линии, триггер переключится в то или иное состояние.

Рисунок 8 0х008 Временные диаграммы чтения/записи асинхронной статической памяти

в крошечную керамическую пластинку, свободно

Миллиарды битовых ячеек, упакованных в крошечную керамическую пластинку, свободно умещающуюся на ладони... Сегодня, когда счет оперативной памяти пошел на сотни мегабайт, мы – программисты – наконец-то избавились от "удовольствия" оптимизации своих программ по скорости и размеру одновременно. Пусть будет нужен хоть гигабайт – система выделит его за счет жесткого диска!
Правда, производительность подсистемы памяти все еще оставляет желать лучшего. Причем, современная ситуация даже хуже, чем была десять-пятнадцать лет тому назад. Если персональные компьютеры конца восьмидесятых – начала девяностых оснащались микропроцессорами с тактовой частотой порядка 10MHz и оперативной памятью со временем доступа в ~200 нс., типичная конфигурация ПК ближайшего будущего: 1.000 – 2.000 MHz и 20 ns. Нетрудно подсчитать, что соотношение производительности памяти и процессора уменьшилось более чем в тысячу раз!
Несмотря на стремительный рост пропускной способности оперативной памяти, наблюдающийся в последние годы, разрыв "CPU vs Memory" растет с чудовищной быстротой. Забавно, но с этой ситуаций мы сталкиваемся отнюдь не впервые: приблизительно сорок-пятьдесят лет тому назад, – в эпоху "больших" машин с быстродействующими (по тем временам!) процессорами и жутко медленной барабанной (а позже и ферритовой) памятью, – соотношение быстродействие памяти и процессора было приблизительно тем же самым.
Интересно, как же конструкторы ЭВМ выходили из этой ситуации? Откроем, например, "Структуры ЭВМ и их математическое обеспечение" Л. Н. Королева: "Для того чтобы достичь необходимого баланса между высокой скоростью выполнения арифметических и логических действий в центральном процессоре и ограниченным быстродействием блоков оперативного ферритового запоминающего устройства (время цикла работы каждого блока - 2 мксек.), были предприняты следующие меры.
Оперативное запоминающее устройство состоит из восьми блоков, допускающих одновременную выборку информации (командных слов и операндов), что резко повышает эффективное быстродействие системы памяти.
Подряд идущие физические адреса памяти относятся к разным блокам, и если оказалось, например, так, что последовательно выбираемые операнды имеют последовательно возрастающие (убывающие) адреса, то они могут выбираться со средней скоростью, равной 2 мксек/8=0,25 мксек...
Второй структурной особенностью организации обращений к оперативному запоминающему устройству является метод буферизации, или метод накопления очереди заказов к системе памяти. В машине БЭСМ-6 существуют группы регистров, на которых хранятся запросы (адреса), называемые буферами адресов слов и команд. Разумеется, что эти буфера могут работать эффективно только в том случае, если структура машины позволяет просматривать команды "вперед", т. е. загодя готовить запросы. Устройство управления БЭСМ-6 позволяет это делать. Буфера адресов позволяют в конечном итоге сгладить неравномерность поступления запросов к памяти и тем самым повысить эффективность ее использования.
Третьей структурной особенностью БЭСМ-6 является метод использования сверхоперативной, не адресуемой из программы памяти небольшого объема, цель которого – автоматическая экономия обращений к основному оперативному запоминающему устройству. Эта сверхоперативная память управляется таким образом, что часто используемые операнды и небольшие внутренние командные циклы оказываются на быстрых регистрах и готовы к немедленному использованию в арифметическом устройстве или в системе управления машиной. Быстрые регистры в ряде случаев позволяют экономить до 60% всех обращений к памяти и уменьшают тем самым временные затраты на ожидание чисел и команд из основной памяти.
Следует еще раз подчеркнуть, что об использовании быстрых регистров заботится аппаратура самой машины и при составлении программ об экономии обращений к памяти думать нет необходимости. [Выделение мое – КК]
Эти структурные особенности БЭСМ-6 получили название водопроводного [ныне "конвейерного" – КК] принципа построения структуры машины. В самом деле, если подсчитать время от начала выполнения команды до его окончания, то для каждой команды оно будет очень велико, однако глубокий параллелизм выполнения, просмотр вперед, наличие буфера адресов, быстрых регистров приводят к тому, что "поток" команд и темп обработки информации очень высок.


Аналогия с водопроводом состоит в том, что если проследить время, за которое частица воды проходит по некоторому участку водопровода, то оно будет большим, хотя скорость на выходе потока может быть очень велика.
Четвертой структурной особенностью БЭСМ-6, имеющей очень важное значение для построения операционных систем и работы машины в мультипрограммном режиме, является принятый аппаратный способ преобразования математических, или виртуальных адресов в физические адреса машины. В машине БЭСМ-6 четко выдержано деление на физическую и математическую память, принята постраничная организация, однако способ отображения, заложенный в аппаратуру, значительно отличается от того, который был применен в машине…".
Трудно отделаться от впечатления, что перед тобой лежит не перечень ключевых концепций архитектуры P6 (Pentium Pro, Pentium-II, Pentium-III…), а описание "морально устаревшей" электронно-вычислительной машины, ценящейся сегодня разве что за драг. мет. Ан нет! Еще может старушка нас чему-то научить! Мы гордимся современной аппаратурой и пренебрежительно относимся к достижениям двадцати-тридцати летней давности, между тем это ослиная гордость. Чтобы там ни говорила реклама, невозможно не признать, что за последнее время ничего принципиально нового не придумано. Эксплуатируется сравнительно небольшое количество весьма древних идей и, если что и совершенствуется, – так это проектные нормы. БЭСМ-6 занимала целый шкаф, а процессор Pentium свободно умещается на ладони. Но в нем нет ничего такого, что в том или ином виде ни присутствовало бы в "динозаврах" первых поколений.
Обратите внимание на выделенный жирным шрифтом абзац. Идеология сверхоперативной
(или "кэш", как принято сейчас говорить) памяти изначально позиционирует ее как прозрачную и не видимую для программиста. Так утверждали и конструкторы БЭСМ, так утверждают и создатели процессоров Pentium/Krypton. Между тем, это утверждение неверно. Эффективная работа с памятью всех иерархий без учета ее физических, конструктивных и архитектурных особенностей невозможна! Как минимум программист должен позаботиться о том, чтобы интенсивно используемые данные целиком уместились в кэш, а для достижения наивысшей производительности следует тщательно согласовать запросы к памяти с "характером" всех ее подсистем.
Проблемам такого согласования, собственно, и посвящена эта книга…

Вычисление полного времени доступа

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

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

·         контроллер шины, получив запрос, ставит его в очередь и, если контроллер памяти свободен, передает ему запрос с началом следующего такта;

·         в течение следующего такта контроллер памяти декодирует адрес и ставит его в свою внутреннею очередь запросов на чтение памяти;

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

                                                        I.      если соответствующая страница открыта и банк памяти не находится на регенерации, – чипсет выставляет сигнал CAS и передает сокращенный адрес ячейки. Спустя 2-3 такта частоты памяти на шине появляются первая порция считанных данных;

                                                      II.      контроллер памяти считывает ее за один такт;

§         синхронный контроллер памяти с началом следующего такта передает считанные данные контролеру шины и в дальнейшем пересылка осуществляется параллельно с чтением, но с задержкой в один такт;

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

§         примечание: Некоторые дешевые чипсеты, в частности VIA KT133/KT266, осуществляет передачу данных внутри чипсета только по фронту импульса, что полностью обесценивает все преимущества шины EV6, на которой работает Athlon, и ее эффективная часта (определяемая, как известно, самым узким местом системы) оказывается равной всего 100/133 MHz.

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

                                                   III.      на чтение "хвоста" пакета в зависимости от его длины уходит еще три или семь тактов частоты оперативной памяти;

                                                    IV.      если длина запроса превышает длину пакета, то мы возвращаемся к пункту I.



                                                      V.      контроллер шины, получив считанные данные, формирует запрос на передачу данных от чипсета к процессору и ставит его в очередь, на что расходуется один такт;

                                                    VI.      если в очереди не находится ничего другого, и шина никем не занята, контроллер шины извлекает запрос из очереди и "выстреливает" его в шину, передавая за один такт одну, две или четыре порции данных (на K6/P-II/P-III, Athlon и P-4 соответственно).

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

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



·         если требуемая DRAM- страница закрыта, но банк не находится на регенерации, контроллер памяти передает адрес строки, вырабатывает сигнал RAS, ждет 2 или 3 такта пока микросхема его "переварит", и переходит к сценарию I.

·         если же банк находится на регенерации, контролеру приходится подождать от одного до трех тактов пока она не будет завершена.

Конечно, это только приблизительная схема, не учитывающая конструктивные особенности отдельных наборов системных логик. Так, например, чипсеты от nVIDIA оснащены двумя независимыми контроллерами памяти, общающиеся со "своими" модулями памяти, в результате чего запросы от AGP-карты исполняются параллельно с запросами процессора, уменьшая тем самым латентность чипсета. Но самое интересное – Dynamic Adaptive Speculative pre-Processor /DASP/ (адаптивная система динамической упреждающей предвыборки), распознающая регулярные шаблоны обращения к памяти и заблаговременно осуществляющая предвыборку требуемых ячеек во внутренний буфер, расположенный где-то поблизости от контроллера шины (где именно – компания умалчивает, да это, собственно, и не важно).

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

Полный исходный текст читатель найдет в файле "Memory/speed.exactly.c", в книге же ради экономии места приведен лишь ее ключевой фрагмент. Рассмотрим его (см. листинг 1).

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

C = (N /* разрядность памяти, байт */ * BRST_LEN /* длина пакета, итер */) /

(



  2/FSB                                         /* арбитраж                       */

+ 1/FSB                                         /* передача адреса ячейки         */

+ 1/FSB                                         /* передача идентификатора транзакции    */

+ 1/FSB                                         /* латентность BIU                */

+ 1/FSB                                         /* декодирование MCT адреса ячейки */

+ 1/FSB                                         /* латентность MCT                */

+ Chipset_penalty/Fm                     /* пенальти на согласов. частот Mem/FSB*/

+ BRST_NUM*CAS_latency/Fm                /* CAS Delay                      */

+ (fSrl?BRST_LEN/Fm:1/Fm)                /* передача данных от DRAM к BUFF/BIU    */

+ Chipset_penalty/FSB                           /* пенальти на согласование частот */

+ (fMCT2BIUparallel?BRST_LEN/FSB:1/FSB)  /* передача данных от BUFF к BIU  */

+ 1/FSB                                         /* латентность BIU                */

+ (fImmediately?1/FSB:BRST_LEN/Ftransf)  /* передача данных от BIU к CPU   */

+ CPU_latency/Fcpu                       /* латентность СPU                */

+ X_CACHE*BRST_LEN/Fcpu                  /* передача данных от L2 к L1            */

+ CPU_penalty/Fcpu                       /* пенальти на согласов. частот CPU/FSB*/

+ RAS_latency/((LEN_page*K/(N*BRST_LEN))*Fm)    /* задержка на открытие страницы памяти*/

+ (fInterleaving?0:RAS_precharge/Fm)            /* задержка на перезарядку банка  */

);

Листинг 1 [Memory/speed.exactly.c] Фрагмент программы измерения реальной пропускной способности памяти с учетом латентности чипсета и CPU

Сразу видно, что величина RAS to CAS Delay при последовательном доступе к ячейками на производительность практически не влияет и ей можно пренебречь. Время перезарядки банка (RAS Precharge) за счет чередования банков и вовсе маскируется, поэтому, при последовательном доступе не играет никакой роли.

Величина CAS Delay, будучи много меньше общей латентности чипсета, очень незначительно влияет на производительность системы, особенно на AMD Athlon, где одним CAS Delay считывается восемь порций данных из памяти (на P-II/P-III лишь четыре).

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

и частота передачи данных по системной шине

(при условии, что внутри чипсета данные перемещаются с не меньшей скоростью, – в противном случае частота системной шины утрачивает свою определяющую роль).

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

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

Компиляторы Microsoft Visual C++ и WATCOM всегда выполняют свертку констант в границах одной функции, а вот передачу аргументов они отслеживать не умеют и на с

func(int a, int b)

{

return a+b;

}

main()

{

printf("%x\n",func(0x666,0x777));

}

Несмотря на его тривиальность, предвычислить значение функции func не сможет ни Microsoft C++, ни Borland C++, ни WATCOM!

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

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

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

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

Логично: если все члены выражения (подвыражения) – константные переменные, то и значение выражения – тоже константа.

Например:

int a=0x666;

int b=0x777;

int c=b-a;

printf("%x\n", c);

c=a+b;

printf("%x\n", c);

Значение переменной 'c' инвариантно относительно входных данных программы и его можно вычислить еще на этапе трансляции, удалив переменные 'a' и 'b', и заменив 'c' ее фактическим значением. В результате всех преобразований оптимизированный код программы будет выглядеть так:

printf("%x\n", 0x111);

printf("%x\n", 0xDDD);

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

Компиляторы Microsoft Visual C++ и WATCOM всегда выполняют свертку констант, а вот Borland  C++ этого делать не умеет.

Выделение

"Горячая" клавиша <F8> включает режим выделения текста, что равносильно удержанию <Shift>. Повторное нажатие на <F8> выключает режим выделения. Удобно при выделении больших блоков текста, - не затекает палец, ранее удерживающий <Shift>.

Еще интереснее комбинация <Shift-Ctrl-F8>, позволяющая выделять вертикальные блоки текста, что позволяет, в частности, одним махом удалить вертикальную строку комментариев.

Выход из кэша первого уровня

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

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

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

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

Легче всего понять это обстоятельство на примере кэша прямого отображения. Вообразим себе такой полностью заполненный кэш. При обращении к следующей ячейке, кэш-котроллер загружает ее в кэш-строку под номером (cache_size+1) % cache_size == 1. Затем, при следующем проходе цикла, первая ячейка вновь идет в эту же самую строку (т. к. 1 % cache_size == 1), а вовсе не в самую "дневную" кэш-строку под "номером два". Да, строка "номер один" будет работать "вхолостую", но она не затронет всех остальных. Соответственно, если размер обрабатываемого блока превышает размер кэш-памяти на две строки, то количество "холостых" кэш-линеек будет равно двум. Наконец, при обработке блока данных, вдвое превышающего размер сверхоперативной памяти, кэш будет работать полностью вхолостую.

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

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

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



(Замечание: это правило не обходится без исключений, – см. Особенности кэш-подсистемы процессоров P-II и P-III).

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

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

Рисунок 19 graph 0x029 Зависимость скорости обработки от размера блока на CELERON?300A

Выход из кэша второго уровня (мнимый)

Придерживаясь самых общих рассуждений о природе кэша, попытаемся определить его размер по характеру изменения скоростного показателя с ростом размера обрабатываемого блока. Первое, что сразу бросается в глаза – внезапный скачек кривой удельной скорости записи при пересечении отметки в ~128 Кб. Синхронно с ней изменяется и кривая чтения, пускай ее излом и менее ярко выражен, но он все-таки есть. Выходит, размер кэша второго уровня составляет 128 Кб? Но это не согласуется с показаниями BIOS, которая оценивает его размер в 512 Кб, что в четверо больше! Нас надули?! Или кэш работает неправильно? Можно, например, предположить, что кэш состоит из нескольких микросхем статической памяти с различным временем доступа…

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

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

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

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

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

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

Выход из кэша второго уровня (настоящий)

Изменение скоростного показателя при выходе за границы кэша второго уровня описывается теми же самыми формулами, что и выход за границы кэша первого уровня, т.е. на участке от L2.CACHE.SIZE до L2.CACHE.SIZE+ L2.CACHE.SIZE*WAY кривая чтения "взлетает" с коэффициентом пропорциональности , где F.L2.CACHE – частота работы кэша, F.MEM – частота работы памяти, N.CACHE.BUS – разрядность шины кэша второго уровня, а N.MEM.BUS разрядности шины памяти.

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

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

Кривая записи ведет себя иначе. Если не предпринять

Выход за пределы кэша первого уровня

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

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

В частности, на AMDAthlon 1050 удельное время выполнения команд при выходе за пределы кэша уровня увеличивается по меньшей мере втрое (вспомним, что удельное время доступа к данным в аналогичной ситуации возрастает всего лишь на 10%, – см. рис. graph 2).

На P-III (за счет огромной ширины шины) падение быстродействия, к счастью, не столь значительно, но все-таки достигает добрых 25%, за просто так "съедая" четверть производительности. С другой стороны, размер кодового кэша составляет всего 32 Кб против 64 Кб AMD Athlon, – вот пойди разберись какой из них предпочтительнее.

Выход за пределы кэша второго уровня

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

Причем, падание производительности будет… нет, даже не обвальным, а по настоящему, без дураков, ошеломляющим – порядка тридцати (!) крат на AMD Athlon и шести –на P-III. Так никаких мегагерц процессора не хватит! Впрочем, с выходом исполняемого кода за границы кэша второго уровня приходится сталкиваться не так уж и часто, а если и приходится – практически всегда удается разбить его на несколько циклов меньшего размера, обрабатывающихся последовательно.

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

Рисунок 22 graph 04 Изменение удельного времени выполнения команд в зависимости от размера исполняемого кода

Вынесение инвариантного кода за пределы цикла

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

Рассмотрим следующий пример:

for(a=0;a<(b*2);a++)

printf("%x\n",a*(b/2));

Выражения (b*2) и (b/2) очевидно представляют собой инвариант, и оптимизированный код будет выглядеть так:

tmp_1=b*2;

tmp_2=b/2;

for(a=0;a<tmp_1;a++)

printf("%x\n",tmp_2+=tmp_2);

Это экономит одну операцию деления и две операции умножения на каждую итерацию, что очень и очень неплохо!

Компиляторы Microsoft Visual C++ и WATCOM успешно распознают инвариантный код и выносят его за пределы цикла, а вот Borland C++ увы, нет.

Выполнение алгебраических упрощений

Вычисление многих выражений можно существенно ускорить, если на этапе компиляции выполнить все возможные алгебраические упрощения. Очень показателен следующий пример, кстати, заимствованный из фирменного "хелпа" компилятора Microsoft Visual C++ (см. описание функции PreCreateWindows):

cs.y = ((cs.cy * 3) - cs.cy) / 2;

cs.x = ((cs.cx * 3) - cs.cx) / 2;

Если раскрыть скобки (помните школьный кур математики?), то получится буквально следующее:

cs.y = cs.cy;

cs.x = cs.cx;

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

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

Ни Microsoft Visual C++, ни Borland C++, ни WATCOM не избавятся от операций деления и умножения в выражении (a=2*b/2), хотя его избыточность очевидна.

Самый продвинутый в этом плане – Microsoft Visual C++ – сокращает лишь простейшие выражения наподобие (a=3*b-b) или (a=b-b). А компиляторы Borland C++ и WATCOM могут похвастаться только тем, что автоматически вычисляют результат умножения (деления) на нуль или единицу. Т.е. следующий код "a=b*0; c=d/1" после оптимизации будет выглядеть так: "a=0; c=d".

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

Заметим, что сказанное не имеет никакого отношения к константным выражениям вроде (2*3+4/2) – их "сворачивают" все три рассматриваемых компилятора.

Выполнение кода в стеке

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

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

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

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

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

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

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

Выравнивание данных

В силу конструктивных ограничений пакетный цикл обмена с памятью не может начинаться с произвольного адреса. В зависимости от типа процессора он автоматически выравнивается по границе 32-, 64- и 128байт на K6/P-II/P-III, Athlon и P-4 соответственно. (см. "Отображение физических DRAM-адресов на логические").

Задумаемся, что произойдет, если на P-III мы запросим двойное слово, лежащее по адресу, равному, ну скажем, 30? Правильно! Для его чтения потребуется выполнить два пакетных цикла! В первом цикле будут загружены ячейки из интервала [(30 % 32); (30 % 32) + 32), т.е. [0; 32), в который входит лишь половина запрошенного нами двойного слова. Для чтения другой его половины потребуется совершить еще один цикл, – [32; 64). В результате, – время доступа к ячейке возрастет как минимум вдвое.

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

Подавляющее большинство руководств по оптимизации (равно как и техническая документация от производителей процессоров) настоятельно рекомендуют всегда выравнивать данные независимо то того, по каким адресам они лежат. На самом же деле, если запрошенные данные целиком умещаются в один пакетный цикл, то величина выравнивания не играет никакой роли! Чтение двойного слова, начинающегося с адреса 0x40001, осуществляется безо всяких задержек (no penalty!), поскольку оно гарантированно не пересекает пакетный цикл. Действительно, 0x20 – (0x40001 % 0x20) == 0x1F, а 0x1F > sizeof(DWORD) /* в смысле расстояние до правой границы пакетного цикла превышает размер читаемых данных */! Следовательно, чтение двойного слова с адреса 0х40001 вполне законно, хотя он (адрес) отнюдь и не кратен 4.

Подробный разговор о проблемах выравнивания мы отложим на потом (см. "Кэш. Выравнивание данных"), поскольку он больше относится к кэшу, чем к подсистеме оперативной памяти, здесь же мы рассмотрим лишь влияние начального адреса на скорость обработки больших блоков памяти (см. [Memory/align.c]).

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

На самом деле, некоторая разница все же есть. При чтении данных, пересекающих пакетный цикл, процессор вынужден тратить по крайней мере один такт, на склеивание двух половинок данных, что несколько ухудшит производительность. Впрочем, ненамного: на ~10% на P-III, и на ~20 на AMD Athlon (см. рис. graph 34). В подавляющем большинстве случаев этой величиной можно безболезненно пренебречь. Тем нее менее, если вы хотите достичь максимальной производительности, соответствующим образов выравнивайте адреса (см. таблицу 2 ниже).

Размер данных	Граница
1 байтов (8 битов)	Произвольная
2 байтов (16 битов)	Кратная 2 байтам
4 байтов (32 бита)	Кратная 4 байтам
8 байтов (64 битов)	Кратная 8 байтам
10 байтов (80 битов)	Кратная 16 байтам
16 байтов (128 битов)	Кратная 16 байтам

Таблица 2 Рекомендуемая степень выравнивания для различных типов данных

Совершенно иная ситуация с записью данных. Механизм отложенной записи, реализованный в процессорах Pentium и AMD Athlon, предотвращает падание производительности вызванное несовпадением размером записываемых данных с границами пакетных циклов. На P?III запись не выровненных данных выполняется всего лишь на 3% медленнее, а на AMD Athlon даже на 35% быстрее! Нет, это не ошибка! В силу конструктивных особенностей процессора Athlon и северного моста чипсета VIA KT133, запись не выровненных данных действительно осуществляется значительно быстрее.



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

при обработке огромных блоков памяти (от 1 Mб и выше), многократно превосходящих в объеме емкость кэшей всех уровней.



Рисунок 35 graph 026 Эффективность выравнивания начального адреса при обработке больших массивов данных. Не выровненный начальный адрес читаемого потока памяти несет ~15% издержки производительности. Записывание данных, напротив, не требует выравнивания, а на AMD Athlon не выровненные данные обрабатываются даже быстрее

В заключении рассмотрим какое влияние на производительность оказывает выбор адресов источника и приемника при копировании больших блоков памяти (см. [memory/align.memcpy]. Как нетрудно догадаться, выравнивание адреса-приемника не имеет решающего значения, а вот неудачный выбор адреса-источника заметно снижает быстродействие программы. И это действительно так! (см. рис. graph 27).



Рисунок 36 graph 27 Влияние на производительность выравнивания адресов источника и приемника при копировании памяти. Главное – выровнять источник. Выравниванием же начального адреса приемника можно пренебречь

Техника ручного выравнивания данных

Штанных средств выравнивания данных (подробнее см. "Кэш. Выравнивание") очень часто оказывается недостаточно. Во-первых, они действуют только на элементы структур, а локальные и глобальные переменные компилятор всегда выравнивает по собственному усмотрению, и, во-вторых, максимально допустимая степень выравнивания обычно (читай у Microsoft Visual C++ и Borland C++) ограничена кратностью в 16 байт. Т.е. выровнять массив по границе кэш-линий (32 байта для P–III и 64 байта для Athlon) не удастся! /* ну почему же не удастся? еще как удастся – см. "Кеш.


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

Однако для решения этой задачи вполне достаточно штатных средств языка Си. Поскольку, 32-битные near-указатели представляют собой по сути 32-битные целые, – весь математический аппарат к услугам программиста. Фактически решение задачи сводится к следующему: есть число X, из него надо получить число Y, максимально близкое к X и кратное N. Первое, что приходит на ум: Y = (X / N)*N. Если N не любое число, а кратное степени двойки, то от медленной операции деления можно отказаться, вручную сбрасывая соответствующий двоичный разряд с помощью логического AND. Так же, будет необходимо увеличить "усеченный" указатель на величину, равную степени выравнивания, т.к. при выравнивании происходит уменьшение указателя, в результате чего он залезает в чужую область. Естественно, количество выделяемой памяти придется увеличить на величину округления. Таким образом, законченное решение будет выглядеть приблизительно так:

char p;

p = (char*) malloc(need_size + (align_powr – 1));

p = (char *) (((int)p + align_power – 1) & ~(align_power - 1));

где align_power – требуемая степень выравнивания, а "char*" – тип указателя (естественно, не обязательно именно char* – это может быть и int*)

Тот же трюк может использоваться и при выравнивании массивов, расположенных в стеке или сегменте данных. Например:

#define array_size 1024

#define align_power 64

int a[array_size + align_power –1];

int *p;

p = (int *) (((int)&a + align_power – 1) & ~(align_power-1));

Указатель 'p' будет указывать на начало массива, выровненного по 64-байтной границе (такое выравнивание обеспечивает наиболее эффективную обработку данных – см. "Кэш.


Использование упреждающего чтения").

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

char array[9];

#define a array[0]

#define b (int *array[sizeof(char)])[0]

#define c (int *array[sizeof(char)+sizeof(int)])[0]

#define d (int *array[sizeof(int)*3])[0]

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

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

int sum(int *array, int n)

{

      int a, x = 0;

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

            x+=array[a];

      return x;

}

Листинг 24 Не оптимизированный пример реализации функции. *array может быть не выровнен!

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

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


Легко доказать, что если (x & 3) != 0, то и ((x + sizeof(int)*k) & 3) != 0. Действительно, это так, но… в том-то и все и дело, что штрафные такты за доступ по не выровненным данным даются лишь в том, и только в том случае когда они пересекают границы пакетных циклов обмена. А вот на этом можно и сыграть!

Читаем память двойными словами до тех пор, пока текущий адрес (((p % BRST_LEN) + sizeof(DWORD)) < BRST_LEN), – т.е. пока мы не дойдем до двойного слова, пересекающего границы пакетных циклов обмена. "Опасный" участок трассы проходим маленькими – побайтовыми – шажками, что гарантированно страхует нас от почетной "награды" в виде пенальти. Остается лишь собрать эти четыре байта в одно слово, что элементарно осуществляется битовыми операции сдвига. Затем описанный цикл чтения вновь повторяется (см. рис. 45). И так происходит до тех пор, пока не будет достигнут конец обрабатываемого блока памяти.



Рисунок 37 45 Техника эффективной обработки не выровненного двухсловного потока данных

Одна из возможных реализаций предложенного алгоритма показана ниже. Обратите внимание: общих решений поставленная задача не имеет. Максимальное количество двойных слов в типичном пакете всего восемь, а при работе с не выровненными адресами и того меньше! Цикл из нескольких интеракций – крайне медленная штука и во избежание падения производительности он должен быть развернут целиком. В этом-то и заключается основная проблема: поскольку количество итераций зависит от величины смещения указателя в пакетном цикле обмена, нам необходимо создать BRST_LEN – BRST_LEN/sizeof(DWORD) различных циклов, каждый из которых будет обрабатывать "свое" смещение указателя. Для экономии места в книге ### приведен лишь один вариант, поскольку остальные реализуются практически аналогично.

// -[Посечет суммы массива]----------------------------------------------------

//

//     ARG:

//            array  - указатель на массив



//            n             - кол-во элементов для сортировки

//

// README:

//            Функция справляется с не выровненными массивами, и сама выравнивает их

//     (правда, было бы лучше, если бы она это не делала)

//----------------------------------------------------------------------------

int sum_align(int *array, int n)

{

       int a, x = 0;

       char supra_bytes[4];

              // внимание: это решения для _частного_ случая

              // когда array & 15== 1, т.е. попросту говоря,

              // указатель смещен на 1 байт вправо относительно

              // выровненного по границе 32 байт адреса

              // общее решение данной задачи без использования

              // циклов (циклы - снижают производительность)

              // невозможно!

              // единственный вариант - вручную создать свой

              // "обработчик" для каждой ситуации

              // всего их будет 32 - 32/4 = 24, что слишком

              // громоздко для книжного варианта

       if (((int)array & 15)!=1)

              ERROR("-ERR: Недопустимое выравнивание\n");

             

       for(a = 0; a < n; a += 8)

       {

              // копируем все двойные слова, которые

              // не пересекают границы пакетных циклов

              // обмена

              x+=array[a + 0];

              x+=array[a + 1];

              x+=array[a + 2];

              x+=array[a + 3];

              x+=array[a + 4];

              x+=array[a + 5];

              x+=array[a + 6];

             

              // двойное слово, пересекающие пакетный цикл

              // копируем во временный буфер по б а й т а м

              supra_bytes[0]=*((char *) array + (a+7)*sizeof(int) + 0);

              supra_bytes[1]=*((char *) array + (a+7)*sizeof(int) + 1);

              supra_bytes[2]=*((char *) array + (a+7)*sizeof(int) + 2);

              supra_bytes[3]=*((char *) array + (a+7)*sizeof(int) + 3);

             



              // извлекаем supra-байты и обрабатываем их как двойное слово

              x+=*(int *)supra_bytes;

       }

       return x;

}

Листинг 25 [Memory/align.dwstream.c] Пример реализации эффективной обработки не выровненного двухсловного потока данных

И вот тут нас ждет неожиданный и весьма неприятный сюрприз. "Оптимизированная" программа выполняется намного медленнее

первоначального варианта! На P?III 733/133/100/I815EP падение производительности составляет ~15%, а на AMD Athlon 1050/100/100/VIA KT133… аж ~130%!!! Ничего себе "оптимизация"! В чем же причина? Дело в том, что предотвращение пересечения пакетных циклов обмена достается нам дорогой ценой, а именно – увеличением количества обращений к памяти. Это-то и снижает производительность!

Тем не менее, автор отнюдь не собирается выбрасывать предложенный алгоритм на помойку. Тут еще есть над чем подумать! "А почему бы нам ни подумать вместе?" (с) Котенок Гав.



Рисунок 38 graph 34 Описанная методика "эффективной" обработки не выровненного двухсловного потока данных, на самом деле снижает производительность. Самое интересное, что не выровненный поток на AMD Athlon обрабатывается даже быстрее, чем выровненный!

Выравнивание байтовых потоков данных.

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

Поскольку байтовый поток однороден мы можем начать читать его с любого места. Вычисляем адрес ближайшей границы пакетного цикла (в общем случае он равен p + (BRST_LEN ? ((int) p % BRST_LEN))) и гоним двойными словами в полную силу, не забывая, конечно, о том, что размер блока не всегда бывает кратен sizeof(DWORD).


Постойте! А как же первые (BRST_LEN ? ((int) p % BRST_LEN)) байтов?! Ведь они остались необработанными! Что ж, добавить дополнительный цикл обработки – не проблема! (см. рис. 46)



Рисунок 39 46 Техника выравнивания байтовых потоков данных. В отличии от выравнивая двухсловных потоков, она действительно эффективна

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

// -[Simple byte-crypt]-------------------------------------------------------

//

//     ARG:

//            src           - указатель на шифруемый блок

//            mask   - маска шифрования (байт)

//

//     DEPENCE:

//            unalign_crypt

//

//     README:

//            функция самостоятельно выравнивает шифруемые данные

//----------------------------------------------------------------------------

void align_crypt(char *src, int n, int mask)

{

       int a;

       char *x;

       int n_ualign;

      

       // вычисляем величину на которую следует "догнать" блок

       // чтобы он стал выровненным блоком

       n_ualign= 32 - ((int) src & 15);

       // шифруем пока не достигнем границы пакетного цикла обмена

       unalign_crypt(src, n_ualign, mask);

       // смело шифруем все остальное

       // т.к. src+n_ualign - гарантированно выровненный указатель!

       unalign_crypt(src+n_ualign, n-n_ualign, mask);

       /* не забываем уменьшить   ^^^^^^^^^^^^ ко-во шифруемых байтов */

}

Листинг 26 [Memory/align.bstream.c] Пример реализации функции, самостоятельно выравнивающий байтовый поток данных

Прогон программы показывает, что оптимизированный вариант с одинаковой эффективностью обрабатывает как выровненные так и не выровненные блоки данных, в то время как не оптимизированный теряет на не выровненных блоках от ~17% до 69% производительности (на P-III 733/133/100/I815EP и AMD Athlon 1050/100/100/VIA KT 133 соответственно).

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



Рисунок 40 graph 35 Демонстрация эффективности выравнивания байтовых потоков данных. Легко видеть, что предложенная техника выравнивания на 100% эффективна

Выравнивание команд

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

Исполняемые файлы лучше не паковать.

1) Исполняемые файлы лучше не паковать. В крайнем случае используйте для упаковки/распаковки функции операционной системы (LZInit, LZOpenFile, LZRead, LZSeek, LZClose, LZCopy) динамически распаковывая в специально выделенный буфер только те части файла, которые действительно нужны в данный момент для работы.
2) Динамические библиотеки вообще не следует паковать, ибо это ведет к чудовищному расходу и физической, и виртуальной памяти и извращает саму концепцию DLL – один модуль – всем процессам.
3) Кстати, о динамических библиотеках: не стремитесь кромсать свое приложение на множество DLL – страницы исполняемого файла не требуют физической памяти до тех пор, пока к ним не происходит обращений. Поэтому – смело помещайте весь код программы в один файл.

Взаимодействие памяти и процессора

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

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

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

Независимо от размера читаемой ячейки (байт, слово, двойное слово) длина запроса всегда равна размеру линейки L2-кэша (подробнее об устройстве кэша мы поговорим в одноименной главе), что составляет 32 байта для процессоров K6/P-II/P-III, 64 байта – для AMD Athlon и 128 байт – для P-4. Такое решение значительно увеличивает производительность памяти при последовательном чтении ячеек, и практически не уменьшает ее при чтении ячеек вразброс, что и неудивительно, т.к.
латентность чипсета в несколько раз превышает реальное время передачи данных и им можно пренебречь.

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

Но, так или иначе, наш запрос оказывается у контроллера памяти (MCT – Memory Controller). В течение одного такта он декодирует полученный адрес в физический номер строки/столбца ячейки и передает его модулю памяти по сценарию, описанному в главе "Устройство и принципы функционирования оперативной памяти".

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


Таким образом, асинхронный контроллер, работающий с памятью SDRAM PC-133 на 100 MHz системной шине, проигрывает своему синхронному собрату, работающему на той же шине с памятью SDRAM PC-100.

Контроллер шины, получив от контроллера памяти уведомление о том, что запрошенные данные готовы, дожидается освобождения шины и передает их процессору в пакетном режиме. В зависимости от типа шины за один такт может передаваться от одной до четырех порций данных. Так, в процессорах K6, P-II и P-III осуществляется одна передача за такт, в процессоре Athlon – две, а в процессоре P-4 – четыре.

Все! С этого момент данные поступают в кэш и становятся доступными процессору.

>>>>> Врезка.

Большинство наборов системных логик состоит из двух микросхем – северного

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

<<<<< 

Рисунок 11 0х27 Устройство серверного моста чипсета Intel 815EP, содержащего (среди всего прочего) контроллер памяти



Рисунок 12 815ep_chipset_photo.jpg Внешний вид чипсета Intel 815EP



Рисунок 13 845-northbridge.jpg Этот же чипсет на материнской плате. Северный мост традиционно украшен радиатором

До сих пор мы рассматривали и шинный контроллер, и контроллер памяти как черные ящики. Сейчас же настало время снять с них крышку и изучить их внутренности. Дабы автора не объявили в излишней любви к Intel, сделаем это на примере чипсета AMD 750, попутно отметив, что по качеству документации собственных чипсетов AMD значительно превосходит своих конкурентов.

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



(Processor Source Synch Clock Transceiver), планировщика запросов (command queue CQ), контроллера очередей запросов (control system  queue CSQ) и агента транзакций (transaction combiner agent XCA). Остальные компоненты контроллера шины, присутствующие на рис. 0х28 необходимы для поддержки зондовой отладки, которая к обсуждаемой теме не относится, а потому здесь не рассматривается.

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

Ответы агентов сохраняются в трех раздельных очередях: очереди чтения (SysDC Read Queue SRQ), очереди записи памяти (Memory Write Queue) и очереди записи шины PCI (PCI/A-PCI Write Queue AWQ). Обратите внимание: в данном случае речь идет о записи/чтении в процессор, а не наоборот! Т.е. очередь записи памяти хранит данные, передаваемые из памяти в процессор, но не записываемые процессором в память!

Агент транзакций (transaction combiner agent XCA) извлекает содержимое очередей и преобразует их в командные пакеты, которые передаются трансферу данных для отправки в процессор. Если же все очереди пусты, процессору передается команда NOP.

Планировщик запросов памяти (Memory Request Organizer MRO) принимает заказы на чтение/запись памяти сразу от трех устройств: контроллера шины, шины PCI и порта AGP, и стремиться обслужить каждого из своих клиентов максимально эффективно, что совсем не просто (память-то одна!).

Арбитр очереди памяти (Memory Queue Arbiter MQA) помещает всех клиентов в кольцевую очередь (round-robin RBN) и обрабатывает по одной транзакции за такт, в дополнение к этому преобразуя физический адрес ячейки в тройку чисел: банк DRAM, номер строки и колонки. Обработанные транзакции помещаются в одну из нескольких очередей. В чипсете AMD 760 их пять – четыре очереди по четыре элемента на чтение (MRQ0 – MRQ3) и одна на шесть элементов (MWQ) – на запись.


В данном случае под "чтением" имеется в виду чтение из памяти, а под "записью", соответственно, запись в память.

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

Контроллер памяти (Memory Controller MCT) отвечает за физическую поддержку модулей оперативной памяти, установленных на компьютере (в чипсете AMD 760 этим занимается SDRAM Memory Controller – SMC, более поздние чипсеты умеют работать с DDR и Rambus-памятью). Он же отвечает за инициализацию, регенерацию микросхем памяти и ее конфигурирование – установку задержек RAS to CAS Delay, CAS Delay, RAS Precharge, выбор рабочей тактовой частоты и др.

Арбитр запросов к памяти (Memory Request Arbiter MRA) – принимает запросы на чтение/запись памяти, поступающие от MRO и AGP, и передает их SMC. Передача одного запроса занимает один такт.

Данные, записываемые в память, извлекаются из очереди SRQ контроллера системной шины, а данные, читаемые из памяти отправляются в очередь MWQ, откуда они в последствии передаются процессору.



Рисунок 14 0x28 Устройство механизма взаимодействия с памятью в чипсете AMD 750

Взятие остатка

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

Таким образом, если делимое – беззнаковое число, то выражение (a % 2N) транслируется в конструкцию: (AND a, 2n-1N), в противном случае трансляция становится неоднозначна – компилятор может вставлять явную проверку на равенство нулю с ветвлением, а может использовать хитрые математические алгоритмы, самый популярный из которых выглядит так: DEC x\ OR x, -N\ INC x. Весь фокус в том, что если первые N бит числа x равны нулю, то все биты результата кроме старшего, знакового бита, будут гарантированно равны одному, а (OR x, - N) принудительно установит в единицу и старший бит, т.е. получится значение, равное, –1. А (INC –1) даст ноль! Напротив, если хотя бы один из N младших битов равен одному, заема из старших битов не происходит и (INC x) возвращает значению первоначальный результат.

А можно ли вычислять остаток посредством умножения и битовых сдвигов? Теоретически возможно, но не для всех делителей. Делитель обязательно должен быть кратен , где k и t – некоторые целые числа. Тогда остаток будет можно вычислить по следующей формуле:

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

Заблуждение I За меня все оптимизирует мой компилятор!

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

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

ЗаблуждениеII Максимальная эффективность

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

Подробнее о сравнении качества машинной и ручной оптимизации см. "Часть III. Ассемблер vs Компилятор".

ЗаблуждениеIII Человек, в отличии

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

Тем не менее, современные процессоры с одной стороны достаточно умны и самостоятельно оптимизируют переданный им на выполнение код, а с другой – кода, оптимального для всех процессоров, все равно не существуют и архитектурные особенности процессоров P-II, P-4, AMD K6 и Athlon отличаются друг от друга столь разительно, что все позывы к ручной оптимизации гибнут прямо на корю.

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

ЗаблуждениеIV Процессоры семейства

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

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

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

Закладки

Visual Studio поддерживает два типа закладок. Одни перечисляются в диалоговом окне "Bookmark", доступном из меню "~Edit\Bookmarks…", а другие отмечаются голубым квадратиком слева от "заложенной" строки (см. рис.1). Причем первые и последние никак не связаны между собой – добавление закладки "голубого квадратика" не изменяет содержимого списка "Bookmark" и наоборот. Более того, управление закладками "голубых квадратиков" вообще не доступно из системы меню! (Правда, закладками можно управлять через панель инструментов "Edit", но по умолчанию она на экране не отображается). Чтобы установить такую закладку подведите курсор к соответствующей строке и нажмите "горячую" клавишу <Ctrl-F2>. Повторное нажатие удаляет закладку.

Для удаления всех закладок "голубых квадратиков" предусмотрена команда BookmarckClearAll, доступная через комбинацию клавиш <Shift-Ctrl-F2>. Закладки, назначенные через меню "Edit\Bookmarks…" (<Alt-F2>) при этом не удаляются.

Для быстрого поиска закладок можно воспользоваться как листанием вперед: клавиша <F2> перемещает курсор к следующей закладке (при этом курсор не обязательно должен находится на закладке), так и листанием назад: нажатие клавиш <Shift-F2> перемещают курсор к предыдущей закладке.

Кстати, при контекстном поиске подстроки можно автоматически помечать все, содержащие ее строки, "голубыми" закладками. Для этого в диалоговом окне "Find" (<Ctrl-F>) вместо "ОК" нажмите кнопку "Mark All". Повторный поиск не удаляет старых закладок, но добавляет к ним новые. Причем, удалить закладки, пользуясь одной лишь системой меню, невозможно! Но мы-то с вами уже знаем, что такие закладки удаляются либо нажатием <Ctrl-F2>, либо нажатием <Shift-Ctrl- F2>.

Секреты закладок на этом не заканчиваются. Если вас раздражает, что для добавления новой Bookmark–закладки необходимо выполнять целый ряд операций (нажимать <Alt-F2>, вводить имя закладки, искать кнопку "Add"…), – воспользуйтесь командой "BookmarkDrop(Epsilon)", делающий все это автоматически! По непонятным причинам, ей не соответствует никакая клавишная комбинация, поэтому ее приходится назначать самостоятельно.
Это можно сделать, например, так. В меню "Tools" выберите пункт "Customize", в открывшемся диалоговом окне перейдите к закладке "Keyboard" и в ниспадающем боксе "Category" выберите категорию "Edit". Теперь в окне "Commands" найдите команду "BookmarkDrop(Epsilon)", переместите курсор в окно "Press new shortcut key" и нажмите комбинацию клавиш, которой вам будет удобно выполнять эту команду. Если эта комбинация уже используется – в поле "Currently assigned" появится название ее владельца, в противном случае – "unassigned". Для подтверждения назначения новой клавишной комбинации нажмите кнопку "Assign".

Теперь при нажатии вашей "горячей" клавиши в "Bookmark" будут автоматически добавляться закладки, нумеруемые в прядке возрастания от нуля до девяти. Если возникнет необходимость установить закладку с каким-нибудь конкретным номером, воспользуйтесь командами "BoolmarkDrop1 (Brief)", "BoolmarkDrop2 (Brief)"… "BoolmarkDrop10 (Brief)". По умолчанию им так же не соответствует никакая клавишная комбинация, и вы должны назначить ее самостоятельно.

Очень полезна команда "BookmarkJumpToLast (Epsilon)", циклически пролистывающая Bookmark-закладки в порядке убывания их номеров. Ей, как и предыдущим командам, назначать "горячую" клавишу приходится самостоятельно.

Рисунок 1 0x001 Закладка "голубого квадратика"

Конечно же, это далеко не

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


Что же делать потребителям? Как не попасться на удочку? О! Это очень просто. Достаточно забыть два слова "вера" и "доказательство", оставив лишь "скептицизм". Не верьте ни в какие доказательства. При желании можно доказать, что Земля – плоская и держится на трех китах. Бизнесмен никогда не работает на благо клиента. За каждым его шагом стоит личная выгода (деньги – не обязательно, но выгода – наверняка).


Так какой же компилятор лучше всех? Пальму первенства по праву, безусловно, заслуживает Microsoft Visual C++. За ним, существенно отставая, идет WATCOM, а Borland C++ плетется в самом хвосте, показывая на удивление низкий результат – и за что только его оптимизирующим компилятором называют?
"А где же количественные тесты?" – спросит придирчивый читатель. Их нет в этой статье. Нет, потому что выигрыш, даваемый оптимизатором, очень сильно зависит от рода компилируемого кода и более чем на порядок варьируется от одной программы к другой.


Вердикт. Ассемблер жил, ассемблер жив, ассемблер будет жить. Наблюдаемое засилье высокоуровневых языков и визуальных средств разработки – явление временное. Это – затишье перед бурей. А буря грянет – можете не сомневаться. Не сегодня – завтра перед программистами встанут новые задачи, под чистую съедающие все вычислительные мощности и требующие еще. Главное – быть готовым к этому и вовремя предложить свои знания, умения и навыки, дождавшись момента острой нехватки ассемблерных специалистов. (Мимоходом: программисты, знающие практически забытый ныне Фортран, с руками отрываются на Запад, ибо там половина научных приложений написана на Фортране, но ныне их некому сопровождать – старые кадры уходят на пенсию, а новое поколение выбирает пепСи).
Если же вы органически не приемлите наживу и бизнес, – программируйте на ассемблере из спортивного интереса. Последние поколения Pentium'ов в этом отношении – просто клад и там, поверьте, есть чему поучиться!
Программируйте! Удачи вам и… побольше сложностей от жизни!

Замена циклов с предусловием на циклы с постусловием

Существуют три основных типа цикла: циклы с условием вначале

(см. рис. 2 слева), циклы с условием в конце

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

Рисунок 2 0х002 Логическое дерево цикла с условием вначале (слева) и условием в конец (справа).

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

Замена инкремента цикла на декремент

Поскольку, машинные инструкции декремента (уменьшения значения переменной) автоматически выбрасывают Zero-флаг при достижении нуля, сравнивать уменьшаемую переменную с нулем не требуется – это автоматически делает сам процессор. Отсюда: цикл for (a=10;a>0;a--)

транслируется в более компактный и быстродействующий код, нежели цикл for (a=0;a<10;a++).

Если аргумент цикла не используется в самом цикле, то компилятор Microsoft Visual C++ всегда транслирует его в цикл с декрементом. Например, пусть исходный код программы выглядел так:

for(a=0;a<10;a++)

printf("Hello, Sailor!\n");

Поскольку, переменная 'a' не используется в теле цикла, заголовок цикла можно безболезненно переписать так:

for(a=10;a>0;a--)

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

Замена переменных константными значениями ("размножение" констант)

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

int a=0x666;

if (b > a) b=a;

Поскольку, непосредственное сравнение (равно как и присвоение) двух переменных невозможно, переменную 'a' предпочтительнее заменить ее непосредственным значением (обратите внимание: попутно это экономит одну операцию пересылки):

int a=0x666;

if (b > 0x666) b=0x666;

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

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

Замена условных переходов арифметическими операциями

Суперконвейерные процессоры, коими как раз и являются все старшие представители серии Intel 80x86, крайне болезненно относятся к ветвлениям. При нормальном ходе исполнения программы в то время, покуда обрабатывается текущий код, блок упреждающей выборки успевает считать и декодировать следующую партию инструкций, не допуская простоя шины памяти. Ветвления же отправляют всю эту работу насмарку, очищая конвейер. А конвейер у поздних моделей микропроцессоров Pentium очень длинный и быстро его не заполнишь – на это может уйти не один десяток тактов процессора, в течение которых вся "кухня" будет простаивать. Нехорошо! Программа, критичная к производительности, должна содержать минимум ветвлений.

Сказать-то просто, – трудно сделать. Как, скажем, избавиться от ветвлений в следующем примере: "if (a>b) a=b"? Непосредственно ликвидировать условный переход невозможно, попытка переписать код так: "a =((a>b)?b:a)" ничего не даст – оператор "?" с точки зрения компилятора – точно такой же условный переход, как и "if". Но вот спустившись на уровень ассемблера, мы можем кое-что предпринять (увы, в данном случае обращение к языку ассемблера – вынужденное, да пусть простят меня те, кто с ним не в ладах):

SUB b, a

; Отнять от содержимого 'b' значение 'a', записав результат в 'b'

; Если a > b, то процессор установит флаг заема в единицу

SBB c, c

; Отнять от содержимого 'c' значение 'c' с учетом флага заема,

; записав результат обратно в 'c' ('c' – временная переменная)

; Если a <= b, то флаг заема сброшен, и 'c' будет равно 0,

; Если a > b, то флаг заема установлен и 'c' будет равно –1.

AND c, b

; Выполнить битовую операцию (c & b), записав результат в 'c'

; Если a <= b, то флаг заема равен нулю, 'c' равно 0,

; значит, с =(c & b) == 0, в противном случае: c == b - a

;

ADD a, c

; Выполнить сложение содержимого 'a' со значением 'c', записав

; результат в 'a'.

; Если a <= b, то c = 0 и a = a

; Если a > b, то c = b - a, и a = a + (b-a) == b

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

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

---

---