)]}'
{
  "commit": "0c6b87dd46ffe9d84cdeb1f4ccc054ceef009bdb",
  "tree": "7bc4e474823f9ed93175c69a7b374e3ed7ab422b",
  "parents": [
    "8a147ac82eff765103adf32a9fddc1eca153afed"
  ],
  "author": {
    "name": "birenroy",
    "email": "birenroy@google.com",
    "time": "Wed Aug 12 12:06:12 2026 -0700"
  },
  "committer": {
    "name": "Copybara-Service",
    "email": "copybara-worker@google.com",
    "time": "Wed Aug 12 12:06:54 2026 -0700"
  },
  "message": "Implements `StableBlockList` for `QuicheLinkedHashMap`.\n\n`StableBlockList` is a simplified, block-based append-only sequence container designed to provide iterator stability for linked hash map backing stores.\n\nThis 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.\n\nKey optimizations:\n- Compact iterator can be returned in registers.\n- Large block size allows amortization of data structure overhead.\n- Fast traversal: Uses C++20 bitwise intrinsics (`std::countr_zero`, `std::countl_zero`) for constant-time within-block traversal.\n- Synchronous block recycling: Empty blocks are unlinked in O(1) and cached for reuse.\n\n## Benchmark Results (N \u003d 8192, Optimized Build)\n\n### 1. Raw Container Comparison: `std::list` vs `StableBlockList`\n\n#### Small Element Type: `std::pair\u003cint, int\u003e` (8 bytes)\n| Workload | `std::list` (CPU) | `StableBlockList\u003c16\u003e` (CPU) | Speedup (16) | `StableBlockList\u003c32\u003e` (CPU) | Speedup (32) |\n| :--- | :--- | :--- | :--- | :--- | :--- |\n| **Insert Only** | 228.8 us | 180.7 us | **1.27x** | 171.1 us | **1.34x** |\n| **FIFO (Insert + Erase)** | 299.1 us | 274.5 us | **1.09x** | 263.0 us | **1.14x** |\n| **Random Erase** | 411.8 us | 284.5 us | **1.45x** | 273.3 us | **1.51x** |\n| **Traversal** | 14.8 us | 12.4 us | **1.19x** | 12.9 us | **1.14x** |\n\n#### Large Element Type: `std::pair\u003cabsl::string_view, absl::string_view\u003e` (32 bytes)\n| Workload | `std::list` (CPU) | `StableBlockList\u003c16\u003e` (CPU) | Speedup (16) | `StableBlockList\u003c32\u003e` (CPU) | Speedup (32) |\n| :--- | :--- | :--- | :--- | :--- | :--- |\n| **Insert Only** | 394.6 us | 349.2 us | **1.13x** | 336.6 us | **1.17x** |\n| **FIFO (Insert + Erase)** | 525.1 us | 498.3 us | **1.05x** | 483.5 us | **1.09x** |\n| **Random Erase** | 684.3 us | 549.2 us | **1.25x** | 523.2 us | **1.31x** |\n| **Traversal** | 17.4 us | 17.7 us | 1.02x Slower | 14.4 us | **1.21x** |\n\n### 2. `HttpHeaderBlock` E2E A/B Comparison (Base: `std::list` vs. Exp: `StableBlockList\u003c32\u003e`)\n\n| Workload | Base (`std::list`) | Exp (`StableBlockList\u003c32\u003e`) | Speedup / Overhead |\n| :--- | :--- | :--- | :--- |\n| **Insert Only** | 1,015.1 us | 998.2 us | **1.02x (Neutral)** |\n| **FIFO Workload** | 1,633.0 us | 1,646.0 us | **0.99x (Neutral)** |\n| **Random Erase** | 1,996.0 us | 1,876.0 us | **1.06x (Neutral)** |\n| **Lookup** | 296.8 us | 322.5 us | 1.09x Slower (8.6% overhead) |\n| **Clone** | 844.8 us | 827.3 us | **1.02x Faster (2.1% saving)** |\n| **Traversal** | 34.9 us | 31.5 us | **1.11x (Neutral)** |\n\nPiperOrigin-RevId: 963585805\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "3aa9288d78ee9f93ce196dea54f0357d08cf4028",
      "old_mode": 33188,
      "old_path": "build/source_list.bzl",
      "new_id": "64dfb018e4db6452053f8a5e8a0cb7765e8a55cd",
      "new_mode": 33188,
      "new_path": "build/source_list.bzl"
    },
    {
      "type": "modify",
      "old_id": "553b0a4cc32405be0b172a642503936db7e6629c",
      "old_mode": 33188,
      "old_path": "build/source_list.gni",
      "new_id": "bd07125cf05aa3fa84f40341755c9991c617eb10",
      "new_mode": 33188,
      "new_path": "build/source_list.gni"
    },
    {
      "type": "modify",
      "old_id": "8e9046a7d59a720e79b109ec4b7a60983fd7b28d",
      "old_mode": 33188,
      "old_path": "build/source_list.json",
      "new_id": "1212ca476d672dff84506fdfb73d3c795c4fb4d9",
      "new_mode": 33188,
      "new_path": "build/source_list.json"
    },
    {
      "type": "add",
      "old_id": "0000000000000000000000000000000000000000",
      "old_mode": 0,
      "old_path": "/dev/null",
      "new_id": "f46646d0b1c8660cab746485e52c33b652fece55",
      "new_mode": 33188,
      "new_path": "quiche/common/stable_block_list.h"
    },
    {
      "type": "add",
      "old_id": "0000000000000000000000000000000000000000",
      "old_mode": 0,
      "old_path": "/dev/null",
      "new_id": "e1bc9425a66f1de06e2c907b7ae96b132ee33b59",
      "new_mode": 33188,
      "new_path": "quiche/common/stable_block_list_test.cc"
    }
  ]
}