陣列與異質資料結構 (Arrays & Heterogeneous Data Structures)

Overview Table

3.8.1 陣列配置與存取基本原理 (p.291)

宣告 T A[N](元素型別 T 大小為 L bytes)有兩個效果:配置一塊 連續 的 L*N bytes 記憶體;引入識別字 A 作為指向陣列開頭的指標,其值為起始位址 xA。元素 i(範圍 0 到 N−1)的位址為:

• char A[12] → 元素 1 byte、總大小 12、xA + i
• char *B[8] → 指標陣列,元素 8 bytes、總大小 64、xB + 8i
• int C[6] → 元素 4 bytes、總大小 24、xC + 4i
• double *D[5] → 元素 8 bytes(指標!非 double 本身)、總大小 40、xD + 8i

x86-64 記憶體定址模式 Imm(rb, ri, s) 就是為陣列存取設計的:若 xE 在 %rdx、索引 i 在 %rcx,則 movl (%rdx,%rcx,4),%eax 一條指令完成 xE + 4i 位址計算 + 讀取。scale factor 只能是 1, 2, 4, 8,恰好對應常見基本型別大小。

3.8.2 指標算術 (Pointer Arithmetic) (p.293)

C 的指標算術會依「指向型別的大小 L」自動縮放:若 p 值為 xp,則 p+i 的值為 xp + L*i。&Expr 取址、*AExpr 解參考,Expr 與 *&Expr 等價;A[i] 與 *(A+i) 完全相同。

以 int E[](xE 在 %rdx、i 在 %rcx)為例:

• 回傳 陣列值(int) → 4-byte 操作(movl / %eax);回傳 指標 → 8-byte 操作(leaq / %rax)。
• 指標相減:同一資料結構內兩指標相減,結果型別為 long,值 = (位址差) ÷ L,即「元素個數差」。
• 位址計算(不存取記憶體)用 leaq;實際讀寫才用 mov。

3.8.3 巢狀陣列與 Row-Major Order (p.294)

int A[5][3] 等價於 typedef int row3_t[3]; row3_t A[5];——「5 個元素、每個元素是 3 個 int 的陣列」。總大小 = 4*5*3 = 60 bytes。元素在記憶體中依 row-major order(列優先)排列:先整個 row 0,再 row 1……

記憶體位址遞增 →
xA        xA+4      xA+8      xA+12     xA+16     xA+20     xA+24  ...  xA+56
+---------+---------+---------+---------+---------+---------+------ ... ------+
| A[0][0] | A[0][1] | A[0][2] | A[1][0] | A[1][1] | A[1][2] | A[2][0] ...A[4][2]|
+---------+---------+---------+---------+---------+---------+------ ... ------+
 \_______ row 0 ________/      \_______ row 1 ________/

對宣告 T D[R][C];,元素位址公式(Equation 3.1):

以 A[5][3]、xA/i/j 在 %rdi/%rsi/%rdx 為例,編譯器用 leaq 的 shift-add 能力算 3i,避免乘法:

leaq (%rsi,%rsi,2), %rax    # 3*i  (i + 2i)
leaq (%rdi,%rax,4), %rax    # xA + 12i
movl (%rax,%rdx,4), %eax    # M[xA + 12i + 4j]

3.8.4 固定大小陣列的編譯器最佳化 (p.296)

以 #define N 16; typedef int fix_matrix[N][N]; 計算矩陣乘積的 (i,k) 元素 $\sum _{0\le j<N}{a}_{i,j}\cdot b_{j,k}$ 為例,gcc -O1 做了以下轉換:消去索引變數 j,把所有陣列存取改為指標解參考:

• Aptr = &A[i][0]:沿 row i 走,每次 Aptr++(位址 +4)
• Bptr = &B[0][k]:沿 column k 走,每次 Bptr += N(位址 +4N = +64)
• Bend = &B[N][k]:迴圈終止哨兵(column k 的「第 N+1 個」位置)

A (row i 橫走)                B (column k 直走)
[ . . . . ]                   [ . k . . ]
[ i→→→→→ ]  Aptr++ (+4)       [ . ↓ . . ]  Bptr += N (+64)
[ . . . . ]                   [ . ↓ . . ]
[ . . . . ]                   [ . ↓ . . ]   ...直到 Bptr == Bend

對應組語核心:salq $6,%rdx(64i,因每列 16×4=64 bytes)、迴圈內 addq $4,%rdi、addq $64,%rcx、cmpq %rsi,%rcx + jne。迴圈測試用 do-while + 指標比較,不需計數器。

• Practice Problem 3.40(對角線設值)同理:單一指標每次 += (N+1)*4 = 68 bytes(跨一列再多一欄),終點為 N*(N+1)*4 = 1088,即恰好走過 N 個對角元素後停止。

3.8.5 可變大小陣列 (Variable-Size Arrays) (p.298)

歷史背景:早期 C 的多維陣列除第一維外,各維大小必須是編譯期常數;動態大小需自行用 malloc/calloc 配置一維陣列 + 手動套 Equation 3.1 做 row-major 索引。ISO C99 引入 VLA:int A[expr1][expr2] 可作為區域變數或函式參數,維度在宣告當下求值。

int var_ele(long n, int A[n][n], long i, long j) { return A[i][j]; }

參數 n 必須出現在 A[n][n] 之前,編譯器才能在遇到 A 時計算維度。產生的組語:

imulq %rdx, %rdi              # n * i   ← 必須用乘法指令!
leaq  (%rsi,%rdi,4), %rax     # xA + 4(n*i)
movl  (%rax,%rcx,4), %eax     # M[xA + 4(n*i) + 4j]

位址公式:$\mathrm{\&}A[i][j]=x_A+4(n\cdot i+j)$

與固定大小的差異:(1) 暫存器配置因多了參數 n 而不同;(2) n*i 無法用 leaq shift-add,必須用 imulq,在某些處理器上有明顯效能代價。

迴圈中的 VLA 最佳化(Figure 3.38):gcc 仍能利用存取規律消去乘法——保留 j 作為迴圈計數兼 Arow[j] 索引,Bptr += n 直走欄;組語同時需要 4n(在 %r9,遞增 Bptr 用)與 n(在 %rdi,比較 j:n 用)兩個值,這在 C 原始碼中因指標算術自動縮放而看不出來。

3.9.1 Structures (p.301)

struct 把不同型別的物件聚合成單一物件,以名稱存取欄位。實作上與陣列類似:所有欄位存於 連續記憶體,結構指標 = 第一個 byte 的位址。編譯器為每種 struct 型別維護各欄位的 byte offset,產生記憶體存取指令時以 offset 作為 displacement。

struct rec { int i; int j; int a[2]; int *p; };

Offset:   0       4       8       12      16              24
        +-------+-------+-------+-------+---------------+
        |   i   |   j   | a[0]  | a[1]  |       p       |
        +-------+-------+-------+-------+---------------+
          4B      4B      4B      4B          8B          總計 24 bytes

存取範例(r 在 %rdi):

• 複製 r->i 到 r->j:movl (%rdi),%eax + movl %eax,4(%rdi)(offset 0 與 4)
• 產生指標 &(r->a[i])(i 在 %rsi):leaq 8(%rdi,%rsi,4),%rax——struct 位址 + 欄位 offset + 陣列縮放索引 一條指令完成
• r->p = &r->a[r->i + r->j];:取 j、加 i、cltq 符號擴展成 8 bytes、leaq 8(%rdi,%rax,4)、movq %rax,16(%rdi)

C 提供 -> 作為「解參考 + 選欄位」的簡寫:rp->width ≡ (*rp).width。注意 *rp.width 會被解讀為 *(rp.width),是錯的(p.302 New to C aside)。struct 是 C 中最接近 C++/Java 物件的機制,但方法只能寫成一般函式。

3.9.2 Unions (p.305)

union 語法與 struct 相同、語義完全不同:所有欄位 參考同一塊記憶體(offset 全為 0),用來繞過 C 的型別系統。union 總大小 = 最大欄位的大小(再考慮對齊)。

用途一:節省空間(欄位互斥時)。二元樹節點:leaf 存 2 個 double、internal 存 2 個子指標,兩者互斥:

• struct node_s {left; right; double data[2];} → 每節點 32 bytes,一半浪費
• union node_u {struct {left; right;} internal; double data[2];} → 每節點 16 bytes
• 但 union 無法分辨節點種類 → 常見解法:tagged union——外層 struct 帶 enum tag:

typedef enum { N_LEAF, N_INTERNAL } nodetype_t;
struct node_t {
    nodetype_t type;         /* 4 bytes + 4 bytes padding */
    union { struct {...} internal; double data[2]; } info;  /* 16 bytes */
};                           /* 總計 4 + 4 + 16 = 24 bytes */

用途二:存取不同型別的位元模式(bit-level reinterpretation):

unsigned long double2bits(double d) {
    union { double d; unsigned long u; } temp;
    temp.d = d;
    return temp.u;   /* u 與 d 位元完全相同(含 sign/exponent/significand) */
}

與 cast (unsigned long) d 對比:cast 做「數值轉換」、union 做「位元重解讀」;兩者結果除 d == 0.0 外完全不同。

3.9.3 Data Alignment (p.309)

許多系統要求基本型別的位址必須是某個值 K 的倍數(對齊限制),以簡化處理器—記憶體介面硬體:若 double 保證 8-byte 對齊,一次 8-byte 記憶體操作即可讀寫;否則可能跨越兩個 8-byte block、需要兩次存取。

x86-64 無論對齊與否都能正確運作,但 Intel 建議對齊以提升效能。規則:任何 K bytes 的基本物件,其位址必須是 K 的倍數。

• 全域資料:編譯器在組語中放 .align 8 之類的 directive(如 switch jump table)。
• struct 內部 padding:編譯器在欄位間插入空隙,使每個欄位滿足自身對齊。
• struct 整體對齊:struct 指標本身也要滿足「最大欄位對齊需求」的對齊。
• 尾端 padding:struct 總大小必須是其對齊需求的倍數,才能讓「struct 陣列」中每個元素都對齊。

struct S1 { int i; char c; int j; };     — 內部 padding
Offset:  0        4  5        8        12
       +--------+--+########+--------+
       |   i    |c | 3B gap |   j    |     總大小 12(非 9)
       +--------+--+########+--------+     j 需 4-byte 對齊 → offset 8

struct S2 { int i; int j; char c; };     — 尾端 padding
Offset:  0        4        8  9       12
       +--------+--------+--+########+
       |   i    |   j    |c | 3B pad |     總大小 12(非 9)
       +--------+--------+--+########+
       否則 struct S2 d[4] 的元素位址 xd+9, xd+18, xd+27 無法全部對齊

計算 struct 佈局的通用流程:

逐欄位:offset = 「目前位置向上取整到該欄位對齊 K 的倍數」
             ↓
整體對齊 = max(所有欄位的 K)
             ↓
總大小   = 最後欄位結尾向上取整到「整體對齊」的倍數

• 節省空間技巧(Practice Problem 3.45):把欄位依對齊需求由大到小重排,可減少 padding 浪費。

Exam/Test Patterns

Related Notes

• 03-Machine-Level-Programs/02-Data-Movement-and-Arithmetic — 定址模式 Imm(rb,ri,s) 與 leaq 是陣列存取的基礎
• 03-Machine-Level-Programs/03-Control-Flow — 迴圈翻譯與 jump table(.align 8 出處)
• 03-Machine-Level-Programs/04-Procedures-and-the-Stack — stack frame 的 16-byte 對齊要求
• 03-Machine-Level-Programs/06-Buffer-Overflow-and-Pointer-Safety — 陣列越界與指標誤用的安全後果
• 02-Information-Representation/01-Information-Storage-and-Bits — byte ordering(union 端序陷阱)與位元表示
• 06-Memory-Hierarchy/04-Cache-Friendly-Code-and-Memory-Mountain — row-major 走訪順序對 cache locality 的影響