1. Си / Говнокод #25334

    +3

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    void add_SSE(uint8_t a[static 7], uint8_t b[static 7], uint8_t out[static 7])
    {
      uint64_t a_64 = 0;
      uint64_t b_64 = 0;
      for (size_t i = 0; i < 7; i++) // можно наанроллить
      {
        a_64 |= (uint64_t)a[i] << (i*9);
        b_64 |= (uint64_t)b[i] << (i*9);
      }
      
      uint64_t c_64 = a_64 + b_64;
      
      for (size_t i = 0; i < 7; i++) // можно наанроллить
      {
        out[i] = (uint64_t)c_64 >> (i*9);
      }
    }

    SSE

    Запостил: j123123, 28 Января 2019

    Комментарии (32) RSS

    • Наанроллил тебе за щщеку. Проверь:
      : ?>
        BEGIN
          SOURCE >IN @ /STRING 2DUP
          S" <?" SEARCH NIP
          IF
            NIP OVER -
            DUP 2 + >IN +!
            STATE @ IF
              POSTPONE SLITERAL
              ['] TYPE COMPILE,
            ELSE
              TYPE
            THEN
            TRUE
          ELSE
            DROP 
            STATE @ IF
              POSTPONE SLITERAL
              ['] TYPE COMPILE,
              ['] CR COMPILE,
            ELSE
              TYPE CR
            THEN
            REFILL 0=
          THEN
        UNTIL
      ; IMMEDIATE
      
      :noname ?>
      void add_SSE(uint8_t a[static 7], uint8_t b[static 7], uint8_t out[static 7])
      {
        uint64_t a_64 = 0;
        uint64_t b_64 = 0;
        <? 7 0 do ?>
          a_64 |= (uint64_t)a[ <? i . ?> ] << ( <? i . ?> *9);
          b_64 |= (uint64_t)b[ <? i . ?> ] << ( <? i . ?> *9);
        <? loop ?>
        
        uint64_t c_64 = a_64 + b_64;
        
        <? 7 0 do ?>
          out[ <? i . ?> ] = (uint64_t)c_64 >> ( <? i . ?> *9);
        <? loop ?>
      } <? ; execute
      https://ideone.com/BFhcDA
      Ответить
      • #include <stdio.h>
        #include <stdlib.h>
        #include <inttypes.h>
        
        int main(void)
        {
          puts(
        R"(void add_SSE(uint8_t a[static 7], uint8_t b[static 7], uint8_t out[static 7])
        {
          uint64_t a_64 = 0;
          uint64_t b_64 = 0;)"); // raw string literal
        
          for (size_t i = 0; i < 7; i++) // анроллим
          {
            printf("  a_64 |= (uint64_t)a[%zu] << (%zu*9);\n", i, i);
            printf("  b_64 |= (uint64_t)b[%zu] << (%zu*9);\n", i, i);
          }
        
          puts("  uint64_t c_64 = a_64 + b_64;");
        
          for (size_t i = 0; i < 7; i++) // анроллим
          {
            printf("  out[i] = (uint64_t)c_64 >> (%zu*9);\n", i);
          }
          puts("}");
          return 0;
        }

        https://wandbox.org/permlink/y5oFcXGjMxDTh5KW
        Ответить
        • а теперь напиши на m4 который который это генерит
          Ответить
          • divert(-1)
            define(`SIGNATURE', `void add_SSE(uint$1_t $2[static decr($1)], uint$1_t $3[static decr($1)], uint$1_t $4[static decr($1)])')
            define(`MAKE_VAR', `uint$1_t $2_$1 = 0;')
            define(`MUXSHIFT', `$1_$4 |= (uint$4_t)$1[$2] << ($2*incr($3));')
            define(`DEMUXSHIFT', `$5[$1] = (uint$3_t)$4_$3 >> ($1*incr($2));')
            define(`LOOP1', `ifelse(`$1', 0,, `LOOP1(decr($1), $2, $3, $4, $5)dnl
              MUXSHIFT($4, $1, $2, $3)
              MUXSHIFT($5, $1, $2, $3)
            ')')
            define(`LOOP2', `ifelse(`$1', 0,, `LOOP2(decr($1), $2, $3, $4, $5)dnl
              DEMUXSHIFT($1, $2, $3, $4, $5)
            ')')
            define(`MAKE_SUM', `uint$1_t $4_$1 = $2_$1 + $3_$1;')
            divert(0)dnl
            SIGNATURE(8, `a', `b', `out') {
              MAKE_VAR(64, `a')
              MAKE_VAR(64, `b')
            LOOP1(8, 8, 64, `a', `b')dnl
              MAKE_SUM(64, `a', `b', `c')
            LOOP2(8, 8, 64, `c', `out')dnl
            }
            Ответить
            • Я немного напутал. В некоторых местах decr пропустил. Вот так будет лучше:
              divert(-1)
              define(`SIGNATURE', `void add_SSE(uint$1_t $2[static decr($1)], uint$1_t $3[static decr($1)], uint$1_t $4[static decr($1)])')
              define(`MAKE_VAR', `uint$1_t $2_$1 = 0;')
              define(`MUXSHIFT', `$1_$4 |= (uint$4_t)$1[$2] << ($2*incr($3));')
              define(`DEMUXSHIFT', `$5[$1] = (uint$3_t)$4_$3 >> ($1*incr($2));')
              define(`LOOP1', `ifelse(`$1', 0,, `LOOP1(decr($1), $2, $3, $4, $5)dnl
                MUXSHIFT($4, decr($1), $2, $3)
                MUXSHIFT($5, decr($1), $2, $3)
              ')')
              define(`LOOP2', `ifelse(`$1', 0,, `LOOP2(decr($1), $2, $3, $4, $5)dnl
                DEMUXSHIFT(decr($1), $2, $3, $4, $5)
              ')')
              define(`MAKE_SUM', `uint$1_t $4_$1 = $2_$1 + $3_$1;')
              divert(0)dnl
              SIGNATURE(8, `a', `b', `out') {
                MAKE_VAR(64, `a')
                MAKE_VAR(64, `b')
              LOOP1(8, 8, 64, `a', `b')dnl
                MAKE_SUM(64, `a', `b', `c')
              LOOP2(8, 8, 64, `c', `out')dnl
              }
              Ответить
              • Запишем более общий вариант:
                divert(-1)
                define(`SIGNATURE', `void add_SSE$1x$2(uint$2_t $3[static decr($1)], uint$2_t $4[static decr($1)], uint$2_t $5[static decr($1)])')
                define(`MAKE_VAR', `uint$1_t $2_$1 = 0;')
                define(`MUXSHIFT', `$1_$4 |= (uint$4_t)$1[$2] << ($2*incr($3));')
                define(`DEMUXSHIFT', `$5[$1] = (uint$3_t)$4_$3 >> ($1*incr($2));')
                define(`LOOP1', `ifelse(`$1', 0,, `LOOP1(decr($1), $2, $3, $4, $5)dnl
                  MUXSHIFT($4, decr($1), $2, $3)
                  MUXSHIFT($5, decr($1), $2, $3)
                ')')
                define(`LOOP2', `ifelse(`$1', 0,, `LOOP2(decr($1), $2, $3, $4, $5)dnl
                  DEMUXSHIFT(decr($1), $2, $3, $4, $5)
                ')')
                define(`MAKE_SUM', `uint$1_t $4_$1 = $2_$1 + $3_$1;')
                define(`MAKE_FUNC', `SIGNATURE($1, $2, `a', `b', `out') {
                define(`CONTAINER', eval($1 * $2))dnl
                  MAKE_VAR(CONTAINER, `a')
                  MAKE_VAR(CONTAINER, `b')
                LOOP1($1, $2, CONTAINER, `a', `b')dnl
                  MAKE_SUM(CONTAINER, `a', `b', `c')
                LOOP2($1, $2, CONTAINER, `c', `out')dnl
                undefine(`CONTAINER')dnl
                }')
                divert(0)dnl
                typedef __int128 int128_t;
                typedef unsigned __int128 uint128_t;
                
                MAKE_FUNC(4, 8)
                MAKE_FUNC(8, 8)
                MAKE_FUNC(16, 8)
                
                MAKE_FUNC(4, 16)
                MAKE_FUNC(8, 16)
                
                MAKE_FUNC(4, 32)
                Ответить
                • Фрагмент выхлопа моего кода:
                  void add_SSE4x8(uint8_t a[static 3], uint8_t b[static 3], uint8_t out[static 3]) {
                    uint32_t a_32 = 0;
                    uint32_t b_32 = 0;
                    a_32 |= (uint32_t)a[0] << (0*9);
                    b_32 |= (uint32_t)b[0] << (0*9);
                    a_32 |= (uint32_t)a[1] << (1*9);
                    b_32 |= (uint32_t)b[1] << (1*9);
                    a_32 |= (uint32_t)a[2] << (2*9);
                    b_32 |= (uint32_t)b[2] << (2*9);
                    a_32 |= (uint32_t)a[3] << (3*9);
                    b_32 |= (uint32_t)b[3] << (3*9);
                    uint32_t c_32 = a_32 + b_32;
                    out[0] = (uint32_t)c_32 >> (0*9);
                    out[1] = (uint32_t)c_32 >> (1*9);
                    out[2] = (uint32_t)c_32 >> (2*9);
                    out[3] = (uint32_t)c_32 >> (3*9);
                  }
                  void add_SSE8x8(uint8_t a[static 7], uint8_t b[static 7], uint8_t out[static 7]) {
                    uint64_t a_64 = 0;
                    uint64_t b_64 = 0;
                    a_64 |= (uint64_t)a[0] << (0*9);
                    b_64 |= (uint64_t)b[0] << (0*9);
                    a_64 |= (uint64_t)a[1] << (1*9);
                    b_64 |= (uint64_t)b[1] << (1*9);
                    a_64 |= (uint64_t)a[2] << (2*9);
                    b_64 |= (uint64_t)b[2] << (2*9);
                    a_64 |= (uint64_t)a[3] << (3*9);
                    b_64 |= (uint64_t)b[3] << (3*9);
                    a_64 |= (uint64_t)a[4] << (4*9);
                    b_64 |= (uint64_t)b[4] << (4*9);
                    a_64 |= (uint64_t)a[5] << (5*9);
                    b_64 |= (uint64_t)b[5] << (5*9);
                    a_64 |= (uint64_t)a[6] << (6*9);
                    b_64 |= (uint64_t)b[6] << (6*9);
                    a_64 |= (uint64_t)a[7] << (7*9);
                    b_64 |= (uint64_t)b[7] << (7*9);
                    uint64_t c_64 = a_64 + b_64;
                    out[0] = (uint64_t)c_64 >> (0*9);
                    out[1] = (uint64_t)c_64 >> (1*9);
                    out[2] = (uint64_t)c_64 >> (2*9);
                    out[3] = (uint64_t)c_64 >> (3*9);
                    out[4] = (uint64_t)c_64 >> (4*9);
                    out[5] = (uint64_t)c_64 >> (5*9);
                    out[6] = (uint64_t)c_64 >> (6*9);
                    out[7] = (uint64_t)c_64 >> (7*9);
                  }
                  Ответить
                  • P.S. Наглючил. Мы же последний элемент не трогаем, он полностью не вмещается в базовый тип. У нас временные «байты» девятибитные, чтобы вместить разряд переноса. Значит, там нужно ещё с декрементом пошаманить, чтобы цикл был короче на одну итерацию. И названия функций тогда подкорректировать (3 вместо 4; 7 вместо 8; 15 вместо 16).
                    Ответить
                    • Сдвиги, имхо, надо убрать в отдельные функции load и store как в настоящем SSE. Тогда можно будет один раз упаковать число, сделать над упакованным вектором много операций и в конце один раз распаковать. Тогда может и будет какой-то профит.
                      Ответить
                      • Ещё можно сделать разные варианты упаковки:
                        1. Упаковка для побитовых операций.
                        2. Упаковка для сложения: каждое число будет расширено на один бит.

                        Последний вариант ещё может быть знаковым и беззнаковым.

                        А ещё можно упаковать для умножения на скаляр, тогда каждое число будет расширено в два раза.
                        Ответить
                        • Ну в два раза проще всего. j123123 ниже как раз так и сделал.
                          Ответить
                          • Кстати, на каких платформах в Гэцэцэ и в Шланге есть тип __int128? Документация об этом молчит. Видимо, власти приказали это скрывать.

                            P.S. Тут чувак накостылил __int128 через перегрузку операторов:
                            https://stackoverflow.com/a/37907522
                            Ответить
                            • Костылить - так универсально. integer<128>.
                              Ответить
                              • Почему только integer? А плавающий питух? А кококококомплексные числа?
                                Ответить
                              • Это кстати хотят пропихнуть в крестоговностандарт, вон какие-то пропозалы пишут https://habr.com/ru/company/yandex/blog/327080/

                                Лучше б сделали тупо произвольно-длинную арифметику, потом бы запилили специализацию под конечный размер. И тогда для произвольно-длинной арифметики можно было б сделать всякие умные оптимизации, типа
                                a*n+b*n+c*n = n*(a+b+c)

                                Только вот это нихера не выйдет с говном, которое есть в крестопомойной параше (разве что компилятор допилить специально под эту дрисню). Шаблонами нельзя определять всякие свойства коммутативности, ассоциативности и стратегии оптимизации.
                                Ответить
                                • Напомните мне, придумали ли управление ленивостью у перегруженных операторов || и &&.
                                  Ответить
                                • >> Предложение отказаться от привязки к количеству бит, а задавать количество машинных слов, мне показалось самым странным: бизнес-логике всё равно, сколько слов в числе на какой-то платформе, — ей важно однозначно определять одни и те же числа на разных платформах. Скажем, уникальный идентификатор пользователя — беззнаковое целое число из 64 бит, а не из одного unsigned long long.

                                  >> В частности, комиссия всё-таки попросила в wide_int оперировать количеством машинных слов.

                                  Вот уроды. Они хотят, чтобы при перекококомпиляции на другой платформе программа оперировала числами другого размера? Т. е. опять придётся потеть с мокросами и ифдефами?
                                  Ответить
                                • Начал копать ссылки:
                                  https://stdcpp.ru/proposals/7ade694d-61bb-4ebe-ba89-93ea3ae03b3c


                                  Из 64-битного MSVC убрали встроенный асм, так что приходится использовать интринсики. Интринсики –— хорошая штука, так как на первый взгляд позволяют писа́ть код, не привязанный к кокококонкретному процессору. Однако, они оказались привязанными к кокококомпилятору:
                                  unsigned char _BitScanReverse(unsigned long * Index, unsigned long Mask); // MSVC x86 and ARM, Intel C Compiler
                                  unsigned int _arm_clz(unsigned int _Rm); // MSVC ARM
                                  unsigned int __lzcnt(unsigned int); // MSVC x86
                                  int __builtin_clz (unsigned int x); // GCC and clang - on any supported processor (?)
                                  int __builtin_ffs (unsigned int x); // GCC and clang - on any supported processor (?)
                                  unsigned int __clz(uint32_t x); // ARM C Language Extensions (ACLE) - supported by GCC (clang?)

                                  Причём даже семантика не совпадает:
                                  FFS(x) = x ? 1 + BSR(x) : 0
                                  CLZ(x) = 8*sizeof(x) - FFS(x)

                                  Полная жопа, короче.
                                  Ответить
                                  • То ли дело «Паскаль»:
                                    type
                                      bitnum = 0..63;
                                      set64 = set of bitnum;
                                    
                                    function BT(x: uint64; n: bitnum): boolean;
                                    var
                                      tempset: set64 absolute x;
                                    begin
                                      BT := n in tempset
                                    end;
                                    
                                    function BTS(var x: uint64; n: bitnum): boolean;
                                    var
                                      tempset: set64 absolute x;
                                    begin
                                      BTS := n in tempset;
                                      tempset := tempset + [1 shl n]
                                    end;
                                    
                                    function BSR(x: uint64): bitnum;
                                    var
                                      tempset: set64 absolute x;
                                      i: bitnum;
                                    begin
                                      for i in tempset do
                                        begin
                                          BSR := i;
                                          break;
                                        end;
                                    end;


                                    https://ideone.com/JQJ5wk

                                    «Интринсинки» для BT, BTR, BTS, BTC, BSR (или их эмуляцию) можно записа́ть через множества.

                                    Жаль, с BSF такой трюк не выходит: цикл перечисляет элементы множества только начиная с меньших, поэтому придётся гонять полный цикл. Функции High и Low возвращают наибольший и наименьший элементы всего пространства (выбранного типа), а не текущего множества, поэтому тоже не годятся.
                                    Ответить
                                    • Выхлоп кококомпилятора:
                                      ; [9] BT := n in tempset
                                      		and	eax,255
                                      		bt	dword ptr [ebp+8],eax
                                      ; Var $result located in register al
                                      		setc	al


                                      Оператор in выполняется через инструкции BT и SETC. Вот с добавлением элемента хуже (оптимизатор не хочет выкидывать call fpc_varset_add_sets; видимо, задел для больших множеств) и цикл не хочет выкидывать, хотя задача должна решаться одной итерацией. Оптимизатор –— питух.
                                      Ответить
                                      • В «fpc» сделали хреново (только BT задействована). Надо посмотреть, как в реализовали в других кокококомпиляторах.
                                        Ответить
                                        • В «Delphi» (включая «XE») и в заброшенном «Virtual Pascal» используется только инструкция BT, как и во «Фрипаскале».

                                          «GPC» (ныне заброшен) использует вызов библиотечной функции (call __p_set_in).

                                          «TMT Pascal» (похоже, что тоже заброшен) тоже всё делает через вызов библиотечных функций и инлайнить не хочет.

                                          «WDSibyl» мне не удалось даже запустить.

                                          Компиляторы, основанные не на «Object Pascal», а на «Standard Pascal» или «Extended Pascal», я не тестировал.

                                          Итого: ныне развивающиеся компиляторы в нативный код («Delphi» и «FPC») при работе со множествами из специнструкций используют только BT.
                                          Ответить
                                          • Кто знает статически тупизированные ЯП со множествами, кроме «Паскаля»?
                                            Ответить
                                            • чем тебе Set не множество?

                                              Set от enum или кококок sealed
                                              Ответить
                                          • >WDSibyl
                                            у тебя просто OS/2 старая
                                            Ответить
                                            • А у тебя поди последняя версия «eComstation»?
                                              Ответить
                                              • в жопу ёё
                                                там xHCI не поддржвц

                                                без УЗБ три нуль нет мгне жизни
                                                Ответить
                                    • >> tempset := tempset + [1 shl n]

                                      Фигню написал. Надо просто tempset := tempset + [n]. Сдвиг не нужен.

                                      Всё равно использует только BT, а установку/сброс делает через сдвиг + OR/XOR.
                                      Ответить
                              • И тогда Тойо спросил: "Учитель, а как будет звучать хлопок одной ладо integer<129>" ?
                                Ответить
                                • 3 блока по 64 или 5 блоков по 32. Ну и масочки.
                                  Ответить
    • Что-то мне намекает, что тут упаковка будет дольше поштучного сложения. Надо её отделить от вычислений и делать один раз в начале кода.
      Ответить
      • Если тебя интересует практичный вариант, то наверно лучше так:
        void add_SSE(uint8_t a[static 8], uint8_t b[static 8], uint8_t out[static 8])
        {
          uint64_t a_64;
          uint64_t b_64;
          memcpy(&a_64, a, sizeof(a_64));
          memcpy(&b_64, b, sizeof(b_64));
          uint64_t a_00FF_64 = a_64 & 0x00FF00FF00FF00FFULL;
          uint64_t b_00FF_64 = b_64 & 0x00FF00FF00FF00FFULL;
          uint64_t a_FF00_64 = a_64 & 0xFF00FF00FF00FF00ULL;
          uint64_t b_FF00_64 = b_64 & 0xFF00FF00FF00FF00ULL;
        
          uint64_t c_64 =
          ((a_00FF_64 + b_00FF_64) & 0x00FF00FF00FF00FFULL) |
          ((a_FF00_64 + b_FF00_64) & 0xFF00FF00FF00FF00ULL);
          memcpy(out, &c_64, sizeof(b_64));
        }


        Хотя тут теперь два сложения на 8 элементов (против одного сложения на 7 элементов), думаю что на сдвигах проебется больше времени.
        Ответить

    Добавить комментарий