Bố trí bộ nhớ: Stack, Heap và Cache Line

Hai chương trình có thể thực hiện cùng phép tính nhưng chênh nhau cả bậc độ lớn về thời gian chạy. Chương trình nhanh hơn chưa chắc dùng thuật toán thông minh hơn: có thể nó duyệt vùng nhớ liên tục, trong khi chương trình còn lại đuổi theo pointer, gây page fault và khiến nhiều CPU core tranh nhau cùng cache line.

Vì vậy, “stack hay heap” mới chỉ là cửa vào của memory layout. Mô hình hữu ích phải nối lifetime trong source code, block của allocator, virtual page của process, physical memory và cache hierarchy. Mỗi tầng có quy tắc riêng. Trộn lẫn các tầng dẫn đến những kết luận như “dữ liệu trên stack luôn ở trong cache” hoặc “mỗi lần cấp phát heap là một lần gọi operating system.” Cả hai đều không đúng trong trường hợp tổng quát.

Virtual memory là bản đồ, không phải lãnh thổ #

Mỗi process thường nhìn thấy một virtual address space riêng. Địa chỉ mà lệnh load sử dụng được page table dịch sang physical frame, hoặc chưa trỏ đến frame resident nào. Operating system ánh xạ executable code, shared library, file, anonymous memory, stack và allocator arena vào không gian này. Page thường có kích thước 4 KiB, nhưng large page và những kích thước khác vẫn tồn tại.

Translation lookaside buffer, hay TLB, cache các phép dịch virtual-to-physical gần đây. Data cache hit vẫn có thể cần TLB lookup; TLB miss có thể kích hoạt hardware page-table walk. Nếu chưa có physical page resident, page fault chuyển quyền điều khiển vào kernel. Minor fault có thể chỉ thiết lập mapping hoặc cấp một zeroed page. Major fault có thể phải chờ storage nên đắt hơn rất nhiều.

Hình trên mô tả cách bố trí thường gặp chứ không phải language contract. Randomization dịch chuyển các vùng; allocator có thể dùng mapping không liên tục; stack có thể có guard page; operating system có thể overcommit. Vì vậy virtual size, resident set size và số byte object đang sống là ba đại lượng khác nhau. Guard page, non-executable mapping và randomization giảm rủi ro security nhưng không biến truy cập out-of-bounds thành hợp lệ.

Stack frame và heap allocation biểu diễn lifetime khác nhau #

Stack của thread phục vụ lời gọi hàm. Frame chứa return address, saved register, spill slot và local value; return bỏ frame với chi phí hằng số. Trong code đã optimize, function có thể được inline, local nằm trong register và stack slot được tái sử dụng. Recursion hoặc local array lớn vẫn có thể làm cạn stack.

Heap lưu value có kích thước hoặc lifetime không khớp call nesting. malloc thường không hỏi kernel cho từng object: allocator chia region lớn thành size class hoặc run rồi theo dõi free block. Allocation nhỏ có thể dùng thread-local cache, còn allocation lớn nhận mapping riêng. Metadata, synchronization, fragmentation và locality kém vẫn là chi phí thật.

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

static long sum_copy(const int *values, size_t count) {
    long total = 0;                 /* Thường ở register hoặc stack slot. */
    for (size_t i = 0; i < count; ++i) {
        total += values[i];
    }
    return total;
}

int main(void) {
    const size_t count = 1024;
    int *values = malloc(count * sizeof *values);
    if (values == NULL) return EXIT_FAILURE;

    for (size_t i = 0; i < count; ++i) values[i] = (int)i;
    printf("%ld\n", sum_copy(values, count));
    free(values);
    return EXIT_SUCCESS;
}

Ở đây biến pointer values có automatic lifetime trong main, còn array có allocated lifetime đến lúc free. Điều đó không đảm bảo pointer nằm vật lý “trên stack”: optimizer có thể giữ nó trong register. Nó cũng không đảm bảo page của array resident ngay sau malloc. Nhiều hệ thống chỉ commit physical page khi code chạm vào page lần đầu.

Alignment và padding định hình mọi object #

Processor và application binary interface đặt ra yêu cầu alignment. uint64_t thường ưu tiên địa chỉ chia hết cho 8, còn byte có alignment 1. Compiler chèn padding trước field và ở cuối structure để mỗi field được căn đúng và mỗi phần tử array bắt đầu tại địa chỉ hợp lệ.

Với offset hiện tại là offset và alignment bắt buộc là A, số byte chèn trước field là:

padding = (A - (offset % A)) % A
aligned_size = round_up(raw_size, maximum_field_alignment)

Khi A là lũy thừa của hai, low-level code thường làm tròn integer address bằng (x + A - 1) & ~(A - 1) sau khi kiểm tra overflow. Biểu thức này không thể thay thế allocator có cam kết alignment phù hợp.

Hãy đo layout thay vì đoán:

#include <stddef.h>
#include <stdint.h>
#include <stdio.h>

struct Event {
    uint8_t kind;
    uint64_t timestamp;
    uint8_t active;
};

int main(void) {
    printf("size=%zu align=%zu offsets=%zu,%zu,%zu\n",
           sizeof(struct Event), _Alignof(struct Event),
           offsetof(struct Event, kind),
           offsetof(struct Event, timestamp),
           offsetof(struct Event, active));
}

Trên ABI 64-bit phổ biến, layout này chiếm 24 byte, nhưng C standard không bảo đảm con số đó. Đưa hai byte field cạnh nhau thường giảm còn 16 byte trên ABI ấy. Reorder vì thế tiết kiệm đáng kể khi có hàng triệu phần tử, nhưng cũng thay đổi binary layout. Đây là vấn đề với foreign-function interface, record được persist, network protocol và code dựa vào field offset.

Packed structure bỏ bớt padding nhưng có thể tạo misaligned load, chậm hoặc fault trên architecture nghiêm ngặt. Packing không định nghĩa byte order; hãy serialize từng field, chỉ rõ endianness và xem raw structure dump là format phụ thuộc ABI. Rust cũng để compiler chọn default layout; dùng #[repr(C)] cho field order tương thích C, #[repr(transparent)] cho wrapper phù hợp và vẫn kiểm tra external contract.

Cache line thưởng cho locality và làm lộ false sharing #

CPU chuyển dữ liệu qua cache theo cache line có kích thước cố định, thường là 64 byte trên desktop và server hiện nay nhưng không phải ở mọi nơi. Đọc một byte thường kéo cả line xung quanh vào cache gần CPU. Hardware prefetcher nhận diện stream đều, nên duyệt array liên tục có thể tiến gần memory bandwidth trong khi pointer chasing bị dừng bởi chuỗi cache miss phụ thuộc nhau.

Hai ước lượng nhỏ giúp định hướng quá trình điều tra:

working_set_bytes = element_count * bytes_per_element
minimum_lines_touched = ceil(bytes_scanned / cache_line_bytes)

Công thức thứ hai chỉ là lower bound. Stride, alignment, associativity conflict, page boundary và write có thể tăng traffic. Temporal locality là tái sử dụng dữ liệu trước khi nó bị evict; spatial locality là sử dụng byte lân cận đã được fetch. Chia matrix algorithm thành tile vừa cache cải thiện cả hai mà không đổi độ phức tạp tiệm cận.

Cache coherence trên multicore tạo thêm một vấn đề. Các core thường duy trì coherence ở granularity cache line. Nếu hai thread cập nhật hai counter khác nhau nhưng cùng nằm trên một line, quyền sở hữu line liên tục di chuyển giữa core dù hai biến độc lập về logic. Đây là false sharing.

use std::sync::atomic::{AtomicU64, Ordering};

// Giả định khoảng cách 64 byte phù hợp với target triển khai.
#[repr(align(64))]
struct PaddedCounter {
    value: AtomicU64,
}

fn increment(counter: &PaddedCounter) {
    counter.value.fetch_add(1, Ordering::Relaxed);
}

Padding counter nóng theo từng thread có thể hữu ích, nhưng nó tăng footprint và có thể lãng phí cache capacity. Relaxed ở đây chỉ đúng khi counter cần atomicity nhưng không publish memory khác; synchronization semantics mạnh hơn cần ordering mạnh hơn hoặc lock. Hãy benchmark đúng target. Khi không cần tổng số chính xác tức thời, counter local được shard và aggregate định kỳ thường hiệu quả hơn.

AoS, SoA và TypedArray biến access pattern thành cụ thể #

Array of structures (AoS) đặt mọi field của một entity cạnh nhau. Structure of arrays (SoA) đặt cùng một field của mọi entity cạnh nhau. AoS phù hợp khi operation dùng gần hết field của từng object. SoA thường tốt hơn cho loop có vectorization nhưng chỉ đọc một tập field nhỏ.

Rust biểu diễn khác biệt này rõ ràng mà không cần lộ unsafe pointer:

#[repr(C)]
struct Particle {
    x: f32,
    y: f32,
    z: f32,
    mass: f32,
}

struct Particles {
    x: Vec<f32>,
    y: Vec<f32>,
    z: Vec<f32>,
    mass: Vec<f32>,
}

fn advance_x(particles: &mut Particles, velocity_x: &[f32], dt: f32) {
    assert_eq!(particles.x.len(), velocity_x.len());
    for (x, velocity) in particles.x.iter_mut().zip(velocity_x) {
        *x += *velocity * dt;
    }
}

Loop SoA chỉ load x và velocity_x; y, z và mass không chiếm cache line cho operation này. Lợi thế biến mất nếu operation kế tiếp lập tức cần mọi field của một particle. Layout phải đi theo dominant query, không đi theo trào lưu.

JavaScript object không cam kết byte layout kiểu C. Engine dùng shape, tagged value, pointer compression và representation có thể đổi sau optimization hoặc deoptimization. TypedArray là công cụ dành cho numeric storage dày đặc, tường minh:

const count = 100_000;
const storage = new ArrayBuffer(
  count * 3 * Float32Array.BYTES_PER_ELEMENT,
);
const all = new Float32Array(storage);
const x = all.subarray(0, count);
const y = all.subarray(count, count * 2);
const z = all.subarray(count * 2, count * 3);

for (let index = 0; index < count; index += 1) {
  x[index] += 0.25;
}

const header = new DataView(new ArrayBuffer(8));
header.setUint32(0, count, true); // Encode little-endian tường minh.

Các view dùng chung một ArrayBuffer; subarray không copy. JavaScript runtime kiểm tra bounds, nhưng index theo logic ứng dụng vẫn phải được validate, còn detached hoặc shared buffer có thêm quy tắc riêng. Dùng DataView khi binary format cần endianness tường minh hoặc unaligned field. Dùng Atomics để synchronization trên SharedArrayBuffer; read và write đồng thời thông thường không thể thay thế synchronization protocol.

Garbage collection, profiling và safety cùng nằm trong mô hình #

Garbage-collected runtime thay đổi cách reclaim memory chứ không xóa chi phí layout. Young-generation collector tận dụng quan sát rằng nhiều object chết sớm. Bump allocation có thể cực rẻ, còn copy live object có thể compact chúng. Tuy nhiên, một cơn bão wrapper tạm thời làm tăng allocation và tracing; graph sống lâu gây áp lực lên old generation; reference bị cache giữ lại có thể giữ sống cả subgraph; pointer từ object già đến object trẻ cần write barrier và remembered set.

Object pooling không tự động nhanh hơn. Pool có thể giữ memory sống, tăng old-generation occupancy, bảo toàn stale state và cản collector vốn đã tối ưu cho object sống ngắn. Chỉ pool sau khi profile xác định allocation hoặc pause là bottleneck, đồng thời phải giới hạn kích thước pool.

Phép đo nên nối symptom với đúng tầng:

Bắt đầu bằng workload đại diện và release build. Trên Linux, perf stat đo cycle, instruction, cache miss và page fault; perf record tìm hot call path. Heap profiler và runtime snapshot chỉ ra allocation site cùng retention path; browser panel cho thấy GC và ArrayBuffer. Valgrind hoặc sanitizer tìm invalid access trong C dù làm thay đổi timing. Ghi CPU model, compiler flag, runtime version, input và confidence interval trước khi tuyên bố layout mới nhanh hơn.

Cuối cùng, performance không đứng trên memory safety. Pointer arithmetic vượt ra ngoài object, use-after-free, data race và đọc uninitialized storage trong C là undefined behavior. Borrow checker của Rust ngăn nhiều lỗi trong safe code, nhưng unsafe, FFI, atomic và custom allocator đưa proof obligation trở lại. Typed array ngăn arbitrary pointer dereference chứ không ngăn allocation lớn gây denial of service hoặc logical race. Hãy làm ownership tường minh, kiểm tra overflow trong phép tính kích thước, test boundary size và dùng sanitizer hoặc interpreter chuyên bắt violation.

Takeaways #

• Virtual address được dịch theo page; virtual size, resident memory, allocator capacity và kích thước live object là những phép đo khác nhau.
• Stack frame hợp với call lifetime lồng nhau; heap allocator quản lý lifetime linh hoạt qua arena, size class và mapping.
• Alignment và padding là thuộc tính ABI có thể quan sát. Hãy đo chúng và serialize tường minh thay vì dump structure.
• Cache performance đi theo temporal và spatial access pattern. Duyệt liên tục thường tốt; pointer chasing và false sharing thường gây hại.
• Chọn AoS, SoA hay hybrid từ những field mà hot loop thực sự sử dụng. Typed array cung cấp numeric storage tường minh trong JavaScript.
• Garbage collection không xóa chi phí allocation, retention, locality hay synchronization.
• Profile release workload đại diện trước khi đổi layout; không đánh đổi defined behavior hoặc synchronization correctness để lấy một benchmark đẹp.