스택을 능가하는 힙 솔루션?

Question

나는 검증을위한 일련의 규칙이 주어지면, C 슬라이스를 '조각'으로 분해하고 각 슬라이스를 검증하는 C 시뮬레이션을 코딩하고있다. (기본 아이디어는 순서가 중요하며 규칙의 실제 의미는 그 위에있는 몇 가지 규칙의 영향을 받기 때문에 각 규칙과 그 위에 겹쳐있는 규칙 만 사용하여 '조각'을 만들 수 있습니다. 일반적으로 전체 시퀀스보다 훨씬 작은 조각입니다.)

내 문제는 다음과 같습니다.

구조체 (규칙)의 배열과 int (길이)를 포함하는 struct (policy)가 있습니다. 내 원래 구현은 후한의 malloc과 realloc을 사용 :

struct{ 
    struct rule *rules; 
    int length; 
}policy; 
... 
struct policy makePolicy(int length) 
{ 
    struct policy newPolicy; 
    newPolicy.rules = malloc(length * sizeof(struct rule)); 
    newPolicy.length = length; 
    return newPolicy; 
} 
... 
struct policy makeSlice(struct policy inPol, int rulePos) 
{ 
    if(rulePos > inPol.length - 1){ 
    printf("Slice base outside policy \n"); 
    exit(1); 
    } 
    struct slice = makePolicy(inPol.length); 
    //create slice, loop counter gets stored in sliceLength 
    slice.rules = realloc(slice.rules, sliceLength * sizeof(struct rule)); 
    slice.length = sliceLength; 
    return slice; 
} 

이 malloc으로 할당 한 메모리를 사용하면서, 나는 그것이 힙 많이 사용한다 있으리라 믿고있어. 이제 malloc이없는 실험용 병렬 시스템으로 이식하려고합니다.

슬픈 듯이 모든 것을 고정 크기 배열로 할당했습니다.

이제 충격을받습니다.

새 코드가 더 느리게 실행됩니다. 훨씬 느립니다.

(슬라이스 길이가 200이고, 한 시간이 300을 넘을 때까지 기다리는 데 사용 된 원래 코드 ... 이제 슬라이스 길이가 70, 80 ... 인 경우 시간이 오래 걸렸습니다. 아직은 200이 아닙니다.)

유일한 점은 전체 정책 (MAXBUFLEN은 10000)과 동일한 메모리가 슬라이스에 주어 지지만 전체가 실행되지 않는 것입니다. 전혀 메모리가 없습니다. 'top'은 소비 된 총 메모리가 이전과 마찬가지로 수십 메가 바이트 범위라는 것을 의미합니다. (그리고 물론 길이를 저장하는 동안, 나는 모든 것을 반복하지 않고 실제 규칙을 가진 부분 만 반복합니다.)

왜 갑자기 왜 그렇게 느린지 설명해 주시겠습니까?

Answer 1

구조체의 크기를 더 큰 크기 (예 : 10000 개의 규칙)로 고정하면 캐시 위치가 원래 크기보다 훨씬 더 커질 수 있습니다. 프로파일 러 (Valgrind의 oprofile 또는 cachegrind)를 사용하여 캐시가 문제인지 확인할 수 있습니다.

원본 프로그램에서 한 캐시 라인은 최대 8 개의 struct policy (64 비트 캐시 라인이있는 32 비트 시스템)을 유지할 수 있습니다. 그러나 수정 된 버전에서는 현재 캐시 라인 크기보다 훨씬 크기 때문에 하나만 보유 할 수 있습니다.

length 필드를 위로 이동하면 length과 처음 몇 개의 struct rule 개가 단일 캐시 라인에 들어갈 수 있으므로이 경우 성능을 향상시킬 수 있습니다.

struct policy{ 
    int length; 
    struct rule rules[10000]; 
}; 

이 문제를 해결하려면 캐시 위치를 보장하기 위해 사용자 지정 할당자를 작성해야합니다. 이 프로그램의 병렬 버전을 작성하는 경우 캐시 라인 경합을 피하기 위해 다른 스레드가 사용하는 메모리를 다른 캐시 라인으로 분리해야합니다.