tree 7bc4e474823f9ed93175c69a7b374e3ed7ab422b
parent 8a147ac82eff765103adf32a9fddc1eca153afed
author birenroy <birenroy@google.com> 1786561572 -0700
committer Copybara-Service <copybara-worker@google.com> 1786561614 -0700

Implements `StableBlockList` for `QuicheLinkedHashMap`.

`StableBlockList` is a simplified, block-based append-only sequence container designed to provide iterator stability for linked hash map backing stores.

This implementation uses a heap-allocated `ControlBlock` containing a list sentinel, and a circular doubly-linked list of active blocks. Empty blocks are unlinked and recycled in a LIFO pool to reduce allocator pressure. Iterators store direct pointers to blocks and element indices, resulting in a compact iterator size of 16 bytes. A `shrink_to_fit()` method is provided to release recycled blocks in the free list.

Key optimizations:
- Compact iterator can be returned in registers.
- Large block size allows amortization of data structure overhead.
- Fast traversal: Uses C++20 bitwise intrinsics (`std::countr_zero`, `std::countl_zero`) for constant-time within-block traversal.
- Synchronous block recycling: Empty blocks are unlinked in O(1) and cached for reuse.

## Benchmark Results (N = 8192, Optimized Build)

### 1. Raw Container Comparison: `std::list` vs `StableBlockList`

#### Small Element Type: `std::pair<int, int>` (8 bytes)
| Workload | `std::list` (CPU) | `StableBlockList<16>` (CPU) | Speedup (16) | `StableBlockList<32>` (CPU) | Speedup (32) |
| :--- | :--- | :--- | :--- | :--- | :--- |
| **Insert Only** | 228.8 us | 180.7 us | **1.27x** | 171.1 us | **1.34x** |
| **FIFO (Insert + Erase)** | 299.1 us | 274.5 us | **1.09x** | 263.0 us | **1.14x** |
| **Random Erase** | 411.8 us | 284.5 us | **1.45x** | 273.3 us | **1.51x** |
| **Traversal** | 14.8 us | 12.4 us | **1.19x** | 12.9 us | **1.14x** |

#### Large Element Type: `std::pair<absl::string_view, absl::string_view>` (32 bytes)
| Workload | `std::list` (CPU) | `StableBlockList<16>` (CPU) | Speedup (16) | `StableBlockList<32>` (CPU) | Speedup (32) |
| :--- | :--- | :--- | :--- | :--- | :--- |
| **Insert Only** | 394.6 us | 349.2 us | **1.13x** | 336.6 us | **1.17x** |
| **FIFO (Insert + Erase)** | 525.1 us | 498.3 us | **1.05x** | 483.5 us | **1.09x** |
| **Random Erase** | 684.3 us | 549.2 us | **1.25x** | 523.2 us | **1.31x** |
| **Traversal** | 17.4 us | 17.7 us | 1.02x Slower | 14.4 us | **1.21x** |

### 2. `HttpHeaderBlock` E2E A/B Comparison (Base: `std::list` vs. Exp: `StableBlockList<32>`)

| Workload | Base (`std::list`) | Exp (`StableBlockList<32>`) | Speedup / Overhead |
| :--- | :--- | :--- | :--- |
| **Insert Only** | 1,015.1 us | 998.2 us | **1.02x (Neutral)** |
| **FIFO Workload** | 1,633.0 us | 1,646.0 us | **0.99x (Neutral)** |
| **Random Erase** | 1,996.0 us | 1,876.0 us | **1.06x (Neutral)** |
| **Lookup** | 296.8 us | 322.5 us | 1.09x Slower (8.6% overhead) |
| **Clone** | 844.8 us | 827.3 us | **1.02x Faster (2.1% saving)** |
| **Traversal** | 34.9 us | 31.5 us | **1.11x (Neutral)** |

PiperOrigin-RevId: 963585805