mirror of
https://github.com/carbon-language/carbon-lang.git
synced 2026-11-14 13:08:29 +00:00
dependabot/github_actions/github-actions-major-8a185ec9c8
8
Commits
| Author | SHA1 | Message | Date | |
|---|---|---|---|---|
 Chandler Carruth
|
632a81fcb6 |
Keep benchmark values passed to DoNotOptimize in registers (#7870)
Clang implements the `"+r,m"` constraint in `benchmark::DoNotOptimize` by always choosing memory, so each call stores the value to the stack and loads it back. Most of our benchmarks call it on a loop counter or another value carried to the next iteration, which puts that store and reload on the loop's critical path. On an Apple M1, the cost of that round trip depends on which register the compiler uses to address the stack slot, and unrelated code changes move it. Changing only that register from `x29` to `sp`, with the same address, made `BM_SetLookupHitPtr<Set<int>>` 41.5% to 49.1% slower. Add `Carbon::Testing::DoNotOptimize` in `//testing/base:benchmark_helpers`, and switch every benchmark to it. It only accepts types it can keep in registers: integers, enums, and pointers go into a `"+r"` constraint with a `"memory"` clobber, and containers pass their `data()` pointer to that form, so the compiler must assume the call reads and writes their contents. Any other type is a compile error. The container form doesn't block optimizing based on a container's size; passing the container's address does. Benchmarks that pass a loop counter or carried value no longer measure a store and reload per iteration, so their numbers aren't comparable with earlier runs. For example, the hashing latency benchmarks no longer include one in each hash's latency. Assisted-by: Claude Code |
||
 Chandler CarruthandNicholas Bishop
|
53dfe6bff9 |
Run hashtable benchmark loops at randomly chosen code offsets (#7864)
On Zen 5, a hashtable benchmark's result depends on where its timed loop lands in memory. With a fixed hash seed, `BM_MapContainsMiss<Map<int, int>>/64` takes 5.5-6.3 cycles per lookup at 8 of the 16 possible loop positions within 256 bytes, and 6.7-7.1 at the other 8, through effects in the op cache, the BTB, and the branch predictor. Which position a build gets is an accident of the surrounding code, so comparing two builds conflates a change's effect with where its code landed. Each timed loop now runs from one of 16 out-of-line copies, aligned to 256 bytes and padded in 16-byte steps, which place the loop at each of those 16 positions. A process picks a copy at random, or the one named in `CARBON_BENCH_LAYOUT`, and reports it in the `Layout` counter. Running `bench_runner.py` with enough runs to sample every position, 48 for example, makes its medians and confidence intervals account for layout. In a sweep over 1024 bytes, performance depended only on the loop's address modulo 256, and loop heads are 16-byte aligned, so finer or wider padding found nothing more on this CPU. `CARBON_BENCH_LAYOUT_PAD_STEP` and `CARBON_BENCH_LAYOUT_PAD_RANGE` adjust it. The copies grow `map_benchmark` from 4.8 MB to 7.6 MB. On AArch64, LLVM doesn't align loop heads for generic or Apple CPUs, so they land on any 4-byte boundary and 16-byte steps only reach a quarter of the positions. AArch64 builds pad in 4-byte steps instead, giving 64 layouts and growing `map_benchmark` there to 16.6 MB. Every copy, including the unpadded one, also emits the padding `asm` statement, because its presence changes how the surrounding code is compiled. Assisted-by: Claude Code --------- Co-authored-by: Nicholas Bishop <nbishop@nbishop.net> |
||
|
Chandler Carruth
|
d037848a96 |
Replace hashtable ForEach callback with range-based iteration (#7806)
Replaces the callback-based `ForEach` methods on `RawHashtable`, `Map`,
and
`Set` with a range object supporting range-for loops, structured
bindings, and
the standard range concepts.
- Adds `.entries()` on `Map`, `Set`, and `RawHashtable`, returning a
range that
models `std::ranges::forward_range` and `std::ranges::common_range`.
Obtaining one is an explicit call rather than `begin()`/`end()` on the
container, as scanning a whole table is costly and shouldn't be hidden.
- Iterating a `Map` yields a `std::pair` of key and value references,
which
fits in two registers and is returned without being materialized in
memory.
- `Map::Range` and `Set::Range` are aliases of the raw hashtable's range
rather
than wrappers around it. The raw iterator produces the user-facing
reference
itself -- a `KeyT&` for a set, a pair of references for a map -- picked
by
`StorageEntry`, which is already specialized on whether there is a value
type. That leaves one iterator to reason about instead of three.
- Deletes the rvalue `.entries()` overloads on the owning containers, as
a
range built from a temporary table would dangle. Views don't own their
storage, so the operation remains available on them.
- In release builds, the walk over the groups is a single induction
variable: a
negative byte offset counting up to zero, anchored at the ends of the
metadata and entry arrays. Both arrays are then reached by indexed
addressing
off a base that stays put, and the entry pointer is formed only once a
group
with a present entry has been found.
- In debug builds, the range hashes the table's metadata when it is
built and
re-checks that hash when it is destroyed, catching mutation of the table
while a range is live. It also picks a random starting group and a
random odd
group stride, which varies the traversal order between ranges while
still
visiting every group exactly once. That entropy is drawn when the range
is
built rather than in `begin()`, so `begin()` stays a pure function of
the
range and the multi-pass guarantee holds.
- Removes `ForEachEntry` and all of its callers.
Measured against the iteration benchmark added in its own commit, a
traversal is at or ahead of what the callback compiled to across nearly
the
whole size range. The largest tables spend 3-5% fewer cycles, small
`Set`s as
much as 24% fewer, and instruction counts stay within about 1%. What
remains
behind is a handful of mid-sized `Map`s by up to 1%, and `Set` at 65536,
which
sits at exactly half its load factor, by 2%.
Both revisions were built with `-c opt --copt=-march=x86-64-v3` and
compared
with:
```
./scripts/bench_runner.py --exp_benchmark=... --base_benchmark=... \
--benchmark_args=--benchmark_perf_counters=INSTRUCTIONS,CYCLES \
--benchmark_args='--benchmark_filter=(Set|Map)Iterate<(Set|Map)<' \
--extra_metrics_filter='(INSTRUCTIONS|CYCLES)'
```
Trimmed below to the primary integer configurations and to the two
counters;
the pointer- and string-keyed configurations follow the same pattern.
```
Benchmark ┃ CYCLES ┃ INSTRUCTIONS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
BM_MapIterate<Map<int, int>>/1....... │ 👍 -6.032% p=1.14e-05 │ ?? p=0.752
baseline: │ 12.06 ± 1.520% │ 64 ± 3.125%
experiment: │ 11.33 ± 2.765% │ 65.5 ± 3.817%
│ │
BM_MapIterate<Map<int, int>>/2....... │ ?? p=0.155 │ ?? p=0.343
baseline: │ 7.587 ± 1.285% │ 41 ± 0.000%
experiment: │ 7.652 ± 0.865% │ 41 ± 2.439%
│ │
BM_MapIterate<Map<int, int>>/3....... │ ?? p=0.343 │ 👍 -1.020% p=0.0039
baseline: │ 6.663 ± 4.260% │ 32.67 ± 2.041%
experiment: │ 6.368 ± 12.224% │ 32.33 ± 2.062%
│ │
BM_MapIterate<Map<int, int>>/4....... │ ?? p=0.343 │ 👍 -1.786% p=0.0297
baseline: │ 6.091 ± 15.470% │ 28 ± 3.571%
experiment: │ 5.957 ± 8.932% │ 27.5 ± 3.636%
│ │
BM_MapIterate<Map<int, int>>/8....... │ ?? p=0.323 │ 👍 -1.220% p=0.000148
baseline: │ 4.845 ± 0.800% │ 20.5 ± 0.000%
experiment: │ 4.814 ± 3.585% │ 20.25 ± 0.000%
│ │
BM_MapIterate<Map<int, int>>/16...... │ 👍 -2.195% p=0.00908 │ 👍 0.769% p=6.58e-06
baseline: │ 4.312 ± 0.187% │ 16.25 ± 0.000%
experiment: │ 4.218 ± 2.368% │ 16.13 ± 0.000%
│ │
BM_MapIterate<Map<int, int>>/32...... │ ?? p=0.236 │ 👍 0.442% p=9.53e-06
baseline: │ 4.051 ± 1.084% │ 14.13 ± 0.000%
experiment: │ 4.063 ± 0.737% │ 14.06 ± 0.000%
│ │
BM_MapIterate<Map<int, int>>/64...... │ ?? p=0.693 │ 👎 0.227% p=4.52e-06
baseline: │ 4.021 ± 0.239% │ 13.75 ± 0.000%
experiment: │ 4.019 ± 0.417% │ 13.78 ± 0.000%
│ │
BM_MapIterate<Map<int, int>>/256..... │ 👍 0.360% p=0.00119 │ 👎 0.754% p=1.37e-05
baseline: │ 3.996 ± 0.173% │ 13.47 ± 0.000%
experiment: │ 3.982 ± 0.272% │ 13.57 ± 0.000%
│ │
BM_MapIterate<Map<int, int>>/4096.... │ 👍 0.581% p=1.96e-05 │ 👎 0.923% p=1.96e-05
baseline: │ 4.005 ± 0.816% │ 13.38 ± 0.000%
experiment: │ 3.981 ± 0.192% │ 13.5 ± 0.000%
│ │
BM_MapIterate<Map<int, int>>/65536... │ 👍 -4.957% p=1.14e-05 │ 👎 0.934% p=1.14e-05
baseline: │ 5.307 ± 0.501% │ 13.38 ± 0.000%
experiment: │ 5.044 ± 1.746% │ 13.5 ± 0.000%
│ │
BM_MapIterate<Map<int, int>>/1048576. │ 👍 -3.947% p=9.09e-05 │ 👎 0.935% p=3.3e-05
baseline: │ 6.074 ± 0.807% │ 13.38 ± 0.000%
experiment: │ 5.834 ± 2.159% │ 13.5 ± 0.000%
│ │
BM_MapIterate<Map<int, int>>/16777216 │ ?? p=0.155 │ 👎 0.935% p=2.11e-05
baseline: │ 5.082 ± 3.650% │ 13.38 ± 0.000%
experiment: │ 5.012 ± 1.316% │ 13.5 ± 0.000%
│ │
BM_MapIterate<Map<int, int>>/56...... │ 👎 0.825% p=0.0268 │ 👍 0.270% p=1.14e-05
baseline: │ 3.918 ± 0.501% │ 13.21 ± 0.000%
experiment: │ 3.951 ± 0.342% │ 13.18 ± 0.000%
│ │
BM_MapIterate<Map<int, int>>/224..... │ 👎 0.788% p=0.000504 │ 👎 0.346% p=1.64e-05
baseline: │ 3.895 ± 0.111% │ 12.89 ± 0.000%
experiment: │ 3.926 ± 0.285% │ 12.94 ± 0.000%
│ │
BM_MapIterate<Map<int, int>>/3584.... │ 👎 1.028% p=0.000148 │ 👎 0.545% p=1.14e-05
baseline: │ 3.913 ± 0.427% │ 12.79 ± 0.000%
experiment: │ 3.954 ± 0.325% │ 12.86 ± 0.000%
│ │
BM_MapIterate<Map<int, int>>/57344... │ ?? p=0.236 │ 👎 0.558% p=2.55e-06
baseline: │ 4.574 ± 0.721% │ 12.79 ± 0.000%
experiment: │ 4.51 ± 3.709% │ 12.86 ± 0.000%
│ │
BM_MapIterate<Map<int, int>>/917504.. │ 👍 -3.826% p=6.58e-06 │ 👎 0.559% p=2.33e-05
baseline: │ 5.221 ± 0.507% │ 12.79 ± 0.000%
experiment: │ 5.021 ± 0.556% │ 12.86 ± 0.000%
│ │
BM_MapIterate<Map<int, int>>/14680064 │ 👍 -3.839% p=1.37e-05 │ 👎 0.559% p=3.31e-05
baseline: │ 5.129 ± 1.194% │ 12.79 ± 0.000%
experiment: │ 4.932 ± 1.475% │ 12.86 ± 0.000%
│ │
Benchmark ┃ CYCLES ┃ INSTRUCTIONS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
BM_SetIterate<Set<int>>/1....... │ 👍 -3.104% p=0.000583 │ ?? p=0.206
baseline: │ 11.2 ± 6.323% │ 60 ± 3.333%
experiment: │ 10.85 ± 5.820% │ 61 ± 3.279%
│ │
BM_SetIterate<Set<int>>/2....... │ 👍 -7.037% p=0.0362 │ ?? p=0.155
baseline: │ 7.086 ± 16.857% │ 37 ± 0.000%
experiment: │ 6.587 ± 0.479% │ 36 ± 4.167%
│ │
BM_SetIterate<Set<int>>/3....... │ 👎 1.400% p=2.34e-05 │ 👍 -1.163% p=0.00136
baseline: │ 5.363 ± 0.463% │ 28.67 ± 2.326%
experiment: │ 5.438 ± 32.763% │ 28.33 ± 1.176%
│ │
BM_SetIterate<Set<int>>/4....... │ ?? p=0.968 │ ?? p=0.286
baseline: │ 4.642 ± 32.751% │ 23.5 ± 2.128%
experiment: │ 4.658 ± 38.416% │ 23.63 ± 3.704%
│ │
BM_SetIterate<Set<int>>/8....... │ 👍 -23.823% p=3.74e-06 │ 👍 -1.515% p=5.52e-05
baseline: │ 4.701 ± 6.589% │ 16.5 ± 0.000%
experiment: │ 3.581 ± 7.790% │ 16.25 ± 0.000%
│ │
BM_SetIterate<Set<int>>/16...... │ 👍 -4.502% p=1.37e-05 │ 👍 -1.020% p=3.31e-05
baseline: │ 3.124 ± 0.585% │ 12.25 ± 0.000%
experiment: │ 2.983 ± 0.625% │ 12.13 ± 0.000%
│ │
BM_SetIterate<Set<int>>/32...... │ 👍 -4.032% p=5.46e-06 │ 👍 0.617% p=1.96e-05
baseline: │ 2.957 ± 0.260% │ 10.13 ± 0.000%
experiment: │ 2.838 ± 0.434% │ 10.06 ± 0.000%
│ │
BM_SetIterate<Set<int>>/64...... │ 👍 -5.054% p=4.52e-06 │ 👎 0.321% p=1.37e-05
baseline: │ 2.937 ± 0.301% │ 9.75 ± 0.000%
experiment: │ 2.788 ± 1.143% │ 9.781 ± 0.000%
│ │
BM_SetIterate<Set<int>>/256..... │ 👍 -5.325% p=1.14e-05 │ 👎 1.073% p=6.58e-06
baseline: │ 2.916 ± 0.220% │ 9.469 ± 0.000%
experiment: │ 2.761 ± 0.142% │ 9.57 ± 0.000%
│ │
BM_SetIterate<Set<int>>/4096.... │ 👍 -4.865% p=4.52e-06 │ 👎 1.317% p=2.34e-05
baseline: │ 2.921 ± 0.194% │ 9.381 ± 0.000%
experiment: │ 2.779 ± 0.224% │ 9.504 ± 0.000%
│ │
BM_SetIterate<Set<int>>/65536... │ 👎 1.961% p=3.93e-05 │ 👎 1.332% p=1.49e-05
baseline: │ 4.015 ± 0.482% │ 9.375 ± 0.000%
experiment: │ 4.094 ± 0.613% │ 9.5 ± 0.000%
│ │
BM_SetIterate<Set<int>>/1048576. │ 👍 -4.843% p=1.14e-05 │ 👎 1.333% p=5.38e-06
baseline: │ 5.239 ± 0.144% │ 9.375 ± 0.000%
experiment: │ 4.986 ± 0.139% │ 9.5 ± 0.000%
│ │
BM_SetIterate<Set<int>>/16777216 │ 👍 0.840% p=0.0362 │ 👎 1.333% p=2.52e-06
baseline: │ 3.719 ± 1.420% │ 9.375 ± 0.000%
experiment: │ 3.688 ± 1.308% │ 9.5 ± 0.000%
│ │
BM_SetIterate<Set<int>>/56...... │ 👍 -2.857% p=9.53e-06 │ 👍 0.388% p=3.31e-05
baseline: │ 2.942 ± 0.439% │ 9.214 ± 0.000%
experiment: │ 2.858 ± 0.619% │ 9.179 ± 0.000%
│ │
BM_SetIterate<Set<int>>/224..... │ 👍 -2.161% p=2.34e-05 │ 👎 0.502% p=4.52e-06
baseline: │ 2.888 ± 0.347% │ 8.893 ± 0.000%
experiment: │ 2.826 ± 0.450% │ 8.938 ± 0.000%
│ │
BM_SetIterate<Set<int>>/3584.... │ 👍 -1.750% p=6.58e-06 │ 👎 0.793% p=2.34e-05
baseline: │ 2.89 ± 0.261% │ 8.792 ± 0.000%
experiment: │ 2.84 ± 0.411% │ 8.862 ± 0.000%
│ │
BM_SetIterate<Set<int>>/57344... │ ?? p=0.502 │ 👎 0.812% p=2.78e-05
baseline: │ 3.684 ± 4.246% │ 8.786 ± 0.000%
experiment: │ 3.644 ± 4.431% │ 8.857 ± 0.000%
│ │
BM_SetIterate<Set<int>>/917504.. │ 👍 -2.629% p=0.000148 │ 👎 0.813% p=3.08e-06
baseline: │ 4.372 ± 0.693% │ 8.786 ± 0.000%
experiment: │ 4.257 ± 0.210% │ 8.857 ± 0.000%
│ │
BM_SetIterate<Set<int>>/14680064 │ 👍 -2.927% p=0.0219 │ 👎 0.813% p=3.03e-06
baseline: │ 4.154 ± 3.286% │ 8.786 ± 0.000%
experiment: │ 4.032 ± 3.198% │ 8.857 ± 0.000%
│ │
```
Assisted-by: Antigravity with Opus
|
||
 Dana Jansens
|
49345352d6 |
Remove redundant use of typename (#7751)
clang-tidy 24 warns about these |
||
 Thomas Köppe
|
bf32da8dad |
Add missing standard library header inclusions (#5316)
Discovered by clang-tidy. |
||
 
|
4845f40dff |
Switch CARBON_CHECK to a format string API (#4285)
This switches `DCHECK` and `FATAL` as well. The goal is to reduce the code size impact of these assertions so that we can keep more of them enabled. Currently, the largest cost I see from `CHECK` is not the actual check or the cold code itself, but actually the failure to inline trivial functions due to the presence of the cold code. This means that our goal isn't to reduce apparent code size in the final binary but the LLVM IR cost assessed for these routines in the inliner, which closely correlates with code size but is a bit different. As discussed in #4283, experimentation shows that a single function call with a minimal number of arguments is the lowest cost model for these. This is easily achieved with a format-string API that internally uses `llvm::formatv`. This PR is essentially the `CHECK` version of #4283. However, the check macros are substantially harder to make work with both format strings and streaming because they also take a condition. Also, unexpectedly, I was very successful at devising a regular expression based automated rewrite from the streaming to the format string form with only low 10s of manual fixes. This includes compacting strings broken up across lines, etc. Given how well that went, I've prepared this PR which just directly switches to the format string API and migrate everything to use it. One nice side-effect is that the format string approach ends up greatly simplifying the implementation here as well. This is ... *shockingly* effective. Parsing speeds up by more than 3% with just this change. And checking speeds up by **8%** with this change alone: ``` BM_CompileAPIFileDenseDecls<Phase::Parse>/256 86.3µs ± 1% 82.9µs ± 1% -3.94% (p=0.000 n=17+19) BM_CompileAPIFileDenseDecls<Phase::Parse>/1024 431µs ± 1% 415µs ± 1% -3.76% (p=0.000 n=18+19) BM_CompileAPIFileDenseDecls<Phase::Parse>/4096 1.77ms ± 1% 1.71ms ± 1% -3.18% (p=0.000 n=18+19) BM_CompileAPIFileDenseDecls<Phase::Parse>/16384 7.44ms ± 1% 7.17ms ± 2% -3.56% (p=0.000 n=18+20) BM_CompileAPIFileDenseDecls<Phase::Parse>/65536 30.7ms ± 1% 29.7ms ± 1% -3.15% (p=0.000 n=18+20) BM_CompileAPIFileDenseDecls<Phase::Parse>/262144 131ms ± 1% 127ms ± 1% -2.81% (p=0.000 n=18+18) BM_CompileAPIFileDenseDecls<Phase::Check>/256 878µs ± 2% 800µs ± 1% -8.91% (p=0.000 n=19+20) BM_CompileAPIFileDenseDecls<Phase::Check>/1024 1.88ms ± 2% 1.72ms ± 1% -8.56% (p=0.000 n=19+20) BM_CompileAPIFileDenseDecls<Phase::Check>/4096 5.78ms ± 2% 5.28ms ± 1% -8.70% (p=0.000 n=20+18) BM_CompileAPIFileDenseDecls<Phase::Check>/16384 21.9ms ± 1% 20.1ms ± 1% -8.02% (p=0.000 n=18+20) BM_CompileAPIFileDenseDecls<Phase::Check>/65536 90.4ms ± 2% 83.1ms ± 1% -8.04% (p=0.000 n=19+20) BM_CompileAPIFileDenseDecls<Phase::Check>/262144 381ms ± 2% 352ms ± 1% -7.79% (p=0.000 n=19+19) ``` --------- Co-authored-by: Richard Smith <richard@metafoo.co.uk> Co-authored-by: josh11b <15258583+josh11b@users.noreply.github.com> |
||
|
Chandler CarruthandRichard Smith
|
3be57b71e0 |
Collect more detailed metrics on hashtables. (#4046)
Previously we just looked at the raw count of probed keys. Now, we compute the average and max of both the probe _distance_ measured in the number of _groups_ probed, and the number of probe _compares_ measured in the compares required _before_ finding the matching entry. This lets us understand the relative impact of probe-distance vs. tag collisions on a given set of benchmark keys. Some of this is motivated by considering additional optimization techniques similar to those used in Boost's table and the F14 table from Facebook/Meta. --------- Co-authored-by: Richard Smith <richard@metafoo.co.uk> |
||
|
Chandler Carruthandjosh11b
|
21a81bc59e |
Introduce custom hash table data structures. (#3940)
The hash table design is heavily based on Abseil's ["Swiss Tables"][swiss-tables] design. It uses an array of bytes storing metadata about each entry and an array of entries where each is a pair of key and value. The metadata byte consists of 7-bits of hash of the key (distinct from the bits used to index the table), and one bit indicating the presence of a special entry -- either empty or deleted. [swiss-tables]: https://abseil.io/about/design/swisstables There are a large range of optimizations and other nuanced aspects of this hash table design and implementation, a good point to understand that context is `raw_hashtable.h` which has an overview of the design and references to various other files for relevant details. --------- Co-authored-by: josh11b <15258583+josh11b@users.noreply.github.com> |