실제(고정/변동 지점) 값을 클램프하는 가장 빠른 방법은 무엇입니까?
if 문 또는 3진 연산자를 사용하는 것보다 실제 숫자를 클램프하는 더 효율적인 방법이 있습니까?이중 및 32비트 픽스포인트 구현(16.16) 모두에 대해 이 작업을 수행하려고 합니다.나는 두 사건을 모두 처리할 수 있는 코드를 요구하는 것이 아닙니다. 그것들은 별도의 기능으로 처리될 것입니다.
분명히, 저는 다음과 같은 일을 할 수 있습니다.
double clampedA;
double a = calculate();
clampedA = a > MY_MAX ? MY_MAX : a;
clampedA = a < MY_MIN ? MY_MIN : a;
또는
double a = calculate();
double clampedA = a;
if(clampedA > MY_MAX)
clampedA = MY_MAX;
else if(clampedA < MY_MIN)
clampedA = MY_MIN;
픽스포인트 버전은 비교를 위해 함수/매크로를 사용합니다.
이 작업은 코드의 성능에 중요한 부분에서 수행되므로 가능한 한 효율적인 방법을 찾고 있습니다(비트 조작이 포함될 것으로 예상됨).
편집: 표준/휴대용 C여야 하며 플랫폼별 기능은 여기서 관심이 없습니다.또한.MY_MIN그리고.MY_MAX클램프할 값과 동일한 유형입니다(위의 예에서 두 배).
GCC와 clang 모두 다음과 같은 간단하고 간단한 휴대용 코드를 위한 아름다운 어셈블리를 생성합니다.
double clamp(double d, double min, double max) {
const double t = d < min ? min : d;
return t > max ? max : t;
}
> gcc -O3 -march=native -Wall -Wextra -Wc++-compat -S -fverbose-asm clamp_ternary_operator.c
GCC 생성 어셈블리:
maxsd %xmm0, %xmm1 # d, min
movapd %xmm2, %xmm0 # max, max
minsd %xmm1, %xmm0 # min, max
ret
> clang -O3 -march=native -Wall -Wextra -Wc++-compat -S -fverbose-asm clamp_ternary_operator.c
Clang 생성 어셈블리:
maxsd %xmm0, %xmm1
minsd %xmm1, %xmm2
movaps %xmm2, %xmm0
ret
명령어 세 개(레트 수 제외), 분기 없음.훌륭합니다.
이것은 GCC 4.7로 테스트되었으며 Ubuntu 13.04에서 Core i3 M 350으로 3.2를 설치했습니다.참고로 std::min 및 std::max를 호출하는 간단한 C++ 코드가 동일한 어셈블리를 생성했습니다.
이것은 복식입니다.그리고 int의 경우 GCC와 clang 모두 5개의 명령어(ret를 세지 않음)와 분기가 없는 어셈블리를 생성합니다.또한 훌륭합니다.
저는 현재 고정점을 사용하지 않기 때문에 고정점에 대한 의견을 제시하지 않겠습니다.
오래된 질문입니다만, 저는 오늘 이 문제에 대해 (더블/플로트로) 작업을 하고 있었습니다.
가장 좋은 방법은 플로트에 SSE MINSS/MAXSS를 사용하고 더블에 SSE2 MINSD/MAXSD를 사용하는 것입니다.이것들은 분기가 없고 각각 하나의 클럭 사이클이 걸리며 컴파일러 내장 덕분에 사용하기 쉽습니다.이들은 std::min/max를 사용하는 클램핑에 비해 성능이 몇 배 이상 향상되었습니다.
당신은 그것을 놀랄지도 모릅니다.확실히 그랬어요!불행히도 VC++ 2010은 /arch: 경우에도 std::min/max에 대해 단순 비교를 사용합니다.SSE2 및 /FP:fast가 활성화됩니다.다른 컴파일러는 말할 수 없습니다.
VC++에서 이 작업을 수행하는 데 필요한 코드는 다음과 같습니다.
#include <mmintrin.h>
float minss ( float a, float b )
{
// Branchless SSE min.
_mm_store_ss( &a, _mm_min_ss(_mm_set_ss(a),_mm_set_ss(b)) );
return a;
}
float maxss ( float a, float b )
{
// Branchless SSE max.
_mm_store_ss( &a, _mm_max_ss(_mm_set_ss(a),_mm_set_ss(b)) );
return a;
}
float clamp ( float val, float minval, float maxval )
{
// Branchless SSE clamp.
// return minss( maxss(val,minval), maxval );
_mm_store_ss( &val, _mm_min_ss( _mm_max_ss(_mm_set_ss(val),_mm_set_ss(minval)), _mm_set_ss(maxval) ) );
return val;
}
이중 정밀도 코드는 xxx_sd를 대신 사용하는 것을 제외하고는 동일합니다.
Edit: 처음에는 clamp 기능을 코멘트대로 작성하였습니다.그러나 어셈블러 출력을 보면 VC++ 컴파일러가 중복 동작을 제거할 만큼 똑똑하지 않다는 것을 알 수 있었습니다.지시사항 하나만 줄이면 됩니다.:)
프로세서에 절대값에 대한 빠른 명령어가 있다면(x86과 마찬가지로) 분기가 없는 최소 및 최대를 수행할 수 있습니다. 이는 다음과 같습니다.if문 또는 3차 연산.
min(a,b) = (a + b - abs(a-b)) / 2
max(a,b) = (a + b + abs(a-b)) / 2
용어 중 하나가 0인 경우(클램핑할 때 자주 있는 경우) 코드는 다음을 더 단순화합니다.
max(a,0) = (a + abs(a)) / 2
할 때 두 결작합수대두할습체니을우경는하수있습니▁when다▁the대할▁oper체ations▁two▁you▁replace▁both▁can▁you're두▁combining 을/2/4또는*0.25한 발짝도 아끼기 위해.
다음 코드는 FMIN=0에 대한 최적화를 사용할 때 내 Athlon II X2의 ternary보다 3배 이상 빠릅니다.
double clamp(double value)
{
double temp = value + FMAX - abs(value-FMAX);
#if FMIN == 0
return (temp + abs(temp)) * 0.25;
#else
return (temp + (2.0*FMIN) + abs(temp-(2.0*FMIN))) * 0.25;
#endif
}
대부분의 컴파일러는 분기 대신 조건부 이동을 사용하는 네이티브 하드웨어 작업으로 컴파일할 수 있기 때문에 3차 연산자는 실제로 사용할 수 있습니다(따라서 잘못된 예측 패널티 및 파이프라인 버블 등을 방지합니다).비트 조작으로 인해 로드 히트 스토어가 발생할 가능성이 있습니다.
특히 SSE2를 사용하는 PPC와 x86에는 다음과 같은 고유한 하드웨어 op가 있습니다.
double fsel( double a, double b, double c ) {
return a >= 0 ? b : c;
}
이점은 분기를 일으키지 않고 파이프라인 내부에서 이 작업을 수행한다는 것입니다.실제로 컴파일러가 내장형을 사용하면 클램프를 직접 구현하는 데 사용할 수 있습니다.
inline double clamp ( double a, double min, double max )
{
a = fsel( a - min , a, min );
return fsel( a - max, max, a );
}
정수 연산을 사용하는 이중 비트 조작을 피하는 것이 좋습니다.대부분의 최신 CPU에서는 dcache로 왕복 이동하는 것 외에는 이중 레지스터와 int 레지스터 간에 데이터를 직접 이동할 수 있는 방법이 없습니다.이로 인해 메모리 쓰기가 완료될 때까지 CPU 파이프라인을 비우는 로드 히트 스토어(load-hit-store)라는 데이터 위험이 발생합니다(일반적으로 약 40 사이클).
이중 값이 이미 메모리에 있고 레지스터에 없는 경우에는 예외입니다. 이 경우 로드 히트 저장소의 위험이 없습니다.그러나 당신의 예는 당신이 방금 곱셈을 계산하고 함수에서 반환했다는 것을 나타내며, 이것은 그것이 여전히 XMM1에 있을 가능성이 높다는 것을 의미합니다.
16.16 표현의 경우, 단순한 3항성은 속도 면에서 더 나을 것 같지 않습니다.
그리고 더블의 경우, 표준/휴대용 C가 필요하기 때문에 어떤 종류의 비트 처리도 나쁘게 끝날 것입니다.
비트-피들이 가능하다고 해도(아마도), 당신은 2진수 표현인 2진수에 의존할 것입니다.이것(및 그 크기)은 구현에 따라 다릅니다.
아마도 당신은 크기(더블)를 사용하여 이것을 "추측"할 수 있고, 그 다음 다양한 이중 값의 레이아웃을 공통 이진 표현과 비교할 수 있지만, 당신은 아무것도 숨기지 않고 있다고 생각합니다.
가장 좋은 규칙은 컴파일러에게 원하는 것을 말하는 것입니다(기본적으로). 그리고 컴파일러가 사용자에게 최적화되도록 합니다.
편집: 겸손한 파이 타임.방금 Quinmars 아이디어(아래)를 테스트했는데 IEEE-754 플로트가 있으면 작동합니다.이것은 아래 코드에서 약 20%의 속도 향상을 제공했습니다.분명히 휴대할 수 없지만 컴파일러가 IEEE754 float 형식을 #IF...?를 사용하는지 묻는 표준화된 방법이 있을 수 있다고 생각합니다.
double FMIN = 3.13;
double FMAX = 300.44;
double FVAL[10] = {-100, 0.23, 1.24, 3.00, 3.5, 30.5, 50 ,100.22 ,200.22, 30000};
uint64 Lfmin = *(uint64 *)&FMIN;
uint64 Lfmax = *(uint64 *)&FMAX;
DWORD start = GetTickCount();
for (int j=0; j<10000000; ++j)
{
uint64 * pfvalue = (uint64 *)&FVAL[0];
for (int i=0; i<10; ++i)
*pfvalue++ = (*pfvalue < Lfmin) ? Lfmin : (*pfvalue > Lfmax) ? Lfmax : *pfvalue;
}
volatile DWORD hacktime = GetTickCount() - start;
for (int j=0; j<10000000; ++j)
{
double * pfvalue = &FVAL[0];
for (int i=0; i<10; ++i)
*pfvalue++ = (*pfvalue < FMIN) ? FMIN : (*pfvalue > FMAX) ? FMAX : *pfvalue;
}
volatile DWORD normaltime = GetTickCount() - (start + hacktime);
IEEE 754 부동 소수점의 비트는 정수로 해석되는 비트를 비교하면 부동 소수점과 직접 비교하는 것처럼 동일한 결과를 얻는 방식으로 정렬됩니다.따라서 정수를 클램프하는 방법을 찾거나 알고 있다면 (IEEE 754) 플로팅에도 사용할 수 있습니다.죄송합니다, 더 빠른 방법을 모르겠습니다.
어레이에 플로트가 저장되어 있다면 SSE3와 같은 일부 CPU 확장을 사용하는 것을 고려할 수 있다고 rkj는 말했습니다.당신은 liboil을 볼 수 있습니다. 그것은 당신을 위해 모든 더러운 일을 합니다.프로그램을 휴대용으로 유지하고 가능한 경우 더 빠른 CPU 명령을 사용합니다. (OS/컴파일러 독립적인 liboil이 어떤 방식인지는 잘 모르겠습니다.)
테스트 및 분기보다는 일반적으로 클램핑에 다음 형식을 사용합니다.
clampedA = fmin(fmax(a,MY_MIN),MY_MAX);
비록 컴파일된 코드에 대한 성능 분석을 한 적은 없지만요.
현실적으로, 어떤 괜찮은 컴파일러도 if() 문과 ?: 표현식 사이에 차이를 만들지 않습니다.코드는 충분히 간단해서 가능한 경로를 찾아낼 수 있습니다.그렇긴 하지만, 당신의 두 예는 동일하지 않습니다.?:를 사용하는 동등한 코드는 다음과 같습니다.
a = (a > MAX) ? MAX : ((a < MIN) ? MIN : a);
> MAX일 때 A < MIN 테스트를 피할 수 있습니다.그렇지 않으면 컴파일러가 두 테스트 간의 관계를 발견해야 하기 때문에 차이가 있을 수 있습니다.
클램핑이 드문 경우 한 번의 테스트로 클램프 필요성을 테스트할 수 있습니다.
if (abs(a - (MAX+MIN)/2) > ((MAX-MIN)/2)) ...
예를 들어 MIN=6 및 MAX=10의 경우 먼저 a를 8만큼 낮춘 다음 -2와 +2 사이에 있는지 확인합니다.이를 통해 비용을 절감할 수 있는지 여부는 분기의 상대적인 비용에 따라 크게 달라집니다.
다음은 @Roddy의 답변과 유사한 더 빠른 구현입니다.
typedef int64_t i_t;
typedef double f_t;
static inline
i_t i_tmin(i_t x, i_t y) {
return (y + ((x - y) & -(x < y))); // min(x, y)
}
static inline
i_t i_tmax(i_t x, i_t y) {
return (x - ((x - y) & -(x < y))); // max(x, y)
}
f_t clip_f_t(f_t f, f_t fmin, f_t fmax)
{
#ifndef TERNARY
assert(sizeof(i_t) == sizeof(f_t));
//assert(not (fmin < 0 and (f < 0 or is_negative_zero(f))));
//XXX assume IEEE-754 compliant system (lexicographically ordered floats)
//XXX break strict-aliasing rules
const i_t imin = *(i_t*)&fmin;
const i_t imax = *(i_t*)&fmax;
const i_t i = *(i_t*)&f;
const i_t iclipped = i_tmin(imax, i_tmax(i, imin));
#ifndef INT_TERNARY
return *(f_t *)&iclipped;
#else /* INT_TERNARY */
return i < imin ? fmin : (i > imax ? fmax : f);
#endif /* INT_TERNARY */
#else /* TERNARY */
return fmin > f ? fmin : (fmax < f ? fmax : f);
#endif /* TERNARY */
}
자세한 내용은 분기 없이 두 정수의 최소(최소) 또는 최대(최대) 계산 및 부동 소수점 수 비교를 참조하십시오.
IEEE 플로트와 이중 형식은 숫자가 사전적으로 정렬되도록 설계되었으며, 이는 IEEE 설계자 윌리엄 카한의 말에 따르면 "같은 형식의 두 부동소수점 숫자가 정렬되면(예: x < y), 비트가 부호 크기 정수로 재해석될 때 동일한 방식으로 정렬됩니다."
테스트 프로그램:
/** gcc -std=c99 -fno-strict-aliasing -O2 -lm -Wall *.c -o clip_double && clip_double */
#include <assert.h>
#include <iso646.h> // not, and
#include <math.h> // isnan()
#include <stdbool.h> // bool
#include <stdint.h> // int64_t
#include <stdio.h>
static
bool is_negative_zero(f_t x)
{
return x == 0 and 1/x < 0;
}
static inline
f_t range(f_t low, f_t f, f_t hi)
{
return fmax(low, fmin(f, hi));
}
static const f_t END = 0./0.;
#define TOSTR(f, fmin, fmax, ff) ((f) == (fmin) ? "min" : \
((f) == (fmax) ? "max" : \
(is_negative_zero(ff) ? "-0.": \
((f) == (ff) ? "f" : #f))))
static int test(f_t p[], f_t fmin, f_t fmax, f_t (*fun)(f_t, f_t, f_t))
{
assert(isnan(END));
int failed_count = 0;
for ( ; ; ++p) {
const f_t clipped = fun(*p, fmin, fmax), expected = range(fmin, *p, fmax);
if(clipped != expected and not (isnan(clipped) and isnan(expected))) {
failed_count++;
fprintf(stderr, "error: got: %s, expected: %s\t(min=%g, max=%g, f=%g)\n",
TOSTR(clipped, fmin, fmax, *p),
TOSTR(expected, fmin, fmax, *p), fmin, fmax, *p);
}
if (isnan(*p))
break;
}
return failed_count;
}
int main(void)
{
int failed_count = 0;
f_t arr[] = { -0., -1./0., 0., 1./0., 1., -1., 2,
2.1, -2.1, -0.1, END};
f_t minmax[][2] = { -1, 1, // min, max
0, 2, };
for (int i = 0; i < (sizeof(minmax) / sizeof(*minmax)); ++i)
failed_count += test(arr, minmax[i][0], minmax[i][1], clip_f_t);
return failed_count & 0xFF;
}
콘솔:
$ gcc -std=c99 -fno-strict-aliasing -O2 -lm *.c -o clip_double && ./clip_double
인쇄:
error: got: min, expected: -0. (min=-1, max=1, f=0)
error: got: f, expected: min (min=-1, max=1, f=-1.#INF)
error: got: f, expected: min (min=-1, max=1, f=-2.1)
error: got: min, expected: f (min=-1, max=1, f=-0.1)
제가 직접 SSE 접근법을 시도해봤는데, 조립품 출력이 꽤 깨끗해 보여서 처음에는 용기를 얻었지만, 수천 번이나 타이밍을 맞추다 보니 실제로는 꽤 느렸습니다.VC++ 컴파일러는 당신이 진정으로 의도하는 바를 알 수 있을 만큼 충분히 똑똑하지 않은 것처럼 보이며, 그렇게 해서는 안 될 때 XMM 레지스터와 메모리 사이에서 사물을 왔다 갔다 하는 것처럼 보입니다.그렇긴 하지만, 컴파일러가 어쨌든 모든 부동소수점 계산에 SSE 명령어를 사용하는 것처럼 보이는데 왜 3차 연산자에서 SSE min/max 명령어를 사용할 만큼 똑똑하지 않은지 모르겠습니다.반면에 PowerPC용으로 컴파일하는 경우 FP 레지스터에 내장된 fsel을 사용할 수 있으며 훨씬 더 빠릅니다.
위에서 지적한 것처럼 fmin/fmax 함수는 잘 작동합니다(cc, -fast-math 사용).gfortran에는 max/min에 해당하는 IA 명령어를 사용하는 패턴이 있지만 g++에는 없습니다.icc에서는 fmin/fmax가 무한 피연산자에서 작동하는 방식의 사양을 단축할 수 없기 때문에 std::min/max 대신 사용해야 합니다.
내 2센트짜리 C++.아마도 3차 연산자를 사용하는 것과 다르지 않을 것이며 분기 코드가 생성되지 않기를 바랍니다.
template <typename T>
inline T clamp(T val, T lo, T hi) {
return std::max(lo, std::min(hi, val));
}
내가 제대로 이해했다면, 당신은 "a" 값을 MY_MIN과 MY_MAX 사이의 범위로 제한하기를 원합니다."a"의 유형은 이중입니다.MY_MIN 또는 MY_MAX 유형을 지정하지 않았습니다.
간단한 표현:
clampedA = (a > MY_MAX)? MY_MAX : (a < MY_MIN)? MY_MIN : a;
그 묘기를 부려야 합니다.
MY_MAX와 MY_MIN이 정수일 경우 작은 최적화가 이루어질 수 있다고 생각합니다.
int b = (int)a;
clampedA = (b > MY_MAX)? (double)MY_MAX : (b < MY_MIN)? (double)MY_MIN : a;
정수 비교로 변경하면 약간의 속도 이점을 얻을 수 있습니다.
빠른 절대값 명령을 사용하려면 플로트를 [0,1] 범위로 고정하는 미니 컴퓨터에서 찾은 이 코드 캡처를 확인하십시오.
clamped = 0.5*(fabs(x)-fabs(x-1.0f) + 1.0f);
(코드를 조금 단순화했습니다.)우리는 두 가지 값을 취하는 것으로 생각할 수 있습니다. 하나는 >0으로 반영됩니다.
fabs(x)
그리고 다른 하나는 약 1.0을 반영하여 <1.0이 되었습니다.
1.0-fabs(x-1.0)
그리고 우리는 그들의 평균을 취합니다.범위 내에 있으면 두 값이 모두 x와 동일하므로 평균이 다시 x가 됩니다. 범위를 벗어나면 값 중 하나는 x가 되고 다른 하나는 "경계" 지점 위로 x가 되므로 평균은 정확하게 경계 지점이 됩니다.
언급URL : https://stackoverflow.com/questions/427477/fastest-way-to-clamp-a-real-fixed-floating-point-value
'programing' 카테고리의 다른 글
| 노드를 사용하여 MariaDB에 데이터를 삽입하는 데 문제가 발생했습니다.제이에스 (0) | 2023.06.19 |
|---|---|
| 카트 페이지 "WooCommerce"에서 배송 등급의 제로 레이트 값을 표시하는 방법 (0) | 2023.06.19 |
| PL/SQL에서 스레드화를 사용할 수 있습니까? (0) | 2023.06.14 |
| Oracle, 날짜 시간을 해당 월의 첫 번째 요일로 지정 (0) | 2023.06.14 |
| '' 항목이 이미 추가되었습니다. 오류 (0) | 2023.06.14 |