C Academy · บทเรียน

ตัวจัดสรรแบบเพิ่มตำแหน่งอย่างง่าย

แจกจ่ายหน่วยความจำตามลำดับ

ตัวจัดสรรแบบเพิ่มตำแหน่งอย่างง่าย เป็นบทเรียน C Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน C Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส C Academy มีบทเรียนทั้งหมด 4 บทเรียน

แนวคิดตัวจัดสรรแบบ bump

ตัวจัดสรรแบบ bump (หรือแบบ arena) เป็นการออกแบบที่เรียบง่ายที่สุด คุณมีบัฟเฟอร์ขนาดใหญ่หนึ่งตัวและออฟเซ็ตเพียงหนึ่งค่า การจัดสรรแต่ละครั้งเพียงส่งคืนออฟเซ็ตปัจจุบัน แล้วเลื่อนออฟเซ็ตไปข้างหน้าตามขนาดที่ร้องขอ

ไม่มีข้อมูลกำกับประจำบล็อกและไม่มีการค้นหา การจัดสรรแทบจะเป็นเพียงการบวกพอยน์เตอร์หนึ่งครั้ง จึงทำงานได้รวดเร็วมาก

บัฟเฟอร์หนุนแบบคงที่

สำหรับตัวอย่างที่ทำงานได้ในตัวเอง เราจะใช้แอร์เรย์แบบคงที่เป็นพื้นที่หนุนตัวจัดสรรแทนฮีปของ OS โค้ดนี้คอมไพล์และทำงานได้ทุกที่ โดยไม่ใช้ sbrk หรือ mmap

แอร์เรย์นี้ให้พื้นที่ไบต์คงที่หนึ่งชุดสำหรับแบ่งใช้งาน

#define POOL_SIZE 1024
static unsigned char pool[POOL_SIZE];
static size_t offset = 0;

ฟังก์ชัน bump หลัก

การจัดสรรจะตรวจสอบว่ายังมีพื้นที่เพียงพอหรือไม่ บันทึกจุดเริ่มต้น เลื่อนออฟเซ็ต แล้วส่งคืนพอยน์เตอร์จุดเริ่มต้น หากคำขอทำให้พื้นที่เกินขนาดพูล จะส่งคืน NULL

การตรวจสอบพื้นที่เกินขนาดนี้คือกลไกความปลอดภัยเพียงอย่างเดียวที่ตัวจัดสรรแบบ bump มีให้

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 ที่ทำงานได้สมบูรณ์

นี่คือโปรแกรมฉบับเต็ม โปรแกรมจัดสรรจำนวนเต็มสองค่าและสตริงสั้นหนึ่งค่าออกจากพูล แล้วแสดงผลเพื่อยืนยันว่าตัวจัดสรรทำงานได้

สังเกตว่าใช้โค้ดน้อยเพียงใดเมื่อเทียบกับ malloc จริง

#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;
}

ไม่สามารถคืนหน่วยความจำทีละรายการ

ข้อจำกัดคือ ตัวจัดสรรแบบ bump ไม่สามารถคืนหน่วยความจำของการจัดสรรเพียงรายการเดียวได้ เนื่องจากไม่มีข้อมูลกำกับ จึงไม่ทราบว่าบล็อกหนึ่งสิ้นสุดตรงไหนและบล็อกถัดไปเริ่มต้นตรงไหนเพื่อจะนำกลับมาใช้

คุณทำได้เพียงรีเซ็ต arena ทั้งหมดในครั้งเดียว โดยกำหนดออฟเซ็ตกลับเป็นศูนย์

void bump_reset(void) {
    offset = 0;   /* frees everything at once */
}

เหตุใดการรีเซ็ตจึงมีประโยชน์

รูปแบบที่เลือกทำอย่างใดอย่างหนึ่งทั้งหมดนี้เหมาะอย่างยิ่งกับงานที่แบ่งเป็นระยะ ได้แก่ จัดสรรออบเจ็กต์จำนวนมากระหว่างคำขอหรือเฟรมหนึ่ง ๆ แล้วรีเซ็ต arena เมื่อระยะนั้นสิ้นสุด

เอนจินเกมและคอมไพเลอร์ใช้ arena อย่างมาก เพราะการรีเซ็ตใช้เวลา O(1) และไม่ต้องติดตามการคืนหน่วยความจำทีละรายการนับพันรายการ

/* Per-frame pattern */
for (int frame = 0; frame < 3; frame++) {
    void *tmp = bump_alloc(128);
    /* ... use tmp this frame ... */
    bump_reset();   /* reclaim instantly */
}

การติดตามพื้นที่ที่เหลือ

การเปิดเผยว่ามีพื้นที่เหลือเท่าใดจะช่วยให้ใช้งานได้สะดวก ซึ่งคำนวณได้ง่าย ๆ จากขนาดของพูลลบด้วยออฟเซ็ตปัจจุบัน

ผู้เรียกใช้ข้อมูลนี้เพื่อตัดสินใจว่าจะล้างข้อมูลหรือขยายพื้นที่ก่อนขอพื้นที่เพิ่มได้

size_t bump_remaining(void) {
    return POOL_SIZE - offset;
}

ตัวอย่างการรีเซ็ตที่เรียกใช้ได้

โปรแกรมนี้เติมข้อมูลลงในพูลบางส่วน แสดงการใช้งาน รีเซ็ต แล้วแสดงให้ออฟเซ็ตกลับเป็นศูนย์ เพื่อให้เห็นว่าพื้นที่นั้นนำกลับมาใช้ใหม่ได้

#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;
}

การจัดแนวในตัวจัดสรรแบบ Bump

การขยับทีละไบต์โดยไม่จัดแนวอาจคืนพอยน์เตอร์ที่จัดแนวไม่ถูกต้อง เพื่อความปลอดภัย ให้ปัดออฟเซ็ตขึ้นไปยังขอบเขตการจัดแนวก่อนคืนพอยน์เตอร์

เราจะอธิบายคณิตศาสตร์โดยละเอียดในภายหลัง แต่ตัวจัดสรรแบบ bump เป็นจุดที่การจัดแนวสำคัญที่สุด เพราะไม่เช่นนั้นจะไม่มีไบต์เติมคั่นไว้

static size_t align_up(size_t n, size_t a) {
    return (n + a - 1) & ~(a - 1);   /* a must be power of 2 */
}

ตัวจัดสรรแบบ Bump ที่จัดแนวแล้ว

เมื่อนำส่วนต่าง ๆ มารวมกัน เราจะจัดแนวออฟเซ็ตก่อนการจัดสรรแต่ละครั้ง วิธีนี้รับประกันว่าพอยน์เตอร์ทุกตัวที่คืนมาจะเหมาะสำหรับชนิดข้อมูลทั่วไปทุกชนิด

ข้อแลกเปลี่ยนคือเกิดการสูญเสียพื้นที่ภายในเล็กน้อยจากไบต์เติมคั่น

#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;
}

จุดแข็งและข้อจำกัด

ตัวจัดสรรแบบ bump มีความเร็วที่ไม่มีวิธีอื่นเทียบได้และเรียบง่ายอย่างมาก โดยไม่มีค่าใช้จ่ายต่อออบเจ็กต์เลย เหมาะอย่างยิ่งเมื่อออบเจ็กต์มีอายุการใช้งานร่วมกัน

จุดอ่อนคือไม่สามารถคืนพื้นที่แบบละเอียดเป็นรายชิ้นได้ เมื่ออายุการใช้งานแตกต่างกัน คุณจำเป็นต้องใช้การออกแบบรายการพื้นที่ว่าง ซึ่งจะกล่าวถึงในบทเรียนถัดไป

ตรวจสอบอย่างรวดเร็ว

ลองพิจารณาว่าตัวจัดสรรแบบ bump เรียกคืนหน่วยความจำอย่างไร

สรุปทบทวน

ตัวจัดสรรแบบ bump จ่ายหน่วยความจำโดยเลื่อนออฟเซ็ตหนึ่งตัวไปตามบัฟเฟอร์ ทำให้การจัดสรรมีต้นทุนต่ำพอ ๆ กับการบวกพอยน์เตอร์

วิธีนี้แลกการคืนพื้นที่เป็นรายชิ้นกับความเร็วและความเรียบง่าย โดยจะเรียกคืนหน่วยความจำได้ก็ต่อเมื่อรีเซ็ตทั้งหมด จัดแนวออฟเซ็ตเพื่อให้พอยน์เตอร์ที่คืนมายังคงใช้งานได้กับทุกชนิดข้อมูล

คำถามที่พบบ่อย

บทเรียน “ตัวจัดสรรแบบเพิ่มตำแหน่งอย่างง่าย” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “ตัวจัดสรรแบบเพิ่มตำแหน่งอย่างง่าย” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส C Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส C Academy มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “ตัวจัดสรรแบบเพิ่มตำแหน่งอย่างง่าย”

แจกจ่ายหน่วยความจำตามลำดับ คุณปฏิบัติ C Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน C Academy หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน C Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน

บทเรียน “ตัวจัดสรรแบบเพิ่มตำแหน่งอย่างง่าย” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน C Academy นี้ได้ไหม

ได้ บทเรียน C Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

← กลับไปที่ C Academy