оптимизировать 32-битное значение

Question

Итак, у меня есть следующий код:

uint32_t val;
if (swap) {
   val = ((uint32_t)a & 0x0000ffff) | ((uint32_t)b << 16);
} else {
   val = ((uint32_t)b & 0x0000ffff) | ((uint32_t)a << 16);
}

Есть ли способ оптимизировать его и включить в выражение swap проверку как-то ?

Answer 1

Если цель состоит в том, чтобы избежать ветки, то вы можете написать это:

val = ((!!swap) * (uint32_t)a + (!swap) * (uint32_t)b) & 0x0000ffff)
        | (((!!swap) * (uint32_t)b + (!swap) * (uint32_t)a) << 16);

Здесь используется тот факт, что !x оценивается в 0, когда swap является правдивым, и в 1, когда swap является ложным, и поэтому !!x оценивается в 1, когда x является правдивым, даже если x само по себе не может быть 1. При умножении на результат выбирается либо a, либо b в зависимости от ситуации.

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

---

Предоставлено @ChristianGibbons:

[При условии, что a и b гарантированно неотрицательны и меньше чем 2 ¹⁶ ,] вы можете существенно упростить этот подход, удалив побитовый компонент AND и применив умножение к сдвигам вместо аргументов:

val = ((uint32_t) a << (16 * !swap)) | ((uint32_t)b << (16 * !!swap));

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

uint32_t val;
if (swap) {
   val = (uint32_t)a | ((uint32_t)b << 16);
} else {
   val = (uint32_t)b | ((uint32_t)a << 16);
}

Answer 2

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

uint8_t shift_mask = (uint8_t) !swap * 16;
val = ((uint32_t) a << (shift_mask)) | ((uint32_t)b << ( 16 ^ shift_mask  ));

Ни один из компиляторов на самом деле даже не использует инструкцию умножения, поскольку единственное умножение здесь - это степень двойки, поэтому он просто использует простое смещение влево для построения значения, которое будет использоваться для смещения либо a, либо b.

Разборка оригинала с Clang -O2

0000000000000000 <cat>:
   0:   85 d2                   test   %edx,%edx
   2:   89 f0                   mov    %esi,%eax
   4:   66 0f 45 c7             cmovne %di,%ax
   8:   66 0f 45 fe             cmovne %si,%di
   c:   0f b7 c0                movzwl %ax,%eax
   f:   c1 e7 10                shl    $0x10,%edi
  12:   09 f8                   or     %edi,%eax
  14:   c3                      retq   
  15:   66 66 2e 0f 1f 84 00    data16 nopw %cs:0x0(%rax,%rax,1)
  1c:   00 00 00 00 

Разборка новой версии с Clang -O2

0000000000000000 <cat>:
   0:   80 f2 01                xor    $0x1,%dl
   3:   0f b6 ca                movzbl %dl,%ecx
   6:   c1 e1 04                shl    $0x4,%ecx
   9:   d3 e7                   shl    %cl,%edi
   b:   83 f1 10                xor    $0x10,%ecx
   e:   d3 e6                   shl    %cl,%esi
  10:   09 fe                   or     %edi,%esi
  12:   89 f0                   mov    %esi,%eax
  14:   c3                      retq   
  15:   66 66 2e 0f 1f 84 00    data16 nopw %cs:0x0(%rax,%rax,1)
  1c:   00 00 00 00 

Разборка оригинальной версии с gcc -O2

0000000000000000 <cat>:
   0:   84 d2                   test   %dl,%dl
   2:   75 0c                   jne    10 <cat+0x10>
   4:   89 f8                   mov    %edi,%eax
   6:   0f b7 f6                movzwl %si,%esi
   9:   c1 e0 10                shl    $0x10,%eax
   c:   09 f0                   or     %esi,%eax
   e:   c3                      retq   
   f:   90                      nop
  10:   89 f0                   mov    %esi,%eax
  12:   0f b7 ff                movzwl %di,%edi
  15:   c1 e0 10                shl    $0x10,%eax
  18:   09 f8                   or     %edi,%eax
  1a:   c3                      retq   

Разборка новой версии с gcc -O2

0000000000000000 <cat>:
   0:   83 f2 01                xor    $0x1,%edx
   3:   0f b7 c6                movzwl %si,%eax
   6:   0f b7 ff                movzwl %di,%edi
   9:   c1 e2 04                shl    $0x4,%edx
   c:   89 d1                   mov    %edx,%ecx
   e:   83 f1 10                xor    $0x10,%ecx
  11:   d3 e0                   shl    %cl,%eax
  13:   89 d1                   mov    %edx,%ecx
  15:   d3 e7                   shl    %cl,%edi
  17:   09 f8                   or     %edi,%eax
  19:   c3                      retq   

EDIT: Как отметил Джон Боллинджер, это решение было написано в предположении, что a и b являются значениями без знака, что делает избыточным маскирование битов. Если этот подход должен использоваться со значениями со знаком в 32-битном формате, то потребуется модификация:

uint8_t shift_mask = (uint8_t) !swap * 16;
val = ((uint32_t) (a & 0xFFFF) << (shift_mask)) | ((uint32_t) (b & 0xFFFF) << ( 16 ^ shift_mask  ));

Я не буду слишком углубляться в разборку этой версии, но вот вывод clang в -O2:

0000000000000000 <cat>:
   0:   80 f2 01                xor    $0x1,%dl
   3:   0f b6 ca                movzbl %dl,%ecx
   6:   c1 e1 04                shl    $0x4,%ecx
   9:   0f b7 d7                movzwl %di,%edx
   c:   d3 e2                   shl    %cl,%edx
   e:   0f b7 c6                movzwl %si,%eax
  11:   83 f1 10                xor    $0x10,%ecx
  14:   d3 e0                   shl    %cl,%eax
  16:   09 d0                   or     %edx,%eax
  18:   c3                      retq   
  19:   0f 1f 80 00 00 00 00    nopl   0x0(%rax)

В ответ на P__J__ относительно производительности по сравнению с его решением для объединения, вот что Clang показывает в -O3 для версии этого кода, которая безопасна для работы со знаковыми типами:

0000000000000000 <cat>:
   0:   85 d2                   test   %edx,%edx
   2:   89 f0                   mov    %esi,%eax
   4:   66 0f 45 c7             cmovne %di,%ax
   8:   66 0f 45 fe             cmovne %si,%di
   c:   0f b7 c0                movzwl %ax,%eax
   f:   c1 e7 10                shl    $0x10,%edi
  12:   09 f8                   or     %edi,%eax
  14:   c3                      retq   
  15:   66 66 2e 0f 1f 84 00    data16 nopw %cs:0x0(%rax,%rax,1)
  1c:   00 00 00 00 

Это немного ближе к решению объединения в общих инструкциях, но не использует SHRD, который, согласно Этот ответ , требует 4 такта для работы на процессоре Intel Skylake и использует несколько операций. единицы. Мне было бы немного любопытно, как они на самом деле выступят.

Answer 3

Там нас не так уж много, чтобы оптимизировать

Здесь у вас есть две версии

typedef union
{
    uint16_t u16[2];
    uint32_t u32;
}D32_t;


uint32_t foo(uint32_t a, uint32_t b, int swap)
{
    D32_t da = {.u32 = a}, db = {.u32 = b}, val;

    if(swap)
    {
        val.u16[0] = da.u16[1];
        val.u16[1] = db.u16[0];
    }
    else
    {
        val.u16[0] = db.u16[1];
        val.u16[1] = da.u16[0];
    }

    return val.u32;
}


uint32_t foo2(uint32_t a, uint32_t b, int swap)
{
    uint32_t val;
    if (swap) 
    {
        val = ((uint32_t)a & 0x0000ffff) | ((uint32_t)b << 16);
    } 
    else 
    {
        val = ((uint32_t)b & 0x0000ffff) | ((uint32_t)a << 16);
    }

    return val;
}

сгенерированный код практически одинаков.

лязг:

foo:                                    # @foo
        mov     eax, edi
        test    edx, edx
        mov     ecx, esi
        cmove   ecx, edi
        cmove   eax, esi
        shrd    eax, ecx, 16
        ret
foo2:                                   # @foo2
        movzx   ecx, si
        movzx   eax, di
        shl     edi, 16
        or      edi, ecx
        shl     esi, 16
        or      eax, esi
        test    edx, edx
        cmove   eax, edi
        ret

НКА:

foo:
        test    edx, edx
        je      .L2
        shr     edi, 16
        mov     eax, esi
        mov     edx, edi
        sal     eax, 16
        mov     ax, dx
        ret
.L2:
        shr     esi, 16
        mov     eax, edi
        mov     edx, esi
        sal     eax, 16
        mov     ax, dx
        ret
foo2:
        test    edx, edx
        je      .L6
        movzx   eax, di
        sal     esi, 16
        or      eax, esi
        ret
.L6:
        movzx   eax, si
        sal     edi, 16
        or      eax, edi
        ret

https://godbolt.org/z/F4zOnf

Как видите, клангу нравятся союзы, gcc смены.

Answer 4

Компилировать с -O3. GCC и Clang имеют несколько разные стратегии для 64-битных процессоров.GCC генерирует код с ответвлением, тогда как Clang запускает обе ветви и затем использует условное перемещение.И GCC, и Clang сгенерируют инструкцию "short-int to int" вместо and.

Использование ?: не изменило сгенерированный код ни в одном из них.

Версия Clang кажется более эффективной.

В целом, оба сгенерируют один и тот же код , если вам не понадобится своп.

Answer 5

val = swap ? ((uint32_t)a & 0x0000ffff) | ((uint32_t)b << 16) : ((uint32_t)b & 0x0000ffff) | ((uint32_t)a << 16);

Это обеспечит требуемое «вложение».Однако я не рекомендую это, поскольку это ухудшает читаемость и не требует оптимизации во время выполнения.