Говнокод #25334 — Си — Говнокод.ру

Си / Говнокод #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

Tweet
Комментарии (32) RSS
- 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
  Ответить
  - 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
    Ответить
    - gueest8 29.01.2019 00:00 # 0
      
      а теперь напиши на m4 который который это генерит
      Ответить
      
      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 }
      Ответить
      
      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 }
      Ответить
      
      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)
      Ответить
      
      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); }
      Ответить
      
      JIyHHblu_nemyx 30.01.2019 01:50 # 0
      
      P.S. Наглючил. Мы же последний элемент не трогаем, он полностью не вмещается в базовый тип. У нас временные «байты» девятибитные, чтобы вместить разряд переноса. Значит, там нужно ещё с декрементом пошаманить, чтобы цикл был короче на одну итерацию. И названия функций тогда подкорректировать (3 вместо 4; 7 вместо 8; 15 вместо 16).
      Ответить
      
      bormand 30.01.2019 02:56 # +1
      
      Сдвиги, имхо, надо убрать в отдельные функции load и store как в настоящем SSE. Тогда можно будет один раз упаковать число, сделать над упакованным вектором много операций и в конце один раз распаковать. Тогда может и будет какой-то профит.
      Ответить
      
      JIyHHblu_nemyx 30.01.2019 03:17 # 0
      
      Ещё можно сделать разные варианты упаковки:
      1. Упаковка для побитовых операций.
      2. Упаковка для сложения: каждое число будет расширено на один бит.
      
      Последний вариант ещё может быть знаковым и беззнаковым.
      
      А ещё можно упаковать для умножения на скаляр, тогда каждое число будет расширено в два раза.
      Ответить
      
      bormand 30.01.2019 08:07 # 0
      
      Ну в два раза проще всего. j123123 ниже как раз так и сделал.
      Ответить
      
      JIyHHblu_nemyx 30.01.2019 08:53 # 0
      
      Кстати, на каких платформах в Гэцэцэ и в Шланге есть тип __int128? Документация об этом молчит. Видимо, власти приказали это скрывать.
      
      P.S. Тут чувак накостылил __int128 через перегрузку операторов:
      https://stackoverflow.com/a/37907522
      Ответить
      
      bormand 30.01.2019 11:57 # +2
      
      Костылить - так универсально. integer<128>.
      Ответить
      
      JIyHHblu_nemyx 30.01.2019 16:00 # 0
      
      Почему только integer? А плавающий питух? А кококококомплексные числа?
      Ответить
      
      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)
      
      Только вот это нихера не выйдет с говном, которое есть в крестопомойной параше (разве что компилятор допилить специально под эту дрисню). Шаблонами нельзя определять всякие свойства коммутативности, ассоциативности и стратегии оптимизации.
      Ответить
      
      JIyHHblu_nemyx 30.01.2019 16:17 # 0
      
      Напомните мне, придумали ли управление ленивостью у перегруженных операторов || и &&.
      Ответить
      
      JIyHHblu_nemyx 30.01.2019 16:21 # +2
      
      >> Предложение отказаться от привязки к количеству бит, а задавать количество машинных слов, мне показалось самым странным: бизнес-логике всё равно, сколько слов в числе на какой-то платформе, — ей важно однозначно определять одни и те же числа на разных платформах. Скажем, уникальный идентификатор пользователя — беззнаковое целое число из 64 бит, а не из одного unsigned long long.
      
      >> В частности, комиссия всё-таки попросила в wide_int оперировать количеством машинных слов.
      
      Вот уроды. Они хотят, чтобы при перекококомпиляции на другой платформе программа оперировала числами другого размера? Т. е. опять придётся потеть с мокросами и ифдефами?
      Ответить
      
      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)
      
      Полная жопа, короче.
      Ответить
      
      guest8 30.01.2019 18:50 # −999
      
      показать все, что скрытоvanished
      Ответить
      
      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; видимо, задел для больших множеств) и цикл не хочет выкидывать, хотя задача должна решаться одной итерацией. Оптимизатор –— питух.
      Ответить
      
      JIyHHblu_nemyx 30.01.2019 19:21 # 0
      
      В «fpc» сделали хреново (только BT задействована). Надо посмотреть, как в реализовали в других кокококомпиляторах.
      Ответить
      
      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.
      Ответить
      
      JIyHHblu_nemyx 31.01.2019 20:53 # 0
      
      Кто знает статически тупизированные ЯП со множествами, кроме «Паскаля»?
      Ответить
      
      guest8 31.01.2019 21:03 # −999
      
      показать все, что скрытоvanished
      Ответить
      
      guest8 31.01.2019 21:04 # −999
      
      показать все, что скрытоvanished
      Ответить
      
      JIyHHblu_nemyx 31.01.2019 23:30 # 0
      
      А у тебя поди последняя версия «eComstation»?
      Ответить
      
      guest8 31.01.2019 23:35 # −999
      
      показать все, что скрытоvanished
      Ответить
      
      PA3yMHblu_nemyx 01.02.2019 14:05 # 0
      
      >> tempset := tempset + [1 shl n]
      
      Фигню написал. Надо просто tempset := tempset + [n]. Сдвиг не нужен.
      
      Всё равно использует только BT, а установку/сброс делает через сдвиг + OR/XOR.
      Ответить
      
      guest8 30.01.2019 17:03 # −999
      
      показать все, что скрытоvanished
      Ответить
      
      bormand 30.01.2019 17:28 # 0
      
      3 блока по 64 или 5 блоков по 32. Ну и масочки.
      Ответить
- bormand 29.01.2019 09:12 # 0
  
  Что-то мне намекает, что тут упаковка будет дольше поштучного сложения. Надо её отделить от вычислений и делать один раз в начале кода.
  Ответить
  - 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 элементов), думаю что на сдвигах проебется больше времени.
    Ответить
Добавить комментарий
Ошибка компиляции комментария:

Гости могут высказаться только во вторник, пятницу или субботу
Семь раз отмерь — один отрежь, guest!

А не использовать ли нам bbcode?

[b]жирный[/b] — жирный

[i]курсив[/i] — курсив

[u]подчеркнутый[/u] — подчеркнутый

[s]перечеркнутый[/s] — перечеркнутый

[blink]мигающий[/blink] — мигающий

[color=red]цвет[/color] — цвет (подробнее)

[size=20]размер[/size] — размер (подробнее)

[code=<language>]some code[/code] (подробнее)

Проверочный код: *

Говнокод: по колено в коде.

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

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

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