Самый быстрый способ закрепить целое число в диапазоне 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
Возможно ли улучшение?
9 ответов
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, вы можете не получить инструкцию условного перемещения. Попробуйте перейти на современную версию визуальной студии.
Вот моя попытка:
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
Заключение 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 секундам, которые возникли, когда я полностью снял зажим.
Мне было бы интересно, как будет работать простое разветвленное решение?
inline char Clamp(int n)
{
if(n < 0)
return 0;
else if(n > 255)
return 255;
return n;
}
Использование 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
; первая генерирует оптимизированные (меньшие) выходы; последний генерирует более подробный вывод.
Результат может зависеть от того, будут ли пиксельные данные предсказуемо более часто находиться в диапазоне, чем вне диапазона. Это может быть быстрее в первом случае:
int clamp(int n)
{
if ((unsigned) n <= 255) {
return n;
}
return (n < 0) ? 0 : 255;
}
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
unsigned char clamp(int n) {
return (-(n >= 0) & n) | -(n >= 255);
}
Вы можете оптимизировать это, если сможете оптимизировать - (a> = b)
как насчет этого?
x &= 255
Он очень эффективен и не влияет на значения в нормальном диапазоне. Я хотел бы знать, какая часть ваших результатов требует зажима. Если простой и не будет делать трюк, попробуйте следующее:
x &= (~x) >> 8