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

    +2

    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

    • ava Rooster 28.01.2019 20:18 # +2

      Наанроллил тебе за щщеку. Проверь:
      : ?>
  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
      Ответить

      • ava j123123 28.01.2019 23:50 # +1 

        #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
        Ответить

        • ava gueest8 29.01.2019 00:00 # 0

          а теперь напиши на m4 который который это генерит
          Ответить

          • ava JIyHHblu_nemyx 29.01.2019 15:32 # +2 

            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
}
            Ответить

            • ava JIyHHblu_nemyx 29.01.2019 15:39 # +1

              Я немного напутал. В некоторых местах 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
}
              Ответить

              • ava JIyHHblu_nemyx 30.01.2019 01:42 # 0

                Запишем более общий вариант:
                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)
                Ответить

                • ava JIyHHblu_nemyx 30.01.2019 01:46 # 0

                  Фрагмент выхлопа моего кода:
                  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);
}
                  Ответить

                  • ava JIyHHblu_nemyx 30.01.2019 01:50 # 0

                    P.S. Наглючил. Мы же последний элемент не трогаем, он полностью не вмещается в базовый тип. У нас временные «байты» девятибитные, чтобы вместить разряд переноса. Значит, там нужно ещё с декрементом пошаманить, чтобы цикл был короче на одну итерацию. И названия функций тогда подкорректировать (3 вместо 4; 7 вместо 8; 15 вместо 16).
                    Ответить

                    • ava bormand 30.01.2019 02:56 # +1

                      Сдвиги, имхо, надо убрать в отдельные функции load и store как в настоящем SSE. Тогда можно будет один раз упаковать число, сделать над упакованным вектором много операций и в конце один раз распаковать. Тогда может и будет какой-то профит.
                      Ответить

                      • ava JIyHHblu_nemyx 30.01.2019 03:17 # 0

                        Ещё можно сделать разные варианты упаковки:
                        1. Упаковка для побитовых операций.
                        2. Упаковка для сложения: каждое число будет расширено на один бит.

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

                        А ещё можно упаковать для умножения на скаляр, тогда каждое число будет расширено в два раза.
                        Ответить

                        • ava bormand 30.01.2019 08:07 # 0

                          Ну в два раза проще всего. j123123 ниже как раз так и сделал.
                          Ответить

                          • ava JIyHHblu_nemyx 30.01.2019 08:53 # 0

                            Кстати, на каких платформах в Гэцэцэ и в Шланге есть тип __int128? Документация об этом молчит. Видимо, власти приказали это скрывать.

                            P.S. Тут чувак накостылил __int128 через перегрузку операторов:
                            https://stackoverflow.com/a/37907522
                            Ответить

                            • ava bormand 30.01.2019 11:57 # +2

                              Костылить - так универсально. integer<128>.
                              Ответить

                              • ava JIyHHblu_nemyx 30.01.2019 16:00 # 0

                                Почему только integer? А плавающий питух? А кококококомплексные числа?
                                Ответить

                              • ava j123123 30.01.2019 16:15 # +3

                                Это кстати хотят пропихнуть в крестоговностандарт, вон какие-то пропозалы пишут https://habr.com/ru/company/yandex/blog/327080/

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

                                Только вот это нихера не выйдет с говном, которое есть в крестопомойной параше (разве что компилятор допилить специально под эту дрисню). Шаблонами нельзя определять всякие свойства коммутативности, ассоциативности и стратегии оптимизации.
                                Ответить

                                • ava JIyHHblu_nemyx 30.01.2019 16:17 # 0

                                  Напомните мне, придумали ли управление ленивостью у перегруженных операторов || и &&.
                                  Ответить

                                • ava JIyHHblu_nemyx 30.01.2019 16:21 # +2

                                  >> Предложение отказаться от привязки к количеству бит, а задавать количество машинных слов, мне показалось самым странным: бизнес-логике всё равно, сколько слов в числе на какой-то платформе, — ей важно однозначно определять одни и те же числа на разных платформах. Скажем, уникальный идентификатор пользователя — беззнаковое целое число из 64 бит, а не из одного unsigned long long.

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

                                  Вот уроды. Они хотят, чтобы при перекококомпиляции на другой платформе программа оперировала числами другого размера? Т. е. опять придётся потеть с мокросами и ифдефами?
                                  Ответить

                                • ava JIyHHblu_nemyx 30.01.2019 16:50 # +1

                                  Начал копать ссылки:
                                  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)

                                  Полная жопа, короче.
                                  Ответить

                                  • ava guest8 30.01.2019 18:50 # −999

                                    показать все, что скрытоvanished
                                    Ответить

                                    • ava JIyHHblu_nemyx 30.01.2019 19:08 # 0

                                      Выхлоп кококомпилятора:
                                      ; [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; видимо, задел для больших множеств) и цикл не хочет выкидывать, хотя задача должна решаться одной итерацией. Оптимизатор –— питух.
                                      Ответить

                                      • ava JIyHHblu_nemyx 30.01.2019 19:21 # 0

                                        В «fpc» сделали хреново (только BT задействована). Надо посмотреть, как в реализовали в других кокококомпиляторах.
                                        Ответить

                                        • ava JIyHHblu_nemyx 31.01.2019 20:36 # 0

                                          В «Delphi» (включая «XE») и в заброшенном «Virtual Pascal» используется только инструкция BT, как и во «Фрипаскале».

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

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

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

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

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

                                    • ava PA3yMHblu_nemyx 01.02.2019 14:05 # 0

                                      >> tempset := tempset + [1 shl n]

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

                                      Всё равно использует только BT, а установку/сброс делает через сдвиг + OR/XOR.
                                      Ответить

                              • ava guest8 30.01.2019 17:03 # −999

                                показать все, что скрытоvanished
                                Ответить

                                • ava bormand 30.01.2019 17:28 # 0

                                  3 блока по 64 или 5 блоков по 32. Ну и масочки.
                                  Ответить

    • ava bormand 29.01.2019 09:12 # 0

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

      • ava j123123 29.01.2019 14:53 # +2

        Если тебя интересует практичный вариант, то наверно лучше так:
        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 элементов), думаю что на сдвигах проебется больше времени.
        Ответить

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