К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 41
Текст из файла (страница 41)
лежит в младших адресах), алгоритм копирования реализуется аналогично функции иеисру, поскольку ячейки памяти переносятся "назад" — в свободную неинициализированную область (рис. 2.42). Единственное условие — количество ячеек памяти, переносимых за одну итерацию, не должно превышать разницу адресов приемника и источника. Таким образом, если приемник расположен всего в двух байтах от источника, переносить память двойными словами уже не получится! Оперативная память 201 Рис. 2.42.
Копирование перекрывающихся блоков памяти. Если источник расположен "правее" приемника (верхний рисунок), то перенос ячеек памяти происходит без каких-либо проблем. Напротив, если источник расположен "левее" приемника(нижний рисунок), то перенос ячеек "вперед" приведет к затиранию источника (см. компакт-диск) Гораздо сложнее справиться с ситуацией, когда приемник расположен "правее" источника (т. е. лежит в старших адресах).
Попытка скопировать память слева направо приведет к краху, т, к, перенос ячеек будет осуществляться в уже "занятые" адреса с неизбежным затиранием их содержимого. Попросту говоря, функция ру в этом случае будет работать как г (см. рис. 2.42), что явно не входит в наши планы. Как же выйти из этой ситуацииу Обратившись к исходным текстам функции и е (в частности у М(сговой Ч(вца! С++ они расположены в каталоге ')М(сговой Чсша! Я(цб(о~ ЧС98~СКР,ЖС),гпепцпоче.с), мы обнаружим следующий подход (листинг 2.29). /* отег1арртпч Впетега сору Ггот Шдпег аббгеааеа Го 1онег аббгеааеа бзп - (сваг *)бае + сопле — 1) згс = )сваг *)агс + соопг — 1) нш1е (соопг — ) *)сваг *)баг = *(оьаг *)згс) бае = )сваг *)бзс — )и згс = (опаг *)агс - Ы гог Глава г Ага, память копируется "задом наперед", т.
е. справа налево. В таком случае затирания ячеек гарантированно не происходит, но за это приходится платить. Ведь, как мы уже знаем, подсистема памяти оптимизирована именно под прямое чтение„и попытка "погладить ее против шерсти" ничего хорошего в плане быстродействия не несет. Насколько сильно это снижает производительность? На этот вопрос нет универсального ответа. В зависимости от особенностей архитектуры используемого аппаратного обеспечения эта величина может колебаться в несколько раз. В частности, на 1пге! Р-1П/1п!е! 815ЕР обратное копирование памяти уступает прямому приблизительно в полтора раза.
А вот на АМР А!!1!оп/У!А КТ133 разница в скорости между прямым и обратным копированием составляет всего 2%, чем со спокойной совестью можно пренебречь. Тем не менее, компьютеры на основе Абйоп/КТ133 занимают значительно меньшую долю рынка, нежели системы на базе 1п1е! Реп!шш, поэтому не стоит закладываться на такую конфигурацию. При интенсивном использовании функции ее .сее общее снижение производительности может оказаться весьма значительным и неудивительно, если у разработчика возникнет жгучее желание ну хоть немного его поднять.
Это действительно возможно сделать, достаточно лишь копировать память не байтами и даже не двойными словами, а блоками с размером, равным разнице адресов приемника и источника. Если размер блока составит хотя бы пару килобайт, память будет копироваться в прямом направлении, хотя и "задом наперед". Как это можно реализовать на практике? Рассмотрим следующий пример, написанный на чистом С без применения ассемблера !листинг 2.30). Для повышения наглядности отсюда исключен вспомогательный код, обеспечивающий, в частности, обработку ошибок и выравнивание стартовых адресов с последующим переносом "хвоста" /си, разд.
сВыравнивание данных" этой главы). Шс иуиепИсчех~сьас *бее, свае *асс, 1ее а1ае~ ( свае *р1,*рго 1ае а,х-11 1ас бе1са1 бе1еа=а*С-аас1 11 Ыбе1еа<1Ы аеесса -1; Оперативная память кОЭ тот(а ахее:а>бе1та;а- бе1та~ вепсру(бес+а-бе1та,его+а-бе1та,бе1там хеевтп О; В сравнении со штатной в е данная функция работает на 20% быстрее (если разница адресов источника и приемника не превышает размер кэшпамяти первого уровня) и на 30% при перемещении блоков памяти на большое расстояние (рис.
2.43). Причем, это еще не предел, — переписав функцию муме мо ех на ассемблер, мы получим еще больший прирост производительности (см. также равд. "Параллельная обработка данных" этой главы и раэд. "Практическое использование предвыборки" главы 3). Рис. 2.43. "Четырехтактный" алгоритм прямого переноса памяти с использованием двух промежуточных буферов (см.
компакт-диск] Разумеется, если разница адресов источника и приемника невелика (менее килобайта), то "обмануть" систему не получится, и память будет копироваться скорее в обратном направлении, чем в прямом. При этом накладные расходы на организацию цикла поблочного копирования вызовут значительное снижение производительности, проигрывая штатной функции и сте в два и более раз.
Поэтому на область применения функции мум мб х наложены определенные ограничения. Хорошо, но ведь бывают же такие случаи, когда перекрывающиеся области необходимо копировать именно "вперед"? Допустим, у нас имеется поток данных, не поддерживающий позиционирование указателя или, скажем, весь блок памяти на момент начала копирования целиком еще недоступен. Вот вполне жизненный пример (из практики автора) — при перемещении 204 Глава 2 фрагментов изображения в графическом редакторе техническое задание (ТЗ) требовало выполнять обновление изображения от начала блока к концу. (Дабы пользователь мог приступать к работе с изображением, не дожидаясь, пока блок будет перемешен целиком.) Причем, использовать ссылочную организацию данных запрешалось.
(Кто сказал, что это глупость? Нет, это не глупость, это — техническое задание.) Тупик? Вовсе нет! Напротив,— возможность "поразмять" мозги (ну не все же время рисовать интерфейсы в Ч(зца! Бгц(((о). Первое, что приходит на ум, так это перенос памяти через промежуточный буфер. Вся идея реализуется тривиальным кодом (листинг 2.31). :фред) ' па пап (и "~Г Ъ пп)ппопепес(спас *Опс, спас *ппс, ьпс пыле) сьап *ппр; ппр=ппп11ос(В(.ОСК 512е)) апппсру(пппр, ппс выюк Бтае)( аепсрутпп, пппр, вьоск азат) Гуд? Да какой там гуд!И Во-первых, предложенный алгоритм удваивает количество потребляемой памяти, что в ряде случаев просто неприемлемо, вовторых, он в два раза увеличивает время копирования и, наконец, в-третьих, он не решает задачи, поставленной в ТЗ. Ведь обновление начала изображения начнется не сразу, а через довольно продолжительное время, в течение которого будет заполняться временный буфер, Так что не стоит этот алгоритм и обсуждать! Но, постойте, зачем нам копировать весь перемещаемый блок в промежуточный буфер целиком? Достаточно сохранить лишь ту его часть, которая затирается выступаю(цим влево "хвостом".
Следовательно, максимально разумный размер буфера равен апп — ппс. Рассмотрим упрошенный вариант алгоритма прямого перемещения памяти, использующий два таких буфера. Назовем его четырехтактным потоковым алгоритмом копирования памяти. Почему "четырехтактным" станет ясно далее. Г3 Такт первый: ру(всг т, опп, опп — с) — мы сохраняем память приемника, по- скольку этот фрагмент будет затерт в следующем такте (см. рис.
2.43). Оперативная память П Такт второй: 205 вевсру)авс, вес, свс — все) — мы копируем (свс все) байт из источника в приемник, не беспокоясь о затираемой памяти, т. к. она уже сохранена в буфере. 13 Такт третий: вевсру)вот г, свс + )свс — ), свс - ввс) — сохраняем следующую порцию данных приемника во втором промежуточном буфере.
!3 Такт четвертый: ве ру)свс+ )свс — в ), всг ), свс — ввс) — помещаем содержимое буфера В1)Г 1 на положенное место (оно только что было сохранено в В(3Г 2). Все! Первый буфер освобождается и можно смело переходить к первому такту, — "рабочий цикл" нашего "движка" завершен. Как нетрудно убедиться, копирование происходит только в прямом направлении, причем память приемника обновляется от начала к концу маленькими порциями по (свс — с) байт. При "мышином" перетаскивании областей изображений в графическом редакторе они, действительно, недалеко "уползают" за олин шаг; кстати, М)сготюй Ра!и) (графический редактор из штатной поставки %!пдо)чз) при перетаскивании изображений перемещает память именно при помощи функции веввсче, поэтому жутко 'тормозит' даже на Р-И1.
Причем, если разница адресов источника и приемника составляет порядка 4 — 8 Кбайт, то, несмотря на двойной перегон памяти к буферам и обратно, предложенный алгоритм даже обгоняет реализацию функции . сче на 10%, — во всяком случае на Р-И1 (рис. 2.44 — 2.46). А на АМР А!))1оп,%!А КТ133 разница достигает аж 1,7 крат (в пользу нашего алгоритма, естественно), впрочем, это отнюдь не показатель крутости алгоритма, — просто 'ч'1А КТ133 так уж устроен.
А теперь давайте подумаем: можно ли уменьшить количество буферов с двух до одного? Разумеется, да, — ведь на момент завершения второго такта регион ) с)с).., с)свс- с)) (на рис. 2.43 он расположен слева в верхнем ряду) уже свободен и может использоваться для временного хранения данных. Однако тут есть один подводный камень — если адреса "своих" временных буферов мы можем выбирать самостоятельно с учетом архитектуры и организации РВАМ, то адрес источника нам дается "извне" со всеми отсюда вытекающими...
Разумеется, ничего невозможно нет и при желании обойтись всего одним буфером при не сильно худшей эффективности — вполне возможно, но это значительно усложнит алгоритм и снизит его наглядность. А алгоритм, надобно сказать, и без того не слишком прозрачен (листинг 2.32). гО5 Глава 2 40000000 оамва сч о а (О СЪ Г ОЪ СЪ (Ч л в съ сч о о О(а г а о (ч о о С» СЧ Г (О ОЪ ( О СЧ (Ч чк. В (О СЪ (Ч $ (О СО ОЪ (Ъ В ( ОЪ СЪ а оав гсч в ягвввлаав О СЧ Чв В свао (О (О ф ('Ъ а о г СЧ съ (О (О Расстояние между Оа( и агс (байт) — «» — тле(ловче — с — Мумегомоче — — Муметмочех Рис. 2.44. Демонстрация эффективности различных алгоритмов переноса памяти Сравнение функций птеп(пточе и МуМеспМоче (увеличено,' 22000000 О 20000000 к ж18000000 о 16000000 о. о 14ОООООО ж 12000000 10000000 ас(вам асс(во гас«во гас(в очаг(в онаго(во гас« счиъг сосч (.г всчйвв чва аваоаваосчв~ Зсч г( с(с(сч(с(счаааачч Оввввввввллллаааа Расстояние между Оа( и агс (баит) — Π— нжвгяо ю — — МумегеМоче — е — Муметмочек Рио.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
