Оптимизация строковых штатных Си-функций
С разительным отличием скорости обработки двойных слов и байтов мы уже столкнулись (см. "Обработка памяти байтами, двойными и четвертными словами"). Теперь самое время применить наши знания для оптимизации строковых функций.
Типичная Си-строка (см. рис. 41) представляет собой цепочку однобайтовых символов, завершаемую специальным символом конца строки – нулевым байтом (не путать с символом "0"!), поэтому Си-строки так же называют ASCIIZ-стоками ('Z' – сокращение от "Zero", – нуль на конце). Это крайне неоптимальная структура данных, особенно для современных 32?разрядных процессоров!
Основной недостаток Си-строк заключается в невозможности быстро определить их длину, – для этого нам приходится сканировать всю строку целиком в поисках завершающего ее нуля. Причем, поиск завершающего символа должен осуществляется побайтовым сравнением каждого символа строки с нулем. А ведь производительность побайтового чтения памяти крайне низка! Конечно, можно попробовать сделать "ход котом": загружать ячейки памяти двойными словами, а затем "просвечивать" их сквозь четыре битовых маски, только вряд ли это добавит производительности, – скорее лишь сильнее ухудшит ее.
По тем же самым причинам невозможно реализовать эффективное копирование и объединение Си-строк. Действительно, как прикажете копировать строку не зная какой она длины?
В довершении ко всему, Си-строки не могут содержать символа нуля (т.к. он будет ошибочно воспринят как завершитель строки) и потому плохо подходят для обработки двоичных данных.
Всех этих недостатков лишены Pascal-строки, явно хранящие свою длину в специальном поле, расположенном в самом начале строки. Для вычисления длины Pascal-строки достаточно всего одного обращения к памяти (грубо говоря, длина Pascal-строк может быть вычислена мгновенно). /* Кстати, при работе с любыми структурами данных, в частности, со списками, настоятельно рекомендуется сохранять в специальном после ссылку на последний элемент, чтобы при добавлении новых элементов в конец списка не приходилось каждый раз трассировать его целиком */
Как это обстоятельство может быть использовано для оптимизации копирования и объединения Pascal-строк? А вот смотрите:
char *с_strcpy(char *dst, char *src) char *pascal_strcpy(char *dst, char *src)
{ {
char * cp = dst; int a;
while( *cp++ = *src++ ); for(a=0; a < ((*src+1) & ~3); a += 4)
// копируем строку по байтам *(int *)(dst+a)=*(int *)(src+a);
// одновременно с этим проверяя // копируем строку двойными словами
// каждый символ на равенство нулю // проверять каждый символ на равенство
// нулю в данном случае нет необходимости
// т.к. длина строки наперед известна
for(a=((*src+1) & ~3); a<(*src+1); a ++)
*(char *)(dst+a)=*(char *)(src+a);
// копируем остаток хвоста строки
// (если он есть) по байтам.
// это не снижает производительности,
// т.к. максимально возможная длина
// хвоста составляет всего три байта
return( dst ); return( dst );
} }
Листинг 39 Пример реализации функций копирования Си (слева) и Pascal строк (справа)
char *с_strcat (char *dst, char *src) char *pascal_strcat (char *dst, char *src)
{ {
char *cp = dst; int len;
while( *cp ) ++cp; len=*dst;
// читаем всю строку-источник // за одно обращение к памяти
// байт за байтом в поисках // определяем длину строки-приемника
// ее конца
*dst+=*src;
// корректируем длину строки-приемника
while( *cp++ = *src++ ); pascal_strcpy(dst+len,src);
// байт за байтом дописываем // копируем строку двойными словами
// источник к концу приемника,
// до тех пор пока не встретим нуль
return( dst ); return( dst );
} }
Листинг 40 Пример реализации функций объединения Си (слева) и Pascal строк (справа)
Итак, в отличие от Си-строк, Pascal-строки допускают эффективную блочную обработку и при желании могут копироваться хоть восьмерными словами. Другое немаловажное обстоятельство: при объединении Pascal-строк нам незачем просматривать всю строку-приемник целиком в поисках ее конца, поскольку конец строки определяется алгебраическим сложением указателя на начала строки с первым байтом строки, содержащим ее длину.
Интенсивная работа с Си-строками способна серьезно подорвать производительность программы и потому лучше совсем отказаться от их использования. Проблема в том, что мы не можем "самовольно" перейти на Pascal-строки, не изменив все сопутствующие им библиотеки языка Си и API-функций операционной системы. Ведь функции наподобие fopen или LoadLibrary рассчитаны исключительно на ASCIIZ-строки и попытка "скормить" им Pascal?строку ни к чему хорошему не приведет, – функция, не обнаружив в положенном месте символа-завершителя строки, залезет совершенно в постороннею память!
Выход состоит в создании "гибридных" Pascal + ASCIIZ-строк, явно хранящих длину строки в специально на то отведенном поле, но вместе с тем, имеющих завершающий ноль на конце строки. Именно так и поступили разработчики класса CString библиотеки MFC, распространяемой вместе с компилятором Microsoft Visual C++.
Рисунок 51 0х41 Устройство Си, Pascal, Delphi и MFC-строк.
Си- строки могут иметь неограниченную длину, но не могут содержать в себе символа нуля, т.к. он трактуется как завершитель строки. Pascal-строки хранят длину строки в специальном однобайтовом поле, что значительно увеличивает эффективность строковых функций, позволяет хранить в строках любые символы, но ограничивает их размер 256 байтами. Delphi-строки представляют собой разновидность Pascal-строк и отличаются от них лишь увеличенной разрядностью поля длины, теперь строки могут достигать 64Кб длины. MFC-строки – это гибрид Си и Pascal строк с 32-битным полем длины, благодаря чему макс. длина строки теперь равна 4Гб.
Несложный тест (см. [Memory/MFC.c]) поможет нам сравнить эффективность обработки Си- и MFC-строк на операциях сравнения, копирования и вычисления длины. На последней операции, собственно, и наблюдается наибольших разрыв в производительности, достигающих в зависимости от длины "подопытной" строки от одного до нескольких порядков.
Объединение двух MFC-строк (при условии, что обе они одинаковой длины) осуществляется практически вдвое быстрее, чем аналогичных им Си-строк, что совсем неудивительно, т.к. в первом случае мы обращаемся к вдвое меньшему количеству ячеек памяти. Разумеется, если к концу очень длиной строки дописывается всего несколько символов, то выигрыш от использования MFC-строк окажется много большим и приблизительно составит: крат.
А вот сравнение Си- и MFC- строк происходит одинаково эффективно, точнее одинаково неэффективно, поскольку разработчики библиотеки MFC- предпочли побайтовое сравнение сравнению двойными словами, что не самым лучшим образом сказалось на производительности. Забавно, но штатная функция strcmp из комплекта поставки Microsoft Visual C++ (не intrinsic!), – похоже единственная функция сравнения строк, обрабатывающая их не байтами, а двойными словами, что в среднем происходит вдвое быстрее. В общем, наиболее предпочтительное сравнение MFC-строк выглядит так:
#include <String.h>
#pragma function(strcmp) // вырубаем intrinsic'ы
if (strcmp(s0.GetBuffer(0),s1.GetBuffer(0)))
// строки не равны
else
// строки равны
Листинг 41 Пример эффективного сравнения MFC-строк
Рисунок 52 graph 24 Сравнение эффективности MFC и Си функций, работающий со строками. Как видно, MFC строки более производительны
