這一篇是整個效能的關鍵取捨點，筆者接著會把 Day 18 的震撼與 Day 19 的兩個關鍵修復接起來，補上最後一塊：把原本「看似已經很省」的淺層轉換從 O(n) 降到 O(1)

問題重述：原本的「淺層」仍是 O(n)

在 Ruby bridge 的 VALUE↔C value 轉換策略中，筆者先選擇「淺層深轉換」：

• 做法：只展開第一層 Hash / Array，把 key（字串或整數）映到一個 mongory_value，其 origin 指向外部 Ruby VALUE
• 目的：避免一次把整棵資料樹 deep-convert，降低記憶體壓力與時間成本

可惜在轉換過程中，仍會為了日後方便取值而「逐項走訪第一層」，並把 key 轉 char，資料轉 mongory_value(pointer)
資料越複雜，要走的第一層元素越多，整體仍是 O(n)
這在 Day 18 的 Benchmark 中清楚反映：即使有 pool reset 與 key-cache，仍被這條 O(n) 路徑卡住

目標：真正做到 O(1) 取值

把「取值」做成 O(1) 的唯一方式，就是讓 C Core 在需要存取元素時，能直接用 key 透過 Ruby VM/C API 做一次查找，而不是把第一層攤平後逐項掃過

直白說：

• 讓 mongory_array / mongory_table 的存取行為，能「代理」到 Ruby 的 C API 上
• 在 C Core 看來，是在用原生容器，實際上 get 會透過 function pointer 呼叫到 Ruby 端做單點查找

設計：Ruby 特製容器 × Core 可插拔取值

筆者做的，是準備一個「看起來像 Mongory 原生」的容器結構，但內含 Ruby 的 VALUE，並把存取函式指到 Ruby 的 C 函式（現況已在 mongory_ext.c 中以 rb_mongory_table_t、rb_mongory_array_t 落地）

為了敘述清楚，以下以「示意」寫法呈現結構。這不是 mongory-core 的公開 API，而是文章用來解釋設計要點（實作依各版本微調）

// 現況：Ruby 版 Array/Hash 容器包裝（已存在於 mongory_ext.c）
typedef struct rb_mongory_array_t {
  mongory_array base;
  VALUE rb_array;
  struct rb_mongory_matcher_t *owner; // 供快取與 GC 標記使用
} rb_mongory_array_t;

typedef struct rb_mongory_table_t {
  mongory_table base;
  VALUE rb_hash;
  struct rb_mongory_matcher_t *owner; // 供快取與 GC 標記使用
} rb_mongory_table_t;

static mongory_value *rb_mongory_array_get(mongory_array *self, size_t index) {
  rb_mongory_array_t *array = (rb_mongory_array_t *)self;
  if (index >= (size_t)RARRAY_LEN(array->rb_array)) return NULL;
  VALUE rb_value = rb_ary_entry(array->rb_array, index);
  return rb_to_mongory_value_shallow(self->pool, rb_value); // 保持 shallow
}

static mongory_value *rb_mongory_table_get(mongory_table *self, char *key) {
  rb_mongory_table_t *table = (rb_mongory_table_t *)self;
  VALUE key_str = cache_fetch_string(table->owner, key);
  VALUE rb_value = rb_hash_lookup2(table->rb_hash, key_str, Qundef);
  if (rb_value == Qundef) {
    VALUE key_sym = cache_fetch_symbol(table->owner, key);
    rb_value = rb_hash_lookup2(table->rb_hash, key_sym, Qundef);
  }
  if (rb_value == Qundef) return NULL;
  return rb_to_mongory_value_shallow(self->pool, rb_value);
}

// Wrap 為 mongory_value（供 shallow 模式使用）
mongory_value *rb_mongory_table_wrap(mongory_memory_pool *pool, VALUE rb_hash) {
  rb_mongory_table_t *table = MG_ALLOC_PTR(pool, rb_mongory_table_t);
  table->base.pool = pool;
  table->base.get = rb_mongory_table_get;
  table->rb_hash = rb_hash;
  table->base.count = RHASH_SIZE(rb_hash);
  // owner 由 pool->owner 指回 wrapper（見 mongory_ext.c 實作）
  mongory_value *mg_value = mongory_value_wrap_t(pool, &table->base);
  mg_value->origin = (void *)rb_hash;
  mg_value->to_str = rb_mongory_value_to_cstr; // 以 Ruby 側 inspect 提供觀測字串
  return mg_value;
}

Ruby 端查找（現況 API）：

// 在 ruby_table_get 內部：以 Ruby C API 做單點查找
// 直接以 rb_hash_lookup2 查找（字串 miss 再試符號）
static inline VALUE rb_lookup_hash_value(VALUE hash, VALUE key_str, VALUE key_sym) {
  VALUE v = rb_hash_lookup2(hash, key_str, Qundef);
  if (v == Qundef) v = rb_hash_lookup2(hash, key_sym, Qundef);
  return v;
}

同理，Array 取值可用 rb_ary_entry(rb_array, index) 直接 O(1) 存取，Hash 取值用 rb_hash_lookup2(rb_hash, key, Qnil) 單點查找。整體上，Matcher 的「取值」操作就不再走「第一層掃描」，而是每次直接查一次，達成 O(1)

與 shallow 包裝的關係：零拷貝仍成立

這個設計沒有破壞 shallow 的精神：

• 仍然不複製實際資料，mongory_value.origin 指向外部 VALUE
• 當 Matcher 需要子值，才透過 function pointer 呼叫 Ruby 端取值，並以 shallow 的方式包裝回來
• 配合 Day 19 的 key cache，Ruby 查找鍵也能重複利用，減少 ID / Symbol 轉換成本

效能觀察：先追平，再於複雜條件中超車

把「第一層 O(n) 掃描」替換成「單點 O(1) 查找」後：

• 在簡單條件與小資料上，速度與純 Ruby 幾乎持平（因為仍會呼叫 Ruby C API）
• 在條件漸複雜、可觸發 priority 與 early-exit 的情境下，Mongory 的整體流程反而更有效率，逐漸拉開差距
• 與 Day 18 的 Base-line 相比，整體查詢耗時下降最明顯的，就是曾經受第一層掃描拖累的情況

以「示意」數字說明趨勢（非最終數字）：

條件：{ a: { $gte: 10 }, b: { $in: [1,2,3,4,5] }, c: { $exists: true } }
資料：10 萬筆 Hash，欄位分布均勻

純 Ruby：   1.0x（基準）
原 O(n)：    0.6x（因第一層掃描）
Shallow O(1)：~1.0x（追平）
複雜條件優化後：1.1x–1.3x（視資料與條件而定）

正確性與安全性：四個必修點

1. GC 與壽命管理：

• origin 指到外部 Ruby VALUE，必須確保該 VALUE 在 C Core 使用期間不被 GC 回收
• mark_list 由 Ruby 側 wrapper 維護，在 mark 階段逐一 rb_gc_mark

2. 例外處理：

• 建議以 rb_protect 或等效防護處理 Ruby C API 呼叫，避免例外穿越 C 邊界
• 例外應轉譯為 Mongory 的 error 格式，保證跨語言一致的錯誤語意

3. 執行緒與 GVL：

• Ruby MRI 需要在持有 GVL 下呼叫 Ruby C API，若查詢在非 Ruby 執行緒執行，必須先切回 GVL

4. 可觀測性：

• trace 需能描述「呼叫外部查找（Ruby）」的步驟，方便問題定位
• explain 中可標記容器為「外部驅動」，協助性能判讀

小結：目標達成

筆者想要的並不是一味「全部搬到 C」，而是讓 Mongory 在「該用高階語言的地方」就用它的強項，並以最薄的邊界把它接進來。Shallow wrap 的 O(1) 取值，就是這種務實的工程取捨：

• 不複製資料，保持零拷貝與記憶體友好
• 把攤平掃描換成單點查找，繞過 O(n) 的瓶頸
• 在複雜條件上，憑藉優化策略（priority、unwrap、early-exit）逐步跑贏純 Ruby

筆者很享受把這些邏輯拼在一起的過程，那種「終於跑起來了」的踏實。值得！

下一篇預告

Day 21：跨平台預編譯與 CI ， 把 mongory-core 與 mongory-rb 的建置產物，變成可在 macOS/Linux 上穩定交付的流程，談 toolchain、靜態/動態連結、與 GitHub Actions 的工序安排

專案首頁（Ruby 版）