Dlaczego zestaw malloc + jest wolniejszy niż calloc?


256

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ć?

Odpowiedzi:


455

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()?


7
@Dietrich: wyjaśnienie Dietrich pamięci wirtualnej o tym, że system operacyjny wielokrotnie przydziela tę samą stronę wypełnioną zerą dla calloc jest łatwe do sprawdzenia. Wystarczy dodać pętlę, która zapisuje niepotrzebne dane na każdej stronie przydzielonej pamięci (wystarczy napisać jeden bajt na 500 bajtów). Ogólny wynik powinien być wtedy znacznie bliższy, ponieważ system byłby zmuszony do rzeczywistego przydzielania różnych stron w obu przypadkach.
kriss

1
@kriss: rzeczywiście, chociaż jeden bajt na 4096 wystarcza w zdecydowanej większości systemów
Dietrich Epp

W rzeczywistości calloc()jest często częścią mallocpakietu wdrożeniowego, a zatem jest zoptymalizowany, aby nie dzwonił bzeropodczas pobierania pamięci mmap.
mirabilos

1
Dziękuję za edycję, prawie to miałem na myśli. Wczesne stwierdzenie, że zawsze należy używać calloc zamiast malloc + memset. Podaj 1. domyślną wartość malloc 2. jeśli mała część bufora wymaga wyzerowania, zapisz tę część 3. w przeciwnym razie użyj calloc. W szczególności NIE malloc + zapisz całego rozmiaru (użyj do tego calloc) i NIE domyślaj się wywoływania wszystkiego, ponieważ utrudnia to takie rzeczy jak valgrind i analizatory kodu statycznego (cała pamięć jest nagle inicjowana). Poza tym myślę, że to w porządku.
pracownik miesiąca

5
Chociaż nie jest związany z prędkością, callocjest również mniej podatny na błędy. To znaczy, gdzie large_int * large_intspowodowałoby to przepełnienie, calloc(large_int, large_int)zwraca NULL, ale malloc(large_int * large_int)jest niezdefiniowanym zachowaniem, ponieważ nie znasz faktycznego rozmiaru zwracanego bloku pamięci.
Wydmy

12

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.


2
Jesteś pewny? Które systemy to robią? Myślałem, że większość systemów operacyjnych po prostu wyłącza procesor, gdy są one bezczynne, i zeruje pamięć na żądanie dla procesów, które przydzielają, gdy tylko zapisują się w tej pamięci (ale nie, gdy ją przydzielają).
Dietrich Epp

@Dietrich - Nie jestem pewien. Słyszałem to raz i wydawało się to rozsądnym (i dość prostym) sposobem na calloc()zwiększenie wydajności.
Chris Lutz

@Pierreten - Nie mogę znaleźć żadnych dobrych informacji na temat calloc()optymalizacji specyficznych i nie mam ochoty interpretować kodu źródłowego libc dla OP. Czy potrafisz wyszukać coś, co pokazuje, że ta optymalizacja nie istnieje / nie działa?
Chris Lutz

13
@Dietrich: FreeBSD ma zerować wypełnianie stron w czasie bezczynności: Zobacz jego ustawienie vm.idlezero_enable.
Zan Lynx,

1
@DietrichEpp przepraszam za nekro, ale na przykład Windows to robi.
Andreas Grapentin,

1

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

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.