Is BFS actually faster than DFS?BFS 真的比 DFS 快嗎?

What the walk actually does這個走訪實際在做什麼

Every dirty node may trigger a group walk (AddNodeToGroup): follow the pass-transistors that are currently on to collect the connected conducting group, OR all members' flags together, and resolve the group's 0/1 from the complete set (a 256-entry LUT, or the largest-capacitance member for a floating group). Two facts decide everything here:

每個 dirty 節點都可能觸發一次群組走訪(AddNodeToGroup):沿著當下導通的 pass-transistor 收集相連的導通群組,把所有成員的 flags 一起 OR 起來,再從完整集合解析出群組的 0/1(一張 256-entry LUT,或浮接時取電容最大的成員)。這裡有兩個決定一切的事實:

• The group is a SET. Flags are OR'd; the resolve reads the whole set. So the order you discover members in is irrelevant — BFS and DFS produce a bit-identical result.
• 群組是一個集合。flags 是 OR、解析讀整個集合。所以你以什麼順序發現成員完全無關 —— BFS 與 DFS 產生位元完全相同的結果。
• The group is tiny — ~1.4 nodes on average. There is barely any frontier. At that size the dominant cost is the random memory latency of touching each node's data, not the traversal bookkeeping.
• 群組很小 —— 平均 ~1.4 個節點。幾乎沒有 frontier。在這個尺寸下,主成本是「碰每個節點資料」的隨機記憶體延遲,不是走訪的簿記。

Why BFS's queue is free (and DFS's isn't)為什麼 BFS 的佇列免費(DFS 不是)

The result we need afterward is the full member list (to write every node and to resolve the group). The BFS implementation gets its work-queue for nothing by reusing that very list:

我們事後需要的結果是完整成員清單(用來寫每個節點、解析群組)。BFS 的實作直接「重用這份清單」當佇列,等於佇列不用錢:

// BFS — one array is BOTH the result list AND the queue
groupBuf[gc++] = seed;            // append a member (we must do this anyway)
int readIndex = 0;
while (readIndex < gc) {          // unexpanded = the contiguous suffix [readIndex, gc)
    int nn = groupBuf[readIndex++];   // read cursor — costs nothing extra
    // ...expand nn, append new members at gc...
}

The trick is the invariant "unexpanded = a contiguous suffix [readIndex, gc)": because BFS expands in discovery order (FIFO), a single advancing cursor is the entire queue. The append (gc++) is something we do anyway for the result list, so the queue costs zero extra memory and zero extra writes.

關鍵是那個不變式 「未展開 = 連續後綴 [readIndex, gc)」:因為 BFS 以發現順序(FIFO)展開,一個往前推的游標就是整個佇列。而 append(gc++)本來就要為了結果清單做,所以佇列多花了零記憶體、零額外寫入。

DFS (LIFO) breaks that invariant: it must expand the most-recently-discovered node first, so the unexpanded set is no longer a contiguous suffix you can track with one cursor. DFS therefore needs a separate explicit stack — the member list stays append-only, plus a stack you push every discovered node onto and pop every expansion from:

DFS(LIFO)打破這個不變式:它得先展開最近發現的節點,於是「未展開」不再是能用單一游標追蹤的連續後綴。因此 DFS 必須另開一個獨立的顯式 stack —— 成員清單照樣 append-only,外加一個 stack:每發現一個節點 push 一次、每展開 pop 一次:

// DFS — needs a SEPARATE stack on top of the member list
groupBuf[gc++] = seed;  stack[sp++] = seed;   // member list AND a stack
while (sp > 0) {
    int nn = stack[--sp];                     // LIFO pop = depth-first
    // ...expand nn; for each new member: groupBuf[gc++]=o;  stack[sp++]=o;  // extra push
}

That extra stack[sp++] per discovered node + stack[--sp] per expansion is a whole second random-access stream on a memory-latency-bound loop — pure overhead, since the order it buys is worthless for an order-independent set.

每發現一個節點多一次 stack[sp++]、每展開多一次 stack[--sp],在 memory-latency-bound 的迴圈上等於多一條隨機存取 stream —— 純開銷,因為它換來的「順序」對一個順序無關的集合毫無價值。

The measurement量測

Interleaved-paired A/B (alternating builds, checksum-guarded every round), full_palette 300k half-cycles, AMD Ryzen 7 3700X. The only change is BFS → DFS in the group walk.

interleaved-paired A/B(輪流換 build、每輪 checksum 守門),full_palette 30 萬半週期,AMD Ryzen 7 3700X。唯一的改動就是群組走訪 BFS → DFS。

DFS lost on 17 of 20 paired rounds (−2.28% median, −2.23% trimmed mean). The checksum stayed bit-identical in every DFS run — the clean experimental proof that the group really is order-independent, so this was a pure performance comparison, not a correctness one.

DFS 在 20 輪中輸了 17 輪(median −2.28%、trimmed mean −2.23%)。每一次 DFS run 的 checksum 都位元完全相同 —— 這是「群組確實順序無關」的乾淨實驗證明,所以這是純效能比較,不是正確性比較。

The lesson教訓

It also reinforces the engine's recurring theme: this is a memory-latency-bound simulator, so wins and losses are decided by how many random memory streams a hot loop touches, not by asymptotic cleverness. The same theme killed the P-5 dominant-driver bypass (a second maintained array) and bounds the prunes at the frontier.

它也呼應引擎反覆出現的主題:這是一台 memory-latency-bound 的模擬器,所以勝負取決於熱迴圈碰了幾條隨機記憶體 stream,而不是漸進複雜度上的小聰明。同一個主題終結了 P-5 dominant-driver 旁路(多一條維護的 array),也在前緣界定了剪枝的上限。

Where the numbers come from數字的出處

The DFS variant is a true iterative depth-first traversal (separate LIFO stack, member list kept append-only), built only for this experiment and then reverted — the engine stays on BFS. Numbers are interleaved-paired, median of 20 rounds, checksum-guarded each round, on an AMD Ryzen 7 3700X (full_palette 300k --extra-ram). Companion pages: the event-count prunes (P-1 → P-4), the frontier, a correct optimization that still lost (P-5).

DFS 變體是真正的迭代深度優先(獨立 LIFO stack、成員清單維持 append-only),只為這次實驗而建、之後已退回 —— 引擎維持 BFS。數字為 interleaved-paired、20 輪取中位數、每輪 checksum 守門,在 AMD Ryzen 7 3700X 上(full_palette 30 萬 --extra-ram)。延伸頁面:事件數剪枝(P-1 → P-4)、前緣、一個正確卻仍然輸的優化(P-5)。