К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 44
Текст из файла (страница 44)
"Обработка палити байтами, двойными и учетверенными словами" этой главы). Теперь самое время применить наши знания для оптимизации строковых функций, Типичная С-строка (рис. 2.49) представляет собой цепочку однобайтовых символов, завершаемую специальным символом конца строки — нулевым байтом (не путать с символом "0"1), поэтому С-строки также называют АБСПг.-стоками (г. — сокращение от "г.его").
Это крайне неоптимальная структура данных, особенно для современных 32-разрядных процессоров! Основной недостаток С-строк заключается в невозможности быстро определить их длину — для этого нам приходится сканировать всю строку целиком в поисках завершающего ее нуля. Причем, поиск завершающего символа должен осуществляться побайтовым сравнением каждого символа строки с нулем. А ведь производительность побайтового чтения памяти крайне низка! Конечно, можно попробовать сделать "ход конем": загружать ячейки памяти двойными словами, а затем "просвечивать" их сквозь четыре битовые маски, только вряд ли это добавит производительности — скорее всего лишь ухудшит ее. По тем же самым причинам невозможно реализовать эффективное копирование и объединение С-строк.
Действительно, как прикажете копировать строку, не зная какой она длины? В довершение ко всему, С-строки не могут содержать символа нуля (т. к. он будет ошибочно воспринят как завершитель строки) и потому плохо подходят для обработки двоичных данных. Всех этих недостатков лишены Разов!-строки, явно хранящие свою длину в специальном поле, расположенном в самом начале строки. Для вычисления длины Разса1-строки достаточно всего одного обращения к памяти (грубо говоря, длина Разса!-строк может быть вычислена мгновенно). Оперативная память 3) Ое1рнрстроки 4) МГС-строки Рис.
2.49. Устройство С-, Рааса)-, Ое(рнр и МЕС-строк. С-строки могут иметь неограниченную длину, но не могут содержать в себе символа нуля, т, к, он трактуется как завершнтель строки. Раяса)-строки хранят длину строки в специальном однобайтовом поле, что значительно увеличивает эффективность строковых функций, позволяет хранить в строках любые символы, но ограничивает их размер 256 байтами. Ое)рбрстроки представляют собой разновидность Раяса1- и МГС-строки — это гибрид С- и Рааса)-строк с 32-битным полем длины, благодаря чему максимальная длина строки теперь равна 64 Кбайт 4 Гбайт соотвественно Кстати, при работе с любыми структурами данных, в частности, со списками, настоятельно рекомендуется сохранять в специальном поле ссылку на послед- ний элемент, чтобы при добавлении новых элементов в конец списка не прихо- дилось каждый раз трассировать его целиком.
Как это обстоятельство может быть использовано для оптимизации копиро- вания и объединения Рааса)-строк? А вот смотрите два примера (листин- ги 2.38 и 2.39). (( ) ( ~~ф~~~~~-'рещ~ййацтйи;,фуйаккний.к9апироаании(СХс онат *раяоа1 ятгору(оьаг "бя, оЬат *кто) оЬат *о ятгору(оЬат *бяе, ооат яке) онат * ср = бяы нлт1е( 'орт+ *якотт )) О когнруен строку по байтан тот а; Гог(а=о; а < ((*его+1) а -З); а т= 4) *(ть *)(бама)=*(1от *)(агота)г Глава 2 220 гегшп( бзе ): гебчгп( бзт )( гвг 1еп) сбег *ср - бзб; гегптп( с)зг )) тегцгп( бзт )( // одновременно с этим проверяя // каждый символ на равенство нулю сйат с збгсат (сйаг *бзт, сйаг *зтс) нб11е( *ср ) ь< Р) // читаем в:зв серову-источник // байт за байтом в поисках приемника // зсг1пр Сепсппаб1оп сйагасбег иб11е( *срн.
= *ассы ) ( // бее за балтом дописываем // источник к концу приемника, О до тех пор пока не встретим ноль // копируем строку дежевве оясеаии // проверять кажный символ на равенство О и/лю в данном случае нет необходньюсти, // т.к. дпина строки известна наперед гог(а=((*згст1) ь -3)) а<(*его+1); а ++) *(сйаг *) (бес+а)=*(сйаг *) (его+а); // копируем остаток хвоста строки // (еспи он есть) по байтам.
// это не снижает производительности, // т.к. максимально воэьюжная длинна // хвоста составляет всего три байта сйаг *разса1 ззгсаз (сбег *баб, сваг *згс) 1еп=*бзтс // за одно обраввние к памяти // определяем длину строки приеьеика *бзт~ *згсс // коРректируем длину строки приемника разса1 затору(бзть1еп,згс)) // копируеы строку десеаает слсеает Оперативная память Итак, в отличие от С-строк, Рааса(-строки допускают эффективную блочную обработку и при желании могут копироваться хоть восьмерными словами. Другое немаловажное обстоятельство: при объединении Рааса)-строк нам незачем просматривать всю строку-приемник целиком в поисках ее конца, поскольку конец строки определяется алгебраическим сложением указателя на начало строки с первым байтом строки, содержащим ее длину.
Интенсивная работа с С-строками способна серьезно подорвать производительность программы и потому лучше совсем отказаться от их использования. Проблема в том, что мы не можем "самовольно" перейти на Рааса(- строки, не изменив все сопугствуюшие им библиотеки языка С и АР1- функций операционной системы. Ведь функции наподобие гьр или ьььагльть т рассчитаны исключительно на АЯСПУ.-строки и попытка "скормить" им Рааса)-строку ни к чему хорошему не приведет, — функция, не обнаружив в положенном месте символа-завершителя строки, залезет совершенно в постороннюю память! Выход состоит в создании "гибридных" Рааса! + АЯСПУ.-строк, явно хранящих длину строки в специально на то отведенном поле, но вместе с тем, имеюших завершающий нуль на конце строки.
Именно так и поступили разработчики класса свет ьд библиотеки МГС, распространяемой вместе с компилятором М!сговой 'т!зпа! С++. Несложный тест (см. исходный код программы ~згс\(2]зпетпоту~МГС.зтт.с, наоляшийся на прилагаемом компакт-диске) поможет нам сравнить эффективность обработки С- и МГС-строк на операциях сравнения, копирования и вычисления длины. На последней операции, собственно, и наблюдается наибольший разрыв в производительности, достигающий в зависимости от длины "подопытной" строки от одного до нескольких порядков. Объединение двух МГС-строк (при условии, что обе они одинаковой длины) осушествляется практически вдвое быстрее, чем аналогичных им С- строк, что совсем не удивительно, т.
к. в первом случае мы обращаемся к вдвое меньшему количеству ячеек памяти. Разумеется, если к концу очень длинной строки дописывается всего несколько символов, то выигрыш от использования МГС-строк окажется много большим и приблизительно составит: зтг!еп(бз!)/згг!еп(вгс) крат. А вот сравнение С- и МГС-строк происходит одинаково эффективно, точнее одинаково неэффективно, поскольку разработчики библиотеки МГС предпочли побайтовое сравнение сравнению двойными словами, что не самым лучшим образом сказалось на производительности.
Забавно, но штатная функция ь1 ар из комплекта поставки М!стоьой 'я!зпа! С++ (не яьтьяьте!), — похоже, единственная функция сравнения строк, обрабатывающая их не байтами, а двойными словами, что в среднем происходит вдвое быстрее. В обшем, наиболее предпочтительное сравнение МГС-строк выглядит так, как показано в примере (листинг 2.40) (см. также рис. 2.50). Глава 2 ггг Фьос1сбе <Зтсхоо.н> эртеле еоост|оо(зстсыр~ // вырубаем тосотоз1с'ы 1;,ст .р~ео.еесвоттет~оы е1.сесвсттет~оы ~ // строки не равны е1ее О отроки равны Рис. 2.50. Сравнение эффективности МРС- и С-функций, работающих со строками. Как видно, МРС-строки более производительны Сводная характеристика качества оптимизации штатных С-функций и функций ОС для работы со строками В таблице, приведенной далее (табл.
2.4), содержится краткая характеристика качества оптимизации штатных С-функций и функций операционной системы для работы со строками. Обратите внимание: ни операционная система, ни библиотеки распространенных компиляторов не являются полностью оптимальными и резерв для повышения быстродействия еще есть! 223 а Х Ф с ШФФ » а с >- с о» Ф ф ~ъ о3 $ ~ о О О е т- е в 'В О Ф З о. с с Ф с Ф »- ш а с» Я Ф Ф о. :'О (с Ф ::О й ::О Б Ф :асс» 'о м» »о с + о+ о» О ь »» »» и ФЗ о- х с Ф ! ш .; »- !)" у о Ф с с и > о с (О о ~ оО о И х Ф »» Ф о,: о ы Ф о о Ф Ф Ф с Ф с Ф Ф ы Ф Л о. о о Ф а» л Х $ О с а Ф с О Оперативная память а с О о н о 3 2 с о и О %% о $ о с Ф Я 4 Ф О Ф $Ч Ф с Ф с Л» Ф Ф И 1 а ! х Ф а о.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
