Making Circuit Partitioning Fast

---

# ✂️ Making Circuit Partitioning Fast

## A 1.9× Python win, a 2× C++ kernel, and a 28% Rust cut

### 🐍 → ⚙️ → 🦀

@luk036 👨‍💻 · 2026 📅

---

### 📋 Agenda

**Part 1 — The Setup** 🧭
- What FM partitioning does
- The inner move loop
- How we measure 📏

**Part 2 — Python: Profile First** 🐍
- The #1 find: no-op calls 🔍
- Killing wrapper layers
- Caching adjacency

]

**Part 3 — C++: Kill Allocations** ⚙️
- The per-call `std::vector` tax
- Reusable buffers + `span`
- 2× on the k-way kernel

**Part 4 — Rust: The Same Lesson** 🦀
- The `.clone()` / `.collect()` tax
- Borrow-friendly buffers
- 28% across the board

**Part 5 — Takeaways** 🎓

]

---

## 🧭 Part 1 — The Setup

---

### 🎛️ What Is FM Partitioning?

Given a hypergraph $H=(V,E)$ and $k$ parts, minimize the **weighted cut**:

$$ \min \sum_{e \in E} {\color{#bf616a} w(e)}\,\bigl[\,e \text{ spans} > 1 \text{ part}\,\bigr] $$

<pre>
graph LR
    HG["Hypergraph\nmodules + nets"]
    INIT["Initial partition"]
    FM["FM refinement\nmove vertices"]
    OUT["Optimized partition"]
    HG --> INIT
    INIT --> FM
    FM --> OUT
    style HG fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
    style INIT fill:#fff9c4,stroke:#f57f17,stroke-width:3px
    style FM fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style OUT fill:#d1c4e9,stroke:#6a1b9a,stroke-width:3px
</pre>

]

> Fiduccia–Mattheyses: greedily move the **highest-gain** vertex, then lock it. 🔁

---

### 🔁 The Inner Move Loop

Each move touches every net incident to $v$, and every pin of that net:

$$ \text{cost per move} \;=\; \sum_{e \ni v} {\color{#5e81ac} \deg(e)} $$

```python
for net in vertex_nets[v]:            # nets of v
    for w in net_pins[net]:           # pins of net
        modify_key(w, part[w], delta) # update gain bucket
```

<pre>
graph LR
    V["move v"] --> N1["net e1"]
    V --> N2["net e2"]
    N1 --> P["pins of e1"]
    N2 --> Q["pins of e2"]
    P --> K["modify_key"]
    Q --> K
    style V fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
    style N1 fill:#fff9c4,stroke:#f57f17,stroke-width:3px
    style N2 fill:#fff9c4,stroke:#f57f17,stroke-width:3px
    style P fill:#f8bbd0,stroke:#c2185b,stroke-width:3px
    style Q fill:#f8bbd0,stroke:#c2185b,stroke-width:3px
    style K fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
</pre>

]

---

### 🔬 How We Measure

- `python -m cProfile benchmarks/bench_fm.py` 🐍
- `cargo bench` — criterion 🦀
- `xmake run bench_fmbi_p1` — nanobench ⚙️

| Case | Modules | Nets |
|:-----|--------:|-----:|
| `p1.json` | 833 | 902 |
| `ibm03` | 23 136 | 27 401 |

> Profiling before optimizing is not optional. 🔎

---

## 🐍 Part 2 — Python: Profile First

---

### 🔍 The Profile: A Wrapper Tax

cProfile on `ibm03` — **77.9 M** calls. The top rows are all **indirection**.

<text x="220" y="94" text-anchor="end">FMGainMgr._update_move_net</text>
    <rect x="230" y="80" width="332" height="18" fill="#bf616a" rx="3"/>
    <text x="570" y="94" fill="#bf616a">9.6 s</text>

<text x="220" y="126" text-anchor="end">FMGainMgr.update_move</text>
    <rect x="230" y="112" width="246" height="18" fill="#d08770" rx="3"/>
    <text x="484" y="126" fill="#d08770">7.1 s</text>

<text x="220" y="158" text-anchor="end">FMBiGainCalc.init_idx_vec</text>
    <rect x="230" y="144" width="235" height="18" fill="#d08770" rx="3"/>
    <text x="473" y="158" fill="#d08770">6.8 s</text>

<text x="220" y="190" text-anchor="end">networkx coreviews.__getitem__</text>
    <rect x="230" y="176" width="180" height="18" fill="#ebcb8b" rx="3"/>
    <text x="418" y="190" fill="#b58900">5.2 s</text>

<text x="220" y="222" text-anchor="end">FMBiGainCalc.update_move_general_net</text>
    <rect x="230" y="208" width="228" height="18" fill="#d08770" rx="3"/>
    <text x="466" y="222" fill="#d08770">6.6 s</text>
  </g>
  <text x="16" y="266" font-family="sans-serif" font-size="13" fill="#4c566a">The seconds hide in <tspan font-weight="bold" fill="#bf616a">wrapper frames</tspan> and <tspan font-weight="bold" fill="#bf616a">no-op work</tspan>, not in the algorithm.</text>
</svg>

</p>

---

### 💡 The #1 Find: No-Op Key Updates

For a general net with $\ge 2$ pins in **both** parts, moving one pin changes nothing:

$$ {\color{#2e7d32} \Delta g_w} = 0 \quad \text{whenever} \quad {\color{#bf616a} |e \cap p| \ge 2} \ \ \forall p $$

Yet `modify_key` was still called for **every** neighbour:

```python
for dGw, w in zip(delta_gain, idx_vec):
    if dGw:                     # ← the one-line fix
        modify_key(w, part[w], dGw)
```

> Skipping a zero delta is a no-op in the bucket queue — so it is **free**. 🎯

---

### 🧱 Killing the Wrapper Layers

Two pure-Python layers added a frame to every access:

<pre>
graph TD
    subgraph AFTER["After"]
        A1["vertex_list[w]"] --> A2["list index"]
        A3["net_pins[net]"] --> A4["plain dict"]
    end
    subgraph BEFORE["Before"]
        B1["vertex_list[w]"] --> B2["MapAdapter\n__getitem__"] --> B3["list.__getitem__"]
        B4["ugraph[net]"] --> B5["AtlasView\n__getitem__"] --> B6["dict lookup"]
    end
    style B1 fill:#f8bbd0,stroke:#c2185b,stroke-width:3px
    style B2 fill:#f8bbd0,stroke:#c2185b,stroke-width:3px
    style B3 fill:#f8bbd0,stroke:#c2185b,stroke-width:3px
    style B4 fill:#f8bbd0,stroke:#c2185b,stroke-width:3px
    style B5 fill:#f8bbd0,stroke:#c2185b,stroke-width:3px
    style B6 fill:#f8bbd0,stroke:#c2185b,stroke-width:3px
    style A1 fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style A2 fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style A3 fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style A4 fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
</pre>

]

---

### 🗃️ Caching Adjacency & Degree

Materialise the networkx views **once** per gain calculator:

```python
self.net_pins = {net: list(self.hyprgraph.ugraph[net])
                 for net in self.hyprgraph.nets}
self.net_degree = {net: len(pins) for net, pins in self.net_pins.items()}
self.vertex_nets = {v: [] for v in self.hyprgraph}
for net, pins in self.net_pins.items():
    for v in pins:
        self.vertex_nets[v].append(net)
```

> The hot loop then touches **plain lists** — no view objects, no attribute walks. 📦

---

### 🧩 Bonus: The `mywheel` Dependency

The bucket queue used `id(x) == id(y)` for identity — a **builtin call per check**:

| Function | Before | After |
|:---------|:-------|:------|
| `Dllink.is_locked` | `id(a) == id(b)` | `a is b` ✅ |
| `Dllist.is_empty` | `id(a) == id(b)` | `a is b` ✅ |
| `DllIterator.__next__` | `id(a) != id(b)` | `a is not b` ✅ |

- `builtins.id`: **4.25 M calls** → 0 🗑️
- `increase_key`: only rescan the max when needed 🎯

> A/B/B/A on ckpttnpy: **+2.7% p1, +5.6% ibm03**. 📈

---

### 📊 Python Results

<text x="120" y="141" text-anchor="end">ibm03</text>
    <rect x="130" y="123" width="400" height="16" fill="#bf616a" rx="2"/>
    <text x="537" y="136" fill="#bf616a">14.64 s</text>
    <rect x="130" y="141" width="241" height="16" fill="#a3be8c" rx="2"/>
    <text x="378" y="154" fill="#2e7d32" font-weight="bold">8.83 s · 1.66×</text>
  </g>
  <text x="16" y="212" font-family="sans-serif" font-size="13" fill="#4c566a">Total calls <tspan font-weight="bold" fill="#5e81ac">77.9 M → 42.9 M</tspan> · modify_key <tspan font-weight="bold" fill="#5e81ac">7.37 M → 374 K</tspan></text>
  <text x="16" y="238" font-family="sans-serif" font-size="13" fill="#4c566a">MapAdapter and networkx view frames are <tspan font-weight="bold" fill="#2e7d32">gone from the top-25</tspan>.</text>
</svg>

</p>

---

### ✅ Behavior Equivalence

The optimizations are **semantically identical** — verified by stashing and re-running.

| Property | Before | After |
|:---------|:-------|:------|
| `ibm03` cut cost | 2275 | **2275** |
| `ibm01` cut cost | 663 | **663** |
| Tests | 111 | **111 pass** |
| `modify_key` calls | 7.37 M | **374 K** |

]

> Zero-delta is a no-op in the bucket queue — skipping it cannot change results. 🎲

---

## ⚙️ Part 3 — C++: Kill the Allocations

---

### 👥 The Sibling Projects

<pre>
graph LR
    PY["ckpttnpy\nPython reference"]
    CPP["ckpttn-cpp\nC++20 · CMake + xmake"]
    RS["ckpttn-rs\nRust · cargo"]
    PY -.->|"same algorithm"| CPP
    PY -.->|"same algorithm"| RS
    style PY fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
    style CPP fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style RS fill:#ffe0b2,stroke:#e65100,stroke-width:3px
</pre>

]

> "Enhance the sibling accordingly" — same idea, different constraints. 😅

---

### 📉 The Per-Call Allocation Tax

`update_move_general_net` returned a **fresh `std::vector` per net per move**:

```cpp
auto delta_gain = vector<int>(degree, 0);   // heap allocation!
...
return delta_gain;                          // and a copy
```

- The k-way path allocated a `vector<vector<int>>` — **many** small allocations 🐌
- Called once per net, per moved vertex, per pass

> The C++ was already fast — but not **allocation-free**. 🧾

---

### 🎯 The Fix: Reusable Buffer + Span

Keep the buffer in the calculator; return a **non-owning view**:

```cpp
auto& delta_gain = this->delta_gain_buf;   // reused across calls
delta_gain.assign(degree, 0);
...
return std::span<const int>{delta_gain.data(), degree};
```

<pre>
graph LR
    OLD["new vector\nper call ❌"] --> FIX["member buffer\nreused ✅"]
    FIX --> SPAN["std::span\nview, no copy ✅"]
    style OLD fill:#f8bbd0,stroke:#c2185b,stroke-width:3px
    style FIX fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style SPAN fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
</pre>

]

> All in-tree callers use `auto` — the change stays **source-compatible**. 🔧

---

### 📊 C++ Results

</p>

> The k-way path wins most — it was allocating a matrix per call. 🎯

---

## 🦀 Part 4 — Rust: The Same Lesson

---

### 🦀 The `.clone()` and `.collect()` Tax

The manager cloned the shared index vector **per net per move**:

```rust
let idx_vec: Vec<_> = self.gain_calc.idx_vec().clone(); // alloc + copy
for (i, &w) in idx_vec.iter().enumerate() { ... }
```

And collected neighbours into a `Vec` **per move**:

```rust
let nbrs: Vec<_> = self.hyprgraph.neighbors(v).collect(); // alloc
```

> The borrow checker made the clone *look* necessary — it wasn't. 🧠

---

### 🔧 Borrow-Checker-Friendly Buffers

Keep a reusable buffer on the struct; index it instead of cloning:

```rust
self.nbrs_buf.clear();
self.nbrs_buf.extend(self.hyprgraph.neighbors(v));
let num_nbrs = self.nbrs_buf.len();
for i in 0..num_nbrs {
    let net = self.nbrs_buf[i];        // Copy — the borrow ends here
    ...
}
```

- **Disjoint field borrows** let `nbrs_buf` and `hyprgraph` coexist 🤝
- `update_move_init` no longer reallocates `delta_gain_v` every move ♻️

---

### 📊 Rust Results

</p>

> Consistent **~28%** — and `cargo clippy` stays clean. ✨

---

## 🎓 Part 5 — Takeaways

---

### 🔁 The Same Lesson, Three Times

<pre>
graph LR
    Q["Where is the time?"]
    Q -->|"Python"| PY["per-call wrapper\n& no-op work ✅"]
    Q -->|"C++"| CPP["per-call heap\nallocations ✅"]
    Q -->|"Rust"| RS["per-call clone\n& collect ✅"]
    style Q fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
    style PY fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style CPP fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style RS fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
</pre>

]

- The **language** changes; the **shape** of the win does not 🔁
- Wrapper and allocation overhead is where the seconds hide 🎯

---

### 🧠 Key Takeaways

**Performance** ⚡
- **Profile first** — the bottleneck is rarely where you guess 🔍
- Eliminate **no-op work** before micro-tuning (`if dGw`) 🎯
- Python: kill wrapper frames (`MapAdapter`, networkx views) 🐍
- C++: reuse buffers, return `span` — no per-call `vector` ⚙️
- Rust: don't `.clone()` / `.collect()` what you can index 🦀
- Every change was **behavior-preserving** — verified by quality checks ✅

---

### 📜 Artifacts From This Session

| Artifact | Commit |
|:---------|:-------|
| Python issue | `luk036/ckpttnpy#6` |
| Python core | `ckpttnpy` `ba597a0` 🐍 |
| Python deps | `mywheel` `df4b232` |
| C++ changes | `mywheel-cpp` `989bb2c` · `ckpttn-cpp` `93c3371` ⚙️ |
| Rust change | `ckpttn-rs` `e221559` 🦀 |

> Python 1.9× · C++ 2× kernel · Rust −28% · **zero quality regression** 🎉

---

# 🙋 Q&A

**Making Circuit Partitioning Fast**

### Questions? Discussion? 💬

---

# 👏 Thank You

## Profile. Measure. Reuse the buffer. 🎯

Slides built with Remark.js 🎉 | KaTeX 📐 | Mermaid 🧩 | Nord Theme 🌙