실제 (고정/부동 소수점) 값을 클램핑하는 가장 빠른 방법?

https://stackoverflow.com/questions/427477

06-07-2019
|

문제

IF 문이나 3 배 연산자를 사용하는 것보다 실수를 클램핑하는보다 효율적인 방법이 있습니까? 나는 복식과 32 비트 Fixpoint 구현 (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;

Fixpoint 버전은 비교를 위해 함수/매크로를 사용합니다.

이것은 코드의 성능 크리티컬 부분으로 이루어 지므로 가능한 한 효율적인 방법을 찾고 있습니다 (비트 조작과 관련이있을 것입니다).

편집 : 표준/휴대용 C 여야하며, 플랫폼 별 기능은 여기에 관심이 없습니다. 또한, MY_MIN 그리고 MY_MAX 클램핑하려는 값과 동일한 유형입니다 (위의 예에서 두 배).

해결책

16.16 표현의 경우 간단한 삼구가 속도로 향상되지 않을 것입니다.

그리고 복식의 경우 표준/휴대용 C가 필요하기 때문에 모든 종류의 비트 풀링은 나쁘게 끝납니다.

비트 풀이 가능하더라도 (내가 의심되는), 당신은 복식의 이진 표현에 의존 할 것입니다. 이 (및 그 크기)는 구현에 따라 다릅니다.

아마도 (이중) 크기를 사용하여 이것을 "추측"하고 공통 바이너리 표현과 다양한 이중 값의 레이아웃을 비교할 수 있지만, 나는 당신이 아무것도 숨기고 있다고 생각합니다.

가장 좋은 규칙은 컴파일러에게 원하는 것을 알려주는 것입니다 (예 : Ternary).

편집하다: 겸손한 파이 시간. 방금 Quinmars 아이디어 (아래)를 테스트했으며 IEEE -754 플로트가 있다면 작동합니다. 이것은 아래 코드에서 약 20%의 속도를 높였습니다. iobvely는 포트할 수 없지만 #if ...이있는 IEEE754 플로트 형식을 사용하는 경우 컴파일러를 묻는 표준화 된 방법이있을 수 있습니까?

  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);

다른 팁

오래된 질문이지만 오늘이 문제를 해결하고있었습니다 (복식/부유물 포함).

가장 좋은 방법은 플로트에 SSE MINSS/MAXSS를 사용하고 DOBLES에는 SSE2 MINSD/MAXSD를 사용하는 것입니다. 이것들은 분기가없고 각각 하나의 클록 사이클을 가져 오며 컴파일러 내입 덕분에 사용하기 쉽습니다. 그들은 std :: min/max를 사용한 클램핑과 비교하여 성능의 크기 증가 이상을 부여합니다.

당신은 그 놀라운 것을 알 수 있습니다. 나는 확실히했다! 불행히도 VC ++ 2010은 /arch : SSE2 및 /FP : FAST가 활성화 된 경우에도 std :: min /max에 대해 간단한 비교를 사용합니다. 다른 컴파일러에 대해서는 말할 수 없습니다.

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를 제외하고 동일합니다.

편집 : 처음에 나는 댓글을 달린대로 클램프 함수를 썼습니다. 그러나 어셈블러 출력을 살펴보면 VC ++ 컴파일러가 중복 이동을 흐리게하기에 충분히 똑똑하지 않다는 것을 알았습니다. 덜 지침. :)

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

세 가지 지침 (RET를 세지 않음), 가지가 없습니다. 훌륭한.

이것은 코어 i3 M 350을 사용하여 Ubuntu 13.04에서 GCC 4.7 및 Clang 3.2로 테스트되었습니다. 참고로, 간단한 C ++ 코드를 std :: min 및 std :: max를 동일한 어셈블리를 생성했습니다.

이것은 복식을위한 것입니다. INT의 경우 GCC와 Clang은 모두 5 개의 지침 (RET를 계산하지 않음)과 가지가없는 어셈블리를 생성합니다. 또한 우수합니다.

나는 현재 고정점을 사용하지 않으므로 고정점에 대한 의견을 제시하지 않을 것입니다.

프로세서에 절대 값에 대한 빠른 명령이있는 경우 (X86과 같이), 당신은 분기없는 최소 및 최대를 수행 할 수 있습니다. if 성명서 또는 삼여 작업.

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

두 작업을 결합 할 때 두 가지를 교체 할 수 있습니다. /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 파이프 라인을 비 웁니다 (일반적으로 약 40 사이클 정도).

이에 대한 예외는 이중 값이 이미 메모리에 있고 레지스터에 있지 않은 경우입니다.이 경우로드 히트 스토어의 위험이 없습니다. 그러나 예제는 방금 두 배를 계산하고 함수에서 반환했음을 나타내며, 이는 여전히 XMM1에있을 가능성이 있음을 의미합니다.

IEEE 754 플로팅 포인트의 비트는 정수로 해석 된 비트를 비교하면 직접 플로트로 비교할 수있는 것과 동일한 결과를 얻는 방식으로 주문됩니다. 따라서 정수를 클램핑하는 방법을 찾거나 알고 있다면 (IEEE 754) 플로트에도 사용할 수 있습니다. 죄송합니다. 더 빠른 방법을 모르겠습니다.

RKJ가 말한 것처럼 플로트가 배열에 저장된 경우 SSE3과 같은 일부 CPU 확장을 사용하는 것을 고려할 수 있습니다. 당신은 liboil을 볼 수 있습니다. 그것은 당신을 위해 모든 더러운 일을합니다. 프로그램을 휴대용으로 유지하고 가능한 경우 더 빠른 CPU 지침을 사용합니다. (OS/컴파일러 독립적 인 liboil이 얼마나 확실하지 않습니다).

테스트와 분기 대신 일반적으로 클램핑 에이 형식을 사용합니다.

clampedA = fmin(fmax(a,MY_MIN),MY_MAX);

컴파일 된 코드에 대해 성능 분석을 한 적이 없지만.

현실적으로, 괜찮은 컴파일러는 if () 문과 a? : expression을 차이가 없습니다. 코드는 가능한 경로를 발견 할 수있을 정도로 간단합니다. 즉, 두 가지 예는 동일하지 않습니다. 동등한 코드를 사용 하는가? :

a = (a > MAX) ? MAX : ((a < MIN) ? MIN : a);

a> max 일 때 a <min 테스트를 피하십시오. 컴파일러는 그렇지 않으면 두 테스트 사이의 관계를 발견해야하므로 차이를 만들 수 있습니다.

클램핑이 드문 경우 단일 테스트로 클램프해야 할 필요성을 테스트 할 수 있습니다.

if (abs(a - (MAX+MIN)/2) > ((MAX-MIN)/2)) ...

예를 들어 최소 = 6 및 최대 = 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 아키텍트의 말로 윌리엄 카한 (William Kahan)이라는 말을 의미합니다. 그들은 비트가 부호를받는 정수로 재 해석 될 때 같은 방식으로 주문됩니다.”

시험 프로그램 :

/** 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 지침을 사용하는 것처럼 보일 때 Compiler가 왜 Ternary Operator에서 SSE Min/Max 지침을 사용하기에 충분히 똑똑하지 않은지 모르겠습니다. 반면에 PowerPC를 위해 컴파일하는 경우 FP 레지스터에서 FSEL Intrinsic을 사용할 수 있으며 더 빠릅니다.

내가 올바르게 이해한다면, 당신은 "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를 뒤집으므로 평균은 정확히 경계 지점이됩니다.

위에서 지적한 바와 같이, FMIN/FMAX 기능은 (-ffast -math와 함께 GCC에서) 잘 작동합니다. Gfortran에는 Max/Min에 해당하는 IA 지침을 사용하는 패턴이 있지만 G ++는 그렇지 않습니다. ICC에서는 ICC가 FMIN/FMAX가 아닌 오페라에서 작동하는 방식의 사양을 단축하는 것을 허용하지 않기 때문에 ICC에서는 std :: min/max를 사용해야합니다.

C ++의 2 센트. 아마도 3 배의 연산자 사용과 다르지 않으며 분기 코드가 생성되지 않기를 바랍니다.

template <typename T>
inline T clamp(T val, T lo, T hi) {
    return std::max(lo, std::min(hi, val));
}

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow