Dlaczego malloc + memset jest wolniejszy niż calloc?

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

Quick tour of memory

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

Alokatory pamięci, takie jak malloc() i calloc(), służą głównie do pobierania małych alokacji (od 1 bajtów do 100 Kb) i grupowania ich w większe pule pamięci. Na przykład, jeśli przydzielisz 16 bajtów, malloc() najpierw spróbuje pobrać 16 bajtów z jednej z jego pul, a następnie poprosić o więcej pamięci z jądra, gdy pula jest sucha. Jednak, ponieważ program, o który pytasz, przeznacza na dużą ilość pamięć na raz, malloc() i calloc() po prostu poproszą o tę pamięć bezpośrednio z jądra. Próg dla tego zachowania zależy od Twojego systemu, ale widziałem 1 MiB używany jako próg.

Jądro jest odpowiedzialne za przydzielanie rzeczywistej pamięci RAM każdemu procesowi i upewnianie się, że procesy nie kolidują z pamięcią innych procesów. To się nazywa Ochrona pamięci, jest to Brud powszechny od 1990 roku, i to jest powód, dla którego JEDEN program może się zawiesić bez zniszczyć cały system. Tak więc, gdy program potrzebuje więcej pamięci, nie może po prostu zabrać jej, ale zamiast tego prosi o pamięć z jądra za pomocą wywołania systemowego, takiego jak mmap() lub sbrk(). Jądro da PAMIĘĆ RAM każdemu procesowi, modyfikując tabelę stron.

Tabela stron mapuje adresy pamięci do rzeczywistej fizycznej pamięci RAM. Adresy Twojego procesu, od 0x00000000 do 0xFFFFFFFF w systemie 32-bitowym, nie są rzeczywistą pamięcią, ale zamiast tego są adresami w pamięci wirtualnej . The 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ć tabelę stron.

Jak to nie działa

Oto jak działa alokacja 256 MiB a nie:

1. Twój proces wywołuje calloc() i prosi o 256 MiB.

2. Biblioteka standardowa wywołuje mmap() i prosi o 256 MiB.

3. Jądro znajduje 256 MiB nieużywanej pamięci RAM i przekazuje ją procesowi, modyfikując tabelę stron.

4. Biblioteka standardowa zeruje PAMIĘĆ RAM za pomocą memset() i zwraca z calloc().

5. Proces ostatecznie kończy działanie, a jądro odzyskuje pamięć RAM, aby mogła być używana przez inny proces.

Jak to faktycznie działa

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

• Gdy proces otrzymuje nową pamięć z jądra, pamięć ta prawdopodobnie była wcześniej używana przez inny proces. To zagrożenie bezpieczeństwa. Co jeśli ta pamięć ma hasła, klucze szyfrujące lub tajne przepisy na salsę? Aby chronić poufne dane przed wyciekiem, jądro zawsze wyczyszcza pamięć przed przekazaniem jej procesowi. Możemy równie dobrze wyczyścić pamięć zerując ją, a jeśli nowa pamięć zostanie zerowana, możemy równie dobrze 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 tabeli stron i nie daje żadnej pamięci RAM procesowi. Zamiast tego znajduje trochę przestrzeni adresowej w Twoim procesie, notuje, co ma się tam udać i obiecuje, że umieści tam PAMIĘĆ RAM, jeśli twój program kiedykolwiek go użyje. Gdy program próbuje odczytać lub zapisać z tych adresów, procesor uruchamia Błąd strony , a jądro wykonuje przypisanie pamięci RAM do tych adresów i wznawia program. Jeśli nigdy nie używasz pamięci, Błąd strony nigdy nie wystąpi, a twój program nigdy nie otrzyma pamięci RAM.

• Niektóre procesy przydzielają pamięć, a następnie odczytują ją bez jej modyfikowania. Oznacza to, że wiele stron w pamięci w różnych procesach mogą być wypełnione nieskazitelnymi zerami zwracanymi z mmap(). Ponieważ wszystkie te strony są takie same, jądro sprawia, że wszystkie te wirtualne adresy wskazują jedną wspólną stronę 4 KiB pamięci wypełnioną zerami. Jeśli spróbujesz zapisać do tej pamięci, procesor spowoduje kolejną awarię strony, a jądro uruchomi nową stronę zer, która nie jest współdzielona z żadnymi innymi programami.

Ostatni proces wygląda bardziej jak to:

1. Twój proces wywołuje calloc() i prosi o 256 MiB.

2. Biblioteka standardowa wywołuje mmap() i prosi o 256 MiB.

3. Jądro znajduje 256 MiB nieużywanej przestrzeni adresowej , notuje do czego ta przestrzeń adresowa jest obecnie używana i zwraca.

4. Biblioteka standardowa wie, że wynik {[12] } jest zawsze wypełniony zerami (lub będzie , gdy rzeczywiście dostanie trochę pamięci RAM), więc nie dotknij pamięci, więc nie ma błędu strony, a pamięć RAM nigdy nie jest przekazywana procesowi.

5. Proces ostatecznie kończy działanie, 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 błąd strony, spowoduje przydzielenie pamięci RAM, a następnie zeruje ją, nawet jeśli jest już wypełniona zerami. Jest to ogromna ilość dodatkowej pracy i wyjaśnia, dlaczego calloc() jest szybszy niż malloc() i memset(). Jeśli i tak użyjesz pamięci, calloc() jest nadal szybszy niż malloc() i memset(), ale różnica nie jest aż tak śmieszna.

Nie wszystkie systemy mają paged pamięci wirtualnej, więc nie wszystkie systemy mogą korzystać z tych optymalizacji. Dotyczy to bardzo starych procesorów, takich jak 80286, jak również wbudowanych procesorów, które są po prostu zbyt małe dla wyrafinowanej jednostki zarządzania pamięcią.

To również nie zawsze będzie pracuj z mniejszymi przydziałami. Przy mniejszych przydziałach calloc() pobiera pamięć ze współdzielonej puli zamiast bezpośrednio do jądra. Ogólnie rzecz biorąc, wspólna pula może zawierać niepotrzebne dane ze starej pamięci, która została użyta i zwolniona za pomocą free(), więc calloc() może zabrać tę pamięć i wywołać memset(), aby ją wyczyścić. Wspólne implementacje będą śledzić, które części wspólnej puli są nieskazitelne i nadal wypełnione zerami, ale nie wszystkie implementacje to robią.

Rozwianie jakiegoś błędu odpowiedzi

W zależności od systemu operacyjnego, jądro może lub nie może zerować pamięci w wolnym czasie, na wypadek, gdybyś potrzebował później zerować pamięć. Linux nie zeruje pamięci z wyprzedzeniem i Dragonfly BSD niedawno usunął tę funkcję ze swojego jądra. Jednak niektóre inne jądra nie mają pamięci z wyprzedzeniem. Zerowanie stron podczas bezczynności nie wystarczy, aby wyjaśnić duże różnice w wydajności.

Funkcja calloc() nie używa niektórych specjalna wersja memset() dopasowana do pamięci, a to i tak nie uczyniłoby jej dużo szybszą. Większość implementacji memset() dla nowoczesnych 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

Więc widzisz, memset() jest bardzo szybki i naprawdę nie dostaniesz nic lepszego dla dużych bloków pamięci.

Fakt, że memset() jest zerowaniem pamięci, która jest już zerowana, oznacza, że pamięć jest zerowana dwukrotnie, ale to wyjaśnia tylko różnicę wydajności 2x. Różnica w wydajności jest znacznie większy (mierzyłem więcej niż trzy rzędy wielkości w moim systemie między malloc()+memset() i calloc()).

Party trick

Zamiast zapętlać 10 razy, napisz program, który przydziela pamięć do czasu, aż malloc() lub calloc() zwróci NULL.

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