바닥이 왜 이렇게 느려요?

바닥이 왜 이렇게 느려요?

최근에 코드(ISO/ANSIC)를 작성했는데 성능이 떨어져서 놀랐습니다.간단히 말해서, 범인은 범인인 것으로 밝혀졌습니다.floor()기능. 가 느렸을뿐만 아니라 벡터화가 되지 않았습니다(Intel compiler, 일명 ICL).속도가 느렸을 뿐만 아니라 (인텔 컴파일러, 일명 ICL과 함께) 벡터화되지 않았습니다.

다음은 2D 매트릭스의 모든 셀에 대해 플로어를 수행하는 몇 가지 벤치마크입니다.

VC:  0.10
ICL: 0.20

단순한 캐스팅과 비교해 보십시오.

VC:  0.04
ICL: 0.04

어떻게 할수있을까요floor()단순한 캐스팅보다 훨씬 느리다고요?!그것은 본질적으로 같은 일을 합니다 (부정적인 숫자를 제외하고).두 번째 질문:초고속 단식을 알고 있는 사람이 있습니까?floor()구현?

PS: 제가 벤치마킹하던 루프는 다음과 같습니다.

void Floor(float *matA, int *intA, const int height, const int width, const int width_aligned)
{
    float *rowA=NULL;
    int   *intRowA=NULL;
    int   row, col;

    for(row=0 ; row<height ; ++row){
        rowA = matA + row*width_aligned;
        intRowA = intA + row*width_aligned;
#pragma ivdep
        for(col=0 ; col<width; ++col){
            /*intRowA[col] = floor(rowA[col]);*/
            intRowA[col] = (int)(rowA[col]);
        }
    }
}

몇 가지는 바닥을 깁스보다 느리게 만들고 벡터화를 방지합니다.

가장 중요한 것은:

floor는 글로벌 상태를 수정할 수 있습니다.float 형식의 정수로 표현하기에는 너무 큰 값을 전달하면 errno 변수가 EDM으로 설정됩니다.NaNs에 대한 특별 취급도 수행됩니다.이 모든 동작은 오버플로 사례를 감지하고 어떻게든 상황을 처리하려는 애플리케이션을 위한 것입니다(방법을 묻지 마십시오).

이러한 문제가 있는 상태를 감지하는 것은 간단하지 않으며, 바닥 시공 시간의 90% 이상을 차지합니다.실제 라운딩은 가격이 저렴하며 인라인/벡터 처리가 가능합니다.또한 코드가 많아서 전체 플로어 기능을 줄이면 프로그램 실행 속도가 느려집니다.

일부 컴파일러에는 컴파일러가 거의 사용되지 않는 c-표준 규칙 중 일부를 최적화할 수 있는 특별한 컴파일러 플래그가 있습니다.예를 들어 GCC는 당신이 오류에 전혀 관심이 없다고 말할 수 있습니다.그렇게 하려면 -fno-math-errno 또는 -ff fast-math를 통과합니다.ICC와 VC는 유사한 컴파일러 플래그를 가질 수 있습니다.

Btw - 간단한 깁스를 사용하여 바닥 기능을 직접 굴릴 수 있습니다.부정적인 경우와 긍정적인 경우를 다르게 처리하면 됩니다.오버플로 및 NaN에 대한 특별한 처리가 필요 없다면 훨씬 더 빠를 수 있습니다.

만약 당신이 그 결과를 변환할 것이라면.floor()int에 대한 연산, 오버플로우가 걱정되지 않는다면 다음 코드는 다음 코드보다 훨씬 빠릅니다.(int)floor(x):

inline int int_floor(double x)
{
  int i = (int)x; /* truncate */
  return i - ( i > x ); /* convert trunc to floor */
}

가지가 없는 바닥과 천장(파이프라인을 더 잘 활용) 오류 검사 없음

int f(double x)
{
    return (int) x - (x < (int) x); // as dgobbi above, needs less than for floor
}

int c(double x)
{
    return (int) x + (x > (int) x);
}

바닥을 사용하거나

int c(double x)
{
    return -(f(-x));
}

최신 x86 CPU에서 대용량 어레이를 가장 빠르게 구현할 수 있는 방법은 다음과 같습니다.

• MXCSR FP 반올림 모드를 -Infinity(일명) 방향으로 반올림하도록 변경합니다.C에서, 이것은 가능해야 합니다.fenv물건, 또는_mm_getcsr/_mm_setcsr.

• 배열 작업을 루프오버합니다._mm_cvtps_epi32SIMD 벡터에서 4 변환float현재 반올림 모드를 사용하여 s부터 32비트 정수까지 저장합니다. (그리고 결과 벡터를 목적지에 저장합니다.)

  는 K10 또는 Core 2 이후의 Intel 또는 AMD CPU에서 단일 마이크로 fused uop입니다. (https://agner.org/optimize/) 256비트 AVX 버전의 경우에도 동일하며 YMM 벡터가 있습니다.

• MXCSR의 원래 값을 사용하여 현재 반올림 모드를 일반 IEEE 기본 모드로 복원합니다. (반올림에서 가장 가까이, 타이브레이크까지 있음)

이것은 자르는 것만큼 빠르게 클럭 주기 당 1개의 SIMD 결과 벡터를 로드 + 변환 + 저장할 수 있습니다. (SSE2에는 자르는 것에 대한 특별한 FP->int 변환 명령이 있는데, 그 이유는 정확히 C 컴파일러가 매우 일반적으로 필요하기 때문입니다.x87로 안좋았던 옛날에 심지어(int)xx87 라운딩 모드를 잘라내기로 변경한 후 다시 되돌려야 합니다.cvttps2dq 포장된 float->int(절단 포함)의 경우(추가 사항 참고)t기억법으로)또는 스칼라의 경우, XMM에서 정수 레지스터로 이동하거나,cvttsd2si스칼라에 대하여double스칼라 정수로.

일부 루프가 풀리거나 최적화가 잘 되면 캐시 누락 병목 현상이 없다고 가정할 때 프론트엔드의 클럭당 1개의 스토리지 처리량에서 병목 현상 없이 실행할 수 있습니다. (또한 Skylake 이전의 Intel에서는 클럭당 1개의 팩킹 변환 처리량에서 병목 현상이 발생했습니다.) 즉, SSE2, AVX 또는 AVX512를 사용하여 주기당 16, 32, 64바이트의 데이터를 처리할 수 있습니다.

---

현재 라운딩 모드를 변경하지 않고 SSE4.1이 필요합니다.roundpsA를 한 바퀴 돌다float정수에 가까운float선택한 라운딩 모드를 사용합니다.또는 기호가 지정된 32비트 정수에 들어갈 만큼 크기가 작은 플로트에 적합한 트릭 쇼 중 하나를 다른 답변에서 사용할 수도 있습니다. 어쨌든 최종 목적지 형식이기 때문입니다.)

---

(적절한 컴파일러 옵션을 통해)-fno-math-errno, 그리고 오른쪽-march아니면-msse4옵션, 컴파일러 인라인 가능floor사용.roundps, 또는 스칼라 및/또는 이중 정밀도 등가물(예:roundsd xmm1, xmm0, 1, 하지만 이것은 2uops의 비용이 들고 스칼라 또는 벡터에 대해 Haswell에 대한 2개의 클럭 당 1개의 처리량을 가집니다.는 인라인실, gcc8이 될 것입니다.2는 줄을 설 것입니다.roundsd위해서floorGodbolt 컴파일러 탐색기에서 볼 수 있듯이 빠른 연산 옵션이 없어도 가능합니다.하지만 그건.-march=haswell 버전이 안타깝게도 x86-64의 기본 버전이 아니기 때문에 컴퓨터에서 지원하는 경우 이를 활성화해야 합니다.)

.floor()IEEE fp 사양에서 많은 동작을 구현해야 하므로 모든 플랫폼에서 매우 느립니다.이너 루프에서는 사용할 수 없습니다.

매크로를 사용하여 플로어()의 근사치를 내기도 합니다.

#define PSEUDO_FLOOR( V ) ((V) >= 0 ? (int)(V) : (int)((V) - 1))

정확히 다음과 같이 동작하지 않습니다.floor(): 예를 들면,floor(-1) == -1그렇지만PSEUDO_FLOOR(-1) == -2, 하지만 대부분의 용도로는 충분히 가깝습니다.

부동 소수점과 정수 도메인 간의 단일 변환을 필요로 하는 실제로 분기 없는 버전은 값을 이동시킬 것입니다.x모든 양 또는 모든 음의 범위로 이동한 다음 주조/trunc하고 뒤로 이동합니다.

long fast_floor(double x)
{
    const unsigned long offset = ~(ULONG_MAX >> 1);
    return (long)((unsigned long)(x + offset) - offset);
}

long fast_ceil(double x) {
    const unsigned long offset = ~(ULONG_MAX >> 1);
    return (long)((unsigned long)(x - offset) + offset );
}

의견에서 지적한 바와 같이, 이 구현은 임시 값에 의존합니다.x +- offset넘치지 않는

64비트 플랫폼에서 int64_t 중간 값을 사용하는 원래 코드는 int32_t 축소된 범위 플로어/실에서 사용할 수 있는 것과 동일한 3개의 명령어 커널을 생성합니다.|x| < 0x40000000--

inline int floor_x64(double x) {
   return (int)((int64_t)(x + 0x80000000UL) - 0x80000000LL);
}
inline int floor_x86_reduced_range(double x) {
   return (int)(x + 0x40000000) - 0x40000000;
}

1. 그들은 같은 일을 하지 않습니다.플로어 ()는 함수입니다.따라서 이를 사용하면 함수 호출, 스택 프레임 할당, 파라미터 복사 및 결과 검색이 발생합니다.주조는 함수 호출이 아니기 때문에 더 빠른 메커니즘을 사용합니다(값 처리를 위해 레지스터를 사용할 수도 있다고 생각합니다)
2. 아마 floor()가 이미 최적화되어 있을 것입니다.
3. 알고리즘에서 더 많은 성능을 짜낼 수 있습니까?행과 열을 바꾸는 것이 도움이 될까요?공통 값을 캐시할 수 있습니까?컴파일러의 최적화 작업이 모두 완료되었습니까?운영체제를 바꿀 수 있습니까?컴파일러?Jon Bentley의 Programming Pearls는 가능한 최적화에 대한 훌륭한 리뷰를 가지고 있습니다.

빠른이중회전

double round(double x)
{
    return double((x>=0.5)?(int(x)+1):int(x));
}

---

터미널로그

테스트 사용자 지정_18.3837

테스트 native_118.4989

test custom_28.36333

테스트 native_2 18.5001

test custom_38.37316

테스트 native_3 18.5012

---

시험

void test(char* name, double (*f)(double))
{
    int it = std::numeric_limits<int>::max();

    clock_t begin = clock();

    for(int i=0; i<it; i++)
    {
        f(double(i)/1000.0);
    }
    clock_t end = clock();

    cout << "test " << name << " " << double(end - begin) / CLOCKS_PER_SEC << endl;

}

int main(int argc, char **argv)
{

    test("custom_1",round);
    test("native_1",std::round);
    test("custom_2",round);
    test("native_2",std::round);
    test("custom_3",round);
    test("native_3",std::round);
    return 0;
}

---

결과

타자를 쳐서 뇌를 사용하는 것은 기본 기능을 사용하는 것보다 ~3배 빠릅니다.

언급URL : https://stackoverflow.com/questions/824118/why-is-floor-so-slow