10.5 จองหน่วยความจำด้วย malloc

อาเรย์ทุกตัวที่ผ่านมามีขนาดตายตัวตั้งแต่ตอนเขียนโค้ด ถ้าอยู่ใน main ก็ใหญ่ได้รวมราว 2 MB ตามหน้า 5.5 ถ้าอยู่นอก main ก็ต้องประกาศเผื่อขนาดมากสุดของโจทย์ไว้ก่อน หน้านี้สอนวิธีขอหน่วยความจำระหว่างโปรแกรมรัน ได้ขนาดตามข้อมูลเข้าพอดี ใช้เสร็จแล้วคืนได้ และสร้างตารางที่แต่ละแถวยาวไม่เท่ากัน ซึ่งช่วยในโจทย์ที่มีข้อมูลหลายชุดขนาดต่างกัน และเป็นฐานของ linked list ในบทที่ 14

ทำไมต้องจองเอง

ลองนึกถึงโจทย์ที่ให้ตารางคะแนน K ห้อง ห้องหนึ่งมีนักเรียนได้ถึง 10⁵ คน แต่รวมทุกห้องไม่เกิน 10⁵ คน ถ้าประกาศอาเรย์สองมิติตายตัวต้องเผื่อ K × 10⁵ ช่อง เมื่อ K เป็น 10⁵ ก็คือ 10¹⁰ ช่อง หรือ 40 GB ไม่มีเครื่องไหนรับไหว ทั้งที่ข้อมูลจริงมีแค่ 10⁵ ตัว ถ้าขอหน่วยความจำให้แต่ละห้องตอนรู้ขนาดแล้ว จะใช้รวมแค่ 10⁵ ช่องพอดี

หน่วยความจำที่ขอระหว่างรันมาจากส่วนที่เรียกว่า heap ต่างจากตัวแปรใน main ที่อยู่ใน stack ซึ่งเล็ก heap ใช้ได้จนเกือบเต็มหน่วยความจำของเครื่อง

malloc และ free

malloc (memory allocation) อยู่ใน stdlib.h รับจำนวน byte ที่ต้องการ แล้วคืนที่อยู่ของ byte แรก ได้มาแล้วใช้เหมือนอาเรย์ได้ทันที เพราะ scores[i] คือ *(scores + i) ตามหน้า 10.3 ใช้เสร็จแล้วคืนด้วย free

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n;
    scanf("%d", &n);
    int *scores = malloc(n * sizeof(int)); // (1)!
    if (scores == NULL) { // (2)!
        printf("not enough memory\n");
        return 1;
    }
    long long total = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &scores[i]);
        total += scores[i];
    }
    int above = 0;
    for (int i = 0; i < n; i++) {
        if ((long long)scores[i] * n > total) { // (3)!
            above++;
        }
    }
    printf("%d of %d are above average\n", above, n);
    free(scores); // (4)!
    return 0;
}

ขอ n ช่อง ช่องละ sizeof(int) byte malloc คืนชนิด void * คือที่อยู่ที่ไม่บอกชนิด ภาษา C แปลงเป็น int * ให้เองตอนกำหนดค่า
ถ้าจองไม่สำเร็จ malloc คืน NULL ต้องตรวจก่อนใช้ ตามกฎในหน้า 10.1
เทียบกับค่าเฉลี่ยโดยไม่หาร คือ scores[i] > total / n คูณ n ทั้งสองข้าง จะได้ไม่ต้องใช้ทศนิยม แปลงเป็น long long ก่อนคูณตามกับดักในหน้า 1.3
คืนหน่วยความจำ หลังบรรทัดนี้ห้ามใช้ scores อีก

6
70 85 90 60 75 95

3 of 6 are above average

ค่าเฉลี่ยคือ 475 / 6 ประมาณ 79.2 มีสามคนที่ได้มากกว่า คือ 85 90 95 สิ่งที่ต้องจำมีสามข้อ

ขนาดที่ขอเป็น byte ต้องคูณ sizeof ของชนิดเสมอ ห้ามเขียน 4 เอง ดูแบบที่ 2 ในส่วนลองทำให้พัง
malloc ทุกครั้งต้องมี free คู่กันหนึ่งครั้ง เมื่อไม่ใช้แล้ว
ค่าในช่องที่ได้จาก malloc ยังไม่ได้ตั้งต้น ต้องใส่ค่าเองก่อนอ่าน

calloc ได้ช่องที่เป็น 0

อาเรย์นับแบบหน้า 5.3 ต้องเริ่มที่ 0 ทุกช่อง calloc(จำนวนช่อง, ขนาดของหนึ่งช่อง) จองแล้วใส่ 0 ให้ทุก byte ตัวอย่างนี้นับคะแนนเลือกตั้งประธานนักเรียน ซึ่งจำนวนผู้สมัครรู้ตอนรัน

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int k, n;
    scanf("%d %d", &k, &n);
    int *votes = calloc(k + 1, sizeof(int)); // (1)!
    if (votes == NULL) {
        return 1;
    }
    for (int i = 0; i < n; i++) {
        int choice;
        scanf("%d", &choice);
        votes[choice]++;
    }
    int winner = 1;
    for (int c = 1; c <= k; c++) {
        printf("candidate %d: %d\n", c, votes[c]);
        if (votes[c] > votes[winner]) {
            winner = c;
        }
    }
    printf("winner %d\n", winner);
    free(votes);
    return 0;
}

ผู้สมัครเบอร์ 1 ถึง k จึงขอ k + 1 ช่องแล้วไม่ใช้ช่อง 0 แบบเดียวกับอาเรย์นับในบทที่ 5

4 10
2 3 2 1 4 2 3 2 1 3

candidate 1: 2
candidate 2: 4
candidate 3: 3
candidate 4: 1
winner 2

ถ้าใช้ malloc แทน ค่าเริ่มต้นของแต่ละช่องคืออะไรก็ได้ บนเครื่องที่เขียนเอกสารนี้ลองจองด้วย malloc แล้วพิมพ์ทันทีได้ 0 ทุกช่อง แต่ GCC เตือน may be used uninitialized และมาตรฐานภาษา C ไม่ได้รับประกันว่าจะเป็น 0 ห้ามพึ่งผลนี้ ต้องการ 0 ให้ใช้ calloc

จองได้ใหญ่แค่ไหน

ลองจอง int หนึ่งร้อยล้านช่อง ซึ่งคือ 400 MB ถ้าประกาศใน main จะพังทันทีเพราะเกิน 2 MB ไปสองร้อยเท่า แล้วลองขอ 10¹² byte หรือ 1000 GB ซึ่งไม่มีเครื่องไหนให้ได้

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n = 100000000;
    int *big = malloc(n * sizeof(int));
    if (big == NULL) {
        printf("100 million ints: NULL\n");
    } else {
        for (int i = 0; i < n; i++) {
            big[i] = i;
        }
        printf("100 million ints: OK, last = %d\n", big[n - 1]);
        free(big);
    }
    long long bytes = 1000000000000;
    char *too_big = malloc(bytes);
    if (too_big == NULL) {
        printf("10^12 bytes: NULL\n");
    } else {
        printf("10^12 bytes: OK\n");
        free(too_big);
    }
    return 0;
}

100 million ints: OK, last = 99999999
10^12 bytes: NULL

บนเครื่องที่เขียนเอกสารนี้ (โน้ตบุ๊ก ASUS Vivobook S 14 แรม 32 GB) จอง 400 MB แล้วเขียนครบร้อยล้านช่องได้ไม่มีปัญหา ส่วน 1000 GB ได้ NULL กลับมาอย่างสุภาพ ไม่พัง นี่คือเหตุผลที่ต้องตรวจ NULL แต่ใน grader จริง แต่ละข้อมีขีดจำกัดหน่วยความจำของมัน ต้องอ่านในโจทย์ และคำนวณเองว่าจองรวมกี่ byte ก่อนส่ง

อยู่จนกว่าจะ free

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

#include <stdio.h>
#include <stdlib.h>

int *read_array(int n)
{
    int *values = malloc(n * sizeof(int));
    if (values == NULL) {
        return NULL;
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &values[i]);
    }
    return values; // (1)!
}

int main()
{
    int n;
    scanf("%d", &n);
    int *morning = read_array(n);
    int *evening = read_array(n);
    if (morning == NULL || evening == NULL) {
        return 1;
    }
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d", evening[i] - morning[i]);
    }
    printf("\n");
    free(morning); // (2)!
    free(evening);
    return 0;
}

ตัวแปร values หายไปตอนฟังก์ชันจบ แต่ค่าของมันคือที่อยู่ในส่วน heap ซึ่งยังอยู่ ส่งค่านั้นออกไปจึงปลอดภัย
คนที่ได้ที่อยู่ไปเป็นคนรับผิดชอบ free ฟังก์ชันที่คืนหน่วยความจำจาก malloc ควรบอกไว้ชัดๆ ว่าคนเรียกต้อง free

4
24 25 23 26
31 33 30 32

7 8 7 6

อุณหภูมิตอนเช้าและตอนเย็นของสี่วัน อ่านด้วยฟังก์ชันเดียวกันสองครั้ง ได้อาเรย์สองก้อนแยกกัน เพราะ malloc แต่ละครั้งได้หน่วยความจำก้อนใหม่ linked list ในบทที่ 14 ใช้หลักการนี้สร้างกล่องใหม่ทีละกล่องระหว่างรัน

ตารางที่จองเองทีละแถว

ตารางแบบจองเองคืออาเรย์ของ pointer ช่องที่ r เก็บที่อยู่ของแถวที่ r ซึ่งจองแยกกัน ชนิดของแต่ละช่องคือ int * ชนิดของตัวตารางจึงเป็น int ** คือ pointer ไปยัง int * แต่ละแถวยาวไม่เท่ากันได้ ตัวอย่างนี้สร้างสามเหลี่ยมปาสกาล แถวที่ r มี r + 1 ตัว และแต่ละตัวคือผลบวกของสองตัวที่อยู่เหนือมัน

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n;
    scanf("%d", &n);
    int **row = malloc(n * sizeof(int *)); // (1)!
    for (int r = 0; r < n; r++) {
        row[r] = malloc((r + 1) * sizeof(int)); // (2)!
        row[r][0] = 1;
        row[r][r] = 1;
        for (int c = 1; c < r; c++) {
            row[r][c] = row[r - 1][c - 1] + row[r - 1][c]; // (3)!
        }
    }
    for (int r = 0; r < n; r++) {
        for (int c = 0; c <= r; c++) {
            if (c > 0) {
                printf(" ");
            }
            printf("%d", row[r][c]);
        }
        printf("\n");
    }
    for (int r = 0; r < n; r++) {
        free(row[r]); // (4)!
    }
    free(row);
    return 0;
}

จองอาเรย์ของ pointer n ช่อง ขนาดของแต่ละช่องคือ sizeof(int *) ซึ่งเป็น 8 ไม่ใช่ sizeof(int)
จองแถวที่ r ยาว r + 1 ช่องพอดี แล้วเก็บที่อยู่ไว้ใน row[r]
row[r][c] อ่านทีละขั้น row[r] คือที่อยู่ของแถว แล้ว [c] คือช่องที่ c ของแถวนั้น ใช้สองวงเล็บเหมือนอาเรย์สองมิติในบทที่ 7
คืนทุกแถวก่อน แล้วค่อยคืนอาเรย์ของ pointer ถ้าคืน row ก่อน ก็จะไม่มีที่อยู่ของแถวเหลือให้คืน

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

แต่ละแถวเป็นก้อนแยกกันใน heap ไม่ได้วางต่อกันเป็นแถวยาวแถวเดียวแบบอาเรย์สองมิติในหน้า 7.1 ถ้า n เป็น 10000 ตารางสี่เหลี่ยม n × n ของ int ใช้ 400 MB แต่สามเหลี่ยมนี้ใช้ราวครึ่งหนึ่ง เพราะจองแค่ช่องที่ใช้จริง (ค่าในสามเหลี่ยมปาสกาลล้น int ตั้งแต่แถว r = 34 ถ้าต้องการแถวลึกกว่านั้นให้ใช้ long long ซึ่งก็ล้นอีกทีตั้งแต่แถว r = 67)

pointer ชี้ pointer

int ** ไม่ได้มีไว้ทำตารางอย่างเดียว pointer ก็เป็นกล่องที่มีที่อยู่ ตัวแปรที่เก็บที่อยู่ของ pointer จึงมีชนิด int ** ใส่ * หนึ่งตัวได้ pointer ตัวกลาง ใส่สองตัวได้กล่องปลายทาง

#include <stdio.h>

int main()
{
    int score = 70;
    int *p = &score;
    int **pp = &p;
    **pp = 85;
    printf("score = %d\n", score);
    printf("%d %d %d\n", score, *p, **pp);
    return 0;
}

score = 85
85 85 85

ใช้จริงเมื่อฟังก์ชันต้องแก้ตัว pointer ของคนเรียก ไม่ใช่แก้ค่าที่ pointer ชี้ กฎเดียวกับหน้า 10.2 ทุกอย่าง อยากให้ฟังก์ชันแก้ int ส่ง int * อยากให้แก้ int * ก็ส่ง int ** ตัวอย่างนี้สลับลำดับคนพูดหน้าเสาธงในอาเรย์ const char * จากหน้า 10.4

#include <stdio.h>

void swap_names(const char **x, const char **y) // (1)!
{
    const char *temp = *x;
    *x = *y;
    *y = temp;
}

int main()
{
    const char *speakers[4] = {"Ploy", "Ton", "Mint", "Beam"};
    int a, b;
    scanf("%d %d", &a, &b);
    swap_names(&speakers[a - 1], &speakers[b - 1]); // (2)!
    for (int i = 0; i < 4; i++) {
        printf("%s\n", speakers[i]);
    }
    return 0;
}

หน้าตาเหมือน swap ในหน้า 10.2 ทุกบรรทัด แค่ชนิดของกล่องที่สลับเปลี่ยนจาก int เป็น const char * pointer ไปยังกล่องชนิดนั้นจึงมีดอกจันเพิ่มอีกตัว
แต่ละช่องของ speakers เป็น const char * ที่อยู่ของช่องจึงเป็น const char **

1 4

Beam
Ton
Mint
Ploy

ไม่มีตัวอักษรถูกคัดลอกเลยสักตัว สิ่งที่สลับคือที่อยู่สองค่าใน speakers ไม่ว่าชื่อจะยาวเท่าไรก็สลับเท่ากัน ตารางแบบ int ** ในหัวข้อที่แล้วก็ใช้หลักเดียวกันได้ สลับ row[a] กับ row[b] คือสลับทั้งแถวโดยไม่ต้องคัดลอกทีละช่อง เร็วเท่ากันไม่ว่าแถวจะยาวแค่ไหน

ลองทำให้พัง

แบบที่ 1 ลืม include stdlib.h

ในโปรแกรม average ลบบรรทัด #include <stdlib.h> ออก

average.c:7:19: error: implicit declaration of function 'malloc' [-Wimplicit-function-declaration]
    7 |     int *scores = malloc(n * sizeof(int));
      |                   ^~~~~~
average.c:2:1: note: include '<stdlib.h>' or provide a declaration of 'malloc'
    1 | #include <stdio.h>
  +++ |+#include <stdlib.h>
    2 |

implicit declaration แปลว่าใช้ฟังก์ชันที่ compiler ยังไม่รู้จัก GCC 14 ถือเป็น error และบอกวิธีแก้มาให้ถึงบรรทัดเลย คือเติม #include <stdlib.h> บรรทัดที่มี + คือบรรทัดที่แนะนำให้เพิ่ม ตามมาด้วยข้อความชุดเดียวกันสำหรับ free และคำเตือน incompatible implicit declaration of built-in function อีกหลายบรรทัด ซึ่งหายไปหมดเมื่อเติมบรรทัดเดียวนี้

แบบที่ 2 ลืมคูณ sizeof

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n;
    scanf("%d", &n);
    int *scores = malloc(n);
    for (int i = 0; i < n; i++) {
        scores[i] = i;
    }
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        sum += scores[i];
    }
    free(scores);
    printf("sum = %lld\n", sum);
    return 0;
}

malloc(n) ขอแค่ n byte แต่ n ช่องของ int ต้องใช้ 4n byte ลูปจึงเขียนเลยก้อนที่ได้ไปสามเท่า คอมไพล์ด้วย -Wall ไม่มีคำเตือน บนเครื่องที่เขียนเอกสารนี้ ผลขึ้นกับ n

ป้อน n	ผล
5 10 20	พิมพ์ `sum = 10` `sum = 45` `sum = 190` ถูกทุกครั้ง
100 1000	ไม่พิมพ์อะไร `Process returned -1073740940 (0xC0000374)`
100000	ไม่พิมพ์อะไร `Process returned -1073741819 (0xC0000005)`

ตัวอย่างเล็กเขียนเกินไปแค่ไม่กี่สิบ byte บังเอิญไม่ไปทับอะไรที่ถูกตรวจ จึงดูเหมือนถูก พอ n ใหญ่ขึ้นก็ไปทับข้อมูลที่ระบบใช้จดว่าก้อนไหนจองแล้ว 0xC0000374 คือรหัสของ Windows ที่แปลว่า heap เสียหาย ซึ่งตรวจเจอตอน free และ 0xC0000005 คือเขียนไกลจนออกนอกหน่วยความจำของโปรแกรม บั๊กแบบนี้ผ่านตัวอย่างในโจทย์แต่ตกชุดทดสอบใหญ่ ให้เขียน n * sizeof(int) จนเป็นนิสัย

แบบที่ 3 จองในลูปแล้วไม่ free

โจทย์มีข้อมูลหลายชุด แต่ละชุดจองอาเรย์ใหม่ แล้วลืมคืน

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int rooms, n;
    scanf("%d %d", &rooms, &n);
    long long total = 0;
    for (int r = 0; r < rooms; r++) {
        int *scores = malloc(n * sizeof(int));
        for (int i = 0; i < n; i++) {
            scores[i] = i % 100;
        }
        for (int i = 0; i < n; i++) {
            total += scores[i];
        }
    }
    printf("total = %lld\n", total);
    return 0;
}

ป้อน 1000 100000 ได้ total = 4950000000 ถูกต้อง แต่ทุกรอบจอง 400 KB แล้วไม่คืน พอ scores หายไปตอนจบรอบ ก็ไม่มีใครรู้ที่อยู่ของก้อนนั้นอีกเลย คืนก็ไม่ได้แล้ว เรียกว่า memory leak (หน่วยความจำรั่ว) บนเครื่องที่เขียนเอกสารนี้ วัดหน่วยความจำสูงสุดที่โปรแกรมใช้ด้วย PowerShell สองครั้งได้ 348 MB และ 363 MB พอเติม free(scores); ท้ายลูป ได้คำตอบเท่าเดิมและใช้แค่ 4.7 MB ถ้าโจทย์จำกัดหน่วยความจำไว้ โปรแกรมที่รั่วจะตกเพราะหน่วยความจำเกิน ทั้งที่คำตอบถูก

แบบที่ 4 ใช้หลัง free และ free ซ้ำ

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int *scores = malloc(3 * sizeof(int));
    scores[0] = 70;
    scores[1] = 85;
    scores[2] = 90;
    free(scores);
    printf("%d %d %d\n", scores[0], scores[1], scores[2]);
    return 0;
}

scores.c:11:5: warning: pointer 'scores' used after 'free' [-Wuse-after-free]
   11 |     printf("%d %d %d\n", scores[0], scores[1], scores[2]);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scores.c:10:5: note: call to 'free' here
   10 |     free(scores);
      |     ^~~~~~~~~~~~

คำเตือนขึ้นซ้ำอีกสองชุดสำหรับ scores[1] กับ scores[2] บนเครื่องที่เขียนเอกสารนี้โปรแกรมยังพิมพ์ 70 85 90 เพราะ free แค่บอกว่าก้อนนี้ว่างแล้ว ไม่ได้ลบค่าทิ้ง ตัว pointer ก็ยังเก็บที่อยู่เดิม จึงดูเหมือนไม่มีอะไรผิด แต่ถ้ามี malloc ครั้งต่อไป ก้อนนี้อาจถูกให้คนอื่นไปใช้และค่าเปลี่ยนเมื่อไรก็ได้

ถ้าเปลี่ยนบรรทัดที่ 11 เป็น free(scores); อีกครั้ง คือคืนก้อนเดิมซ้ำ GCC เตือนแบบเดียวกัน และบนเครื่องที่เขียนเอกสารนี้โปรแกรมพังด้วย Process returned -1073740940 (0xC0000374) ทุกครั้ง วิธีกันทั้งสองแบบคือหลัง free(p); ให้ตั้ง p = NULL; ทันทีถ้ายังจะใช้ตัวแปรนั้นต่อ ถ้าเผลอใช้ *p อีกจะพังทันทีแบบที่ 5 ของหน้า 10.1 แทนที่จะได้ค่าเก่าเงียบๆ และ free(NULL) ไม่ทำอะไรเลย จึงไม่พังแม้เผลอเรียกซ้ำ

สรุป

malloc(n * sizeof(int)) จอง n ช่องใน heap ระหว่างรัน ใช้เหมือนอาเรย์ ต้อง #include <stdlib.h> และตรวจ NULL
calloc(n, sizeof(int)) จองแล้วได้ 0 ทุกช่อง malloc ไม่รับประกันค่าเริ่มต้น
หน่วยความจำจาก malloc อยู่จนกว่าจะ free ฟังก์ชันจึงคืนที่อยู่ของมันได้ จองกี่ครั้งต้อง free เท่านั้นครั้ง
ตารางจองเองคือ int ** จองอาเรย์ของ pointer ก่อน แล้วจองทีละแถว แต่ละแถวยาวไม่เท่ากันได้ คืนทุกแถวก่อนคืนตัวตาราง
อยากให้ฟังก์ชันแก้ pointer ของคนเรียก ส่ง pointer ไปยัง pointer สลับแถวหรือสลับข้อความได้โดยสลับแค่ที่อยู่
ลืม sizeof ใช้หลัง free และ free ซ้ำ อาจผ่านตัวอย่างเล็กแต่พังทีหลัง ลืม free ในลูปทำให้หน่วยความจำรั่ว

กลับไปเช็กรายการ ผ่านบทนี้เมื่อ แล้วไปทำแบบฝึกหัด