Есть ли 256-битный целочисленный тип?

ОС: Linux (Debian 10)

CC: GCC 8.3

Процессор: i7-5775C

В GCC есть _1 _ / _ 2_, но есть ли способ иметь _3 _ / _ 4_ в GCC?

Я читал о __m256i, похоже, от Intel. Есть ли какой-нибудь заголовок, который я могу добавить, чтобы получить его?

Это так же удобно, как гипотетический unsigned __int256? Я имею в виду, если вы можете назначать от / к нему, сравнивать их, побитовые операции и т. Д.

Каков его знаковый эквивалент (если есть)?

ИЗМЕНИТЬ 1:

Я добился этого:

#include <immintrin.h>
typedef __m256i uint256_t;

и скомпилирован. Если я смогу поработать с ним, я обновлю его здесь.

ИЗМЕНИТЬ 2:

Обнаружены проблемы:

uint256_t   m;
int         l = 5;

m = ~((uint256_t)1 << l);

вывод:

error: can’t convert a value of type ‘int’ to vector type ‘__vector(4) long long int’ which has different size
  m = ~((uint256_t)1 << l);

gcc c x86-64 bigint extended-precision
person alx    schedule 22.04.2019    source источник
comment
конечно, вы не можете просто использовать __m256i как целочисленный тип, потому что это не целочисленный тип, а вектор, как упоминалось в выводе ошибки. См. Можно ли использовать SSE и SSE2 для создания целого числа шириной 128 бит?, Интегрированная инструкция SIMD AVX в C, возможно использование BigNum AVX / SSE на практике ?   -  person phuclv    schedule 23.04.2019
comment
если вам нужен просто 256-битный тип int, существует множество дубликатов 128/256-битных целочисленных типов фиксированного размера , Представление 128-битных чисел в C ++, C ++: как сохранить 256-битное число и как преобразовать его в шестнадцатеричное? ...   -  person phuclv    schedule 23.04.2019
comment
@phuclv Все эти вопросы касаются C ++. Я посмотрю на них, чтобы увидеть, пригодится ли что-нибудь в C.   -  person alx    schedule 23.04.2019

Ответы (2)


arrow_upward
9
arrow_downward

Clang имеет _ExtInt расширенные целые числа, который поддерживает операции, отличные от деления, но SIMD для этого бесполезен из-за переноса между элементами. В других основных компиляторах x86-64 этого нет; вам нужна библиотека или что-то еще, чтобы определить настраиваемый тип и использовать те же инструкции добавления с переносом, которые будут использовать clang. (Или менее эффективная эмуляция на чистом C 1).

__m256i - это AVX2 SIMD 4x uint64_t (или более узкий размер элемента, например 8x uint32_t). Это не 256-битный скалярный целочисленный тип, вы не можете использовать его для скалярных операций, __m256i var = 1 даже не будет компилироваться. Нет поддержки x86 SIMD для целых чисел шире 64-бит, а внутренние типы Intel, такие как __m128i и __m256i, предназначены исключительно для SIMD.

GCC __int128 / unsigned __int128 обычно использует скаляр add/adc и / или скаляр mul / imul, потому что AVX2 обычно не помогает для повышенной точности. (Только для таких вещей, как побитовое И / ИЛИ / XOR, где границы элементов не имеют значения.)

Сноска 1: К сожалению, C не обеспечивает перенос из сложения / вычитания, поэтому писать на нем даже неудобно. sum = a+b / carry = sum<a работает для выполнения, когда нет переноса, но гораздо сложнее написать полный сумматор на C .И компилятор обычно делает дерьмовый asm, который не просто использует собственные инструкции добавления с переносом на машинах, где они доступны. Библиотеки повышенной точности для очень больших целых чисел, такие как GMP, обычно пишутся на asm.

person Peter Cordes    schedule 22.04.2019
comment
Но нельзя ли использовать это __m256i в моем коде? Я имею в виду, как __m256i var1 = 0x7u; __m256i var2 = 0x8u; __m256i var3 = var2 & var1; - person alx; 23.04.2019
comment
@CacahueteFrito нет, __m256i предназначен для AVX2, который не является одним 256-битным целым числом - person phuclv; 23.04.2019
comment
@CacahueteFrito __m256i - это в основном целые числа 8 x 32 бит (и некоторые другие варианты). Эти 8 целых чисел в основном являются отдельными переменными. Смешивание и сопоставление этих целых чисел (как вам потребуется для добавления с переносом) приводит к снижению производительности. Связь по 2x 128-битным полосам в этом типе еще дороже. Вам нужно будет найти библиотеку C ++, которая обрабатывает большие int с использованием стандартных 64-битных / 32-битных целочисленных типов. - person robthebloke; 23.04.2019
comment
Вам нужна библиотека, в которой используется надстройка с переносом. Вам нужна библиотека, но не важно, как она реализована. IIRC RISCV не имеет надстройки с переносом, но вы все равно можете имитировать 256-битный целочисленный тип. - person Marc Glisse; 23.04.2019
comment
@MarcGlisse: если у него изначально нет add-with-carry, ему придется его эмулировать. Но вам нужно добавить с переносом, если у вас нет собственного 256-битного типа. - person Rudy Velthuis; 23.04.2019
comment
@MarcGlisse: MIPS не имеет функции добавления с переносом, как и другие ISA без регистра флагов. Я забыл, что это может включать RISC-V. Это был вопрос x86-64 (в котором, конечно, есть adc, но я все равно расширил формулировку, так как все равно формулировал его более нейтрально для ISA. - person Peter Cordes; 24.04.2019

arrow_upward
2
arrow_downward

Мне нужен uint256_t только при вычислении f (x) = (x ^ 2 + a) mod n в алгоритме Полларда Ро. Все переменные вне функции f имеют встроенный тип __uint128_t.

Я реализовал uint256_t для этой цели просто как:

typedef __uint128_t uint256_t[2];

Затем я реализовал функции, необходимые для вычисления f ():

__uint128_t set_128(unsigned long h, unsigned long l);
void set_256(uint256_t d, __uint128_t l, __uint128_t h);
void add_128(uint256_t d, uint256_t x, __uint128_t a);
void add_256(uint256_t d, uint256_t x, uint256_t a);
void shl_256(uint256_t d, long s);
void sqr_128(uint256_t d, __uint128_t x);
several print functions and macros for printing 128bit and 256bit numbers
__uint128_t mod_256(uint256_t x, __uint128_t n);
__uint128_t f(__uint128_t x);

Найдите реализацию в этой сути:
https://gist.github.com/Hermann-SW/a20af17ee6666467fe0b5c573dae701d

Я сравнил свой код с функциями gmplib и добился ускорения по сравнению с gmplib для всех (после большой работы), подробности:
https://www.raspberrypi.org/forums/viewtopic.php?f=33&t=311893&p=1873552#p1873552

Время выполнения в наносекундах для 1 миллиона выполнений функции:
введите описание изображения здесь

person HermannSW    schedule 04.06.2021
comment
Для ваших тестов, которые показывают коэффициент ускорения 155k для простого __uint128_t, вполне вероятно, что большая часть работы была оптимизирована или выведена из цикла, но вызовы функций gmp были непрозрачны для оптимизатора. Для современного процессора Intel / AMD невозможно выполнить цикл быстрее, чем 1 итерация за такт, или сделать более 1 скаляра 64x64 = ›128-битных mul за такт. Если вы обнаружите, что ваш код работает быстрее, он фактически оптимизирован. (147 нс при 4 ГГц - это всего 588 циклов, что совершенно невероятно, чтобы сделать миллион чего-либо без огромной алгоритмической оптимизации, то есть не выполнения всей работы) - person Peter Cordes; 05.06.2021
comment
См., Например, такие вещи, как функция DoNotOptimize() в Google Benchmark, чтобы компилятор забыл, что он знает о значении. Вопросы и ответы: Предотвращение оптимизации компилятора во время тестирования / Google Benchmark Фреймворки DoNotOptimize - person Peter Cordes; 05.06.2021
comment
Однако ваше ускорение по сравнению с GMP для вашего uint256_t выглядит более правдоподобным: особенно для возведения в квадрат, три умножения и несколько добавлений не так уж и много по сравнению с общим случаем GMP с циклами переменной длины. Я все еще удивляюсь, что он такой большой, как 20; возможно, часть работы все еще оптимизирована, или, может быть, возникнут дополнительные накладные расходы GMP, если вы не используете напрямую mpn_ функции. - person Peter Cordes; 05.06.2021
comment
Вы правы, компилятор полностью оптимизировал умножения: godbolt.org/z/584f4e9o4 Я добавил переменную суммирования с префиксом s с изменчивым, и код ассемблера полностью меняется: godbolt.org/z/WdnG458E1 Ускорение умножения __uint128_t сверх gmplib mpz_mul () теперь 14694553/1497909 = 9,8 раза. - person HermannSW; 05.06.2021
comment
Я поставил перед переменной __uint128_t префикс volatile и снова запустил тест. Теперь ускорение функции uint256_t sqr () по сравнению с gmp_lib mpz_mul () составляет 17598169/3265127 = 5,39, поэтому ускорение 20 также было неправильным. - person HermannSW; 05.06.2021
comment
volatile может причинять больше, чем необходимо, вызывая дополнительные нагрузки, а также не позволяя компилятору заметить, что a_high * a_low - это то же вычисление, что и a_low * a_high, если вы не делаете этого в особом случае, а вместо этого полагаетесь на компилятор чтобы заметить избыточность при встраивании нормальной функции умножения с одинаковыми аргументами. Или просто отвлекайтесь от лишних нагрузок каждый раз, когда упоминаете a. Микробенчмаркинг сложен: вам нужно проверить asm, чтобы увидеть, соответствует ли работа в цикле именно той, которую вы хотите измерить. (Хотя DoNotOptimize может очень помочь.) - person Peter Cordes; 05.06.2021
comment
Я забыл упомянуть, что mpz_mul () также обрабатывает идентичные операнды в особых случаях (в mpz / mul.c): ... if (up == vp) {mpn_sqr (wp, up, usize); cy_limb = wp [размер - 1]; } еще ... - person HermannSW; 05.06.2021
comment
GMP - это библиотека произвольной точности, поэтому очевидно, что она намного медленнее, чем библиотеки с фиксированной точностью, такие как boost :: multiprecision :: uint256_t, github.com/calccrypto/uint256_t или ttmath: UInt ‹4›. Вместо этого вы должны сравнить с библиотеками фиксированной ширины - person phuclv; 05.06.2021
comment
Питер, вы снова правы, ведь volatile может причинить больше вреда, чем необходимо, по крайней мере, это зависит от того, где он применяется. Я сделал переменную суммирования изменчивой, и ускорение уменьшилось до 9,8 раз. Вместо этого я сделал переменные a и b изменчивыми, и теперь ускорение составляет 13,2. Это работает, как ожидалось, можно проверить, сравнив суммы, указанные в конце. Кстати, что делает clobber (потенциальное использование), я всегда делаю для суммирующих переменных путем явного использования в операторе печати ПОСЛЕ того, как время выполнения было определено, так что печать не влияет на измеренное время выполнения. - person HermannSW; 05.06.2021
comment
phuclv, я расширил свой тест производительности (суммируя 1 миллион квадратов 128-битных чисел) с помощью ttmath. Инструкции по компиляции, а также результаты тестов в sqr.cpp gist: gist.github.com/Hermann-SW / 83c8ab9e10a0bb64d770af543ed08445 К моему удивлению ttmath немного быстрее gmplib с ускорением 16054087/14803914 = 1.08. Но я выберу свой uint256_t, потому что он имеет ускорение на 16054087/2786120 = 5,76 по сравнению с gmplib! - person HermannSW; 06.06.2021
comment
Поскольку я использую 64-битный i7, ttmath :: UInt ‹4› - это 256-битное число. - person HermannSW; 06.06.2021