LINUX.ORG.RU

Объясните сишную магию

 ,


9

14

Пытался понять как реализовать SVG фильтр feComposite, ибо SVG дока унылая, поэтому залез в сорцы вебкита. Там тоже документации ноль, ещё и код очень странный.

Вот что это за ужас (src):

static unsigned char clampByte(int c)
{
    unsigned char buff[] = { static_cast<unsigned char>(c), 255, 0 };
    unsigned uc = static_cast<unsigned>(c);
    return buff[!!(uc & ~0xff) + !!(uc & ~(~0u >> 1))];
}

Я так понимаю, они проверяют что int в 0..255 диапазоне, но уж слишком странным образом.

UPD: коммит, который добавил этот код.

тебе слово clamp перевести? Если c больше 255, но положительное, то возвращаяет 255, если отрицательное, то 0, если принадлежит [0..255], то возвращает само число

Harald ★★★★★ ()
!!(uc & ~0xff)

- это вычисляется в 1 если uc по модулю больше 255

!!(uc & ~(~0u >> 1))

- это вычисляется в 1 если выставлен в 1 старший бит uc, бит знака

значения этих двух выражений складываются и дают индекс в буфере

код не содержит условных переходов, в результате конвейер процессора не сбрасывается в случае неудачного предсказания, производительность зашкаливает, волосы мягкие и шелковистые, все дела :)

Harald ★★★★★ ()

Ну, тут надо разобрать вот эту хрень return buff[!!(uc & ~0xff) + !!(uc & ~(~0u >> 1))];

Собственно, что делает !!? Это такой как бы каст в bool. Т.е. если 0 то 0, а если что-то другое то 1.

Что дает (uc & ~0xff) ? Ну как бы вот есть у нас 0xff, а мы его инвертируем, получается 0xffff.....ff00 и потом делаем побитовое and с этим uc. Т.е. вот это выражение !!(uc & ~0xff) будет 1 если uc больше чем 0xff потому что тогда uc при побитовом and с 0xffff.....ff00 даст отличное от нуля значение.

А вот та другая хрень !!(uc & ~(~0u >> 1)) - ну тут ~0u это 0xffff.....ffff, потом мы сдвигаем на 1 вправо, и потом инвертируем, получается что в двоичной системе счисления это будет 1000000000...000... короче это так проверяется, что самый самый старший (какбы знаковый) бит в uc единичке равен.

Короче блин. Если для числа верно, что оно больше чем 0xff и еще у него последний самый старший бит выставлен в единичку, то тогда вернуть 0 (третий элемент массива buff). Если для числа верно только то, что оно больше чем 0xff то тогда вернем 1 (второй элемент из массива buff). Во всех иных случаях возвращается static cast в unsigned char (первый элемент из массива buff). Ситуации, чтоб у числа был самый старший бит единичкой, но при этом чтоб оно было меньше чем 0xff быть не может.

Если еще конкретней - если число отрицательно - вернуть 0. Если число положително и больше 255 - вернуть 255. В ином случае - его же и вернуть

SZT ★★★ ()

На самом деле, это типичное плюсовское дрочерство на, типа, оптимизации. Типа, нету ветвлений, значит быстра-быстра работает.

Естественно, хрена с три там.

gcc -O2 -c ./clamp_byte.cxx -o clamp_byte.o -g0 && objdump --demangle=auto -M intel -S ./clamp_byte.o

./clamp_byte.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <clampByte(int)>:
   0:   48 83 ec 18             sub    rsp,0x18
   4:   64 48 8b 04 25 28 00    mov    rax,QWORD PTR fs:0x28
   b:   00 00
   d:   48 89 44 24 08          mov    QWORD PTR [rsp+0x8],rax
  12:   31 c0                   xor    eax,eax
  14:   31 c0                   xor    eax,eax
  16:   f7 c7 00 ff ff ff       test   edi,0xffffff00
  1c:   40 88 7c 24 05          mov    BYTE PTR [rsp+0x5],dil
  21:   0f 95 c0                setne  al
  24:   c1 ef 1f                shr    edi,0x1f
  27:   c6 44 24 07 00          mov    BYTE PTR [rsp+0x7],0x0
  2c:   01 c7                   add    edi,eax
  2e:   c6 44 24 06 ff          mov    BYTE PTR [rsp+0x6],0xff
  33:   48 8b 54 24 08          mov    rdx,QWORD PTR [rsp+0x8]
  38:   64 48 33 14 25 28 00    xor    rdx,QWORD PTR fs:0x28
  3f:   00 00
  41:   48 63 ff                movsxd rdi,edi
  44:   0f b6 44 3c 05          movzx  eax,BYTE PTR [rsp+rdi*1+0x5]
  49:   75 05                   jne    50 <clampByte(int)+0x50>
  4b:   48 83 c4 18             add    rsp,0x18
  4f:   c3                      ret
  50:   e8 00 00 00 00          call   55 <clampByte(int)+0x55>
  55:   90                      nop
  56:   66 2e 0f 1f 84 00 00    nop    WORD PTR cs:[rax+rax*1+0x0]
  5d:   00 00 00

Как можно догадаться, потуги плюсодрочеров пошли впустую. Что-то типа ветвления все же вкралось в ассемблерный выхлоп. Да и вообще ...

Ну и:

Сравниваем с:

unsigned char clampByteSimple(int c)
{
    if(c < 0) return 0;
    else if(c > 255) return 255;
    else return (unsigned char)c;
}

gcc -o2 -c ./clamp_byte.cxx -o clamp_byte.o -g0 && objdump --demangle=auto -M intel -S ./clamp_byte.o

./clamp_byte.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <clampByteSimple(int)>:
   0:   31 c0                   xor    eax,eax
   2:   85 ff                   test   edi,edi
   4:   78 0e                   js     14 <clampByteSimple(int)+0x14>
   6:   81 ff ff 00 00 00       cmp    edi,0xff
   c:   b8 ff ff ff ff          mov    eax,0xffffffff
  11:   0f 4e c7                cmovle eax,edi
  14:   f3 c3                   repz ret

Тупо по количеству инструкций сразу понятно, что будет быстрее выполняться.

lovesan ()
Ответ на: комментарий от lovesan

Так и знал, уже набежали хреновы оптимизаторы.

Таких слушать, конечно, не надо, потому что как там типа бранчи влияют на что в современных процессорах - ни один такой оптимизатор сказать наверняка не сможет, это раз, а два - я на C# написал видеостриминг, и он отлично работает без всякого излишнего дрочерства байтиков и тем более ветвлений.

lovesan ()
Ответ на: комментарий от lovesan

Тупо по количеству инструкций сразу понятно, что будет быстрее выполняться.

Жесть. Надо же, нашёлся кто-то, кто это всё-таки сказал.

Вкратце — ты не прав. Более подробно — с gcc 8.3.0 вариант с явными проверками быстрее, если все входные значения лежат в отрезке [0-255]. Тогда фейлов предсказания нет, и рулит число инструкций. С clang 7.0.1 всегда быстрее вариант без ветвлений, потому что у clang получилось сделать его короче, чем получилось у gcc, а на варианте с ветвлениями clang сделал код хуже.

i-rinat ★★★★★ ()
Ответ на: комментарий от i-rinat

Нет, вкратце - я прав, еще раз, потому что:

1) Как влияют бранчи на производительность в современных процессорах - ты наверняка не знаешь, и скорее всего влияют они не сильнее чем вытаскивание данных со стека.

2) Кроме сферических бранчей в вакууме, все зависит от характера данных на входе, и от того, не припрет ли жабе в соседнем процессе включить сборщик мусора чтобы тебе устроили контекстсвитч, и так далее и тому подобное.

3) В любом случае, даже если при прочих равных, там есть какое-то «ускорение», то оно совершенно neglibile, и уж точно не стоит того чтобы так усирать код.

lovesan ()
Ответ на: комментарий от Crocodoom

std::clamp из насколько медленнее

Под GCC 8.3.0 std::clamp — самый быстрый вариант. Он генерирует код без ветвлений, но 6 инструкций, а не 10, как код в заглавном сообщении. Под Clang 7.0.1 std::clamp даёт код с условным переходом, и это получается медленнее, чем битовая магия.

i-rinat ★★★★★ ()
Ответ на: комментарий от yoghurt

Я крайне сомневаюсь.

И опять же, вспомним что это вебкит.

А что такое вебкит? Это значит либо браузер, либо электрон.

А значит, тормоза там откуда?

  • Множество заспавненных процессов
  • Жабоскрипт!11
  • Расширения(на жабоскрипте)!111
  • Пока туда-сюда с видеокарты данные гоняются можно уснуть
  • Сложные графы объектов в динамической памяти, с которой как известно C++ работает отвратительно (сюда же - умные указатели, которые тормозят больше чем любой GC в любой жабе)

А они тут ветвления оптимизируют. Смешно просто. Ну типичное плюсодрочерство, че.

lovesan ()
Ответ на: комментарий от i-rinat

с условным переходом, и это получается медленнее, чем битовая магия

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

lovesan ()
Ответ на: комментарий от lovesan

Нет, вкратце - я прав, еще раз, потому что:

Потому что пытаешься рассуждать, даже не померив? :-)

Как влияют бранчи на производительность в современных процессорах - ты наверняка не знаешь

Intel вообще-то пишет (и AMD тоже), как начальное предсказание работает. Компиляторы знают, как работает начальное предсказание. И только я не знаю.

Ну хорошо, я не знаю. Но померить же можно. Даже наколеночных прикидок достаточно, чтобы увидеть — разница есть. Существенная.

Кроме сферических бранчей в вакууме, все зависит от характера данных на входе

От данных зависит, будут совершаться переходы или нет. Классический пример с подсчётом числа байт, больших определённой величины. Погугли, это популярный пример.

чтобы тебе устроили контекстсвитч

Ты просто пытаешься набросить умных слов. Но получается глупость. Контекст свич не происходит так часто, чтобы про него думать в этой маленькой функции. Если частота проца 2 гигагерца, а свич происходит 1000 раз в секунду, у процесса два миллиона тактов. IPC зачастую около одного или даже выше. В таком случае цикле из 10 инструкций успеет выполниться двести тысяч раз до переключения контекста.

В любом случае, даже если при прочих равных, там есть какое-то «ускорение», то оно совершенно neglibile, и уж точно не стоит того чтобы так усирать код.

«Вы не правы. Вы не правы. Ну хорошо, вы правы, но это не имеет смысла».

В данном случае действительно вряд ли из-за скорости это меняли. Но если быстрее стало, это хорошо.

i-rinat ★★★★★ ()
Ответ на: комментарий от lovesan

Это не обязательно так

Я смотрю на числа. Смотрю на твои слова. Почему твоим словам нужно верить больше, чем числам?

в общем случае

Не видно в твоих словах анализа даже частного случая. А ты на общий замахнулся?

наглое вранье.

Почему ты постоянно пытаешься заявить, что это враньё? Думаешь, что если многократно заявить, что слова собеседника — враньё, твои слова станут правдой?

i-rinat ★★★★★ ()

Мне вообще кажется, что кто-то просто хотел повыпендриваться знаниями two's complement и битовыми масками.

Можно проще сделать:

unsigned char clampByte(int c)
{ 
  unsigned char buff[3] = {(unsigned char)c, 255, 0};
  return buff[ (c < 0) + ((unsigned)c > 255) ];
}

SZT ★★★ ()
Ответ на: комментарий от lovesan

на пустом месте. И вряд ли стало хоть сколько-то быстрее

Тему читай. Этот код добавили не из-за скорости. И других адекватных решений нет.

i-rinat ★★★★★ ()
Последнее исправление: i-rinat (всего исправлений: 1)
Ответ на: комментарий от i-rinat

Если это защита от тайминг-атак, то лично я это решение адекватным назвать не могу. Вполне может быть, что в какой-то версии какого-то компилятора появится оптимизация, которая втулит туда условный переход, и это могут даже и не заметить. Тут надо или асмовставки/интринсики, или какие-то специальные флаги выдумывать, типа -ftiming-attack-protect

SZT ★★★ ()
Ответ на: комментарий от RazrFalcon

Я всё равно такой ужас не пишу - оно мне не надо

Я надеюсь ты не программист, иначе у меня для тебя плохие новости. Если человек не в состоянии разобраться с битовыми операциями, а это базовая вещь, то не понятно, что он вообще делает в этой профессии.

anonymous ()
Ответ на: комментарий от mittorn

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4659.pdf#section.7.8

If the destination type is unsigned, the resulting value is the least unsigned integer congruent to the source integer modulo 2^n where n is the number of bits used to represent the unsigned type). [Note: In a two’s complement representation, this conversion is conceptual and there is no change in the bit pattern (if there is no truncation).— end note]

SZT ★★★ ()
Ответ на: комментарий от lovesan

Тупо по количеству инструкций сразу понятно, что будет быстрее выполняться

Бэнчить по количеству инструкций - удел не очень умных людей.

anonymous ()