비트 필드:설정 대 테스트 및 설정(성능을 위해)

StackOverflow https://stackoverflow.com/questions/964522

  •  12-09-2019
  •  | 
  •  

문제

다음과 같은 C 구조의 인스턴스가 많이 있습니다.

struct mystruct
{
    /* ... */
    unsigned flag: 1;
    /* ... */
};
  • flag 처음에는 0이지만 특정 기능을 종료할 때는 1이어야 합니다.

가장 간단한 구현은 다음과 같습니다.

void set_flag(struct mystruct *sp)
{
    sp->flag = 1U;
}

그러나 대신 이 작업을 수행하면 성능에 어떤 영향을 미칠 수 있습니까?

void set_flag(struct mystruct *sp)
{
    if (sp->flag == 0U)
    {
        sp->flag = 1U;
    }
}

메인 메모리에 쓰는 것을 피하고 싶습니다.첫 번째 버전은 항상 쓰기를 수행하고 두 번째 버전은 플래그가 아직 설정되지 않은 경우에만 쓰기를 수행하지만 대부분의 경우 플래그가 이미 설정되어 있습니다.

다른 요인(예:분기 예측)이 성능에 영향을 미칠 가능성이 있습니까?

지금까지 약간의 속도 증가를 보았지만 데이터 세트가 커질수록 속도가 더욱 중요해지기를 바랍니다.

이러한 변경으로 인해 대규모 데이터 세트의 경우 프로그램 속도가 느려질 위험이 있습니까? 그렇다면 어떤 상황에서 이런 일이 발생할 수 있습니까?

도움이 되었습니까?

해결책

세트 전 테스트는 차이를 만들지 만, 그것이 얼마나 많이 사용되는지에 따라 다릅니다.

데이터는 두 경우 모두 캐시 라인으로 끝납니다 (예 : 쓰기 또는 테스트 및 세트).

그러나 캐시 라인에 더러운 (예 : 수정) 또는 청소로 태그가 지정된 경우 차이가 있습니다. 더러운 캐시 라인은 메인 메모리로 다시 작성해야하며 깨끗한 캐시 라인은 잊혀지고 새로운 데이터로 채워질 수 있습니다.

이제 코드가 엄청난 양의 데이터를 망설이고 각 데이터 덩어리에 한 번 또는 두 번만 액세스 할 수 있습니다. 그렇다면 대부분의 메모리 액세스가 캐시 미스라고 가정 할 수 있습니다. 캐시 라인의 대부분이 캐시 미스가 발생하고 대부분의 캐시 라인이 더러워지는 지점에서 더럽 히면 어떻게됩니까?

새로운 데이터가 라인에로드되기 전에 메인 메모리에 다시 작성해야합니다. 이것은 캐시 라인의 내용을 잊어 버리는 것보다 느립니다. 또한 캐시와 기본 메모리 사이의 메모리 대역폭을 두 배로 늘립니다.

요즘 메모리가 빠르기 때문에 한 번 CPU 코어에 차이가 없을 수도 있지만 다른 CPU는 다른 작업도 수행 할 것입니다. 버스가 캐시 라인을 안팎으로 움직이지 않으면 다른 CPU 코어가 모든 것을 더 빨리 실행할 수 있습니다.

간단히 말해서 : 캐시 라인을 깨끗하게 유지하면 대역폭 요구 사항의 절반이 될 것이며 캐시 미스를 약간 더 저렴하게 만듭니다.

지점과 관련하여 : 물론 : 비용이 많이 들지만 캐시 미스는 훨씬 더 나쁩니다! 또한 운이 좋으면 CPU는 주문 실행 기능을 사용하여 분기 비용으로 캐시가 오프셋됩니다.

이 코드에서 가능한 최상의 성능을 얻으려면 실제로 액세스 할 수있는 대부분의 액세스가 캐시 미스 인 경우 두 가지 옵션이 있습니다.

  • 캐시를 우회하십시오 : X86 아키텍처에는이 목적을 위해 비 시간 부하와 저장소가 있습니다. 그들은 SSE 명령 세트 어딘가에 숨겨져 있으며 내 고유를 통해 C- 언어에서 사용할 수 있습니다.

  • (전문가의 경우에만) : 테스트 및 세트 기능을 CMOV (조건부 이동) 명령어를 사용하는 어셈블러로 대체하는 일부 인라인 어셈블러 라인을 사용하십시오. 이것은 캐시 라인을 깨끗하게 유지할뿐만 아니라 분기를 피할 수 있습니다. 이제 CMOV는 느린 지시이며 분기를 예측할 수없는 경우에만 지점을 능가합니다. 따라서 코드를 벤치마킹하는 것이 좋습니다.

다른 팁

이것은 흥미로운 질문이며, 캐시 라인에 대한 Nils의 답변은 확실히 훌륭한 조언입니다.

나는의 중요성을 강조하고 싶습니다 실제 성능을 측정하기위한 프로파일 링 코드 - 당신이 겪고있는 데이터에 이미 깃발을 얼마나 자주 설정하는지 측정 할 수 있습니까? 답변에 따라 성능이 많이 바뀔 수 있습니다.

재미를 위해, 나는 당신의 코드를 사용하여 다양한 비율의 1의 다양한 비율로 채워진 5 천만 요소 배열에서 세트와 세트를 약간 비교했습니다. 그래프는 다음과 같습니다.

comparison of set vs. test-then-set
(원천: natekohl.net)

이것은 물론 장난감 예일뿐입니다. 그러나 내가 기대하지 않은 비선형 성능에 주목하고 배열이 거의 완전히 채워질 때 테스트-세트가 일반 세트보다 빠릅니다.

이것이 당신의 요구 사항에 대한 나의 해석입니다.

  • 플래그가 별도로 초기화되어 있습니다
  • 한 번만 설정되며 그 후에는 재설정되지 않습니다.
  • 그러나이 세트 시도는 같은 깃발에서 여러 번 이루어집니다.
  • 그리고이 깃발 인스턴스가 많이 있습니다 (각각 동일한 종류의 처리가 필요합니다)

그것을 가정하면

  • 공간 최적화는 시간 최적화보다 상당히 낮습니다.

나는 다음과 같은 것을 제안한다.

  • 첫째, 32 비트 시스템에서 액세스 시간에 대해 걱정하는 경우 32 비트 정수를 사용하는 데 도움이됩니다.
  • 플래그 'Word'에서 확인을 건너 뛰면 쓰기가 매우 빠릅니다. 그러나 아직 설정하지 않은 경우 계속 확인하고 설정할 수있는 매우 많은 플래그가 있다는 점을 감안할 때 조건부 체크인을 유지하는 것이 좋습니다.
  • 그러나 플랫폼이 병렬 작업을 수행하는 경우 (예를 들어, 디스크에 쓰기가 일반적으로 코드 실행과 병렬로 전송 될 수 있음) 수표를 건너 뛰는 것이 좋습니다.

이 최적화는 더 큰 데이터세트로 이동할 때 속도 감소를 유발하지 않을 가능성이 높습니다.

값을 읽을 때 캐시 스래싱은 동일하고 분기 예측 페널티도 동일하며 이것이 여기에서 최적화할 핵심 요소입니다.

분기 예측은 분기 명령어별로 기록을 저장하므로 다른 주소(예: 인라인 함수)의 명령어를 사용하여 분기하는 한 인스턴스 수는 상관하지 않습니다.인라인되지 않은 단일 함수 엔터티가 있는 경우 모든 항목에 대해 하나의 분기 명령을 갖게 되며 이로 인해 분기 예측이 억제되어 더 자주 누락되고 페널티가 증가합니다.

당신은 항상 프로필을 할 수 있지만 첫 번째 버전이 더 빠르고 모호하다고 확신합니다.

어느 접근법도 데이터가 캐시에로드되어야하므로 저장은 읽기/쓰기와 쓰기의 차이입니다.

이 변경이 어떻게 더 큰 데이터 세트로 코드가 느리게 만들 수 있는지 알지 못하므로 그 앞에서 충분히 안전 할 것입니다.

그것은 나에게 조기에 최적의 냄새가납니다. (프로파일 링이 이것을 병목 현상으로 식별하지 않는 한)

모든 것과 마찬가지로 성능과 마찬가지로 코드 변경의 영향을 확인하는 가장 좋은 방법은이를 측정하는 것입니다. 많은 양의 테스트 데이터를 비교적 쉽게 만들 수 있어야합니다.

시간 성능에 대해 정말로 걱정된다면 비트 필드 대신 Full Int로 플래그를 변경하십시오. 그런 다음 설정은 단지 쓰기 일뿐 아니라 비트 필드와 마찬가지로 읽기 쓰기가 아닙니다.

그러나 이미 지적했듯이, 이것은 미세 최적화의 냄새가납니다.

세트 전 테스트는 의미가 없습니다. 테스트가없는 코드는 더 깨끗하고 조금 더 빠릅니다.

부수적으로 - 기능 호출에 대한 오버 헤드가 기능 본체보다 크기 때문에 이와 같은 기능을 인라인으로하는 것이 합리적입니다.

아무도 말하지 않았기 때문에 나는 할 것이다.

왜 비트 필드를 전혀 사용하고 있습니까? 레이아웃은 컴파일러마다 다르므로 인터페이스의 경우 쓸모가 없습니다. 그들은 더 공간 효율적 일 수도 있고 그렇지 않을 수도 있습니다. 컴파일러는 단지 물건을 효율적으로 패드하기 위해 32 비트 필드로 밀어 넣기로 결정할 수 있습니다. 더 빠른 보장은 없으며 실제로 느리게 될 가능성이 높습니다.

나는 직장에서 그들의 사용을 금지했다. 누군가가 나에게 추가 기능을 제공한다는 설득력있는 이유를 줄 수 없다면, 그들과 함께 연주 할 가치가 없습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top