問題#

動態語言的 stack 上可能放任何東西：

arr = [1, 3.14, "hello", :sym, true, nil, MyClass.new]

VM 內部怎麼用一個 C 型別表示這些？這是動態語言實作最基礎的設計決策，影響：

  • 每個 value 的記憶體大小（直接乘以 stack 深度、object 欄位數）
  • 運算速度（型別判斷的成本）
  • GC 必須能識別「這是不是指標」

方案 1：tagged union（最直觀）#

typedef enum { VAL_NIL, VAL_BOOL, VAL_INT, VAL_DOUBLE, VAL_OBJ } ValueType;

typedef struct {
    ValueType type;
    union {
        bool    boolean;
        int64_t integer;
        double  number;
        Object *obj;
    } as;
} Value;

特點：

  • 結構大小：64-bit 平台上 16 bytes（type tag 4 bytes + padding 4 + union 8）
  • 型別檢查直接 value.type == VAL_INT
  • 直觀、跨平台
#define INT_VAL(i)    ((Value){.type = VAL_INT,    .as.integer = (i)})
#define BOOL_VAL(b)   ((Value){.type = VAL_BOOL,   .as.boolean = (b)})
#define OBJ_VAL(p)    ((Value){.type = VAL_OBJ,    .as.obj = (p)})
#define IS_INT(v)     ((v).type == VAL_INT)
#define AS_INT(v)     ((v).as.integer)

代表：早期 Lua、Crafting Interpreters 第一階段、許多教學 VM。

缺點：

  • 空間翻倍：每個值要 16 bytes（payload 只 8 bytes）。對 stack 深的程式吃記憶體
  • 每次取值要走兩級 indirection（讀 type、讀 union）

方案 2：tagged pointer#

利用「指標一定對齊到 8 / 16 byte」── 指標的低幾位永遠是 0。把這幾個 bit 用來放 tag：

typedef uintptr_t Value;       // 64-bit 機器是 8 byte

#define TAG_BITS    3            // 低 3 bits
#define TAG_MASK    0x7

#define TAG_OBJ     0
#define TAG_INT     1
#define TAG_BOOL    2
#define TAG_NIL     3

#define IS_INT(v)   (((v) & TAG_MASK) == TAG_INT)
#define AS_INT(v)   ((int64_t)(v) >> TAG_BITS)         // 算術右移帶符號
#define INT_VAL(i)  ((Value)((i) << TAG_BITS) | TAG_INT)

#define IS_OBJ(v)   (((v) & TAG_MASK) == TAG_OBJ)
#define AS_OBJ(v)   ((Object*)(v))                      // 低 3 bits 已經是 0
#define OBJ_VAL(p)  ((Value)(p))

特點：

  • 結構大小：8 bytes
  • INT 失去 3 bits（變 61-bit signed integer）
  • 每次存取 INT 要 shift（一條 cycle）

代表：CRuby（YARV）、JavaScriptCore（部分）、CLR、Dalvik。

CRuby 的 VALUE：

低 1 bit = 1   →  Fixnum（左移 1 位）
低 2 bit = 10  →  Flonum（特殊壓縮 double）
0 / 2 / 4 / 6  →  指標（依 alignment 不同）
specific 常數  →  Qfalse=0、Qtrue=20、Qnil=8（神奇魔法數）

對 small int、特殊常數（true/false/nil）零分配，效能極好。

方案 3：NaN-boxing（最巧妙）#

利用 IEEE 754 雙精度浮點的特性：NaN 有 2^52 種表示，正常數值用不到那麼多。把不是 NaN 的 64-bit 視為 double，把 NaN 的 payload 拿來放型別 tag + 指標 / 整數。

IEEE 754 雙精度結構#

| sign(1) | exponent(11) | mantissa(52) |

NaN：exponent 全 1、mantissa 不全 0。

0xFFF0_0000_0000_0000  ← -infinity
0x7FF0_0000_0000_0000  ← +infinity
0xFFF8_0000_0000_0001 ~ 0xFFFF_FFFF_FFFF_FFFF  ← Quiet NaN（含 51-bit payload）

我們把這 51 bits 拿來：

0xFFF8_0000_0000_0000   QNaN bits（固定）
0xXXXX_YYYY_YYYY_YYYY   高 16 bits 是 type tag、低 48 bits 是 payload

48 bits 剛好能放下一個 user-space 指標（多數 64-bit OS 只用 48-bit 虛擬位址）。

#define QNAN     0x7FFC000000000000ULL
#define SIGN_BIT 0x8000000000000000ULL

#define TAG_NIL   1
#define TAG_FALSE 2
#define TAG_TRUE  3

typedef uint64_t Value;

#define IS_NUMBER(v)  (((v) & QNAN) != QNAN)         // 不是 NaN，是 double
#define AS_NUMBER(v)  (*(double*)&(v))
#define NUMBER_VAL(d) (*(uint64_t*)&(d))

#define NIL_VAL    ((Value)(QNAN | TAG_NIL))
#define FALSE_VAL  ((Value)(QNAN | TAG_FALSE))
#define TRUE_VAL   ((Value)(QNAN | TAG_TRUE))

#define IS_OBJ(v)   (((v) & (QNAN | SIGN_BIT)) == (QNAN | SIGN_BIT))
#define AS_OBJ(v)   ((Object*)((v) & ~(QNAN | SIGN_BIT)))
#define OBJ_VAL(p)  ((Value)(QNAN | SIGN_BIT | (uint64_t)(uintptr_t)(p)))

優點：

  • 結構 8 bytes
  • double 是原生表示，零開銷取值
  • 指標是 48-bit 直接拿，零開銷
  • 整數可內嵌在 NaN payload，零分配

缺點：

  • 編碼複雜
  • 在某些 ARM 平台上 48-bit 假設不總成立
  • Debug 較痛苦（看不出記憶體 dump 是什麼）

代表：SpiderMonkey（Firefox）、LuaJIT、JavaScriptCore（部分）、Wren、mruby/c。Crafting Interpreters 第二階段優化用這個。

方案 4：boxed everything#

最簡單但最慢：每個值都是堆上物件：

struct Value {
    Type type;
    union { ... };
};

Value *make_int(int i);   // malloc 一個

代表：早期 Smalltalk、教學語言。優勢只有「同質」── 任何地方都是 Value*。GC 壓力極大、cache locality 極差。沒人會這樣設計生產級 VM。

整數的特例：small int 內嵌#

對動態語言，整數使用率極高（迴圈 counter、index）。如果把每個 int 都堆配置 ➡️ 效能災難。所以幾乎所有現代 VM 都把小整數內嵌在 value 裡：

VM整數表示
CRuby Fixnumtagged：63-bit signed
CPython int物件，但 -5..256 是預先配置的 immortal
V8 Smitagged：31-bit signed（32-bit V8）/ 32-bit (64-bit V8)
JSCNaN-boxing 中的 int32
Lua 5.3+tagged union 中的 int64

bignum（任意大小）超過 small int 範圍時 promote 到堆物件。Ruby 的 Bignum、Python 的任意大整數都是這樣處理。

浮點數：double 的特殊地位#

NaN-boxing 把 double 放第一公民。tagged pointer / tagged union 體系下，double 通常 boxed：

struct Float {
    Object obj;
    double value;
};

為了避免這個分配，CRuby 引入 flonum ── 把 double 的 mantissa 截短，塞進 tagged value。代價是少幾 bit 精度，益處是大量浮點運算不分配。

V8 有 “double field unboxing”：物件如果欄位永遠是 double，存原生 double 而非 boxed。

tag 配置例子#

64-bit value 拿出 3-bit tag 的常見方案：

000  obj pointer
001  fixnum (61-bit signed)
010  symbol
011  immediate constants (true/false/nil/undefined ...)
100  small string (7-byte ASCII inline)
101  ...
110  ...
111  ...

看起來簡單，實際 trade-off 一堆：

  • 整數要不要符號擴展（讀的時候 shift）？
  • nil 要不要單獨 tag（vs immediate）？
  • 字串要不要嘗試 inline（4~7 byte 短字串可塞進 tag）？

每個 trade-off 對應一個 benchmark 上幾個百分點。

value 與 GC 的互動#

GC 必須回答：「這個 64-bit 是不是指標？」── 各方案的處理：

方案GC 怎麼判斷
Tagged union看 type 欄位
Tagged pointer檢查 tag bits
NaN-boxing檢查是否是 NaN + sign bit
Conservative把任何看起來像對齊指標的 64-bit 當作可能指標

最後一個叫 conservative GC（如 Boehm GC）── 不需要 VM 配合，就能掃 C stack。代價是會錯把整數當指標 ➡️ 多保留一些其實死的物件。

GC 也決定哪些 value 變動需要 write barrier：

  • 指標寫入老物件 ➡️ 需要 barrier 通知 generational GC
  • 純整數更新 ➡️ 不需要

效能影響量級#

對動態語言密集計算（數字 + 物件混合）：

方案相對速度記憶體（每 value）
Boxed all1.0x16~24 bytes
Tagged union2~3x16 bytes
Tagged pointer3~4x8 bytes
NaN-boxing3~5x8 bytes

加上 GC 壓力的差異，實際差距可能更大。

該選哪個#

決策樹：

是否優先寫起來簡單?
  ├ 是 → tagged union（教學 VM、原型、嵌入式）
  └ 否 → 主要型別是浮點?
         ├ 是 → NaN-boxing
         └ 否 → tagged pointer（指標 + 整數為主）

實務上：

  • 學寫 VM、玩具語言 ➡️ tagged union（之後再升級）
  • 想榨效能、有時間調 ➡️ NaN-boxing
  • 嵌入式、嚴格控制記憶體 ➡️ tagged pointer 或 NaN-boxing
  • 教學 / 除錯 ➡️ tagged union

小結#

  • value 表示是動態語言 VM 最基礎的決策，影響整個系統
  • 四種主流：boxed / tagged union / tagged pointer / NaN-boxing
  • 選擇依：簡單度、效能要求、記憶體預算、目標型別分布
  • GC、frame 大小、stack 深度都會反過來受 value 表示影響

下一章看 opcode 怎麼用這些 value 做算術與分支。

Backward OPCode 派發 算術與控制流 Forward