int128 на C++

sergeyyankovich2@tut.by
sergeyyankovich2@tut.by

Я считаю, что int128 точно должен быть в C++. Так же как и возможность реализовать деление 128-битного на 64-битное целое,
с помощью одной div команды процессора (после компиляции),
и умножение двух 64-битных с получением 128-битного целого, с помощью одной mul команды процессора (после компиляции).

Если компилятор не поддерживает то, что поддерживает процессор - это огромный пробел компилятора.

Не раз сталкивался с подобным мнением.

 

Реализация на уровне компилятор не должна быть сложнее реализации __int64,  для  32-битных систем, которая существует уже давно.

 

Преимущества -

Любая длинная арифметка, всякие задачи факторизации и другие,  будут работать на порядок быстрее, если
использовать один mul-div , вместо "простыни иструкций процессора", либо разбиении длинных целых на меньшие "порции" по int32. Причём разница (соотношение производительностей), с увеличением длины используемых чисел -
растёт с экспоненциальной зависимостью.

 

1
рейтинг
7 комментариев
Виктор Губин

Посмотрите суда:

Unbounded integers:  https://stdcpp.ru/proposals/33ecfae3-7382-44bb-8b2f-4e599faf7e98

int128_t, int256_t, и т.д. https://stdcpp.ru/proposals/531b7d66-037b-48b7-8262-eb9c0c1f7535

Виктор Губин
Antervis

я конечно плоховато знаю ассемблер, но как реализовать целочисленное 128-битное деление "одной командой процессора"?

Antervis
Виктор Губин

Antervis, Intel/AMD начиная с SSE2 SIMD . В современных процессорах Intel через AVX).

Компиляторы давно поддерживают процессоры, но как-то по разному

GCC  https://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html

MS МС++ - https://msdn.microsoft.com/en-us/library/26232t5c.aspx

Intel C++  https://software.intel.com/en-us/articles/introduction-to-intel-advanced-vector-extensions

Виктор Губин
Antervis

Виктор Губин, во-первых, команд целочисленного деления в SSE/AVX попросту нет. Во-вторых, SIMD деление реализуется через каст в float/double, деление и каст обратно. Вещественное 128-битное деление процессоры тоже не умеют. Мой вопрос был риторическим.

Antervis
Виктор Губин

Antervis,

Поигрался тут малость с GCC, что-бы посмотреть что собсвенно происходит на ассемблерном уровне.

Т.е. соводит-ли компилятор деление к умножению, при зарание известном делителе, как в случае с int[8..64]_t

Вот так выглядит код:

#include <cstdio>
#include <cstdint>

constexpr const unsigned __int128 radix = 10;

int main()
{

    char str[43];
    __builtin_memset(str, 0, 43 );

    unsigned __int128 octoword = __UINT64_MAX__;
    octoword <<= 8;

    uint8_t divend;
    char *c = &str[42];
    do {
        divend = uint8_t(octoword % radix);
        octoword /= 10ULL;
        * (c--) = '0' + divend;
    } while(0 != octoword );

    __builtin_memmove( str, (c+1), std::size_t(&str[42] - c)  );

    std::printf( str );
    return 0;
}

Если скомпилировать с ключами -mtune=native -Ofast -mavx -S получим ассемблерный вывод.

Похоже что  GCC переклыдывает деление 128-ми битных целых вообще на библиотеку, в случае с Intel (Windows GCC 7.2), имеем:

...

call    __umodti3

...

call    __udivti3

И того получим в итоге не самый быстрый код,  деление идет не только не одной инструкцией, но еще и перекидывает процессор в другие области памяти - возможно за кеш.

В общем пока стандарта длинной арифметики нет, имеет смысл критические алгоритмы писать на ассемблере и "подлинковывать".

Виктор Губин
sergeyyankovich2@tut.by

я конечно плоховато знаю ассемблер, но как реализовать целочисленное 128-битное деление "одной командой процессора"?

 

Если деление 128-битного числа на 128-битное, то в случае делителся не больше чем

2^64-1 - процессор делает одной командой. Уже в этом выигрыш есть по производительности.  Если делитель больше, тогда  компилятор реализует деление как вызов некой встроенной функции на асемблере.

В принципе, подобное было, когда существовали 32-битные компьютеры, а в c++ уже были типы  __int64.

А __int128  уже даже зарезервировали как особенное определение в Visual Studio, оно даже другим цветом подствечивается. Но в стандарт языка C++ пока не входит. 

Хотя уже многие предлагали, я далеко не первый.

 

 

sergeyyankovich2@tut.by
sergeyyankovich2@tut.by

И того получим в итоге не самый быстрый код,  деление идет не только не одной инструкцией, но еще и перекидывает процессор в другие области памяти - возможно за кеш.

Так это GCC. Кто сказал, что в GCC - лучший компилятор?  Или может у вас x86 режим

в GCC ?  Дизасм показывает, что используются регистры rax-rbx и т.д.,  или  eax-ebx и т.д.?

 

Вот если в студии 2015 дизассемблировать такой код -

#include <intrin.h> 
#pragma intrinsic(_umul128) 

 

// .....

unsigned __int64 aaa = 1111222333444555666;

unsigned __int64 bbb = 1111222333444555;

unsigned __int64 c, d;
d = _umul128(aaa, bbb, &c);

 

то последняя  функция преобразуется вот во что --


        //00007FF7D9005F77  mov         rax, qword ptr[aaa]
        //00007FF7D9005F7B  mov         qword ptr[rbp + 178h], rax
        //00007FF7D9005F82  mov         rcx, qword ptr[bbb]
        //00007FF7D9005F86  mov         rax, rcx
        //00007FF7D9005F89  mov         rcx, qword ptr[rbp + 178h]
        //00007FF7D9005F90  mul         rax, rcx
        //00007FF7D9005F93  mov         qword ptr[c], rdx
        //00007FF7D9005F97  mov         qword ptr[d], rax

 

Есть один вызов  mul,  умножаются  64-битное на 64-битное, с получение

128-битного результата.  Не знаю почему, но для  деления 128-битного целого (находится в регистрах  RDX:RAX) на 64-битный делитель,

подобной  intrinsic-функции  нет.

 

Главное же, что при введении в стандарт  C++, __int128,  лучшее и наибыстрейшее использование будет реализовано уже на уровне компилятора, ну и как я писал,

будут свои преимущества -

 

Любая длинная арифметка, всякие задачи факторизации и другие,  будут работать на порядок быстрее, если
использовать один mul-div , вместо "простыни иструкций процессора", либо разбиении длинных целых на меньшие "порции" по int32. Причём разница (соотношение производительностей), с увеличением длины используемых чисел -
растёт с экспоненциальной зависимостью. 

 

И возможности 64-битного процессора будут использоваться наиболее полно.

 

sergeyyankovich2@tut.by
Обновлено 
Другие идеи
Группа создана, чтобы собирать предложения к стандарту C++, организовывать их внутренние обсуждения, помогать готовить их для отправки в комитет и защищать на общих собраниях в рабочей группе по С++ Международной организации по стандартизации (ISO).
Все предложения