Alokator Bump Sederhana
Bagikan memori secara linear.
Alokator Bump Sederhana adalah pelajaran C Academy gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar C Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus C Academy mencakup 4 pelajaran total.
Gagasan Bump Allocator
Bump allocator (atau pengalokasi arena) adalah desain yang paling sederhana. Anda menyimpan satu buffer besar dan satu offset. Setiap alokasi cukup mengembalikan offset saat ini, lalu "menaikkan" offset tersebut sebesar ukuran yang diminta.
Tidak ada metadata per block dan tidak ada pencarian. Alokasi pada dasarnya hanya berupa satu penjumlahan penunjuk, sehingga sangat cepat.
Buffer Pendukung Statis
Untuk contoh mandiri, kita mendukung pengalokasi dengan array statis, bukan heap OS. Program ini dapat dikompilasi dan dijalankan di mana saja, tanpa sbrk atau mmap.
Array tersebut memberi kita kumpulan byte berukuran tetap untuk dibagi-bagi.
#define POOL_SIZE 1024
static unsigned char pool[POOL_SIZE];
static size_t offset = 0;Fungsi bump Inti
Alokasi memeriksa apakah masih tersedia cukup ruang, mencatat posisi awal, memajukan offset, lalu mengembalikan penunjuk awal. Jika permintaan akan melampaui kapasitas kumpulan, fungsi ini mengembalikan NULL.
Pemeriksaan luapan tersebut adalah satu-satunya keamanan yang disediakan bump allocator.
void *bump_alloc(size_t size) {
if (offset + size > POOL_SIZE)
return NULL; /* out of pool */
void *p = &pool[offset];
offset += size;
return p;
}Bump Allocator Lengkap yang Dapat Dijalankan
Berikut adalah program lengkap. Program ini mengalokasikan dua bilangan bulat dan sebuah string pendek dari kumpulan, lalu mencetaknya untuk membuktikan bahwa pengalokasi berfungsi.
Perhatikan betapa sedikit kode yang diperlukan dibandingkan dengan malloc nyata.
#include <stdio.h>
#include <stddef.h>
#include <string.h>
#define POOL_SIZE 1024
static unsigned char pool[POOL_SIZE];
static size_t offset = 0;
void *bump_alloc(size_t size) {
if (offset + size > POOL_SIZE) return NULL;
void *p = &pool[offset];
offset += size;
return p;
}
int main(void) {
int *a = bump_alloc(sizeof(int));
int *b = bump_alloc(sizeof(int));
char *s = bump_alloc(6);
*a = 10; *b = 32;
strcpy(s, "hi");
printf("%d %d %s\n", *a, *b, s);
printf("used = %zu\n", offset);
return 0;
}Tidak Ada Free Individual
Kekurangannya: bump allocator tidak dapat membebaskan satu alokasi. Karena tidak ada metadata, pengalokasi tidak tahu di mana satu block berakhir dan block berikutnya dimulai untuk digunakan kembali.
Anda hanya dapat mengatur ulang seluruh arena sekaligus dengan mengatur offset kembali ke nol.
void bump_reset(void) {
offset = 0; /* frees everything at once */
}Mengapa Pengaturan Ulang Berguna
Model semuanya atau tidak sama sekali ini sangat cocok untuk pekerjaan berbasis fase: alokasikan banyak objek selama suatu permintaan atau frame, lalu atur ulang arena saat fase berakhir.
Mesin gim dan kompiler banyak menggunakan arena karena pengaturan ulang berbiaya O(1) dan tidak perlu melacak ribuan pembebasan individual.
/* Per-frame pattern */
for (int frame = 0; frame < 3; frame++) {
void *tmp = bump_alloc(128);
/* ... use tmp this frame ... */
bump_reset(); /* reclaim instantly */
}Melacak Ruang yang Tersisa
Menampilkan sisa ruang akan sangat membantu. Nilainya cukup berupa ukuran kumpulan memori dikurangi offset saat ini.
Pemanggil dapat menggunakan informasi ini untuk memutuskan apakah perlu melakukan flush atau memperbesar kumpulan memori sebelum meminta ruang tambahan.
size_t bump_remaining(void) {
return POOL_SIZE - offset;
}Demo Reset yang Dapat Dijalankan
Program ini mengisi sebagian kumpulan memori, mencetak penggunaannya, melakukan reset, lalu menunjukkan offset kembali ke nol sehingga ruang tersebut dapat digunakan kembali.
#include <stdio.h>
#include <stddef.h>
#define POOL_SIZE 256
static unsigned char pool[POOL_SIZE];
static size_t offset = 0;
void *bump_alloc(size_t s){ if(offset+s>POOL_SIZE) return NULL; void *p=&pool[offset]; offset+=s; return p; }
void bump_reset(void){ offset = 0; }
int main(void) {
bump_alloc(100);
printf("after alloc: used=%zu\n", offset);
bump_reset();
printf("after reset: used=%zu\n", offset);
return 0;
}Penyelarasan pada Pengalokasi Bump
Peningkatan satu per satu pada byte mentah dapat menghasilkan pointer yang tidak selaras. Agar aman, bulatkan offset ke atas hingga batas penyelarasan sebelum mengembalikan pointer.
Kita akan membahas perhitungannya secara terperinci nanti, tetapi penyelarasan paling penting pada pengalokasi bump karena jika tidak, tidak ada padding.
static size_t align_up(size_t n, size_t a) {
return (n + a - 1) & ~(a - 1); /* a must be power of 2 */
}Pengalokasi Bump yang Selaras
Dengan menggabungkan semua bagian, kita menyelaraskan offset sebelum setiap alokasi. Ini menjamin setiap pointer yang dikembalikan sesuai untuk tipe umum apa pun.
Konsekuensinya adalah sedikit fragmentasi internal akibat byte padding.
#define ALIGN 16
void *bump_aligned(size_t size) {
offset = align_up(offset, ALIGN);
if (offset + size > POOL_SIZE) return NULL;
void *p = &pool[offset];
offset += size;
return p;
}Kelebihan dan Keterbatasan
Pengalokasi bump sangat cepat dan sangat sederhana, tanpa overhead per objek. Pengalokasi ini ideal ketika objek-objek memiliki masa hidup yang sama.
Kelemahannya adalah tidak adanya pembebasan dengan perincian halus. Jika masa hidup berbeda, Anda memerlukan rancangan daftar bebas yang dibahas pada pelajaran berikutnya.
Pemeriksaan Singkat
Pikirkan bagaimana pengalokasi bump mengambil kembali memori.
Ringkasan
Pengalokasi bump memberikan memori dengan memajukan satu offset melalui buffer, sehingga alokasi semurah penambahan pointer.
Pengalokasi ini mengorbankan pembebasan individual demi kecepatan dan kesederhanaan, serta hanya mengambil kembali memori melalui reset penuh. Selaraskan offset agar pointer yang dikembalikan valid untuk semua tipe.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Alokator Bump Sederhana” gratis?
Ya — teks lengkap “Alokator Bump Sederhana” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus C Academy, upgrade ke CoddyKit PRO. Kursus C Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Alokator Bump Sederhana”?
Bagikan memori secara linear. Kamu berlatih C Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai C Academy?
Tidak diperlukan pengalaman sebelumnya. C Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.
Berapa lama pelajaran “Alokator Bump Sederhana” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran C Academy ini?
Ya. Setiap pelajaran C Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Cara Kerja malloc
- Alokator Bump Sederhana
- Daftar Memori Bebas dan Penggunaan Ulang
- Penyelarasan dan Pemisahan