/* Поиск с помощью strstr – довольно быстрый, переносимый */
char s[]=»a\r\n ab\r\n abc\r\n»;
char *p, *pold=s, *p2 = s; unsigned n;
while(p = strstr(pold, «\r\n») )
{ n = p — pold; //
n == длина перемещаемой части строки (от предыдущего
memmove(p2, pold, n); //
вхождения до текущего)
p2 += n;
pold = p + 2;
}
strcpy(p2, pold);

/* Поиск с помощью toShort, копирование по байтам – немного быстрее */
char s[]=»a\r\n ab\r\n abc\r\n», *p = s, *p2 = s;
while(*p) //
Пока в строке есть символы
{ if ( *(short*)p == toShort(‘\r’,’\n’) )
p+=2; //
Нашли, пропускаем два символа
else
*(p2++) = *(p++); //
Копируем и переходим к следующему символу
}
*p2 = ‘\0’;

Хотя в последнем случае мы копируем строку по байтам, программа будет работать немного быстрее за счет использования макроса toShort. В свою очередь, первый вариант удерживает хорошую скорость по той причине, что копирует строку быстрыми функциями memmove() и strcpy(). Если попробовать скомбинировать оба алгоритма и откомпилировать VC++, полученная программа, как это ни странно, будет самой медленной:

/* memmove+toShort – медленно */
char s[]=»a\r\n ab\r\n abc\r\n», *p = s, *pold = s; unsigned n;
while(*p) //
Ищем первое вхождение подстроки
{ if ( *(short*)p == toShort(‘\r’,’\n’) )
{ pold = p;
p++;
break; //
Если нашли, запоминаем в pold и прерываем цикл
}
p++;
}
n = 0;
while(*p) //
Ищем остальные вхождения
{ if ( *(short*)p == toShort(‘\r’,’\n’) )
{ memmove(pold-n, pold+2, p — pold);
n+=2;
pold = p; //
Сдвигаем участок строки от одного вхождения до другого
}
p++; //
Проверяем следующий символ
}
memmove(pold-n, pold+2, p — pold); //
Сдвигаем остаток строки

Отставание в скорости может быть связано с тем, что memmove() повторно проходит по уже просмотренному участку памяти, а память работает быстрее при последовательном доступе.

Можно попробовать еще один трюк, который ускорит выполнение программы почти на всех компиляторах. Возьмем самый быстрый из наших алгоритмов — тот, что ищет с помощью toShort и копирует по байтам — и перепишем его так, чтобы копировать строку по двойным словам. 32-разрядные процессоры гораздо быстрее работают с двойными словами (32 бита=4 байт), чем с байтами (8 бит). Нам потребуется частично развернуть цикл, записав сравнение четыре раза:

/* Поиск с помощью toShort, копирование двойных слов – самый быстрый */
char s[]=»a\r\n ab\r\n abc\r\n», *p = s, *p2 = s;
while(*p) //
Пока в строке есть символы
{ if ( *(short*)p == toShort(‘\r’,’\n’) )
{ p+=2;
continue; //
Нашли, пропускаем два символа
}
p++;
if ( *(short*)p == toShort(‘\r’,’\n’) )
{ *(p2++) = *(p-1); //
Копируем первый символ
p+=2;
continue; //
Нашли, пропускаем два символа
}
p++;
if ( *(short*)p == toShort(‘\r’,’\n’) )
{ *(short*)p2 = *(short*)(p-2); //
Копируем первые два символа
p+=2, p2+=2;
continue; //
Нашли, пропускаем два символа
}
p++;
if ( *(short*)p == toShort(‘\r’,’\n’) )
{ *(short*)p2 = *(short*)(p-3); //
Копируем первые два символа
p2+=2;
*p2 = *(p-1); //
Копируем третий символ
p+=2, p2++;
continue; //
Нашли, пропускаем два символа
}
*(long*)p2 = *(long*)(p-3); //
Копируем
p++, p2+=4; //
Переходим к следующему символу
}
*p2 = ‘\0’;

Эта программа довольно неуклюжая, но работает она быстрее всех. Результаты прогона всех четырех программ 40 000 раз на процессоре Duron-800, в качестве строки s взята сказка Пушкина «О попе и работнике его Балде» (длиной пять с половиной килобайт), время указано в миллисекундах (1000 миллисекунд = 1 секунда, 60 000 миллисекунд = 1 минута):

Компилятор VC++

memmov + strstr: 2599
копирование байтов + toShort: 2275
memmove + toShort: 3282
копирование двойных слов + toShort: 1817

Компилятор LCC32

memmov + strstr: 63862
копирование байтов + toShort: 2856
memmove + toShort: 3400
копирование двойных слов + toShort: 2194

Компилятор MinGW (порт GCC на Windows)

memmov + strstr: 3123
копирование байтов + toShort: 1756
memmove+toShort: 2809
копирование двойных слов + toShort: 1425

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

Как удвоить амперсанды в строке? Амперсанд (&) служит знаком горячей клавиши в Windows. И чтобы показать в меню или в tooltip (всплывающей подсказке) строку, содержащую знаки &, эти знаки нужно повторить дважды. Например, ты пишешь mp3-плеер, и в tooltip должно быть имя исполнителя. Если имя будет содержать знак &, например, «Vangelis & Demis Roussos», то юзер этот знак не увидит. Нужно повторить его дважды: «Vangelis && Demis Roussos».

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

char buff1[100] = «Vangelis & Demis Roussos», buff2[100];
char *p = buff1, *p2 = buff2;
while(*p)
if(*p == ‘&’)
*(p2++) = ‘&’;
*(p2++) = *(p++);
*p2 = ‘\0’;

Если ты хочешь ускорить эту программу, копируй не по одному символу, а по четыре сразу (на 64-битных процессорах нужно будет копировать сразу 8 символов):

char *p = buff1, *p2 = buff2; unsigned x;
do
{
NEXT: x = *(long*)p; //
Очередные 4 символа строки — в переменную x
if((x & 0xFF) == 0x26) // Если первый символ — ‘&’ (26 — его код в ASCII)
{
R: *(long*)p2 = 0x00002626, p++, p2+=2; //
Вывести ‘&&’
goto NEXT; //
Продолжить
}
else if((x & 0xFF00) == 0x2600) //
Если второй символ — ‘&’
{ *(long*)p2 = x, p++, p2++; //
Вывести первый символ
goto R; //
Затем вывести ‘&&’ и продолжить
}
else if((x & 0xFF0000) == 0x260000) //
Если третий символ — ‘&’
{ *(long*)p2 = x, p+=2, p2+=2; //
Вывести первые два символа
goto R; //
Затем вывести ‘&&’ и продолжить
}
else if((x & 0xFF000000) == 0x26000000) //
Аналогично
{ *(long*)p2 = x, p+=3, p2+=3;
goto R;
}
else //
Если в строке нет амперсандов
*(long*)p2 = *(long*)p, p2+=4, p+=4; //
Просто копируем 4 символа
}
while( (x >> 24) & (x >> 16) &
(x >> 8) & (x & 0xFF) ); //
Пока в x нет нулевых байтов

ФУНКЦИЯ REALLOC

Как пользоваться функцией realloc? Бывает, что размер строки не известен заранее и может изменяться в ходе работы программы. Тогда нужно перераспределять память функцией realloc. Например, юзер вводит текст с макросами типа «Дорогая $name, поздравляем Вас с $holiday», а программа должна заменять эти $name, $holiday, чтобы получилось «Дорогая Клавдия Кузьминична, поздравляем Вас с 8 марта» или «Дорогая Людмила Лукьяновна, поздравляем Вас с Новым Годом».

Размер конечной строки заранее не известен (потому что мы не знаем, сколько в строке макросов и какую длину имеет каждый из них после подстановки значения). Самый простой вариант здесь — это расширять строку каждый раз, когда мы находим макрос:

char *s, *p, *p2; int size, sizeh, sizen, i;
//
‘size’ — размер строки ‘macro’, который мы до этого получили,
//
например от WM_GETTEXTLENGTH (а саму ‘macro’ — с помошью
WM_GETTEXT)

sizeh = strlen(holiday);
sizen = strlen(name); //
Заносим в переменные размер ФИО и названия праздника
s = (char*)malloc(size); //
Создаем строку s, в которую мы будем записывать
//
текст из строки ‘macro’, расширяя макросы
for(p = macro, p2 = s; *p != ‘\0’;)
if(toLong(‘$’, ‘n’, ‘a’, ‘m’) == *(long*)p &&
‘e’ == *(p+4) )
{
size += sizen;
i = p2 — s; //
Сохраняем p2
s = (char*)realloc(s, size); // Перераспределяем память
p2 = s + i; //
Восстанавливаем p2
strcpy(p2, name); //
Копируем имя
p2 += sizen;
p += 5;
}
else if(toLong(‘$’, ‘h’, ‘o’, ‘l’) == *(long*)p &&
toLong(‘i’, ‘d’, ‘a’, ‘y’) == *(long*)(p+4))
{
size += sizeh;
i = p2 — s; //
Сохраняем p2
s = (char*)realloc(s, size); //
Перераспределяем память
p2 = s + i; //
Восстанавливаем p2
strcpy(p2, holiday); //
Копируем праздник
p2 += sizeh;
p += 8;
}
else
*p2++ = *p++;

*p2 = ‘\0’;
//
Выводим строку s
free(s); //
Освобождаем занимаемую ею память

Можно написать более изящный код, если сделать три массива — с названиями макросов ($name, $holiday), с их расширениями (Людмила Лукьяновна, 8 марта) и с длинами строк. Но тогда сравнивать строки придется функцией strcmpn, а не более быстрым макросом
toLong.

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

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

ЧТО ЕЩЕ ПОЧИТАТЬ НА ТЕМУ ОПТИМИЗАЦИИ ПРОГРАММ?

После выхода первой части «Забытых секретов кодинга» ко мне поступило множество писем (ну, это я загнул, прямо как писатель какой-нибудь 😉 с одним вопросом: какие книги, сайты и журналы можно почитать об оптимизации. Вот список тех публикаций, которые мне удалось найти:

  • Бентли Джон. Жемчужины творчества программистов. — М.: Радио и связь, 1990. (или в более новом издании — «Жемчужины программирования», оригинальное название — Programming Pearls). Книга старая, но, увы, многие программы с тех времен не стали быстрее, и описанные трюки все еще актуальны. Очень много примеров на поиск, что называется, «на каждый день», то есть ты можешь завтра же столкнуться с такой же задачей в своей проге, и тогда ты вспомнишь добрым словом Джона Бентли. Примеры не привязаны к какому-то одному языку программирования. Спасибо zer0access, который посоветовал мне эту книгу!
  • Уоррен Генри. Алгоритмические трюки для программистов. — М.: Вильямс, 2003 (в оригинале называется «Hacker’s Delight», что можно перевести как «Хакерские радости»). Трюки в этой книге в основном математические (как ускорить деление, проверку границ, перестановку и выделение отдельных битов, проверку переполнения). Местами напоминает лекции по матлогике и вычмату в университете :(. Другая проблема в том, что автор ориентируется на RISC-машины типа Compaq Alpha, Power PC (Macintosh). А наш любимый IBM PC с Пентиумом или Атлоном — это все-таки CISC. Но, вообще, книга интересная, хотя практическое применение некоторым трюкам Уоррена найти сложновато.
  • Зубков Сергей. Ассемблер для DOS, Windows и Unix. — М. ДМК-Пресс, 2000. Здесь неплохо описано устройство процессора (конвейеры, параллелизм на уровне инструкций). По крайней мере, понять можно, в отличие от многих других статей и книг. Также хорошо написано о низкоуровневой оптимизации (какая инструкция ассемблера работает быстрее).
  • Чистяков Владислав. Кто сегодня самый шустрый (статья в трех частях). Многие спрашивали меня про встроенную оптимизацию компиляторов. Вот эта статья как раз отвечает на вопрос: «Какой компилятор дает более быстрый код?» Автор делает выводы о качестве оптимизации Intel C++, VC++, GCC, BCC, Delphi, Java, C# и Visual Basic, компилируя одни и те же программы и сравнивая скорость их работы.
  • Каньковски Петр. Альтернативные средства разработки для
    Windows
    . Ну, и, конечно, как же мне не вспомнить свою статью с длиннющими и занудными ассемблерными листингами, которые никто никогда не читает ;). В этом опусе я не сравниваю скорость работы программ, как Чистяков, а анализирую качество выдаваемого кода и те оптимизации, которые делает компилятор.
  • Раздел «Оптимизация» на
    codenet.ru
    . На этом сайте ты найдешь статьи по оптимизации разных авторов. Творчество Рэя Дункана уже давно устарело (1992 год), а вот отрывки из книги «Техника оптимизации программ» Криса Касперски советую посмотреть.
  • Guru of the Week (на английском). Канадский сайт хакеров от программирования, которые забивают себе голову задачами типа «Сколько плюсов может быть в правильно написанной программе на Си?» или «Поможет ли компилятору const в формальных параметрах сгенерировать более оптимальный код?». Забавные вопросы, но совершенно непрактичные, применить их некуда. Короче, «игры разума».

В книжных магазинах не так уж много книг, описывающих не конкретный язык программирования, а то, как писать программы на этом языке. Казалось бы, сколько можно учить Си и Delphi, всем давно известные. Ан нет, охотнее берут «библии», в деталях расписывающие какой-то один язык, и многие из этих увесистых томиков на поверку оказываются переведенными help’ами Delphi или Visual Basic. То же относится к Win32 — на прилавках сейчас книги, которые являются буквальным переводом Windows Platform SDK. Да, читать help на русском, да еще и в красивом переплете, довольно удобно. Но не проще ли подучить английский язык и бесплатно читать ту же справку с экрана?

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

Исходники

Оставить мнение

Check Also

Аудит Windows. Выбираем коммерческий софт для комплексной проверки безопасности

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