К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 32
Текст из файла (страница 32)
18) заметна ярко выраженная тенденция уменьшения времени прохождения списков пс мере приближения степени дробления к четырем. При этом быстродействие программы возрастает более чем в полтора раза (точнее — в 1,6 раза)! Дальнейшее увеличение степени дробления лишь ухудшает результат (правда, незначительно). Причина в том, что при параллельной обработке более чем четырех потоков данных происходят постоянные открытия/закрытия РВАМ-страниц, "съедаюших" тем самым весь выигрыш от параллелизма /подробнее см. разд. 7/ланирование потоков данных" этой главы). На АМ(3 А!)т(оп 1050/!00/100/Ч1А КТ133 ситуация совсем иная. Поскольку и сам процессор Аг)т!оп, и чипсет Ч1А КТ133 в первую очередь оптимизированы для работы с одним потоком данных, параллельная обработка расшепленных списков ошутимо снижает производительность.
Впрочем, расшепление одного списка на два все-таки дает незначительный выигрыш в производительности. Однако наиболее оптимальна стратегия расщепления отнюдь не на два, и даже не на четыре, а на шесть списков. Именно шесть списков обеспечивают наилучший компромисс при оптимизации программы сразу для нескольких типов процессоров. Рис. 2.18. Зависимость времени обработки данных от степени расщепления списков. Как видно, наилучшая стратегия заключается в шестикратном расщеплении списков. Это обеспечивает наилучший компромисс для обоих процессоров Оперативная память (49 Разумеется, описанный прием не ограничивается одними списками. Ничуть не менее эффективно расщепление двоичных деревьев и других структур данных, в том числе и не ссьглочных.
Быстрое добавление элементов Чтобы при добавлении нового элемента в конец списка не трассировать весь список целиком, сохраняйте в специальном поле ссылку на последний элемент списка. Это многократно увеличит произволительность программы, подчас больше, чем на один порядок (а то и на два-три). Подробнее об этом см. разд, Оптимизация строковых штатных С-фупкций" этой главы. Какое отношение имеют строки к спискам? Да самое непосредственное! Ведь строка это одна из разновидностей вырожденного списка, не сохраняюшего ссылку на следуюший элемент, а принудительно располагаюшая их в памяти так, чтобы они строго следовали один за другим. Уменьшение размера структур данных Пусть у нас имеется некоторая структура данных (для определенности возьмем список), содержашая фиксированное количество элементов.
Вопрос: имеет ли значение шаг чтения памяти при условии, что каждый элемент обрабатывается однократно? Поскольку минимальная порция обмена с памятью составляет, по меньшей мере, 32 байта, а размеры элементов списка зачастую много меньше этой величины, становится очевидным, что скорость обработки обратно пропорциональна шагу обработки. Действительно, при чтении памяти через байт (слово, двойное слово) к половине загруженных ячеек вообще не происходит обращения, а при чтении памяти через четыре байта (слова, двойных слова) реально задействуется лишь 25% ячеек, а остальные загружаются "вхолостую". Отсюда следует, что данные в палтяти следует располагать тпк плотно, кик это только возможно (см. также разд.:Выравнивание данных" этой главы и одноименный разд.
"Выравнивание данных" главы 3). Раздельные (зерага1е(О структуры данных Вернемся к списку. Классическое представление списка (рис. 2.19) — крайне не оптимально с точки зрения подсистемы памяти 1ВМ РС. Почему? Да ведь при трассировке списка (трассировка — операция прохождения по списку без обрагцения к данным [значениям] его элементов) процессор вынужден загружать все ячейки, а не только ссылки на следующие элементы. Если операция трассировки выполняется неоднократно, то потери производительности могут оказаться весьма значительными. Глава 2 Давайте реорганизуем нашу структуру данных: указатели на следующий элемент поместим в один массив, а содержимое элементов — в другой (рис.
2.20). Теперь при трассировке списка (и большинстве иных типовых операций с ним, как то: определения количества элементов, поиск последнего элемента, замыкание и размыкание списков) окажутся востребованными все загруженные ячейки и, следовательно, эффективность обработки возрастет. Рис. 2.19.
Устройство "классического" списка. При трассировке процессор вынужден загружать и ссылки, и значения, несмотря на то, что нас интересуют одни лишь ссылки Обратите внимание: как в этом случае изменяется обращение к элементам списка. Если доступ к "классическому" списку осуществляется приблизи- ТЕЛЬНО Так: 1сзс[в1вввпС[.пехС=ххх; 11зС[в1вввпС[.ча1=хххг ТО ПОСЛЕ ЕГО модернизации так: ву1[зс.пехс[в1вввпс[=хххг ву11зс.ча1[в1вввпс[=ххх.
Таким образом, квадратные скобки сместились на одно слово вправо! Это не создает никаких неудобств (ну разве что с непривычки), но способно запутать начинающих программистов, не имею[цих опыта работы с С. Рис. 2.20. Устройство оптимизированного списка. Теперь при трассировке процессор загружает лишь те ячейки, к которым происходит реальное обращение, что значительно увеличивает производительность системы В данном случае расщепление списка 1[зс в два раза сокращает объем памяти, загружаемой при его трассировке. И это еще не предел! Если количество элементов списка меньше полусотни тысяч (как чаще всего и бывает), Оперативная память разумно отказаться от 32-битных указателей и перейти на 16-битные индексы (рис.
2.21). Конечно, это не слишком-то продвинутый алгоритм, но его легко усовершенствовать! Выровняв все элементы в памяти по четным адресам, мы сможем задействовать младший бит указателя элемента под "производственные нужды". Скажем, если он равен нулю, то длина указателя 32 бит, а если единице, то лля представления адреса используется компактный 16- битный относительный указатель. Поскольку расстояние между соседними элементами списка, как правило, невелико, нет нужды постоянно обращаться к ним по полному адресу, что экономит 16 бит на каждый элемент. Рис. 2.21. Отводите указателям минимально возможное количество бит — зто значительно сократит объем занимаемой памяти Развивая мысль дальше, можно ввести поддержку ситуаций "следующий элемент находится непосредственно за концом текущего" или "следующий элемент находится в другом списке".
Конечная цель во всех этих случаях одна: вместо указателей с фиксированной разрядностью использовать указатели с "плавающей" разрядностью, занимающие минимально возможное количество бит. Совместное использование обоих этих приемов (разделения списка вкупе с усечением разрядности указателей) сокращает размер ссылочного массива в агхеог~аггпсг тгаг~тагхеогпгпбех пехг~ раэ, т. Е.
В даННОМ СЛуЧаŠ— В ЧЕтЫрЕ раза. Неплохо? А во сколько раз это повышает производительность? Давайте проверим! Рассмотрим следующую программу, реализуюшую "классический" и оптимизированный варианты списков и сравнивающую время их обработки (листинг 2.12). (Полный исходный текст программы читатель найдет в файле ~згсЯ21зпетпогу~1(зг.аерагагег(, который находится на прилагаемом компакт-диске.) обработка классического списка Глава 2 1пг всгцсс 1]вс *с1авяйс 11яс,*сыр 11вс3 // инициализация списка Тог [а = 03 а < Н ЕЬЕМ; а++3 [ с1авв1с 1гвС[а].пехс= с1авя1с 11яс + аь13 с1авв1с 11вг[а].ча1 = а3 ] с1авягс 11вС[Н ЕПЕМ-1].пехС=03 // трассировка списка Сюр 1гяг=с1аяьас 1гяг; нА11е[гшр 3.3.яС = Сшр 13.яг[0].пехг]; яггцсС шу11яг[ '/ ОПТИМИЗИРОВАННЫЙ РАЗДЕПЬНЬЙ СПИСОК яйогг 1пг *пехС3 // Массив указателей на следуюший узел 1пс *ча13 // Массив значений ясгцсс в1У1гяс верагасеб 11вся // инициализацмя списка Тот [а=бяа<Н еПЕМ/ат+] [ верагагеб 1юяС.пехг[а] = ат1я /* обратите внимание где находятся квадратные скобки */ верагагеб 11вг.ча1[а] = а; яерагагеб 11яе,пехг[Н ЕПЮ1-1]=бя // трассировка списка нц11е[ь=яерагасеб 11яс.пехс[ь]]; зггцсг 11вг[ вггпсг 1гвг // КЛАССИЧЕСКИЙ СПИСОК *пехс3 // указатель на следуюший узел ча13 // Значение обработка оптимизированного раздельного списка 153 Оперативная память Результаты ее работы должны быть приблизительно следуюшими (рис.
2.22). Рис. 2.22. Демонстрация эффективности обработки раздельных списков с указателями усеченной разрядности. Как видно, зто значительно сокращает время трассировки списков, причем трехкратный выигрыш производительности, достигнутый в данном случае, далеко не предел! И впрямь, оптимизированный вариант оказался намного быстрее! Правла, не в четыре раза — как ожидалось, — а всего лишь в три с половиной (обработка 1б-разрядных значений на современных процессорах неэффективна), но и этим результатом по праву можно гордиться! К тому же, если развернуть цикл и обрабатывать ссылки параллельно (си.
равд. "Параллельная обработка данньрг" евой главы), выигрыш будет егце большим! Сложные случаи и капризы раздельной оптимизации Хорошо, а если у нас имеется структура вида (листинг 2.13), включаюшая в себя тело не~оторого об~охта сьз ьсву и а~р~буты объекта сьз гьвь. Пусть тело объекта занимает несколько Кбайт, а его атрибуты — с полсотни байт. Допустим так же„что нам необходимо написать функцию, обрабатываюшую атрибуты всех объектов, но не трогаюшую тела этих самых объектов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
