/* Поиск с помощью 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

Безопасность смарт-контрактов. Топ-10 уязвимостей децентрализованных приложений на примере спецификации DASP

Количество смарт-контрактов в блокчейне Ethereum только за первую половину 2018 года вырос…