Dlaczego zestaw malloc + jest wolniejszy niż calloc?

Wiadomo, że callocróżni się od malloctego, że inicjalizuje przydzieloną pamięć. Za callocpomocą pamięć jest ustawiona na zero. Zmalloc pomocą pamięć nie zostanie wyczyszczona.

Tak więc w codziennej pracy uważam callocza malloc+memset . Nawiasem mówiąc, dla zabawy napisałem następujący kod dla testu porównawczego.

Wynik jest mylący.

Kod 1:

#include<stdio.h>
#include<stdlib.h>
#define BLOCK_SIZE 1024*1024*256
int main()
{
        int i=0;
        char *buf[10];
        while(i<10)
        {
                buf[i] = (char*)calloc(1,BLOCK_SIZE);
                i++;
        }
}

Wyjście kodu 1:

time ./a.out  
**real 0m0.287s**  
user 0m0.095s  
sys 0m0.192s  

Kod 2:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define BLOCK_SIZE 1024*1024*256
int main()
{
        int i=0;
        char *buf[10];
        while(i<10)
        {
                buf[i] = (char*)malloc(BLOCK_SIZE);
                memset(buf[i],'\0',BLOCK_SIZE);
                i++;
        }
}

Wyjście kodu 2:

time ./a.out   
**real 0m2.693s**  
user 0m0.973s  
sys 0m1.721s  

Zastępuje memsetsiębzero(buf[i],BLOCK_SIZE) w Kodzie 2 daje ten sam wynik.

Moje pytanie brzmi: dlaczego malloc+ jest memseto wiele wolniejszy niż calloc? Jak to calloczrobić?

Krótka wersja: Zawsze używaj calloc()zamiast malloc()+memset(). W większości przypadków będą takie same. W niektórych przypadkach calloc()wykona mniej pracy, ponieważ może memset()całkowicie pominąć . W innych przypadkach calloc()można nawet oszukiwać i nie przydzielać żadnej pamięci! Jednak,malloc()+memset() zawsze zrobić pełną kwotę pracy.

Zrozumienie tego wymaga krótkiej prezentacji systemu pamięci.

Szybka prezentacja pamięci

Są tutaj cztery główne części: twój program, standardowa biblioteka, jądro i tabele stron. Znasz już swój program, więc ...

Alokatory pamięci lubią malloc()i calloc()są tam głównie po to, aby pobierać małe alokacje (od 1 bajtu do 100 KB) i grupować je w większe pule pamięci. Na przykład, jeśli przydzielisz 16 bajtów, malloc()najpierw spróbujesz pobrać 16 bajtów z jednej z jego pul, a następnie poprosi o więcej pamięci z jądra, gdy pula będzie sucha. Ponieważ jednak program, o który pytasz, przydziela jednocześnie dużą ilość pamięci malloc()i calloc()po prostu poprosi o tę pamięć bezpośrednio z jądra. Próg tego zachowania zależy od twojego systemu, ale widziałem 1 MiB zastosowany jako próg.

Jądro jest odpowiedzialne za przydzielanie rzeczywistej pamięci RAM do każdego procesu i upewnianie się, że procesy nie zakłócają pamięci innych procesów. Nazywa się to ochroną pamięci, było powszechne od lat dziewięćdziesiątych i jest to powód, dla którego jeden program może ulec awarii bez awarii całego systemu. Kiedy więc program potrzebuje więcej pamięci, nie może po prostu wziąć pamięci, ale zamiast tego prosi o pamięć z jądra za pomocą wywołania systemowego, takiego jak mmap()lub sbrk(). Jądro da RAM każdemu procesowi poprzez modyfikację tablicy stron.

Tabela stron odwzorowuje adresy pamięci na rzeczywistą fizyczną pamięć RAM. Adresy twojego procesu, od 0x00000000 do 0xFFFFFFFF w systemie 32-bitowym, nie są prawdziwą pamięcią, ale są adresami w pamięci wirtualnej. Procesor dzieli te adresy na 4 strony KiB, a każda strona może być przypisana do innego kawałka fizycznej pamięci RAM poprzez modyfikację tabeli stron. Tylko jądro może modyfikować tablicę stron.

Jak to nie działa

Oto jak przydzielanie 256 MiB nie działa:

1. Twój proces wzywa calloc()i prosi o 256 MiB.

2. Standardowa biblioteka wzywa mmap()i prosi o 256 MiB.

3. Jądro znajduje 256 MiB nieużywanej pamięci RAM i przekazuje ją do procesu poprzez modyfikację tabeli stron.

4. Biblioteka standardowa zeruje pamięć RAM memset()i zwraca wartość calloc().

5. Twój proces w końcu kończy się, a jądro odzyskuje pamięć RAM, dzięki czemu może być używany przez inny proces.

Jak to faktycznie działa

Powyższy proces działałby, ale po prostu tak się nie dzieje. Istnieją trzy główne różnice.

• Kiedy proces pobiera nową pamięć z jądra, pamięć ta prawdopodobnie była wcześniej używana przez inny proces. To ryzyko bezpieczeństwa. Co jeśli ta pamięć ma hasła, klucze szyfrujące lub tajne przepisy salsy? Aby nie dopuścić do wycieku poufnych danych, jądro zawsze szoruje pamięć przed przekazaniem jej do procesu. Równie dobrze możemy wyszorować pamięć, zerując ją, a jeśli nowa pamięć zostanie wyzerowana, równie dobrze możemy uczynić ją gwarancją, więc mmap()gwarantuje, że nowa pamięć, którą zwraca, jest zawsze zerowana.

• Istnieje wiele programów, które przydzielają pamięć, ale nie używają jej od razu. Czasami pamięć jest przydzielana, ale nigdy nie używana. Jądro to wie i jest leniwe. Kiedy przydzielasz nową pamięć, jądro w ogóle nie dotyka tablicy stron i nie daje żadnej pamięci RAM procesowi. Zamiast tego znajduje w twoim procesie pewną przestrzeń adresową, odnotowuje, co tam ma się udać, i obiecuje, że umieści tam pamięć RAM, jeśli Twój program faktycznie z niej skorzysta. Kiedy program próbuje odczytać lub zapisać z tych adresów, procesor powoduje błąd strony, a jądro wykonuje kroki w celu przypisania pamięci RAM do tych adresów i wznawia działanie programu. Jeśli nigdy nie użyjesz pamięci, błąd strony nigdy się nie zdarzy, a twój program nigdy nie dostanie pamięci RAM.

• Niektóre procesy przydzielają pamięć, a następnie odczytują z niej pamięć, nie modyfikując jej. Oznacza to, że wiele stron w pamięci w różnych procesach może być wypełnionych nieskazitelnymi zerami mmap(). Ponieważ te strony są takie same, jądro sprawia, że ​​wszystkie te wirtualne adresy wskazują pojedynczą wspólną stronę 4 KiB pamięci wypełnioną zerami. Jeśli spróbujesz zapisać w tej pamięci, procesor wyzwala kolejną usterkę strony, a jądro wkracza, aby uzyskać nową stronę zer, która nie jest współużytkowana z innymi programami.

Ostateczny proces wygląda mniej więcej tak:

1. Twój proces wzywa calloc()i prosi o 256 MiB.

2. Standardowa biblioteka wzywa mmap()i prosi o 256 MiB.

3. Jądro znajduje 256 MiB nieużywanej przestrzeni adresowej, robi notatkę o tym, do czego ta przestrzeń adresowa jest teraz używana, i zwraca.

4. Standardowa biblioteka wie, że wynik mmap()jest zawsze wypełniony zerami (lub będzie, gdy rzeczywiście dostanie trochę pamięci RAM), więc nie dotyka pamięci, więc nie ma błędu strony, a pamięć RAM nigdy nie jest przekazywana procesowi .

5. Twój proces w końcu kończy się, a jądro nie musi odzyskiwać pamięci RAM, ponieważ nigdy nie zostało przydzielone.

Jeśli użyjesz memset()do zerowania strony, memset()spowoduje to błąd strony, spowoduje przydzielenie pamięci RAM, a następnie wyzeruje ją, mimo że jest już wypełniona zerami. Jest to ogromna ilość dodatkowej pracy i wyjaśnia, dlaczego calloc()jest szybsza niż malloc()i memset(). Jeśli kończy się przy użyciu pamięci i tak, calloc()jest jeszcze szybszy niż malloc()a memset(), ale różnica nie jest aż tak śmieszne.

To nie zawsze działa

Nie wszystkie systemy mają stronicowaną pamięć wirtualną, więc nie wszystkie systemy mogą korzystać z tych optymalizacji. Odnosi się to do bardzo starych procesorów, takich jak 80286, a także do procesorów osadzonych, które są po prostu zbyt małe, aby stworzyć wyrafinowaną jednostkę zarządzania pamięcią.

To również nie zawsze będzie działać przy mniejszych przydziałach. Przy mniejszych przydziałach calloc()pobiera pamięć ze wspólnej puli zamiast przechodzić bezpośrednio do jądra. Ogólnie we wspólnej puli mogą znajdować się niepotrzebne dane ze starej pamięci, która była używana i zwalniana free(), więc calloc()można było pobrać tę pamięć i wywołaćmemset() aby ją wyczyścić. Typowe implementacje będą śledzić, które części wspólnej puli są nieskazitelne i nadal wypełnione zerami, ale nie wszystkie implementacje to robią.

Rozpraszanie błędnych odpowiedzi

W zależności od systemu operacyjnego jądro może zerować pamięć w wolnym czasie, na wypadek, gdyby później trzeba było ją wyzerować. Linux nie zeruje pamięci z wyprzedzeniem, a Dragonfly BSD niedawno również usunął tę funkcję z jądra . Jednak niektóre inne jądra zajmują zero pamięci przed czasem. Zerowanie stron w czasie bezczynności i tak nie wystarczy, aby wyjaśnić duże różnice w wydajności.

Ta calloc()funkcja nie korzysta ze specjalnej, wyrównanej do pamięci wersji memset(), co i tak nie przyspieszyłoby jej. Większość memset()implementacji współczesnych procesorów wygląda mniej więcej tak:

function memset(dest, c, len)
    // one byte at a time, until the dest is aligned...
    while (len > 0 && ((unsigned int)dest & 15))
        *dest++ = c
        len -= 1
    // now write big chunks at a time (processor-specific)...
    // block size might not be 16, it's just pseudocode
    while (len >= 16)
        // some optimized vector code goes here
        // glibc uses SSE2 when available
        dest += 16
        len -= 16
    // the end is not aligned, so one byte at a time
    while (len > 0)
        *dest++ = c
        len -= 1

Jak widać, memset()jest bardzo szybki i tak naprawdę nie dostaniesz nic lepszego dla dużych bloków pamięci.

Fakt, że memset()pamięć jest już zerowana, oznacza, że ​​pamięć jest zerowana dwukrotnie, ale to tłumaczy jedynie dwukrotną różnicę wydajności. Różnica wydajności jest tutaj znacznie większa (zmierzyłem w moim systemie ponad trzy rzędy wielkości między malloc()+memset()icalloc() ).

Party trick

Zamiast zapętlać 10 razy, napisz program, który przydziela pamięć do malloc()lub calloc()zwraca NULL.

Co się stanie, jeśli dodasz memset()?

Ponieważ w wielu systemach w wolnym czasie system operacyjny samodzielnie ustawia wolną pamięć na zero i oznacza ją jako bezpieczną calloc(), więc kiedy zadzwonisz calloc(), może już mieć wolną, zerowaną pamięć, która ci da.

Na niektórych platformach w niektórych trybach malloc inicjuje pamięć do pewnej zwykle niezerowej wartości przed jej zwróceniem, więc druga wersja może równie dobrze zainicjować pamięć dwukrotnie