Оптимизация работы со строками
Задался сегодня вопросом о том какой код со строками работает быстрее:
u_char c;
if (c == ' ' || c == '\t' || c == '\r' || c == '\n') {
......
}
или:
u_char c;
u_char delimiter[] = “…”;
if (delimiter[c]) {
}
И вот что получилось…
int i, count;
time_t start, finish;
u_char delimiter[] = “\0\0\0\0\0\0\0\0\0\t\n\0\0\r\0\…………”;
u_char text[] = “Eto\r Prosto Nekotoriy\n Test Na\t proiZvoditelnoSt”;
u_char *p, c;
count = 0;
start = time(NULL);
for (i = 0; i < 100000000; i++) {
p = text;
while (*p) {
if (delimiter[*p]) {
count++;
}
p++;
}
}
finish = time(NULL);
printf("%d, %d\n", (int) finish - start, count);
Этот код выполнился за 24 секунды без оптимизации и за 12 секунд с оптимизацией -O3.
Заменяем блок проверки на:
if (*p == ' ' || *p == '\t' || *p == '\n' || *p == '\r') {
count++;
}
И получаем 35 секунд без оптимизации и 28 секунд с оптимизацией -O3. Нехилая получается разница.
Попутно решил проверить даст ли какой-дибо эффект такая модификация:
c = *p;
if (c == ' ' || c == '\t' || c == '\n' || c == '\r') {
count++;
}
Ни какой разницы. Оно и понятно, значение один раз помещается в регистр, а не помещается при каждой проверке.
Вывод я делаю следующий: что в первом, что во втором варианте происходит по одному обращению к памяти для получения байта. В первом варианте (как я подозреваю) происходит ещё одно обращение к памяти для получения значения из таблицы символов. Видимо одно обращение к памяти дешевле чем 3 лишних условных перехода.
После этого провёл ещё один маленький тест, что быстрее для конвертации символов в нижний регистр — использование таблицы символов или операция c = c | 0×20. Результат получился забавный. Без оптимизации 24 секунды для варианта с таблицей и 25 секунд для варианта с логическим ИЛИ. С оптимизацией -O3 получилось наоброт, 12 секунд для варината с таблицей и 9 секунд для варианта с логическим ИЛИ. Не буду делать никаких выводов, для этого надо копать ассемблер, а мне сейчас лениво это делать 
Tags: оптимизация, программирование
