Rozwiązanie w postaci sterty przewyższa stos?

Question

Kodowanie symulacji C, w której, biorąc pod uwagę sekwencję reguł do zweryfikowania, dzielimy ją na "plasterki" i weryfikujemy każdy plaster. (Podstawową ideą jest to, że kolejność jest ważna, a na faktyczne znaczenie reguły mają wpływ niektóre reguły powyżej, możemy utworzyć "plaster" z każdą regułą i tylko powyższe zasady, które ją pokrywają. plasterki, które są zwykle znacznie mniejsze niż cała sekwencja.)

Mój problem wygląda następująco.

Mam struct (policy), która zawiera tablicę struktur (reguł) i int (długość). Moja oryginalna implementacja używane malloc i realloc liberalnie:

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

Ponieważ wykorzystuje pamięć malloc'ed, jestem zakładając, że znaczący sposób korzysta z hałdy. Teraz próbuję przenieść się na eksperymentalną maszynę równoległą, która nie ma malloc.

I smutno poszedł i przyznane wszystko z tablic o ustalonym rozmiarze.

Teraz jest szok.

Nowy kod działa wolniej. Znacznie wolniej.

(Oryginalny kod używany do czekania na minuty na końcu, gdy długość plasterka miała wynosić 200, a może na godzinę na ponad 300 ... teraz robi to, gdy długość plastra wynosi 70, 80 ... i ma trwały godziny, powiedzmy 120. Wciąż nie 200.)

Jedyną rzeczą jest to, że teraz plasterki mają taką samą pamięć jak pełna polityka (MAXBUFLEN to 10000), ale całość nie wydaje się być wyczerpana pamięci w ogóle. "top" pokazuje, że całkowita ilość zużywanej pamięci jest dość skromna i wynosi kilkadziesiąt megabajtów, jak wcześniej. (I oczywiście, kiedy przechowuję długość, nie przejmuję się całą tą kwestią, tylko częścią z prawdziwymi regułami).

Czy ktoś mógłby pomóc ci wyjaśnić, dlaczego nagle stało się tak wolniej?

Answer 1

Wygląda na to, że po poprawieniu rozmiaru struktury do większego rozmiaru (powiedzmy 10000 reguł), lokalizacja pamięci podręcznej może stać się znacznie gorsza niż oryginalna. Możesz użyć profilera (oprofile lub cachegrind w Valgrind), aby sprawdzić, czy bufor jest problemem.

W oryginalnym programie jedna linia pamięci podręcznej może pomieścić maksymalnie 8 struct policy (na 32-bitowej maszynie z 64-bitową linią pamięci podręcznej). Ale w zmodyfikowanej wersji może je tylko posiadać, ponieważ jest teraz dużo większy niż rozmiar linii podręcznej.

przenieść pole length się może poprawić wydajność w tym przypadku od teraz length i kilka pierwszych struct rule s zmieści się w jednej linii cache.

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

Aby rozwiązać ten problem, należy napisać własny niestandardowy przydział, aby zapewnić lokalizację pamięci podręcznej. Jeśli piszesz równoległą wersję tego programu, pamiętaj, aby odizolować pamięć używaną przez różne wątki w różnych liniach pamięci podręcznej, aby uniknąć rywalizacji o linię pamięci podręcznej.