Optimize MessageDifferencer::TreatAsSet time complexity to O(N * K)
Optimizes MessageDifferencer::TreatAsSet() repeated field matching by using
hash map lookup (GetRepeatedElementHash) for unmatched elements.
Previously, set matching performed O(N^2 * K) element-pair comparisons. With
hash map lookup, set matching executes in average O(N * K) time complexity.
Updated documentation in message_differencer.h and added
TreatAsSet_LargeUnorderedSet test case to message_differencer_unittest.cc.
Mitigations:
- Uses absl::InlinedVector<int, 2> in hash map buckets to eliminate per-element heap allocations.
- Uses element count threshold (count > 4) to bypass hash map construction for small lists (N <= 4), avoiding hashing overhead on small element sets.
- 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.
Benchmark Replication Command:
benchy \
--reference=<baseline_client> \
--perflab \
--cpu=haswell \
--runs=6 \
--benchmark_filter=all \
//experimental/users/dpages/message_differencer_benchmark:message_differencer_benchmark \
--benchmark_enable_random_interleaving \
--benchmark_repetitions=50
Benchy Results (Sponge: http://sponge2/d30b23f6-8606-4579-81bb-628600fd8d2e):
Generated by http://go/benchy on Perflab (Haswell, 6 runs, 50 interleaved repetitions).
Overall Geomean: 59.10 µs -> 18.64 µs (-68.45% CPU).
### 1. Repeated Scalar (Int32) - Permuted / Unordered Set Matching
| N | Condition | Baseline CPU | Optimized CPU | Change | Speedup |
|---|---|---|---|---|---|
| 10 | Permuted | 1.73 µs | 1.22 µs | -29.74% | 1.4x |
| 50 | Permuted | 29.37 µs | 5.09 µs | -82.67% | 5.8x |
| 100 | Permuted | 112.28 µs | 9.84 µs | -91.23% | 11.4x |
| 500 | Permuted | 2.71 ms | 50.23 µs | -98.15% | 54.0x |
| 1,000 | Permuted | 10.80 ms | 100.6 µs | -99.07% | 107.4x |
| 5,000 | Permuted | 269.37 ms | 504.1 µs | -99.81% | 534.3x |
| 10,000 | Permuted | 1,078.37 ms | 1.04 ms | -99.90% | 1,037.9x |
### 2. Repeated String - Permuted / Unordered Set Matching
| N | Condition | Baseline CPU | Optimized CPU | Change | Speedup |
|---|---|---|---|---|---|
| 10 | Permuted | 2.26 µs | 1.52 µs | -32.99% | 1.5x |
| 50 | Permuted | 38.06 µs | 6.47 µs | -83.01% | 5.9x |
| 100 | Permuted | 146.64 µs | 12.78 µs | -91.28% | 11.5x |
| 500 | Permuted | 3.53 ms | 66.57 µs | -98.12% | 53.1x |
| 1,000 | Permuted | 14.37 ms | 133.4 µs | -99.07% | 107.7x |
| 5,000 | Permuted | 352.79 ms | 727.0 µs | -99.79% | 485.3x |
### 3. Repeated Scalar (Int32) - Mismatch / Unmatched Elements
| N | Condition | Baseline CPU | Optimized CPU | Change | Speedup |
|---|---|---|---|---|---|
| 10 | Mismatched | 1.16 µs | 0.73 µs | -37.12% | 1.6x |
| 100 | Mismatched | 82.19 µs | 5.34 µs | -93.51% | 15.4x |
| 1,000 | Mismatched | 8.09 ms | 55.29 µs | -99.32% | 146.3x |
| 5,000 | Mismatched | 201.94 ms | 276.6 µs | -99.86% | 730.1x |
| 10,000 | Mismatched | 808.08 ms | 570.7 µs | -99.93% | 1,415.9x |
### 4. String Payload Size Scaling (N=50, Varying String Size)
*(Bounded prefix+suffix hashing eliminates large payload throughput bottlenecks)*
| N | String Size | Baseline CPU | Optimized CPU | Change |
|---|---|---|---|---|
| 50 | 16 B | 19.43 µs | 5.97 µs | -69.25% |
| 50 | 64 B | 20.23 µs | 6.50 µs | -67.88% |
| 50 | 256 B | 21.37 µs | 8.46 µs | -60.43% |
| 50 | 1 KB | 22.32 µs | 9.88 µs | -55.73% |
| 50 | 4 KB | 31.45 µs | 19.70 µs | -37.37% |
| 50 | 16 KB | 68.57 µs | 53.64 µs | -21.77% |
| 50 | 64 KB | 181.7 µs | 167.5 µs | -7.80% |
### 5. Mostly Identical Elements (90% Identical in Order, 10% Permuted)
| Benchmark | N | Baseline CPU | Optimized CPU | Change | Speedup |
|---|---|---|---|---|---|
| Int32_MostlyIdentical | 10 | 660.9 ns | 719.4 ns | +8.86% | ~ parity |
| Int32_MostlyIdentical | 100 | 5.64 µs | 5.33 µs | -5.45% | 1.1x |
| Int32_MostlyIdentical | 1,000 | 151.35 µs | 52.66 µs | -65.21% | 2.9x |
| Int32_MostlyIdentical | 5,000 | 2.91 ms | 263.1 µs | -90.95% | 11.1x |
| Int32_MostlyIdentical | 10,000 | 11.20 ms | 527.2 µs | -95.29% | 21.3x |
| String_MostlyIdentical | 10 | 816.5 ns | 816.8 ns | +0.04% | ~ parity |
| String_MostlyIdentical | 100 | 7.53 µs | 6.74 µs | -10.59% | 1.1x |
| String_MostlyIdentical | 1,000 | 203.80 µs | 66.62 µs | -67.31% | 3.1x |
| String_MostlyIdentical | 5,000 | 3.91 ms | 340.4 µs | -91.30% | 11.5x |
### 6. Duplicate & Identical Order Fast Paths
| Benchmark | N | Condition | Baseline CPU | Optimized CPU | Change |
|---|---|---|---|---|---|
| Int32_IdenticalOrder | 10 | Prefix match (identical order) | 662.1 ns | 719.5 ns | +8.67% |
| Int32_IdenticalOrder | 100 | Prefix match (identical order) | 4.57 µs | 4.97 µs | +8.69% |
| Int32_IdenticalOrder | 1,000 | Prefix match (identical order) | 43.59 µs | 45.62 µs | +4.67% |
| Int32_IdenticalOrder | 5,000 | Prefix match (identical order) | 217.1 µs | 233.0 µs | +7.32% |
| Int32_IdenticalOrder | 10,000 | Prefix match (identical order) | 434.4 µs | 463.4 µs | +6.66% |
| String_IdenticalOrder | 10 | Prefix match (identical order) | 819.0 ns | 818.2 ns | -0.10% |
| String_IdenticalOrder | 100 | Prefix match (identical order) | 6.07 µs | 5.99 µs | -1.25% |
| String_IdenticalOrder | 1,000 | Prefix match (identical order) | 59.50 µs | 59.43 µs | ~ parity |
| String_IdenticalOrder | 5,000 | Prefix match (identical order) | 297.6 µs | 298.2 µs | +0.22% |
| Int32_AllDuplicates | 10 | Duplicates (identical order) | 661.2 ns | 719.8 ns | +8.86% |
| Int32_AllDuplicates | 100 | Duplicates (identical order) | 4.57 µs | 4.97 µs | +8.73% |
| Int32_AllDuplicates | 500 | Duplicates (identical order) | 21.91 µs | 22.98 µs | +4.91% |
| Int32_AllDuplicates | 1,000 | Duplicates (identical order) | 43.58 µs | 45.61 µs | +4.66% |
| Int32_AllDuplicates | 5,000 | Duplicates (identical order) | 217.1 µs | 233.0 µs | +7.34% |
| String_AllDuplicates | 10 | Duplicates (identical order) | 807.8 ns | 824.2 ns | +2.04% |
| String_AllDuplicates | 100 | Duplicates (identical order) | 6.52 µs | 6.49 µs | ~ parity |
| String_AllDuplicates | 500 | Duplicates (identical order) | 34.27 µs | 33.06 µs | -3.55% |
| String_AllDuplicates | 1,000 | Duplicates (identical order) | 71.41 µs | 69.02 µs | -3.35% |
| String_AllDuplicates | 5,000 | Duplicates (identical order) | 366.5 µs | 369.9 µs | ~ parity |
### 7. Small Element Count Fallback Threshold (N=2, Varying String Size)
*(Tests N <= 4 threshold bypass to eliminate hashing overhead on small lists)*
| N | String Size | Baseline CPU | Optimized CPU | Change |
|---|---|---|---|---|
| 2 | 16 B | 384.3 ns | 393.7 ns | +2.45% |
| 2 | 64 B | 384.7 ns | 397.4 ns | +3.29% |
| 2 | 256 B | 407.1 ns | 421.0 ns | +3.42% |
| 2 | 1 KB | 457.6 ns | 485.7 ns | +6.13% |
| 2 | 4 KB | 639.1 ns | 737.7 ns | +15.44% |
| 2 | 16 KB | 1.68 µs | 1.70 µs | +1.10% |
| 2 | 64 KB | 5.19 µs | 5.22 µs | +0.69% |
### 8. Submessages & Baseline Controls
| Benchmark | N | Condition | Baseline CPU | Optimized CPU | Change |
|---|---|---|---|---|---|
| Message_Permuted | 2 | Submessages (direct compare) | 1.51 µs | 1.51 µs | ~ parity |
| Message_Permuted | 5 | Submessages (direct compare) | 4.39 µs | 4.38 µs | -0.10% |
| Message_Permuted | 10 | Submessages (direct compare) | 12.43 µs | 12.48 µs | +0.34% |
| Message_Permuted | 50 | Submessages (direct compare) | 224.2 µs | 227.1 µs | +1.30% |
| Message_Permuted | 100 | Submessages (direct compare) | 856.8 µs | 869.5 µs | +1.48% |
| Message_Permuted | 500 | Submessages (direct compare) | 20.66 ms | 20.98 ms | +1.55% |
| DefaultList_Identical | 10 | Non-set default list diff | 397.3 ns | 407.6 ns | +2.58% |
| DefaultList_Identical | 100 | Non-set default list diff | 2.28 µs | 2.29 µs | +0.31% |
| DefaultList_Identical | 1,000 | Non-set default list diff | 20.95 µs | 20.97 µs | ~ parity |
| DefaultList_Identical | 5,000 | Non-set default list diff | 104.0 µs | 104.1 µs | ~ parity |
| DefaultList_Identical | 10,000 | Non-set default list diff | 207.9 µs | 207.9 µs | ~ parity |
PiperOrigin-RevId: 952878430
Copyright 2008 Google LLC
Protocol Buffers (a.k.a., protobuf) are Google's language-neutral, platform-neutral, extensible mechanism for serializing structured data. You can learn more about it in protobuf's documentation.
This README file contains protobuf installation instructions. To install protobuf, you need to install the protocol compiler (used to compile .proto files) and the protobuf runtime for your chosen programming language.
Most users will find working from supported releases to be the easiest path.
If you choose to work from the head revision of the main branch your build will occasionally be broken by source-incompatible changes and insufficiently-tested (and therefore broken) behavior.
If you are using C++ or otherwise need to build protobuf from source as a part of your project, you should pin to a release commit on a release branch.
This is because even release branches can experience some instability in between release commits.
Protobuf supports Bzlmod with Bazel 8 +. Users should specify a dependency on protobuf in their MODULE.bazel file as follows.
bazel_dep(name = "protobuf", version = <VERSION>)
Users can optionally override the repo name, such as for compatibility with WORKSPACE.
bazel_dep(name = "protobuf", version = <VERSION>, repo_name = "com_google_protobuf")
Users can also add the following to their legacy WORKSPACE file.
Note that with the release of 30.x there are a few more load statements to properly set up rules_java and rules_python.
http_archive(
name = "com_google_protobuf",
strip_prefix = "protobuf-VERSION",
sha256 = ...,
url = ...,
)
load("@com_google_protobuf//:protobuf_deps.bzl", "protobuf_deps")
protobuf_deps()
load("@rules_java//java:rules_java_deps.bzl", "rules_java_dependencies")
rules_java_dependencies()
load("@rules_java//java:repositories.bzl", "rules_java_toolchains")
rules_java_toolchains()
load("@rules_python//python:repositories.bzl", "py_repositories")
py_repositories()
The protobuf compiler is written in C++. If you are using C++, please follow the C++ Installation Instructions to install protoc along with the C++ runtime.
For non-C++ users, the simplest way to install the protocol compiler is to download a pre-built binary from our GitHub release page.
In the downloads section of each release, you can find pre-built binaries in zip packages: protoc-$VERSION-$PLATFORM.zip. It contains the protoc binary as well as a set of standard .proto files distributed along with protobuf.
If you are looking for an old version that is not available in the release page, check out the Maven repository.
These pre-built binaries are only provided for released versions. If you want to use the github main version at HEAD, or you need to modify protobuf code, or you are using C++, it's recommended to build your own protoc binary from source.
If you would like to build protoc binary from source, see the C++ Installation Instructions.
Protobuf supports several different programming languages. For each programming language, you can find instructions in the corresponding source directory about how to install protobuf runtime for that specific language:
| Language | Source |
|---|---|
| C++ (include C++ runtime and protoc) | src |
| Java | java |
| Python | python |
| Objective-C | objectivec |
| C# | csharp |
| Ruby | ruby |
| Go | protocolbuffers/protobuf-go |
| PHP | php |
| Dart | dart-lang/protobuf |
| JavaScript | protocolbuffers/protobuf-javascript |
The best way to learn how to use protobuf is to follow the tutorials in our developer guide.
If you want to learn from code examples, take a look at the examples in the examples directory.
The complete documentation is available at the Protocol Buffers doc site.
Read about our version support policy to stay current on support timeframes for the language libraries.
To be alerted to upcoming changes in Protocol Buffers and connect with protobuf developers and users, join the Google Group.