Mengapa malloc + memset lebih lambat dari calloc?

Diketahui bahwa callocini berbeda dari mallocyang menginisialisasi memori yang dialokasikan. Dengan calloc, memori diatur ke nol. Dengan malloc, memori tidak terhapus.

Jadi dalam pekerjaan sehari-hari, saya anggap callocsebagai malloc+ memset. Kebetulan, untuk bersenang-senang, saya menulis kode berikut untuk benchmark.

Hasilnya membingungkan.

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

Output dari Kode 1:

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

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

Keluaran Kode 2:

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

Mengganti memsetdengan bzero(buf[i],BLOCK_SIZE)dalam Kode 2 menghasilkan hasil yang sama.

Pertanyaan saya adalah: Mengapa malloc+ memsetjauh lebih lambat daripada calloc? Bagaimana bisa callocbegitu?

Versi singkatnya: Selalu gunakan calloc()bukan malloc()+memset(). Dalam kebanyakan kasus, mereka akan sama. Dalam beberapa kasus, calloc()akan melakukan lebih sedikit pekerjaan karena dapat melewati memset()sepenuhnya. Dalam kasus lain, calloc()bahkan bisa menipu dan tidak mengalokasikan memori apa pun! Namun, malloc()+memset()akan selalu melakukan jumlah pekerjaan penuh.

Memahami hal ini membutuhkan tur singkat dari sistem memori.

Tur memori cepat

Ada empat bagian utama di sini: program Anda, pustaka standar, kernel, dan tabel halaman. Anda sudah mengetahui program Anda, jadi ...

Pengalokasi memori menyukai malloc()dan calloc()sebagian besar ada untuk mengambil alokasi kecil (mulai dari 1 byte hingga 100-an KB) dan mengelompokkannya ke dalam kumpulan memori yang lebih besar. Sebagai contoh, jika Anda mengalokasikan 16 byte, malloc()pertama-tama akan mencoba untuk mendapatkan 16 byte dari salah satu kolam, dan kemudian meminta lebih banyak memori dari kernel ketika kolam mengering. Namun, karena program yang Anda tanyakan sedang mengalokasikan untuk sejumlah besar memori sekaligus, malloc()dan calloc()hanya akan meminta memori itu langsung dari kernel. Ambang untuk perilaku ini tergantung pada sistem Anda, tetapi saya telah melihat 1 MIB digunakan sebagai ambang.

Kernel bertanggung jawab untuk mengalokasikan RAM aktual untuk setiap proses dan memastikan bahwa proses tidak mengganggu memori proses lainnya. Ini disebut perlindungan memori, sudah menjadi hal biasa sejak 1990-an, dan itulah alasan mengapa satu program dapat macet tanpa menjatuhkan seluruh sistem. Jadi ketika sebuah program membutuhkan lebih banyak memori, ia tidak bisa hanya mengambil memori, tetapi sebaliknya meminta memori dari kernel menggunakan panggilan sistem seperti mmap()atau sbrk(). Kernel akan memberikan RAM untuk setiap proses dengan memodifikasi tabel halaman.

Tabel halaman memetakan alamat memori ke RAM fisik aktual. Alamat proses Anda, 0x00000000 hingga 0xFFFFFFFF pada sistem 32-bit, bukan memori nyata melainkan alamat dalam memori virtual. Prosesor membagi alamat-alamat ini menjadi 4 halaman KiB, dan setiap halaman dapat ditetapkan ke bagian RAM fisik yang berbeda dengan memodifikasi tabel halaman. Hanya kernel yang diizinkan mengubah tabel halaman.

Bagaimana itu tidak berhasil

Inilah cara mengalokasikan 256 MiB tidak berfungsi:

1. Proses Anda memanggil calloc()dan meminta 256 MiB.

2. Pustaka standar memanggil mmap()dan meminta 256 MiB.

3. Kernel menemukan 256 MiB RAM yang tidak digunakan dan memberikannya ke proses Anda dengan memodifikasi tabel halaman.

4. Pustaka standar nol dengan RAM memset()dan kembali dari calloc().

5. Proses Anda akhirnya keluar, dan kernel mendapatkan kembali RAM sehingga dapat digunakan oleh proses lain.

Bagaimana cara kerjanya sebenarnya

Proses di atas akan berhasil, tetapi tidak terjadi seperti ini. Ada tiga perbedaan utama.

• Ketika proses Anda mendapatkan memori baru dari kernel, memori itu mungkin digunakan oleh beberapa proses lain sebelumnya. Ini adalah risiko keamanan. Bagaimana jika memori itu memiliki kata sandi, kunci enkripsi, atau resep salsa rahasia? Agar data sensitif tidak bocor, kernel selalu menggosok memori sebelum memberikannya ke proses. Kita mungkin juga menggosok memori dengan memusatkan perhatian, dan jika memori baru memusatkan perhatian kita juga dapat menjadikannya jaminan, jadi mmap()menjamin bahwa memori baru yang dikembalikannya selalu memusatkan perhatian.

• Ada banyak program di luar sana yang mengalokasikan memori tetapi tidak langsung menggunakan memori. Beberapa kali memori dialokasikan tetapi tidak pernah digunakan. Kernel tahu ini dan malas. Ketika Anda mengalokasikan memori baru, kernel tidak menyentuh tabel halaman sama sekali dan tidak memberikan RAM apa pun untuk proses Anda. Sebaliknya, ia menemukan beberapa ruang alamat dalam proses Anda, membuat catatan tentang apa yang seharusnya pergi ke sana, dan membuat janji bahwa itu akan menempatkan RAM di sana jika program Anda benar-benar menggunakannya. Ketika program Anda mencoba membaca atau menulis dari alamat-alamat itu, prosesor memicu kesalahan halaman dan langkah-langkah kernel dalam menetapkan RAM ke alamat-alamat itu dan melanjutkan program Anda. Jika Anda tidak pernah menggunakan memori, kesalahan halaman tidak pernah terjadi dan program Anda tidak pernah benar-benar mendapatkan RAM.

• Beberapa proses mengalokasikan memori dan kemudian membacanya tanpa memodifikasinya. Ini berarti bahwa banyak halaman dalam memori di berbagai proses yang berbeda dapat diisi dengan nol murni yang dikembalikan dari mmap(). Karena halaman-halaman ini semuanya sama, kernel membuat semua alamat virtual ini menunjuk satu halaman 4 KiB memori bersama yang diisi dengan nol. Jika Anda mencoba menulis ke memori itu, prosesor memicu kesalahan halaman lain dan kernel masuk untuk memberi Anda halaman baru nol yang tidak dibagi dengan program lain.

Proses akhir lebih terlihat seperti ini:

1. Proses Anda memanggil calloc()dan meminta 256 MiB.

2. Pustaka standar memanggil mmap()dan meminta 256 MiB.

3. Kernel menemukan 256 MiB ruang alamat yang tidak digunakan , membuat catatan tentang apa yang digunakan untuk ruang alamat tersebut, dan kembali.

4. Pustaka standar tahu bahwa hasil mmap()selalu diisi dengan nol (atau akan begitu benar-benar mendapatkan RAM), sehingga tidak menyentuh memori, sehingga tidak ada kesalahan halaman, dan RAM tidak pernah diberikan kepada proses Anda .

5. Proses Anda akhirnya keluar, dan kernel tidak perlu mengklaim kembali RAM karena itu tidak pernah dialokasikan di tempat pertama.

Jika Anda menggunakan memset()untuk nol halaman, memset()akan memicu kesalahan halaman, menyebabkan RAM dialokasikan, dan nol itu meskipun sudah diisi dengan nol. Ini adalah pekerjaan ekstra yang sangat besar, dan menjelaskan mengapa calloc()lebih cepat daripada malloc()dan memset(). Jika akhirnya menggunakan memori, calloc()masih lebih cepat dari malloc()dan memset()tetapi perbedaannya tidak begitu konyol.

Ini tidak selalu berhasil

Tidak semua sistem memiliki memori virtual paged, sehingga tidak semua sistem dapat menggunakan optimasi ini. Ini berlaku untuk prosesor yang sangat lama seperti 80286 dan juga prosesor tertanam yang terlalu kecil untuk unit manajemen memori yang canggih.

Ini juga tidak selalu bekerja dengan alokasi yang lebih kecil. Dengan alokasi yang lebih kecil, calloc()dapatkan memori dari kumpulan bersama alih-alih langsung ke kernel. Secara umum, kumpulan bersama mungkin memiliki data sampah yang tersimpan di dalamnya dari memori lama yang digunakan dan dibebaskan free(), sehingga calloc()dapat mengambil memori itu dan menelepon memset()untuk menghapusnya. Implementasi umum akan melacak bagian mana dari kumpulan bersama yang masih asli dan masih diisi dengan nol, tetapi tidak semua implementasi melakukan ini.

Mengusir beberapa jawaban yang salah

Bergantung pada sistem operasi, kernel mungkin atau mungkin tidak nol memori di waktu luangnya, jika Anda perlu mendapatkan beberapa memori memusatkan perhatian nanti. Linux tidak mem-nolkan memori sebelumnya, dan Dragonfly BSD baru-baru ini juga menghapus fitur ini dari kernel mereka . Namun, beberapa kernel lain tidak memiliki memori nol sebelumnya. Lagipula halaman zero-idle tidak cukup untuk menjelaskan perbedaan kinerja yang besar.

The calloc()fungsi tidak menggunakan beberapa versi memori-blok khusus memset(), dan itu tidak akan membuatnya lebih cepat pula. Sebagian besar memset()implementasi untuk prosesor modern terlihat seperti ini:

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

Jadi Anda bisa lihat, memset()ini sangat cepat dan Anda tidak benar-benar akan mendapatkan sesuatu yang lebih baik untuk blok memori yang besar.

Fakta bahwa memset()memusatkan memori yang sudah memusatkan perhatian berarti bahwa memori akan memusatkan perhatian dua kali, tetapi itu hanya menjelaskan perbedaan kinerja 2x. Perbedaan kinerja di sini jauh lebih besar (saya mengukur lebih dari tiga urutan besarnya pada sistem saya antara malloc()+memset()dan calloc()).

Trik pesta

Alih-alih mengulang 10 kali, tulis sebuah program yang mengalokasikan memori hingga malloc()atau calloc()mengembalikan NULL.

Apa yang terjadi jika Anda menambahkan memset()?

Karena pada banyak sistem, dalam waktu pemrosesan yang lebih lama, OS berkeliling mengatur memori bebas ke nol dengan sendirinya dan menandainya aman calloc(), jadi ketika Anda menelepon calloc(), itu mungkin sudah memberikan memori kosong dan kosong untuk Anda.

Pada beberapa platform dalam beberapa mode, malloc menginisialisasi memori ke beberapa nilai yang biasanya tidak nol sebelum mengembalikannya, sehingga versi kedua dapat menginisialisasi memori dua kali.