Практическая польза fast-типов

Vladimir
Опубликовано в: C/C++

Как замена uint32_t на uint_fast32_t позволяет достичь хорошего прироста скорости

В данной статье речь пойдёт о типах int_fastXX_t/uint_fastXX_t из stdint.h.

Мне было интересно потестировать параллельную реализацию шифрования алгоритмом ГОСТ 28147–89 на многоядерных процессорах (с использованием OpenMP, но это тема для отдельной статьи).

Как известно, ГОСТ 28147–89 — блочный шифр, оперирующий 64-битными (uint64_t) блоками. При выполнении зашифрования в режиме простой замены открытый текст разбивается на две половины (uint32_t). В принципе, это всё, что пока нужно знать :-)

Те, кто знакомы с особенностями архитектур 32- и 64-битных процессоров, знают, что 32-битные процессоры быстрее обрабатывают 32-битные числа, а 64-битные — соответственно, 64-битные.

В стандарте C99 языка C в файле <stdint.h> определены так называемые "быстрые типы": int_fast8_t, int_fast16_t, int_fast32_t, int_fast64_t, uint_fast8_t, uint_fast16_t, uint_fast32_t и uint_fast64_t.

Тип (u)int_fastXX_t определяет наиболее быстродействующий (без)знаковый тип, имеющий как минимум XX бит. Например, для 32-битных процессоров uint_fast32_t = uint32_t, а для 64-битных — uint_fast32_t = uint64_t (ибо, как уже говорилось выше, 64-битный процессор обрабатывает 64-битные числа быстрее, нежели 32-битные).

А теперь собственно о практической пользе. Раунд зашифрования по ГОСТ 28147–89 имеет следующий вид:

[-]
View Code C
    uint32_t* k;
    uint32_t a;
    uint32_t b;
    uint32_t t;

    static uint32_t gost_data_1[256], gost_data_2[256], gost_data_3[256], gost_data_4[256];

// ...

    t  = a + k[0];
    b ^= gost_data_1[(uint8_t)t] ^ gost_data_2[(uint8_t)(t >> 8)] ^ gost_data_3[(uint8_t)(t >> 16)] ^ gost_data_4[t >> 24];

    t = b + k[1];
    a ^= gost_data_1[(uint8_t)t] ^ gost_data_2[(uint8_t)(t >> 8)] ^ gost_data_3[(uint8_t)(t >> 16)] ^ gost_data_4[t >> 24];

Обращу внимание на явное приведение индекса массива к типу uint8_t: в случае с gcc это быстрее, чем t & 0xFF.

При таком коде зашифрование 100 МиБ случайного бинарного мусора (из /dev/urandom) на процессоре AMD Athlon™ 64 X2 Dual Core Processor 5400+ занимает в среднем 1.85 сек (при сборке кода с опциями gcc -O3 -mtune=native -fomit-frame-pointer), что соответствует примерно 54.1 МиБ/сек.

Если же заменить uint32_t на uint_fast32_t, получим среднее время выполнения 1.62 сек, что соответствует примерно 61.7 МиБ/сек.

Итого: выигрыш составил 7.6 МиБ/сек, что не так уж и мало, если приходится на лету шифровать гигабайты информации (на 10 ГиБ разница составляет порядка 23 сек).

Добавить в закладки

Связанные записи

20
Март
2009

Комментарии к статье «Практическая польза fast-типов» (4)  »

  1. Vladimir says:

    На четырёхядерном процессоре Intelⓡ Xeonⓡ CPU X3320 @ 2.50GHz получилась такая картина:

    uint32_t: 2.1 сек, 47.6 МиБ/сек
    uint_fast32_t: 1.8 сек, 55.6 МиБ/сек

    Выигрыш: 8 МиБ/сек

    Сборка с ключами -O3 -fomit-frame-pointer -march=nocona

  2. Vladimir says:

    AMD Phenom™ II X4 940 @ 3GHz:

    uint32_t: 1.7 сек, 58.8 МиБ/сек
    uint_fast32_t: 1.4 сек, 71.4 МиБ/сек

    Выигрыш: 12,7 МиБ/сек

    Сборка с ключами -O3 -fomit-frame-pointer -march=amdfam10

  3. [...] было проверить генерируемый код при использовании быстрых типов: для этого я заменил uint32_t на uint_fast32_t и собрал 64-битную [...]

  4. Vladimir says:

    AMD Phenom™ II X4 940 @ 3GHz:

    uint_fast32_t, параллельная реализация: 268.8 МиБ/сек

Подписаться на RSS-ленту комментариев к статье «Практическая польза fast-типов» Trackback URL: http://blog.sjinks.org.ua/c-cpp/519-practical-use-of-fast-types/trackback/

Оставить комментарий к записи «Практическая польза fast-типов»

Вы можете использовать данные тэги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Оставляя комментарий, Вы выражаете своё согласие с Правилами комментирования.

Подписаться, не комментируя