분기없는 오버플로 처리

Question

분기없이 자동으로 오버플로를 처리하는 안전한 버퍼 유형을 만들려고합니다. 버퍼 크기는 2의 거듭 제곱이며 유효한 양수 (즉, 0을 포함하지 않음) 색인 만 가져야합니다. 또한 해당 인덱스에 저장된 요소가 검색 키와 동일한 경우 지정된 색인에서 제거되는 확인 된 제거를 허용합니다.

나는 기본적으로 전달 된 인덱스가 범위를 벗어마다 buffer[0] 유효한 버퍼 인덱스가 아닙니다 그래서 나는 기본적으로 인덱스 0에 액세스하려면이

Element *buffer[256]; 

inline void buffer_insert(size_t index, Element *elem){ 
    buffer[index < 256 && index] = elem; 
} 

//Optional: checked insert to prevent overwrite. Will only insert 
//if the buffer holds NULL at index. 
inline void buffer_checkedInsert(size_t index, Element * elem){ 
    buffer[index && !buffer[index < 256 && index]] = elem; 
} 

inline void buffer_checkedRemove(size_t index, Element *elem){ 
    buffer[0] = NULL; //Maybe useful if buffer[0] stores elem 
    buffer[((elem == buffer[index < 256 && index)) && index] = NULL; 
} 

처럼 뭔가를 가고 있었다. 또한 제거 할 요소가 제거로 전달 된 요소와 같지 않을 때마다 인덱스 0에 액세스하려고합니다. 버퍼에 인덱스가 포함되어 있으면 인덱스 0에 액세스 할 수도 있습니다.

내 질문은 :

• 난 정말 무점포이 무엇인가? C 컴파일러가 & &의 단락 회로를 사용하기로 결정하면 코드가 분기 될 수 있습니다.
• & &으로 인해 분기가 발생하는 경우 분기와 관련없는 동일한 동작을하는 대체 방법이 있습니까?
• 기본 오버플로 검사보다 빠를 수 있습니까? 또는 C 컴파일러가 어떻게 든 if(index < 256) buffer[index] = elem의 분기없는 버전을 제공 할 수 있습니까?

Answer 1

정말 무점포이 무엇인가? C 컴파일러가 & &의 단락 회로를 사용하기로 결정하면 코드가 분기 될 수 있습니다.

아마도. 컴파일러는 이러한 경우 브랜치리스 머신 코드를 생성 할만큼 충분히 똑똑 할 수 있지만 의존 할 수는 없습니다.

& & 원인이 분기하는 경우, 분기 포함되지 않습니다이 경우 동일한 동작이있는 대안이 무엇입니까?

귀하의 질문에 약간 혼동이 있습니다. 컴파일러가 && 연산을 구현하기 위해 분기 코드를 내보낼 수 있다는 사실은 해당 연산의 정의 된 동작에서 따릅니다. 같은 행동을하는 대안은 동일한 분기 가능성을 가져야합니다.

반면에 이 모든 경우에 동일한 결과 인을 계산하는 대안이 있는지 묻는다면, 분기 가능성없이 그렇게 표현식을 다시 작성할 수 있습니다.

buffer[(index < 256) & (index != 0)] = elem; 

또는, 당신은 당신이 실제로 원하는 동작을 구현할 수 있습니다 : 예를 들어, 당신은 & 또는 * 운영자과 같이 중 하나를 사용할 수

buffer[(index < 256) * index] = elem; 

생각하는 아무 이유도 없다 컴파일러는 것 계산 중 하나에 대해 분기 명령어를 내 보냅니다. 그렇다면 목표 아키텍처에 성능 향상을 제공한다고 생각하기 때문일 것입니다.

기본 오버플로 확인보다 빠를 수 있습니까? 아니면 C 컴파일러는 if (index < 256) 버퍼 [index] = elem?의 분기없는 버전을 줄 수 있습니까?

확실히 분기가없는 버전은 일 수 있습니다.이 빠릅니다. 이들은 (비) 분기가 많이 실행되는 워크로드에서 관찰 가능하게 더 빠를 가능성이 높으며 대안이 취해지기 쉬운 식별 할 수있는 패턴이 없습니다. 그러나 (비) 브랜치가 대부분 규칙적인 패턴을 따르고, 특히 거의 항상 한 방향으로가는 경우, CPU의 브랜치 예측 유닛은 최소한 브랜치가없는 할당만큼 일반적인 유효성 검사를 수행 할 수 있습니다.

궁극적으로 실제 데이터 또는 그 좋은 팩시밀리에서 코드의 실제 성능을 벤치마킹하지 않고서는 걱정할 필요가 없습니다. 결과는 데이터에 따라 달라질 수 있으며, 중요한 것은 프로그램의 런타임이 사용자가 묻는 기능에 소비되는 양에 따라 다릅니다. 때까지 다른 사람이 요구하는 좋은 벤치 마크가 없다면, 명확성과 유지 보수를 위해 코드를 작성해야합니다.