Предлагаю сделать трэд, в котором будем размещать всякие вкусности, которые позволяет выделывать си(нечто среднее между "Маленьким тестом" Явы и "Находками" дотНета, ближе к последнему).
Итак, начинаем.

1) Быстрый floor(float):

Код

static const uint32_t FLOAT_MANTISS_MASK =0x007fffff; static const uint32_t FLOAT_EXPONENT_MASK=0x7f800000; #define __f2i(f) (*(uint32_t*) (&(f))) #define macro_float_floor(f) (__f2i(f) &= ~(FLOAT_MANTISS_MASK >> (((__f2i(f)&FLOAT_EXPONENT_MASK)>>23)-127))) //for c++ inline float inline_float_floor(float f){macro_float_floor(f);return f;}

Для того, чтобы отбросить дробную часть переменной var, используем macro_float_floor(var); или var=inline_float_floor(var).
Тест(прост до безобразия):

Код

time_t st=time(NULL);     for(int i=0; i < 0x7ffffff;++i){ #ifdef MACRO         macro_float_floor(d);     #elif define INLINE         inline_float_floor(d); #else         floor(d); #endif     }     printf("%d secs\n", time(0)-st);

floor() - 9 секунд
macro_float_floor() - 4 секунды.
inline_float_floor() - 1(одна) секунда(!!!)

БАГИ И ОГРАНИЧЕНИЯ:
Число должно быть нормализованным(а для |f| < 1 это не всегда так).
Если число меньше нуля, то округление срабатывает не верно - число округленное число будет больше, чем неокругленное.

(напомню, что аргументы высчитываются справа налево, а конструкция (a,b) высчитывает a и возвращает b, именно по этим
причинам macro стоит первым аргументом - если его поставить взад, то он изменит d, и др. ф-циям будет нечего высчитывать)

Код

printf("macro\t\tfloor\t\tinline\tsource\n");     //баги     printf("%f\t%f\t%f\t%f\n",(macro_float_floor(d),d), floor(d), inline_float_floor(d),d=0.5);     printf("%f\t%f\t%f\t%f\n",(macro_float_floor(d),d), floor(d), inline_float_floor(d),d=-0.5);     printf("%f\t%f\t%f\t%f\n\n",(macro_float_floor(d),d), floor(d), inline_float_floor(d),d=-5.3);     //нормально     printf("%f\t%f\t%f\t%f\n",(macro_float_floor(d),d), floor(d), inline_float_floor(d),d=5);     printf("%f\t%f\t%f\t%f\n",(macro_float_floor(d),d), floor(d), inline_float_floor(d),d=-4);     printf("%f\t%f\t%f\t%f\n",(macro_float_floor(d),d), floor(d), inline_float_floor(d),d=50.4535);     printf("%f\t%f\t%f\t%f\n",(macro_float_floor(d),d), floor(d), inline_float_floor(d),d=51.6535);     printf("%f\t%f\t%f\t%f\n",(macro_float_floor(d),d), floor(d), inline_float_floor(d),d=52.00006535);     printf("%f\t%f\t%f\t%f\n",(macro_float_floor(d),d), floor(d), inline_float_floor(d),d=52.9999);

Это сообщение отредактировал(а) Mayk - 2.9.2005, 06:26

Нда, не густо ответов. Ладно, вот маленький хак номер
2) Подсчет битов.
Довольно известный(благодаря fortune), но всё же не лишне напомнить

Код

#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255) #define  BX_(x)     ((x) - (((x)>>1)&0x77777777)            \                          - (((x)>>2)&0x33333333)            \                          - (((x)>>3)&0x11111111))

Использование - очевидно BITCOUNT(var)

Это сообщение отредактировал(а) Mayk - 3.9.2005, 21:24

Цитата

Подсчет битов

побалуемся немного

Код

int BitCount(unsigned int x) {   int y=x&0xaaaaaaaa;   x-=y>>1;//x=x-y+y>>1;   y=x&0xcccccccc;//раньше была ошибка: 0xbbbbbbbb (чтобы не удивлялись замечанию ниже)...   x=x-y+y>>2;   return x%255; }

1 +
2 -
2 &
1 %
кроме того, не все процессоры любят % или /
некоторые делают эту операцию в 16 раз дольше, чем обычный +
впрочем, тот процессор вообще имел специальную операцию для подсчета битов
да и вообще... не люблю я макросы
уже на BITCOUNT((int)sqrt(x*1.28)) время увеличится в кучу раз (в этому случае по моим подсчетам в 8 раз) по сравнению с вызовом функции, особенно, если сделать ее inline...

Это сообщение отредактировал(а) maxim1000 - 5.9.2005, 01:14

Хмм, BitCount(0xf) даёт 2, что не верно.

Цитата(maxim1000 @ 4.9.2005, 02:54)

кроме того, не все процессоры любят % или /

Кстати, примерах надо заменить % 255 на & 255, работает бо быстрее
Ладно, до целочисленной арифметике мы еще дойдем. Продолжаем мучать флоаты(если немного подправить, то и даблы).
На очереди

3) быстрое преобразование float->int
Мы возьмем все биты мантиссы, которые определяют целую часть, добавим к ней еще 1 бит на перед, домножим на -1 если флоат был отрицательным и успокоимся. Ф-цию можно еще пооптимизировать, но не хочется. Воскресенье, блин, лениво
Итак:

Код

int float2int(float f) {     uint32_t& u = *(uint32_t*)&f;     int exp = ((u & FLOAT_EXPONENT_MASK) >> 23) - 127;     if(exp < 0)         return 0;     int s = u; s >>=31; s |= 1;     return ((((u & FLOAT_MANTISS_MASK) >> (23-exp)) | (1 << exp))) * s; }

Небольшие пояснения
При отрицательной экспоненте (exp < 0), модуль числа гарантированно будет меньше 1. Вернём 0 в этом случае.
int s содержит знак числа. Если исходное число было отрицательным, то s станет тоже станет отрицательным, так как битовые знаки int32 и float совпадают. Далее происходит сдвиг на 31 раздряд вправо. Так как s число знаковое, то при сдвиге знаковый бит не сбрасывается. Таким образом, если в начале число было отрицательным,то после сдвига все биты будут установлены в 1. Если число было положительным(и знаковый бит не был установлен), то все биты будут сброшены в ноль. s |= 1 устанавливает 1-ый бит.
Таким образом если s было нулем, то оно станет единицей. Таким образом мы получим знак 1 со знаком исходного числа.

Проверка
К сожалению, в bcc55 нет ф-ции rint, с которой стоило бы сравнить. Ну ладно, меньше поводов для разочарований, что нас, возможно, обогнали
Мы будем сравнивать с приведением типа.

На верность

Код

for(int i=0; i != 0x7fffff; ++i){         float rnd = rand() % 10000 - 5000;         rnd /= 100;         h=rnd;         j=float2int(rnd);         if(j!=h)             printf("%f) (f2i)%d != (c)%d\n", rnd,j,h);             }     printf("%d %d\n",int(f),float2int(f=0.5));     printf("%d %d\n",int(f),float2int(f=-0.5));     printf("%d %d\n",int(f),float2int(f=1.5));     printf("%d %d\n",int(f),float2int(f=-2.5));     printf("%d %d\n",int(f),float2int(f=-1.5));     printf("%d %d\n",int(f),float2int(f=2.5));

Код выдаст на экран(у меня по крайне мере выдал) только 6 пар чисел - 2 пары нулей, и пары единиц и двоек обоих знаков.
Можете закоментировать if(j!=h) и понаблюдать 2 колонки одинаковых чисел в процессе сравнения.

На скорость.

Код

float f=12.25;         volatile int j;     clock_t cl = clock();     for(int i=0; i != 0x7fffff; ++i){         j=float2int(f);     }     printf("%f elapsed\n", (((float)clock())-cl)/CLOCKS_PER_SEC);

j объявлена как volatile, чтоб особенно умные компиляторы(gcc к примеру) не выкинули вызов ф-ций, а добросовестно присвоили j его значение.
Результат: 0.235 секунды.

Заменим j=float2int(f) на j=f.
Результат: 1(одна) секунда(!!!).
Обогнали компилер в 4 раза

Это сообщение отредактировал(а) Mayk - 4.9.2005, 11:06

Цитата

Хмм, BitCount(0xf) даёт 2, что не верно

конечно, неверно... как же оно может быть верно, если я перевел из bin 1100 в hex 0xb?
исправил...

Цитата

Кстати, примерах надо заменить % 255 на & 255, работает бо быстрее

и неправильнее
тут вся фишка именно в этом %255
дело в том, что &255 эквивалентно %256, данная операция затрагивает только последние 8 бит
а нам как раз надо собрать информацию из всех 4 байт, именно для этого там стоит %255...

Цитата(maxim1000 @ 5.9.2005, 05:12)

тут вся фишка именно в этом %255 дело в том, что &255 эквивалентно %256, данная операция затрагивает только последние 8 бит а нам как раз надо собрать информацию из всех 4 байт, именно для этого там стоит %255...

Протупил, каюсь

На ночь глядя вспомним быструю целочисленную арифметику.

Быстрое деление на константу
Деление, как известно, происходит медленнее умножения. На этом можно сыграть
(идея честно стырена из "Ассемблера для DOS, WIN,UNIX" Зубкова).
Поделим число 55 на 10.

Код

uint32_t t = 55;     t *= 26; //2**8/10=256/10     printf("%08d\n",t>>8);

Трюк заключается в том, что после умножения в старших битах будет искомое число. Действительно, ведь
t*(256/10) это то же самое, что и (t/10)*256 (т.к. умножение - это сочетательная операция).
Очевидно, что кол-во бит на которое сдвигаем, это исходная степень двойки из множителя.
Если использовать последние достижения плюсов, до можно писать типа

Код

template<uint16_t denom> uint16_t fastdiv(uint16_t num){enum{multiplier=65536/denom}; return (num*multiplier)>>16;} ... int t = fastdiv<10>(55);

чтобы у компилятора не возникало желания просчитать константный множитель run-time'ом, запихнуть его в память, а потом доставать от туда(константы - дело не надежное).
ОГРАНИЧЕНИЯ
Очевидно, что трюк годится для беззнаковых чисел;
Знаменатель должен быть не больше максимальной степени двойки(иначе множитель просто обратится в ноль)
Результат не всегда соответствует действительности(выдаётся меньше на единицу).



ПРОВЕРКА НА СКОРОСТЬ
С делением 0x7fffff чисел(от 0 до 0x7fffff) ф-ции справились так(в начале идёт деление умножением, потом оператором /, потом ф-цией div()).
mult=0.141000 elapsed
oper/=0.328000 elapsed
div()=0.281000 elapsed
Надо подумать над точностью...

Mayk
Для хаков обычные правила форматирования кода неприменимы? Записывать ф-цию одной строкой в 116 символов, для чего бы она ни служила, все-таки не стоит

По сабжу: имхо, при современных процессорах и оптимизаторах польза сомнительная. Вот, например, Intel C++ (да и MSVC 7.1 тоже) считает, что быстрейший способ разделить на 55 такой:

Код

;;;    for (unsigned i = 0; i < count; ++i)         xor       ecx, ecx                                      ;16.16         ALIGN     4                                 ; LOE ecx ebx esi edi .B1.5:                          ; Preds .B1.5 .B1.4 ;;;        b[i] = i / 55;         mov       eax, 702812831                                ;17.10         mul       ecx                                           ;17.10         mov       eax, ecx                                      ;17.10         sub       eax, edx                                      ;17.10         shr       eax, 1                                        ;17.10         add       eax, edx                                      ;17.10         shr       eax, 5                                        ;17.10         mov       DWORD PTR [esi+ecx*4], eax                    ;17.3         inc       ecx                                           ;16.36         cmp       ecx, 3500000                                  ;16.2         jb        .B1.5         ; Prob 99%                      ;16.2

Я ничего не могу понять в этом коде, но ведь он прав, черт подери! Потому что:

Код

const unsigned count = 3500000; ...     unsigned *b = new unsigned[count];     clock_t t = clock();     for (unsigned i = 0; i < count; ++i)         b[i] = i / 55;     printf("%.1f ms\n", 1000.0 * (clock() - t) / CLOCKS_PER_SEC);     printf("%u\n", b[count - 1]);     t = clock();     for (unsigned i = 0; i < count; ++i)         b[i] = fastdiv<55>(i);     printf("%.1f ms\n", 1000.0 * (clock() - t) / CLOCKS_PER_SEC);     printf("%u\n", b[count - 1]);

50 ms, 63636 (точный результат). В то время как fastdiv<55> дает 60 ms и 63606.

Эрго: время таких оптимизаций давно прошло. Ну или, быть может, они актуальны на специфических компиляторах и железе.

Цитата(Void @ 6.9.2005, 02:48)

Для хаков обычные правила форматирования кода неприменимы?

Аййападоноккаюсьнафик. Просто мессага и так большая получилась

Цитата(Void @ 6.9.2005, 02:48)

Эрго: время таких оптимизаций давно прошло. Ну или, быть может, они актуальны на специфических компиляторах и железе.

Угу. Не спорю. Но поразвлечься не мешает, ведь так? К тому же на оптимизацию компилятора не всегда можно расчитывать(надо проверять нафик). Вот пример с твоей мессаги:

Цитата(Void @ 6.9.2005, 02:48)

inc      ecx                                          ;16.36         cmp      ecx, 3500000                                  ;16.2

Вот это нашим ассемблерщикам лучше не показывать. Засмеют нафик. Компилятор не догадался перевернуть цикл в орбатном направлении, дабы заюзать loop, хотя догадался взять ecx в кач-ве счетчика. К тому же при обратном счёте(for i=777; i >= 0; --i)) сравнение будет происходить быстрее, даже без лупы. Например, так:

Код

test eax,eax     jg        short @3

(в это безобразие наивно преобразует код bcc55) иногда может выполняется быстрее, чем cmp eax,777. Не всегда впрочем.
Так что в оптимизацию компилятора верить не надо. Надо проверять
Вот еще одна БУГАГА. Зацените код из vs2003: я валяюсь. Это с /Ox. Без ox код еще смешнее(add eax,1 - это круто!)

Код

;5:    for(volatile int i = 0; i!=0xfffFFFF; ++i); ; skip (i объявлен volatile, чтоб компилятор не выкинул цикл)     mov    ecx, DWORD PTR _i$270[esp+4]     inc    ecx     mov    DWORD PTR _i$270[esp+4], ecx     cmp    DWORD PTR _i$270[esp+4], eax

При обратном счёте код немного оптимизируется:

Код

; 5    :    for(volatile int i = 0xfffFFFF; i != 0; --i); ; skip (i объявлен volatile, чтоб компилятор не выкинул цикл)     mov    eax, DWORD PTR _i$270[esp+4]     dec    eax     mov    DWORD PTR _i$270[esp+4], eax     jne    SHORT $L271

Отсюда правило - циклы лучше делать в обратном направлении, ибо компиляторы тупые нафиг. Нее, оптимизация компиляторов - это фантастика. Всегда полезно знать пару запасных вариантов

Это сообщение отредактировал(а) Mayk - 6.9.2005, 07:01

Цитата(Mayk @ 6.9.2005, 08:59)

Без ox код еще смешнее(add eax,1 - это круто!)

Чего ржешь? Сколько я помню, на NetBurst это быстрее, чем inc eax.
А вообще, преимущество компилятора хотя бы в том, что он (если он нормальный) помнит латентности всех инструкций, чего человек физически не может. Зуб даю, что на любом мало-мальски объемном коде, ручная оптимизация, сравнимая по эффективности с тем, что сделают ICC или MSVC, либо невозможна, либо займет очень много сил и времени.

Цитата(Mayk @ 6.9.2005, 08:59)

Нее, оптимизация компиляторов - это фантастика

Прогони один и тот же код на VC 7.1 с -Od и с -Ox - тогда посмотрим, какая это фантастика

Цитата

Компилятор не догадался перевернуть цикл в орбатном направлении, дабы заюзать loop, хотя догадался взять ecx в кач-ве счетчика.

В общем случае loop медленнее банального dec ecx + jnz, т.к. loop - операция комплексная, для её декодирования приходиться юзать ПЗУ микрокодов... Хотя иногда, когда до loop стоят тормозные операции, loop не даст тормоза, выполнится за то же время, что и dec+jnz.

Цитата

Чего ржешь?  Сколько я помню, на NetBurst это быстрее, чем inc eax.

Рекомендуется использовать add/sub вместо inc/dec, т.к. inc/dec модифицируют лишь часть флагов, поэтому для записи в регистр флагов нужно ждать завершения предыдущей операции, влияющей на флаги. Sub/add же модифицируют все флаги, поэтому им ждать ничего не надо, нет ложной зависимости от предыдущих операций... Если же зависимости нет, то смело можно юзать inc/dec они выполнятся быстрее, чем add/sub.

Вобщем, то что на первый взгляд кажется тормознутым, на деле может оказаться шустрее "оптимального" кода, т.к. в дело вступают всякие "хитрости" современных процов...
Рекомендую книжку от Intel'а "IA-32 Architecture Optimization Reference Manual". Я её (и не только эту) когда-то давно заказал с их сайта, совершенно бесплатно с доставкой на дом (до меня шло полгода )

А вообще тема интересная . Жаль только что я не сишник...