Seberapa efisien malloc dan bagaimana perbedaan implementasi?

Jika saya menggunakan malloc, apakah mallocselalu menggunakan algoritma yang sama terlepas dari apa yang dialokasikan atau apakah itu melihat data dan memilih algoritma appriopriate?

Bisakah kita membuat malloc lebih cepat atau lebih pintar dengan memilih algoritma yang lebih efisien? Dalam pengujian saya, sistem resmi bawaan mallocUbuntu adalah 10 kali lebih lambat dari proyek sekolah jika hasil tes saya benar. Apa yang menangkap? Saya terkejut yang mallocmelakukan begitu buruk dalam tes karena itu harus dioptimalkan. Apakah selalu menggunakan algoritma yang sama? Apakah ada implementasi referensi malloc? Jika saya ingin melihat sumbernya malloc, yang mana yang harus saya perhatikan? Tes yang saya jalankan adalah sebagai berikut:

/* returns an array of arrays of char*, all of which NULL */
char ***alloc_matrix(unsigned rows, unsigned columns) {
    char ***matrix = malloc(rows * sizeof(char **));
    unsigned row = 0;
    unsigned column = 0;
    if (!matrix) abort();

    for (row = 0; row < rows; row++) {
        matrix[row] = calloc(columns, sizeof(char *));
        if (!matrix[row]) abort();
        for (column = 0; column < columns; column++) {
            matrix[row][column] = NULL;
        }
    }
    return matrix;
}

/* deallocates an array of arrays of char*, calling free() on each */
void free_matrix(char ***matrix, unsigned rows, unsigned columns) {
    unsigned row = 0;
    unsigned column = 0;
    for (row = 0; row < rows; row++) {
        for (column = 0; column < columns; column++) {
            /*    printf("column %d row %d\n", column, row);*/
            free(matrix[row][column]);
        }
        free(matrix[row]);
    }
    free(matrix);
}


int main(int agrc, char **argv) {

    int x = 10000;
    char *** matrix = alloc_matrix(x, x);
    free_matrix(matrix, x, x);
    return (0);
}

Apakah tes ini baik-baik saja? Saya juga menggunakan tes ini:

   for (i = 0; i < 1000000; i++) {
        void *p = malloc(1024 * 1024 * 1024);
        free(p);
   }

• memperbarui

Menurut komentar, saya harus membuat potongan-potongan berukuran bervariasi dan gratis dalam urutan yang berbeda daripada mengalokasikan, jadi saya mencoba:

int main(int agrc, char **argv) {
     int i;
    srand(time(NULL));
    int randomnumber;
    int size = 1024;
    void *p[size];
    for (i = 0; i < size; i++) {
        randomnumber = rand() % 10;
        p[i] = malloc(1024 * 1024 * randomnumber);
    }

    for (i = size-1; i >= 0; i--) {
        free(p[i]);
    }

    int x = 1024;
    char *** matrix = alloc_matrix(x, x);
    free_matrix(matrix, x, x);
    return (0);
}

Maka malloc khusus saya tidak lagi lebih cepat:

$ time ./gb_quickfit 

real    0m0.154s
user    0m0.008s
sys 0m0.144s
dac@dac-Latitude-E7450:~/ClionProjects/omalloc/openmalloc/overhead$ time ./a.out 

real    0m0.014s
user    0m0.008s
sys 0m0.004s

Algoritma yang saya gunakan adalah:

void *malloc_quick(size_t nbytes) {

    Header *moreroce(unsigned);
    int index, i;
    index = qindex(nbytes);

    /* 
     * Use another strategy for too large allocations. We want the allocation
     * to be quick, so use malloc_first().
     */

    if (index >= NRQUICKLISTS) {
        return malloc_first(nbytes);
    }

    /* Initialize the quick fit lists if this is the first run. */
    if (first_run) {
        for (i = 0; i < NRQUICKLISTS; ++i) {
            quick_fit_lists[i] = NULL;
        }
        first_run = false;
    }


    /*
     * If the quick fit list pointer is NULL, then there are no free memory
     * blocks present, so we will have to create some before continuing.
     */

    if (quick_fit_lists[index] == NULL) {
        Header* new_quick_fit_list = init_quick_fit_list(index);
        if (new_quick_fit_list == NULL) {
            return NULL;
        } else {
            quick_fit_lists[index] = new_quick_fit_list;
        }
    }

    /*
     * Now that we know there is at least one free quick fit memory block,
     * let's use return that and also update the quick fit list pointer so that
     * it points to the next in the list.
     */

    void* pointer_to_return = (void *)(quick_fit_lists[index] + 1);
    quick_fit_lists[index] = quick_fit_lists[index]->s.ptr;
   /* printf("Time taken %d seconds %d milliseconds", msec/1000, msec%1000);*/
    return pointer_to_return;
}

Ada beberapa implementasi mallocdan mereka dapat menggunakan algoritma yang sangat berbeda. Dua implementasi yang sangat banyak digunakan adalah jemalloc dan dlmalloc . Dalam kedua kasus tersebut tautan memiliki banyak informasi tentang proses pemikiran dan pertukaran yang dilakukan dalam pengalokasi tujuan umum.

Ingatlah bahwa mallocimplementasi memiliki informasi yang sangat sedikit, hanya ukuran alokasi yang diminta. Sebuah freeimplementasi hanya memiliki pointer dan apa pun Data 'malloc' mungkin telah diam-diam melekat padanya. Karena itu akhirnya ada sejumlah heuristik yaitu dugaan terilhami dalam memutuskan bagaimana mengalokasikan dan membatalkan alokasi.

Beberapa masalah yang perlu ditangani oleh seorang pengalokasi adalah:

1. perataan - beberapa perataan memori lebih cepat dari yang lain
2. fragmentasi - alokasi dan pembebasan yang naif dapat meninggalkan lubang yang menyebabkan kembung
3. kinerja - kembali ke OS untuk lebih banyak memori bisa mahal
4. Permintaan umum - dalam aplikasi praktik (esp C ++) sering melakukan banyak alokasi kecil sehingga membuat ini efisien dapat banyak membantu

Dengan mempertimbangkan semua ini, yang akan Anda temukan adalah bahwa pengalokasi cenderung merupakan bagian dari perangkat lunak yang kompleks sehingga, dalam penggunaan umum, mereka berkinerja baik. Namun, dalam kasus tertentu, mungkin lebih baik mengelola memori di luar pengalokasi jika Anda mengetahui lebih banyak tentang struktur data. Jelas downside adalah bahwa Anda perlu melakukan pekerjaan sendiri.

Jika Anda hanya peduli pada efisiensi, berikut ini adalah standar yang sesuai dan implementasi yang sangat efisien :

void* malloc(size_t sz) {
  errno = ENOMEM;
  return NULL;
}

void free(void*p) {
  if (p != NULL) abort();
}

Saya cukup yakin Anda tidak akan menemukan yang lebih cepat malloc.

Tetapi sementara masih sesuai dengan standar, implementasi itu tidak berguna (tidak pernah berhasil mengalokasikan memori tumpukan). Ini adalah implementasi lelucon.

Ini menggambarkan bahwa di dunia nyata, malloc& freeimplementasi perlu melakukan trade-off . Dan berbagai implementasi menghasilkan berbagai pengorbanan. Anda akan menemukan banyak tutorial tentang implementasi malloc . Untuk men-debug kebocoran memori dalam program C Anda, Anda ingin menggunakan valgrind .

Perhatikan bahwa pada sistem Linux setidaknya, (hampir) semua pustaka standar C adalah perangkat lunak bebas , sehingga Anda dapat mempelajari kode sumbernya (khususnya untuk malloc& free). musl-libc memiliki beberapa kode sumber yang sangat mudah dibaca.

BTW, kode dalam pertanyaan Anda salah (dan akan macet dengan saya di mallocatas). Setiap panggilan ke malloc dapat gagal, dan Anda harus mengujinya.

Anda mungkin ingin membaca Pemrograman Linux Lanjut dan beberapa materi yang lebih umum tentang sistem operasi, misalnya Sistem Operasi: tiga bagian mudah .

Anda mungkin harus membaca sesuatu tentang pengumpulan sampah , setidaknya untuk mendapatkan konsep & terminologi utama; mungkin dengan membaca buku pegangan GC . Perhatikan bahwa penghitungan referensi dapat dilihat sebagai bentuk GC (yang buruk, yang tidak menangani siklus referensi dengan baik atau grafik siklik ...).

Anda bisa menggunakan dalam program C pengumpul sampah Boehm yang konservatif : Anda kemudian akan menggunakan GC_MALLOC(atau, untuk data tanpa pointer seperti string atau array numerik, GC_MALLOC_ATOMIC) alih-alih mallocdan Anda tidak akan repot-repot menelepon freelagi. Ada beberapa peringatan saat menggunakan Boehm's GC. Anda dapat mempertimbangkan skema atau perpustakaan GC lainnya ...

NB: Untuk menguji kegagalan malloc pada sistem Linux ( mallockadang-kadang memanggil sistem mmap (2) dan / atau sbrk (2) di Linux untuk menumbuhkan ruang alamat virtual , tetapi paling sering ia berusaha keras untuk menggunakan kembali freememori d sebelumnya ) , Anda dapat memanggil setrlimit (2) dengan tepat dengan RLIMIT_ASdan / atau RLIMIT_DATA, sering melalui ulimitbash bawaan dari terminal shell Anda. Gunakan strace (1) untuk mengetahui panggilan sistem yang dilakukan oleh program Anda (atau lainnya).

Pertama, malloc dan kerja bebas bersama, jadi menguji malloc dengan sendirinya menyesatkan. Kedua, tidak peduli seberapa baik mereka, mereka dapat dengan mudah menjadi biaya dominan dalam aplikasi apa pun, dan solusi terbaik untuk itu adalah dengan memanggil mereka lebih sedikit. Memanggil mereka lebih sedikit hampir selalu merupakan cara terbaik untuk memperbaiki program yang tidak terbatas malloc . Salah satu cara umum untuk melakukan ini adalah mendaur ulang objek yang digunakan. Saat Anda selesai dengan sebuah blok, alih-alih membebaskannya , Anda mem-chain-nya pada tumpukan blok-bekas dan menggunakannya kembali saat berikutnya Anda membutuhkannya.

Masalah utama dengan malloc_quick()implementasi Anda adalah, bahwa itu tidak aman. Dan ya, jika Anda menghilangkan dukungan thread dari pengalokasi Anda, Anda dapat mencapai keuntungan kinerja yang signifikan. Saya telah melihat speedup serupa dengan pengalokasi non-thread-safe saya sendiri.

Namun, implementasi standar harus aman-utas. Perlu memperhitungkan semua hal berikut:

• Berbagai utas digunakan malloc()dan free()secara bersamaan. Itu berarti, bahwa implementasi tidak dapat mengakses keadaan global tanpa sinkronisasi internal.

  Karena kunci sangat mahal, malloc()implementasi tipikal mencoba untuk menghindari menggunakan keadaan global sebanyak mungkin dengan menggunakan penyimpanan thread-lokal untuk hampir semua permintaan.

• Thread yang mengalokasikan pointer tidak harus berupa thread yang membebaskannya. Ini harus diurus.

• Utas dapat secara konstan mengalokasikan memori dan meneruskannya ke utas lain untuk membebaskannya. Ini membuat penanganan poin terakhir jauh lebih sulit, karena itu berarti blok bebas dapat terakumulasi dalam penyimpanan thread-lokal. Ini memaksa malloc()implementasi untuk menyediakan sarana bagi utas untuk bertukar blok gratis, dan kemungkinan membutuhkan penjepit kunci dari waktu ke waktu.

Jika Anda tidak peduli dengan utas, semua poin ini tidak ada masalah sama sekali, sehingga pengalokasi yang tidak aman tidak harus membayar untuk penanganannya dengan kinerja. Tetapi, seperti yang saya katakan, implementasi standar tidak dapat mengabaikan masalah ini, dan akibatnya harus membayar untuk penanganannya.

Saya pikir kedua SUT bukan perbandingan langsung. Saya tidak akan terkejut dengan perbedaan yang sebanding ketika Anda mempertimbangkan semua variabel: pembuatan memori, arsitektur motherboard, versi kompiler (yang mengkompilasi malloc), seperti apa aplikasi ruang memori pada SUT pada saat itu, dll dll ... .... Coba gunakan test harness Anda untuk menjadi lebih representatif tentang bagaimana Anda akan menggunakan memori dalam proyek nyata - dengan beberapa alokasi besar / kecil, dan beberapa aplikasi ditahan untuk waktu yang lama dan beberapa dibebaskan segera setelah diambil.

Jika Anda membandingkan implementasi malloc nyata dengan proyek sekolah, pertimbangkan bahwa malloc nyata harus mengelola alokasi, realokasi dan membebaskan memori dari ukuran yang sangat berbeda, bekerja dengan benar jika alokasi terjadi pada utas yang berbeda secara bersamaan, dan realokasi dan membebaskan memori terjadi pada utas yang berbeda . Anda juga ingin memastikan bahwa setiap upaya untuk membebaskan memori yang tidak dialokasikan dengan malloc tertangkap. Dan akhirnya, pastikan bahwa Anda tidak membandingkan dengan implementasi malloc debugging.