Самый быстрый способ закрепить целое число в диапазоне 0-255

Я работаю над некоторым кодом обработки изображений, который может генерировать значения пикселей вне нормального диапазона от 0 до 255, и я хотел бы зажать их обратно в допустимый диапазон. Я знаю, что есть насыщающие инструкции SIMD, которые делают это спорным вопросом, но на данный момент я пытаюсь оставаться в пределах стандартного кода на C ++.

Самый быстрый, который я смог сделать на своем Athlon II, следующий:

inline
BYTE Clamp(int n)
{
    n &= -(n >= 0);
    return n | ((255 - n) >> 31);
}

Это скомпилируется в следующую сборку с MSVC 6.0:

setns dl
neg   edx
and   eax, edx
mov   edx, 255
sub   edx, eax
sar   edx, 31
or    dl, al

Возможно ли улучшение?

88 голосов | спросил Mark Ransom 3 SatEurope/Moscow2011-12-03T10:18:53+04:00Europe/Moscow12bEurope/MoscowSat, 03 Dec 2011 10:18:53 +0400 2011, 10:18:53

9 ответов


39

Try

 int x=n>255?255:n;
 ... x<0?0:x ...

Я ожидаю, что это создаст

 mov eax,n
 cmp eax,255
 cmovgt eax,255 ; conditional mov instruction
 test eax,eax
 cmovlt  eax,0

Если вы используете MSVC SIX, вы можете не получить инструкцию условного перемещения. Попробуйте перейти на современную версию визуальной студии.

ответил Ira Baxter 3 SatEurope/Moscow2011-12-03T11:17:19+04:00Europe/Moscow12bEurope/MoscowSat, 03 Dec 2011 11:17:19 +0400 2011, 11:17:19
26

Вот моя попытка:

unsigned char clamp(int n){
    int a = 255;
    a -= n;
    a >>= 31;
    a |= n;
    n >>= 31;
    n = ~n;
    n &= a;
    return n;
}

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

mov eax, 255
sub eax, ecx
sar eax, 31
or  al , cl
sar ecx, 31
not cl
and al , cl
ответил Mysticial 3 SatEurope/Moscow2011-12-03T10:53:14+04:00Europe/Moscow12bEurope/MoscowSat, 03 Dec 2011 10:53:14 +0400 2011, 10:53:14
10

Заключение 2011-12-05:

Я снова попробовал все предложения с помощью VS 2010 Express. Сгенерированный код сильно не изменился, но выполнялись назначения регистров, которые влияли на общие результаты. Победителем стала небольшая модификация простой реализации, предложенная Ирой Бакстер.

inline
BYTE Clamp(int n)
{
    n = n>255 ? 255 : n;
    return n<0 ? 0 : n;
}

    cmp  ecx, 255
    jle  SHORT $LN8
    mov  ecx, 255
$LN8:
    test ecx, ecx
    sets bl
    dec  bl
    and  bl, cl

Я научился этому ценному уроку. Я начал с предположения, что бит-twiddling будет бить все, что включает ветку; Я действительно не пытался использовать какой-либо код, включающий оператор if или тройной оператор. Это была ошибка, поскольку я не рассчитывал на силу предсказания ветвей, встроенного в современный процессор. Тройное решение оказалось самым быстрым, особенно когда компилятор заменил свой собственный битовый код для одного из случаев. Общее время для этой функции в моем тестовом алгоритме составило 0,24 секунды до 0,19. Это очень близко к 0.18 секундам, которые возникли, когда я полностью снял зажим.

ответил Mark Ransom 17 WedEurope/Moscow2014-12-17T19:36:10+03:00Europe/Moscow12bEurope/MoscowWed, 17 Dec 2014 19:36:10 +0300 2014, 19:36:10
7

Мне было бы интересно, как будет работать простое разветвленное решение?

inline char Clamp(int n)
{
    if(n < 0)
        return 0;
    else if(n > 255)
        return 255;
    return n;
}
ответил ronag 3 SatEurope/Moscow2011-12-03T18:59:54+04:00Europe/Moscow12bEurope/MoscowSat, 03 Dec 2011 18:59:54 +0400 2011, 18:59:54
6

Использование GCC /LLVM для MacOS X и 64-битная компиляция и создание ассемблера с помощью

gcc -S -Os clamp.c

где clamp.c содержит:

typedef unsigned char BYTE;

BYTE Clamp_1(int n)
{
    n &= -(n >= 0);
    return n | ((255 - n) >> 31);
}

BYTE Clamp_2(int n)
{
    if (n > 255)
        n = 255;
    else if (n < 0)
        n = 0;
    return n;
}

Ассемблер для двух функций (с прологом и эпилогом):

    .section        __TEXT,__text,regular,pure_instructions
    .globl  _Clamp_1
_Clamp_1:
Leh_func_begin1:
    pushq   %rbp
Ltmp0:
    movq    %rsp, %rbp
Ltmp1:
    movl    %edi, %eax
    shrl    $31, %eax
    xorl    $1, %eax
    negl    %eax
    andl    %edi, %eax
    movl    $255, %ecx
    subl    %eax, %ecx
    sarl    $31, %ecx
    orl     %eax, %ecx
    movzbl  %cl, %eax
    popq    %rbp
    ret
Leh_func_end1:

    .globl  _Clamp_2
_Clamp_2:
Leh_func_begin2:
    pushq   %rbp
Ltmp2:
    movq    %rsp, %rbp
Ltmp3:
    cmpl    $256, %edi
    jl      LBB2_2
    movl    $255, %edi
    jmp     LBB2_4
LBB2_2:
    testl   %edi, %edi
    jns     LBB2_4
    xorl    %edi, %edi
LBB2_4:
    movzbl  %dil, %eax
    popq    %rbp
    ret
Leh_func_end2:

pushq, popq и ret - это служебные вызовы функции. Ваш код (Clamp_1()) собирается на 11 инструкций; до 9 (но есть два прыжка в шахте, которые могут нанести ущерб конвейерному исполнению). Ни один из них не подходит к 7 инструкциям в вашей оптимизированной версии.

Интересно, однако, когда я использую GCC 4.6.1 на том же коде, выход ассемблера:

    .text
    .globl _Clamp_1
_Clamp_1:
LFB0:
    movl    %edi, %eax
    movl    $255, %edx
    notl    %eax
    sarl    $31, %eax
    andl    %edi, %eax
    subl    %eax, %edx
    sarl    $31, %edx
    orl     %edx, %eax
    ret
LFE0:
    .globl _Clamp_2
_Clamp_2:
LFB1:
    xorl    %edx, %edx
    testl   %edi, %edi
    movl    $255, %eax
    cmovns  %edi, %edx
    cmpl    $255, %edx
    cmovle  %edx, %eax
    ret
LFE1:

Теперь я вижу 8 команд в Clamp_1 и 6 в Clamp_2, кроме ret.


Дальнейшее экспериментирование показывает, что существует разница в выходе между gcc -Os -S clamp.c и gcc -S -Os clamp.c; первая генерирует оптимизированные (меньшие) выходы; последний генерирует более подробный вывод.

ответил Jonathan Leffler 3 SatEurope/Moscow2011-12-03T11:23:34+04:00Europe/Moscow12bEurope/MoscowSat, 03 Dec 2011 11:23:34 +0400 2011, 11:23:34
3

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

int clamp(int n)
{
    if ((unsigned) n <= 255) {
        return n;
    }
    return (n < 0) ? 0 : 255;
}
ответил William Morris 21 SatEurope/Moscow2013-12-21T21:40:25+04:00Europe/Moscow12bEurope/MoscowSat, 21 Dec 2013 21:40:25 +0400 2013, 21:40:25
1

0 зажимать и модифицировать> 255, как это складывается?

inline 
BYTE Clamp(int n)
{
  n &= -(n >= 0);
  return n | ~-!(n & -256);
}

Разборка второй строки (внизу) на моей машине имеет одну дополнительную инструкцию, но нет (дорогих) сдвигов.

mov  eax, ecx
and  eax, -256
neg  eax
sbb  eax, eax
or   eax, ecx
ответил DocMax 3 SatEurope/Moscow2011-12-03T11:24:41+04:00Europe/Moscow12bEurope/MoscowSat, 03 Dec 2011 11:24:41 +0400 2011, 11:24:41
1
unsigned char clamp(int n) {
    return (-(n >= 0) & n) | -(n >= 255);
}

Вы можете оптимизировать это, если сможете оптимизировать - (a> = b)

ответил razpeitia 4 SunEurope/Moscow2011-12-04T05:41:29+04:00Europe/Moscow12bEurope/MoscowSun, 04 Dec 2011 05:41:29 +0400 2011, 05:41:29
1

как насчет этого?

x &= 255

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

x &= (~x) >> 8
ответил Phil Huffman 9 PM00000080000001331 2012, 20:18:13

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132