Трюки от Крыса

Крис Касперски

Хакер, номер #096, стр. 096-144-3

00:50.71 01:50.23 02:49.54 03:50.11 04:49.42 05:50.87 06:49.87 07:49.53 08:50.16 09:50.38 10:50.60 11:49.60 12:50.53 13:49.75 14:49.98 15:50.07 16:49.34 17:49.54 18:49.74 19:49.45 20:50.40 21:50.62 22:49.70 23:49.56 24:49.40 25:50.38 26:49.73 27:50.23 28:49.90 29:49.41 30:49.75 31:00.00

Трюк 4: самое быстрое сравнение памяти

Большинство реализаций функции memcmp() так или иначе сводятся к оптимизированному ассемблерному алгоритму:

while ( --count && *(char *)buf1 == *(char *)buf2 )

{

buf1 = (char *) buf1 + 1;

buf2 = (char *) buf2 + 1;

}

А как насчет того, чтобы ускорить его раза эдак в два, причем без использования SSE, pre-fetch'а и прочих подобных расширений? Поверь мне, это возможно! Достаточно разбить блоки памяти на кусочки от 128 байт до ~4 Кбайт каждый (в зависимости от размера самих блоков), и сравнивать не сами блоки, а контрольные суммы "кусочков". Если функции расчета контрольных сумм разместить в отдельных потоках, то на многоядерных и HT-процессорах они будет выполняться параллельно в результате чего производительность практически удвоится. Но даже на однопроцессорных машинах мы получим определенных выигрыш, поскольку контроллеры памяти оптимизированы под работу с одним потоком памяти и попеременно обращение к двум ячейкам, находящихся в различных DRAM-банкам в некоторых случаях вызывает значительную деградацию производительности (подробнее об этом можно прочитать в моей книге "Техника оптимизации программ", электронная версия которой доступна на http://kpnc.opennnet.ru и ftp://nezumi.org.ru).

Единственная проблема заключается в том, что идентичность CRC еще не гарантирует идентичности блоков! То есть, данный алгоритм никогда не выдает "ложных негативных" результатов, но с определенной (правда, очень невысокой) степенью вероятностью способен на "ложный позитив". Поэтому его следует применять для сравнения тех блоков, о которых заранее известно, что они скорее всего различны, и мы просто хотим убедиться в этом, поскольку, если CRC-алгоритм не обнаружил сравнений, для 100% уверенности необходимо инициировать стандартный алгоритм сравнения. Впрочем, при дроблении сравниваемых блоков на кусочки порядка 128 байт вероятность коллизий CRC32 (и тем более CRC64) насколько мала, что ей можно полностью пренебречь (если, конечно, речь идет о непредумышленной "подделке" блоков злобствующими хакерами).