c-tricks-vii

сишные трюки\\ (7й выпуск)

В Си массивы начинаются с нуля, а во многих других языках — с единицы, что сильно напрягает при переходе с одного языка на другой и еще больше — при переносе программ. Приходится вносить множество правок в самых разных местах и потом долго отлаживать программу. Да и сами сишники далеко не в восторге от того, что индекс последнего элемента массива размером N равен N-1. Это служит не только источником досадных ошибок, но в некоторых случаях снижает производительность.

Существует хитрый хак, позволяющий создавать массивы, начинающиеся с единицы, или, строго говоря, вообще с _любого_ числа. Это невероятно полезно в тех случаях, когда нам нужно создать массив, проиндексированный k, k+1,,,k+n (например, возрастом человека от 16 лет до 100).

А делается это приблизительно так:

задаем размер массива, его тип и индекс первого элемента #define SIZE_OF_ARRAY0x1000 #define TYPE_OF_ARRAYint #define INDEX_OF_FIRST_ELEMENT1 объявляем «сырую» переменную-указатель

TYPE_OF_ARRAY *p;

выделяем блок памяти требуемого размера p = (TYPE_OF_ARRAY*)malloc(SIZE_OF_ARRAY*sizeof(TYPE_OF_ARRAY)); проверка на успешность выделения памяти

if (!p) /* обработка ситуации ошибки выделения */

сдвигаем указатель на нужное кол-во позиций, так, чтобы индекс первого элемента стал равен INDEX_OF_FIRST_ELEMENT

p -= INDEX_OF_FIRST_ELEMENT;

работаем с массивом … возвращаем указатель на место

p += INDEX_OF_FIRST_ELEMENT;

освобождаем блок памяти free(p); Листинг 1 создание массива, начинающегося с произвольного элемента на хипе Аналогичным путем можно обрабатывать и локальные массивы (в этом случае наша задача даже упрощается, поскольку не нужно заботиться об освобождении памяти), которая при выходе из функции освободится сама: задаем размер массива, его тип и индекс первого элемента

#define SIZE_OF_ARRAY0x1000

#define TYPE_OF_ARRAYint

#define INDEX_OF_FIRST_ELEMENT1

выделяем блок памяти требуемого размера TYPE_OF_ARRAY raw[SIZE_OF_ARRAY]; TYPE_OF_ARRAY *p = raw; сдвигаем указатель на нужное кол-во позиций,

так, чтобы индекс первого элемента стал равен INDEX_OF_FIRST_ELEMENT p -= INDEX_OF_FIRST_ELEMENT; Листинг 2 создание массива, начинающегося с произвольного элемента на стеке ===== трюк 2: марафон битовых и логических операций ===== В некоторых руководствах и конференциях можно прочесть, что выражение вида (a || b || c) _практически_ всегда быстрее, чем (a | b | c). Так ли это? И если так, то почему? Попробуем разобраться. Поскольку все современные компиляторы поддерживают «быстрые булевы операции», они вычисляют значение сложного выражения лишь до первого«срабатывания». То есть, если a != 0, то оставшуюся часть выражения можно не проверять, поскольку уже и так все ясно. Напротив, битовое выражение (a | b | c) требует вычисления всех переменных, что на первый взгляд выглядит более похабным и менее производительным. Но это только на первый взгляд. Все зависит от того насколько часто «быстрая булева оптимизация» прерывает вычисление выражения до его завершения. Если все переменные _преимущество_ равны нулю, то ни о каком выигрыше говорить не приходится, а вот код получается намного более громоздким, что легко подтверждается дизассемблером: .text:00000020moveax, [esp+arg_0] .text:00000024testeax, eax .text:00000026jnzshort locret_34 .text:00000028movecx, [esp+arg_4] .text:0000002Ctestecx, ecx .text:0000002Ejnzshort locret_34 .text:00000030movecx, [esp+arg_8] Листинг 3 результатдизассемблирования bar(int a, int b, int c){if (a || b || c) return a;} Что мы видим?! Условные переходы. То есть ветвления. А процессоры с конвейерной архитектурой (типа PentiumPro+) условных переходов не любят, особенно если они выполняются в цикле. Как следствие — вместо обещанного выигрыша мы получаем _падение_ производительности. .text:00000000moveax, [esp+arg_0] .text:00000004movedx, [esp+arg_4] .text:00000008movecx, eax .text:0000000Aorecx, edx .text:0000000Cmovedx, [esp+arg_8] .text:00000010orecx, edx .text:00000012retn Листинг 4 результатдизассемблирования foo(int a,int b,int c){if (a | b | c ) return a;} А вот в выражении (a | b | c) никаких условных переходов нет и оно выполняется предельно быстро! Поэтому, используете (a || … || x) только при большом количеств элементов (намного больше трех) и только если одна или несколько переменных гораздо чаще равны TRUE, чем FALSE (при этом они должны стоять первыми слева). Тоже самое относится и к &&, лишь с той оговоркой, что переменные, преимущественно равные FLASE следует выдвигать вперед. ===== трюк 3: оценка качества генератора случайных чисел ===== Генератор случайных чисел — используется не только в криптоалгоритмах, но и в более «приземленных» программах. Например, в играх. И очень часто нам важно знать, насколько «случаен» выдаваемый им результат (допустим, мы моделируем казино в поисках беспроигрышной стратегии). Причем, кроме «общей» вероятности, представляет интерес выяснить степень распределения вероятности по каждому из битов. Некоторые генераторы страдают хронической предсказуемостью определенных бит (как правило, младших или старших). Следующая программа как раз и позволяет оценить насколько предсказуем тот или иной бит: #define N 10000 unsigned int buf[sizeof(int)*8]; main() { int x=0; unsigned int a, l; srand1); for (l = 0; l < sizeof(int)*8; l++) { for (a = 0,x = 0; a < N; a++) { buf[l] += ((rand()»l) & 1); } } for (a = 0; a < sizeof(int)*8; a++) printf(«%02d:%02d.%02d\t»,a,10000*buf[a]/N/100,10000*buf[a]/N%100); printf(«\n»); } Листинг 5 тестовая программа Результат прогона на MS VC 6 показывает, что биты от 0 до 14 генерируются довольно-таки качественно (с вероятностью 50/50 и погрешностью порядка 1%), а вот начиная с 15 бита мы имеем сплошной облом!!! То есть, по сути rand() возвращает 14 битный результат, не дотягивающий даже до WORD! 00:50.2401:50.2302:49.8403:49.2204:49.8105:49.5806:49.8407:49.7708:50.2409:50.4310:50.6211:50.1012:49.8913:49.4914:50.9015:00.0016:00.0017:00.0018:00.0019:00.0020:00.0021:00.0022:00.0023:00.0024:00.0025:00.0026:00.0027:00.0028:00.0029:00.0030:00.0031:00.00 Листинг 6 распределение вероятности по битам в штатной функции rand() от MS VC (номер бита: вероятность выпада 1 или 0). А вот gcc 3.3.4 (другие версии не тестировались) дает совсем другой результат, задействовав 31 бит, и на десятые доли процента обгоняющий MS VC по качеству. В некоторых приложениях эта разница оказывается более, чем критична! Так что gcc рулит! 00:50.7101:50.2302:49.5403:50.1104:49.4205:50.8706:49.8707:49.5308:50.1609:50.3810:50.6011:49.6012:50.5313:49.7514:49.9815:50.0716:49.3417:49.5418:49.7419:49.4520:50.4021:50.6222:49.7023:49.5624:49.4025:50.3826:49.7327:50.2328:49.9029:49.4130:49.7531:00.00 Листинг 7 распределение вероятности по битам в штатной функции rand() от gcc ===== трюк 4: самое быстрое сравнение памяти ===== Большинство реализаций функции memcmp() так или иначе сводятся к оптимизированному ассемблерному алгоритму: while ( –count && *(char *)buf1 == *(char *)buf2 ) { buf1 = (char *) buf1 + 1; buf2 = (char *) buf2 + 1; } Листинг 8 канонический алгоритм сравнения двух блоков памяти А как на счет того, чтобы ускорить его раза эдак в два, причем без использования SSE, pre-fetch'а и прочих подобных расширений? Поверьте мне, парни, это возможно! Достаточно разбить блоки памяти на кусочки по от 128 байт до ~4 Кбайт (в зависимости от размера самих блоков), и сравнивать не сами блоки, а контрольные суммы «кусочков». Если функции расчета контрольных сумм разместить в отдельных потоках, то на многоядерных и HT-процессорах они будет выполняться _параллельно_ в результате чего производительность практически удвоится. Но даже на однопроцессорных машинах мы получим определенных выигрыш, поскольку контроллеры памяти оптимизированы под работу с одним потоком памяти и попеременно обращение к двум ячейкам, находящихся в различных DRAM-банкам в некоторых случаях вызывает значительную деградацию производительности (подробнее об этом можно прочитать в моей книге «техника оптимизации программ», электронная версия которой доступна на http://kpnc.opennnet.ru и ftp://nezumi.org.ru). Единственная проблема заключается в том, что идентичность CRC еще не гарантирует идентичности блоков! То есть, данный алгоритм никогда не выдает «ложных негативных» результатов, но с определенной (правда, очень невысокой) степенью вероятностью способен на «ложный позитив». Поэтому, его следует применять для сравнения тех блоков, о которых заранее известно, что они скорее всего различны и мы просто хотим убедиться в этом, поскольку, если CRC-алгоритм не обнаружил сравнений, для 100% уверенности необходимо инициировать стандартный алгоритм сравнения. Впрочем, при дроблении сравниваемых блоков на кусочки порядка 128 байт, вероятность коллизий CRC32 (и тем более CRC64) насколько мала, что ей можно полностью пренебречь (если, конечно, речь идет о непредумышленной «подделке» блоков злобствующими хакерами).

1)
unsigned)time(NULL