)]}'
{
  "commit": "003eafbbac0ee47f44bd3ba7fc79c92b5cc17e40",
  "tree": "d796df9df73e82958a71f4ca514c588f45c5fe24",
  "parents": [
    "1143aa2cee4f389e9ff310f2a095fc88fbe7fb02"
  ],
  "author": {
    "name": "Protobuf Team Bot",
    "email": "protobuf-github-bot@google.com",
    "time": "Thu Jul 23 11:50:44 2026 -0700"
  },
  "committer": {
    "name": "Copybara-Service",
    "email": "copybara-worker@google.com",
    "time": "Wed Aug 26 19:04:22 2026 -0700"
  },
  "message": "Optimize MessageDifferencer::TreatAsSet time complexity to O(N * K)\n\nOptimizes MessageDifferencer::TreatAsSet() repeated field matching by using\nhash map lookup (GetRepeatedElementHash) for unmatched elements.\n\nPreviously, set matching performed O(N^2 * K) element-pair comparisons. With\nhash map lookup, set matching executes in average O(N * K) time complexity.\nUpdated documentation in message_differencer.h and added\nTreatAsSet_LargeUnorderedSet test case to message_differencer_unittest.cc.\n\nMitigations:\n- Uses absl::InlinedVector\u003cint, 2\u003e in hash map buckets to eliminate per-element heap allocations.\n- Uses element count threshold (count \u003e 4) to bypass hash map construction for small lists (N \u003c\u003d 4), avoiding hashing overhead on small element sets.\n- Samples 32 bytes from the prefix and 32 bytes from the suffix (64 bytes total) for large strings, keeping string hashing within hardware CRC32/SIMD throughput while eliminating large payload throughput regressions.\n\nBenchmark Replication Command:\n  benchy \\\n    --reference\u003d\u003cbaseline_client\u003e \\\n    --perflab \\\n    --cpu\u003dhaswell \\\n    --runs\u003d6 \\\n    --benchmark_filter\u003dall \\\n    //experimental/users/dpages/message_differencer_benchmark:message_differencer_benchmark \\\n    --benchmark_enable_random_interleaving \\\n    --benchmark_repetitions\u003d50\n\nBenchy Results (Sponge: http://sponge2/d30b23f6-8606-4579-81bb-628600fd8d2e):\nGenerated by http://go/benchy on Perflab (Haswell, 6 runs, 50 interleaved repetitions).\nOverall Geomean: 59.10 µs -\u003e 18.64 µs (-68.45% CPU).\n\n### 1. Repeated Scalar (Int32) - Permuted / Unordered Set Matching\n| N | Condition | Baseline CPU | Optimized CPU | Change | Speedup |\n|---|---|---|---|---|---|\n| 10 | Permuted | 1.73 µs | 1.22 µs | -29.74% | 1.4x |\n| 50 | Permuted | 29.37 µs | 5.09 µs | -82.67% | 5.8x |\n| 100 | Permuted | 112.28 µs | 9.84 µs | -91.23% | 11.4x |\n| 500 | Permuted | 2.71 ms | 50.23 µs | -98.15% | 54.0x |\n| 1,000 | Permuted | 10.80 ms | 100.6 µs | -99.07% | 107.4x |\n| 5,000 | Permuted | 269.37 ms | 504.1 µs | -99.81% | 534.3x |\n| 10,000 | Permuted | 1,078.37 ms | 1.04 ms | -99.90% | 1,037.9x |\n\n### 2. Repeated String - Permuted / Unordered Set Matching\n| N | Condition | Baseline CPU | Optimized CPU | Change | Speedup |\n|---|---|---|---|---|---|\n| 10 | Permuted | 2.26 µs | 1.52 µs | -32.99% | 1.5x |\n| 50 | Permuted | 38.06 µs | 6.47 µs | -83.01% | 5.9x |\n| 100 | Permuted | 146.64 µs | 12.78 µs | -91.28% | 11.5x |\n| 500 | Permuted | 3.53 ms | 66.57 µs | -98.12% | 53.1x |\n| 1,000 | Permuted | 14.37 ms | 133.4 µs | -99.07% | 107.7x |\n| 5,000 | Permuted | 352.79 ms | 727.0 µs | -99.79% | 485.3x |\n\n### 3. Repeated Scalar (Int32) - Mismatch / Unmatched Elements\n| N | Condition | Baseline CPU | Optimized CPU | Change | Speedup |\n|---|---|---|---|---|---|\n| 10 | Mismatched | 1.16 µs | 0.73 µs | -37.12% | 1.6x |\n| 100 | Mismatched | 82.19 µs | 5.34 µs | -93.51% | 15.4x |\n| 1,000 | Mismatched | 8.09 ms | 55.29 µs | -99.32% | 146.3x |\n| 5,000 | Mismatched | 201.94 ms | 276.6 µs | -99.86% | 730.1x |\n| 10,000 | Mismatched | 808.08 ms | 570.7 µs | -99.93% | 1,415.9x |\n\n### 4. String Payload Size Scaling (N\u003d50, Varying String Size)\n*(Bounded prefix+suffix hashing eliminates large payload throughput bottlenecks)*\n| N | String Size | Baseline CPU | Optimized CPU | Change |\n|---|---|---|---|---|\n| 50 | 16 B | 19.43 µs | 5.97 µs | -69.25% |\n| 50 | 64 B | 20.23 µs | 6.50 µs | -67.88% |\n| 50 | 256 B | 21.37 µs | 8.46 µs | -60.43% |\n| 50 | 1 KB | 22.32 µs | 9.88 µs | -55.73% |\n| 50 | 4 KB | 31.45 µs | 19.70 µs | -37.37% |\n| 50 | 16 KB | 68.57 µs | 53.64 µs | -21.77% |\n| 50 | 64 KB | 181.7 µs | 167.5 µs | -7.80% |\n\n### 5. Mostly Identical Elements (90% Identical in Order, 10% Permuted)\n| Benchmark | N | Baseline CPU | Optimized CPU | Change | Speedup |\n|---|---|---|---|---|---|\n| Int32_MostlyIdentical | 10 | 660.9 ns | 719.4 ns | +8.86% | ~ parity |\n| Int32_MostlyIdentical | 100 | 5.64 µs | 5.33 µs | -5.45% | 1.1x |\n| Int32_MostlyIdentical | 1,000 | 151.35 µs | 52.66 µs | -65.21% | 2.9x |\n| Int32_MostlyIdentical | 5,000 | 2.91 ms | 263.1 µs | -90.95% | 11.1x |\n| Int32_MostlyIdentical | 10,000 | 11.20 ms | 527.2 µs | -95.29% | 21.3x |\n| String_MostlyIdentical | 10 | 816.5 ns | 816.8 ns | +0.04% | ~ parity |\n| String_MostlyIdentical | 100 | 7.53 µs | 6.74 µs | -10.59% | 1.1x |\n| String_MostlyIdentical | 1,000 | 203.80 µs | 66.62 µs | -67.31% | 3.1x |\n| String_MostlyIdentical | 5,000 | 3.91 ms | 340.4 µs | -91.30% | 11.5x |\n\n### 6. Duplicate \u0026 Identical Order Fast Paths\n| Benchmark | N | Condition | Baseline CPU | Optimized CPU | Change |\n|---|---|---|---|---|---|\n| Int32_IdenticalOrder | 10 | Prefix match (identical order) | 662.1 ns | 719.5 ns | +8.67% |\n| Int32_IdenticalOrder | 100 | Prefix match (identical order) | 4.57 µs | 4.97 µs | +8.69% |\n| Int32_IdenticalOrder | 1,000 | Prefix match (identical order) | 43.59 µs | 45.62 µs | +4.67% |\n| Int32_IdenticalOrder | 5,000 | Prefix match (identical order) | 217.1 µs | 233.0 µs | +7.32% |\n| Int32_IdenticalOrder | 10,000 | Prefix match (identical order) | 434.4 µs | 463.4 µs | +6.66% |\n| String_IdenticalOrder | 10 | Prefix match (identical order) | 819.0 ns | 818.2 ns | -0.10% |\n| String_IdenticalOrder | 100 | Prefix match (identical order) | 6.07 µs | 5.99 µs | -1.25% |\n| String_IdenticalOrder | 1,000 | Prefix match (identical order) | 59.50 µs | 59.43 µs | ~ parity |\n| String_IdenticalOrder | 5,000 | Prefix match (identical order) | 297.6 µs | 298.2 µs | +0.22% |\n| Int32_AllDuplicates | 10 | Duplicates (identical order) | 661.2 ns | 719.8 ns | +8.86% |\n| Int32_AllDuplicates | 100 | Duplicates (identical order) | 4.57 µs | 4.97 µs | +8.73% |\n| Int32_AllDuplicates | 500 | Duplicates (identical order) | 21.91 µs | 22.98 µs | +4.91% |\n| Int32_AllDuplicates | 1,000 | Duplicates (identical order) | 43.58 µs | 45.61 µs | +4.66% |\n| Int32_AllDuplicates | 5,000 | Duplicates (identical order) | 217.1 µs | 233.0 µs | +7.34% |\n| String_AllDuplicates | 10 | Duplicates (identical order) | 807.8 ns | 824.2 ns | +2.04% |\n| String_AllDuplicates | 100 | Duplicates (identical order) | 6.52 µs | 6.49 µs | ~ parity |\n| String_AllDuplicates | 500 | Duplicates (identical order) | 34.27 µs | 33.06 µs | -3.55% |\n| String_AllDuplicates | 1,000 | Duplicates (identical order) | 71.41 µs | 69.02 µs | -3.35% |\n| String_AllDuplicates | 5,000 | Duplicates (identical order) | 366.5 µs | 369.9 µs | ~ parity |\n\n### 7. Small Element Count Fallback Threshold (N\u003d2, Varying String Size)\n*(Tests N \u003c\u003d 4 threshold bypass to eliminate hashing overhead on small lists)*\n| N | String Size | Baseline CPU | Optimized CPU | Change |\n|---|---|---|---|---|\n| 2 | 16 B | 384.3 ns | 393.7 ns | +2.45% |\n| 2 | 64 B | 384.7 ns | 397.4 ns | +3.29% |\n| 2 | 256 B | 407.1 ns | 421.0 ns | +3.42% |\n| 2 | 1 KB | 457.6 ns | 485.7 ns | +6.13% |\n| 2 | 4 KB | 639.1 ns | 737.7 ns | +15.44% |\n| 2 | 16 KB | 1.68 µs | 1.70 µs | +1.10% |\n| 2 | 64 KB | 5.19 µs | 5.22 µs | +0.69% |\n\n### 8. Submessages \u0026 Baseline Controls\n| Benchmark | N | Condition | Baseline CPU | Optimized CPU | Change |\n|---|---|---|---|---|---|\n| Message_Permuted | 2 | Submessages (direct compare) | 1.51 µs | 1.51 µs | ~ parity |\n| Message_Permuted | 5 | Submessages (direct compare) | 4.39 µs | 4.38 µs | -0.10% |\n| Message_Permuted | 10 | Submessages (direct compare) | 12.43 µs | 12.48 µs | +0.34% |\n| Message_Permuted | 50 | Submessages (direct compare) | 224.2 µs | 227.1 µs | +1.30% |\n| Message_Permuted | 100 | Submessages (direct compare) | 856.8 µs | 869.5 µs | +1.48% |\n| Message_Permuted | 500 | Submessages (direct compare) | 20.66 ms | 20.98 ms | +1.55% |\n| DefaultList_Identical | 10 | Non-set default list diff | 397.3 ns | 407.6 ns | +2.58% |\n| DefaultList_Identical | 100 | Non-set default list diff | 2.28 µs | 2.29 µs | +0.31% |\n| DefaultList_Identical | 1,000 | Non-set default list diff | 20.95 µs | 20.97 µs | ~ parity |\n| DefaultList_Identical | 5,000 | Non-set default list diff | 104.0 µs | 104.1 µs | ~ parity |\n| DefaultList_Identical | 10,000 | Non-set default list diff | 207.9 µs | 207.9 µs | ~ parity |\n\nPiperOrigin-RevId: 952878430\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "ae685a48ae0baffe2290b950fb2ba735784e1b18",
      "old_mode": 33188,
      "old_path": "src/google/protobuf/util/message_differencer.cc",
      "new_id": "6e9f04f60cd82561b7f1feaafcb345b13f8acdbf",
      "new_mode": 33188,
      "new_path": "src/google/protobuf/util/message_differencer.cc"
    },
    {
      "type": "modify",
      "old_id": "d3f0b80cdda5acd14d0a85230570a4c426517701",
      "old_mode": 33188,
      "old_path": "src/google/protobuf/util/message_differencer.h",
      "new_id": "55a90df73b41e2f84c77e511504e7386f17823f5",
      "new_mode": 33188,
      "new_path": "src/google/protobuf/util/message_differencer.h"
    },
    {
      "type": "modify",
      "old_id": "3be1e3c74e006a5b6899b787fbfbb4c0ae6e8ddf",
      "old_mode": 33188,
      "old_path": "src/google/protobuf/util/message_differencer_unittest.cc",
      "new_id": "93018f44cc5db5e9d2c297b00ec0c51c0ab83017",
      "new_mode": 33188,
      "new_path": "src/google/protobuf/util/message_differencer_unittest.cc"
    }
  ]
}