跳转至

数据结构 — 数组与记录:索引和字段名在机器层都是偏移量

这一章讲什么: 程序 = 算法 + 数据结构,算法讲了半本,现在讲数据结构的两块基石。 数组:同类型元素的连续队列,访问靠「数组名 + 索引」;记录(结构体): 可异类型的字段打包,访问靠「记录名 + 字段名」。你会看到: 这两种高级写法,到机器层全变成「基址 + 一个事先算好的偏移量」—— 索引是算出来的偏移量,字段名是查出来的偏移量。 主线例子: 一个 int 数组填进 2×索引的值再逐项打印;一个「char + int + char」 的记录,看它的 6 字节填充是怎么来的。

1. 数组:第 12 章那条 SIB 指令的主场

C 层的两个事实

数组的定义:int intArray[N];——类型、名字、个数三件套。使用数组要先知道两件 和直觉相反的事1:

  1. C 传数组永远传指针。 数组名作为函数参数时,传进去的是首元素的地址, 不是整个数组的副本——因为复制整个数组太浪费,语言设计者直接替你做了选择。 函数原型里 int theArray[] 和 int *theArray 是同一回事。
  2. 长度不跟着数组走。 地址里不含长度,函数要知道元素个数,必须另传一个参数—— 这就是为什么 twiceIndex、displayArray 的签名里都多一个 nElements。

汇编证据(清单 17-2):main 里两次 lea rax, -48[rbp] 算出数组地址、塞进 rdi, 10(元素个数)进 esi,然后 call——没有任何字节被复制,递过去的只是一个地址2。

主线例子:twiceIndex 把 2×i 存进第 i 个格子

C 代码就一行循环体 theArray[i] = 2 * i;。gcc 的汇编(清单 17-5)把它拆成 第 12 章的寻址全家桶3:

mov  eax, DWORD PTR -4[rbp]    ## i(32 位)
cdqe                           ## 符号扩展成 64 位 → rax
lea  rdx, 0[0+rax*4]           ## 偏移量 = i × 4(比例寻址!)
mov  rax, QWORD PTR -24[rbp]   ## 数组首地址
add  rax, rdx                  ## 首地址 + 偏移量 = 元素地址
mov  DWORD PTR [rax], edx      ## 存 2×i

这一段的每个零件都能对上前面的章节:cdqe 是第 16 章的符号扩展桥 (0[rax*4] 要求 64 位索引);rax*4 是第 12 章 SIB 字节的「比例 ×4」; 基址 + 偏移量是第 12 章的带偏移寄存器间接寻址。第 12 章学的「字节解剖」, 在本章第一次看到了它的实战价值。

cdqe 顺手收进工具箱:cbw/cwde/cdqe 三兄弟,分别在 al→ax、ax→eax、 eax→rax 内部做符号扩展,只碰 rax 系、不影响标志——除法 cdq 的同族亲戚4。

手写版:索引全程住寄存器

清单 17-9 的手写 twiceIndex 更直白——索引放 ecx,shl eax, 1 乘 2(第 16 章), 最关键的一行:mov [rdi+rcx*4], eax——基址(rdi)+ 变址(rcx)× 比例(4), 一条指令完成第 12 章 gcc 用四行做的事5。

还有个小优化值得懂:32 位操作会把寄存器高 32 位清零,所以 ecx 当索引进 SIB 时, 高 32 位天然是 0,不需要 cdqe——编译器用 cdqe 是因为 i 是有符号 int, 防御性扩展;你若能保证索引非负,就能省下这一步5。

displayArray(清单 17-10)同款骨架,只是元素要打印:输入输出改用它第 16 章练习 编写的 putInt,循环里同样 mov edi, [r12+rbx*4] 取元素6。注意序言里 push rbx; push r12 又回来了——这次要跨函数调用保住循环变量,轮到 「被调方保存」寄存器登场(第 11 章表 11-2 的伏笔第二次兑现)。

2. 记录:字段名是「查表得到的偏移量」

C 层:struct、标签与箭头运算符

记录(record,也叫结构 struct)是把类型可不同的字段打包成一个程序员自定义类型。 字段在不同语境下也叫成员(member)——第 18 章 C++ 对象的属性就是它7。

两个语法台阶8:

  • 结构标签:struct aTag { … }; 把这个字段组合注册成一个类型名, 之后 struct aTag x, y; 可以定义任意多个;
  • 箭头运算符:(*aRecord).anInt 太啰嗦,C 提供等价简写 aRecord->anInt—— 先解引用再取字段,一步完成。

主线例子:一个 12 字节记录的内存解剖

清单 17-11 的记录:char aChar; int anInt; char anotherChar;。 直觉上 1+4+1 = 6 字节,但图 17-1 揭示了真相9:

  相对记录头    内容
  0            aChar('a' = 0x61)
  1..3         【填充:3 字节浪费】
  4..7         anInt(123,int 必须 4 字节对齐)
  8            anotherChar('b')
  9..11        【填充:3 字节浪费】
  ─────────
  合计 12 字节,其中 6 字节是填充!

对齐规则:这个环境的 int 必须在 4 的倍数的地址上。 char 后面紧跟的 int 会被推到下一个 4 的倍数,中间的空档就是填充(padding)——编译器自动塞的, 不可见,但占空间、占带宽、还影响二进制协议(网络传结构体必踩)9。 这也回答了第 11 章「1 字节变量为何住 16 字节公寓」的亲戚问题:对齐是 贯穿本书的隐性税。

汇编访问(清单 17-12/17-19)就是「记录首地址 + 字段偏移量」:x.anChar = -12[rbp]、x.anInt = -8[rbp]、x.anotherChar = -4[rbp]—— 字段名在机器层就是编译器查表得来的常量9。

传记录:按值的代价,按指针的清爽

清单 17-15 的 main 刻意演示两种传法10:

  • loadRecord(&x, …):要改记录,传地址(第 14 章的输出型参数);
  • displayRecord(x):不改,按值——编译器把 12 字节(含那 6 字节填充!) 从寄存器搬进被调方的栈帧,被调方在自己的副本上工作。

按值的汇编(清单 17-16/17-22)很能说明问题:12 字节的记录塞不进 6 个参数寄存器, gcc 把它拆成「8 字节进 rdx + 4 字节进 esi」两份搬运;被调方收到后在栈上重建 整个记录,再从重建的副本里取字段11。按值传一个输入,纯粹是复制税—— 哪怕只读,传指针也更划算,这是书中练习和 17.2.4 节手写版的共同结论。

汇编版对接 C:offsetof 与 .include

手写汇编函数要和 C 的 struct 对接,字段偏移量必须一致。两个工具12:

  • C 侧 offsetof(struct aTag, anInt)(stddef.h):问编译器「这个字段你放哪了」, 布局以编译器为准;
  • 汇编侧 .include "aRecord":把存着 .equ aChar,0 / .equ anInt,4 / … 的文本文件原样抄进来——相当于 C 的 #include,保证所有汇编文件用同一套偏移量。

然后访问字段就只剩两种写法:叶函数里地址还没被 call 破坏,直接用 mov anInt[rdi], edx;要 call 别人就得先把记录地址存进栈帧 (mov recordPtr[rbp], rdi),再 mov edi, anInt[rax]—— 第 14 章规则 9 的又一个实战场景13。

判断(我们的,不是书里的): 本章最该带走的一句话:「数据结构在机器层只有一种 语法——基址加偏移」。数组的索引、结构体的字段名、乃至对象的方法表, 全都是这个语法的糖衣。回头看:第 12 章的 SIB 是语法本体,第 14 章的栈帧是 数据的家,本章只是两者相乘。如果错,会错在: 现代语言运行时的数据结构 还有隐藏层(对象头、GC 元数据、 boxing),不是裸的基址+偏移——但那是在 本章地基之上加盖的第二层。

判断(我们的,不是书里的): 「传数组永远传指针」是 C 的隐形语法设计, 本书的处理方式值得称道:不把它当语言冷知识,而是从汇编证据反推设计动机 (复制低效 → 语言定死传指针)。学语言机制的正确顺序,永远是「先看机器层 发生了什么,再回头理解语法为什么这么写」。 如果错,会错在: 也有从语言理论(类型系统、值语义)出发讲得同样好的路径; 但对这本书的读者(要读懂机器的人),机器层优先是更顺的次序。

3. 作者的判断与证据

说法 性质
C 数组按指针传递,长度另传 语言事实,由汇编实证12
int 需 4 字节对齐,记录内有填充 本环境 ABI 事实,图中可见 6 字节浪费9
按值传记录=整块复制(含填充) 由清单 17-16/17-22 实证11
按指针传记录更高效,即便只读 作者的工程结论,与复制税的观察一致10
「字段偏移量因编译器而异」 语言标准事实,书中以 offsetof 应对12
索引全程非负可省 cdqe 机制推论(32 位写清零高 32 位),编译器实践可验5

4. 边界与局限

  • 只讲了「记录内含 int + char」的简单对齐。 多字节序、位域(bit field)、 #pragma pack 改变布局等都没出现;跨编译器/跨平台的结构体 ABI 是另一个大坑。
  • 数组不查越界。 C 的数组没有任何运行时边界检查,a[i] 越界就是访问 不该访问的内存——栈金丝雀防的是覆盖,不防读越界。
  • 没有动态数组(堆分配)。 malloc/free 的堆分配本书未展开(第 10 章提过堆段), 数组都是栈上的定长数组。
  • displayRecord 按值传参是教学演示,真实工程几乎总是传指针—— 书中也明说「程序员的惯常做法是按指针传递记录」10。

5. 可带走的

  1. 数组访问 = 基址 + 索引 × 元素大小;SIB 比例字段(1/2/4/8)为此而生;
  2. C 传数组永远传首元素地址;int a[] ≡ int *a;长度永远另传;
  3. cdqe/cbw/cwde:rax 系内部符号扩展三兄弟;索引非负可省;
  4. 结构体字段 = 记录头 + 固定偏移量;字段名是编译器查表来的常量;
  5. 对齐产生填充:char+int+char 实际占 12 字节,6 字节是税;
  6. int 要 4 字节对齐——跨网络/跨语言传结构体前,先想清楚布局;
  7. 按值传记录 = 整块复制(含填充)进被调方栈帧,哪怕只读也付复制税;
  8. C 结构标签 = 注册一个自定义类型;-> 是 (*p). 的简写;
  9. 汇编对接 C 结构体:offsetof 问 C、.include 统一汇编侧偏移量;
  10. 跨 call 保住数据指针:存栈帧;叶函数:直接用寄存器。

6. 原文地图

主题 原书章 原文位置
数组定义与按指针传递 第17 章 数据结构 text/23-ch17.txt:17(搜「顺序排列」) · text/23-ch17.txt:64(搜「第一个元素的地址」)
main 传数组地址的汇编 第17 章 数据结构 text/23-ch17.txt:68(搜「清单 17-2」)
twiceIndex 与 SIB 寻址 第17 章 数据结构 text/23-ch17.txt:120(搜「清单 17-4」) · text/23-ch17.txt:141(搜「清单 17-5」)
cdqe 指令卡 第17 章 数据结构 text/23-ch17.txt:184(搜「字节转字」)
手写 twiceIndex 的 [rdi+rcx*4] 第17 章 数据结构 text/23-ch17.txt:283(搜「清单 17-9」) · text/23-ch17.txt:303(搜「rcx*4」)
displayArray 与 putInt 第17 章 数据结构 text/23-ch17.txt:317(搜「清单 17-10」) · text/23-ch17.txt:358(搜「putInt」)
struct 声明与点号访问 第17 章 数据结构 text/23-ch17.txt:400(搜「清单 17-11」) · text/23-ch17.txt:416(搜「x.aChar」)
记录的栈帧布局与填充 第17 章 数据结构 text/23-ch17.txt:433(搜「清单 17-12」) · text/23-ch17.txt:472(搜「浪费了 6 字节」)
汇编版字段偏移量 第17 章 数据结构 text/23-ch17.txt:481(搜「清单 17-13」) · text/23-ch17.txt:489(搜「aChar,0」)
结构标签与 -> 运算符 第17 章 数据结构 text/23-ch17.txt:1(搜「284 数据结构」) · text/23-ch17.txt:689(搜「->anInt」)
按值传记录与栈上重建 第17 章 数据结构 text/23-ch17.txt:636(搜「8 bytes of x」) · text/23-ch17.txt:767(搜「清单 17-22」) · text/23-ch17.txt:765(搜「重建记录」)
offsetof 与 .include 第17 章 数据结构 text/23-ch17.txt:887(搜「offsetof」) · text/23-ch17.txt:909(搜「.include」)
手写 loadRecord / displayRecord 第17 章 数据结构 text/23-ch17.txt:899(搜「清单 17-25」) · text/23-ch17.txt:931(搜「清单 17-26」)

  1. 出处:「第17 章 数据结构」第 27–70 段(text/23-ch17.txt:58,搜「按值传递的」;text/23-ch17.txt:64,搜「第一个元素的地址」;text/23-ch17.txt:117,搜「等价于」)。 ↩↩

  2. 出处:「第17 章 数据结构」第 68–103 段(text/23-ch17.txt:81,搜「load address of array」;text/23-ch17.txt:101,搜「首先传递给 twiceIndex」)。 ↩↩

  3. 出处:「第17 章 数据结构」第 120–194 段(twiceIndex 汇编,text/23-ch17.txt:156,搜「cdqe」;text/23-ch17.txt:157,搜「rax*4」;text/23-ch17.txt:384,搜「寄存器间接索引寻址模式」)。 ↩

  4. 出处:「第17 章 数据结构」第 184–191 段(text/23-ch17.txt:184,搜「字节转字」;text/23-ch17.txt:191,搜「不影响 rflags」)。 ↩

  5. 出处:「第17 章 数据结构」第 283–314 段(手写 twiceIndex,text/23-ch17.txt:302,搜「shl eax, 1」;text/23-ch17.txt:303,搜「[rdi+rcx*4]」;高 32 位清零见第 312–314 段,text/23-ch17.txt:313,搜「高 32 位清零」)。 ↩↩↩

  6. 出处:「第17 章 数据结构」第 317–377 段(displayArray,text/23-ch17.txt:358,搜「putInt」;text/23-ch17.txt:361,搜「[r12+rbx*4]」)。 ↩

  7. 出处:「第17 章 数据结构」第 388–394 段(text/23-ch17.txt:9,搜「的数据组织方式：数组和记」;text/23-ch17.txt:390,搜「成员」)。 ↩

  8. 出处:「第17 章 数据结构」第 531–578 段(text/23-ch17.txt:1,搜「284 数据结构」;text/23-ch17.txt:569,搜「aTag」)。 ↩

  9. 出处:「第17 章 数据结构」第 400–473 段(记录布局,text/23-ch17.txt:447,搜「-12[rbp]」;对齐与浪费见第 471–473 段,text/23-ch17.txt:472,搜「浪费了 6 字节」)。 ↩↩↩↩

  10. 出处:「第17 章 数据结构」第 581–640 段(text/23-ch17.txt:596,搜「&x」;text/23-ch17.txt:58,搜「按值传递」;text/23-ch17.txt:607,搜「据，所以我们可以按值传递」)。 ↩↩↩

  11. 出处:「第17 章 数据结构」第 611–803 段(按值传递的汇编,text/23-ch17.txt:636,搜「8 bytes of x」;栈上重建见第 780–803 段,text/23-ch17.txt:780,搜「sub rsp, 16」;text/23-ch17.txt:765,搜「重建」)。 ↩↩

  12. 出处:「第17 章 数据结构」第 885–895 段(text/23-ch17.txt:887,搜「offsetof」;text/23-ch17.txt:894,搜「手册页」)与第 925–927 段(text/23-ch17.txt:925,搜「.include」)。 ↩↩

  13. 出处:「第17 章 数据结构」第 899–986 段(手写版,text/23-ch17.txt:918,搜「aChar[rdi]」;存栈帧见第 984 段,text/23-ch17.txt:984,搜「保存在栈帧中」)。 ↩