You’re reviewing a Rust pull request that changes how a batch job counts unique event IDs. The tests pass, and on the first benchmark the patch uses about 24% fewer instructions than the original code. Would you merge it?
Now try a second batch. Both batches contain 2,048 IDs. In the first, the same eight values repeat. In the second, every ID is different. The patch still gets the right answer, but on that second batch CodSpeed’s CPU simulation counts 3.28 times as many instruction references as it did for the original code.
In this tutorial, we’ll run both benchmarks, read the profile to see where the extra work comes from, and fix the patch while keeping most of the gain on repeated IDs. You can run the lab locally without a CodSpeed account. There’s also an optional GitHub Actions walkthrough for comparing both workloads in a pull request.
A telemetry job has to count the distinct event IDs in a batch. A patch replaces a BTreeSet with a small Vec, the tests pass, and the duplicate-heavy benchmark does less work. What would you want to see before merging it?
In this lab, we'll run the same patch on another batch with exactly the same number of IDs. On that second input, the patch used 3.28 times as many instruction references as the baseline in the measured example. The result is still correct. The assumption about the input is what breaks.
We'll use CodSpeed to reproduce that result, find the work that's growing, and try a version that keeps the fast path without letting the scan grow unchecked. The local lab doesn't require an account. There's a separate GitHub Actions workflow if you want CodSpeed to compare the same cases in a pull request.
Make the input shape part of the benchmark
Both fixtures have 2,048 IDs. What changes is cardinality, which is the number of different IDs in the batch. Keeping the batch size fixed lets us see what happens when the data changes without giving either implementation a smaller job.
| Workload | Rows | Distinct IDs | What it represents |
|---|---|---|---|
duplicate-burst |
2,048 | 8 | A short set of event IDs repeated through the batch |
all-distinct |
2,048 | 2,048 | A replay in which each event ID is new |
The existing CodSpeed Rust guide shows how to write function benchmarks with divan. We'll take a different route here and use CodSpeed's named command benchmarks. This measures the whole CLI command, including startup. We keep the command, fixture generator, and output checks the same and change only the deduplication code.
Set up the lab
Use x86-64 Ubuntu, Bash, curl, a C linker, and Rustup. This lab was checked with Ubuntu 26.04.1, Rust 1.95.0, and CodSpeed CLI 5.7.0. The exact release archive below is for Linux x86-64. Use a Linux development VM if your usual machine doesn't match rather than changing a production host to run a tutorial.
The lab itself has no external Rust dependencies. Installing Rust and CodSpeed and fetching the simulator the first time need network access. CodSpeed can install the simulation prerequisites on its first run, so use an environment where you can install development packages if needed (CodSpeed CLI installation and supported platforms).
rustup toolchain install 1.95.0 --profile minimal
mkdir -p pr-cardinality/src
cd pr-cardinality
Create the binary and its tests
Save this as Cargo.toml. The release build keeps debug information so you can see Rust function names in a profile (CodSpeed's command benchmark guide).
[package]
name = "pr-cardinality"
version = "0.1.0"
edition = "2024"
publish = false
[profile.release]
debug = 1
strip = "none"
Start with the tree implementation in src/dedupe.rs. All three versions will take the same slice and return a count. They don't have to return the IDs or preserve their order.
use std::collections::BTreeSet;
#[inline(never)]
pub fn count_distinct(ids: &[u32]) -> usize {
let mut seen = BTreeSet::new();
for &id in ids {
seen.insert(id);
}
seen.len()
}
Save the following as src/main.rs. The arithmetic permutes the 2,048 IDs so the distinct case doesn't arrive in sorted order. Taking those same values modulo eight gives us the duplicate-heavy case. We build the fixture once per process and count it 24 times through the same code path so the useful work stands out from process startup. black_box helps keep the optimizer from treating the measured repetitions as redundant (Rust's black_box documentation).
mod dedupe;
use dedupe::count_distinct;
use std::{env, hint::black_box, process};
const ROWS: u32 = 2_048;
const PASSES: usize = 24;
fn fixture(case: &str) -> Option<(Vec<u32>, usize)> {
let distinct = match case {
"duplicate-burst" => 8,
"all-distinct" => ROWS,
_ => return None,
};
let ids = (0..ROWS)
.map(|i| ((i * 73 + 19) % ROWS) % distinct)
.collect();
Some((ids, distinct as usize))
}
fn main() {
let case = env::args().nth(1).unwrap_or_default();
let Some((ids, expected)) = fixture(&case) else {
eprintln!("usage: pr-cardinality <duplicate-burst|all-distinct>");
process::exit(2);
};
let mut checksum = 0;
for _ in 0..PASSES {
checksum += black_box(count_distinct(black_box(ids.as_slice())));
}
assert_eq!(checksum, expected * PASSES);
println!(
"{case}: rows={} distinct={expected} checksum={checksum}",
ids.len()
);
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn benchmark_fixtures_keep_their_shape() {
for case in ["duplicate-burst", "all-distinct"] {
let (ids, distinct) = fixture(case).unwrap();
assert_eq!(ids.len(), ROWS as usize);
assert_eq!(count_distinct(&ids), distinct);
}
}
#[test]
fn around_the_promotion_boundary() {
for distinct in [15, 16, 17, 33] {
let ids: Vec<_> = (0..128).map(|i| i % distinct).collect();
assert_eq!(count_distinct(&ids), distinct as usize);
}
}
#[test]
fn late_new_ids_still_count() {
let mut ids = vec![5; 128];
ids.extend(100..116);
assert_eq!(count_distinct(&ids), 17);
}
#[test]
fn empty_and_repeated_extremes() {
assert_eq!(count_distinct(&[]), 0);
assert_eq!(count_distinct(&[u32::MAX, 0, u32::MAX]), 2);
}
}
Check both outputs before you measure. The test suite also checks the behavior around the cutoff we'll introduce later.
cargo +1.95.0 generate-lockfile --offline
cargo +1.95.0 test --locked --offline
cargo +1.95.0 build --release --locked --offline
./target/release/pr-cardinality duplicate-burst
./target/release/pr-cardinality all-distinct
The observed program output was the same for all three implementations:
duplicate-burst: rows=2048 distinct=8 checksum=192
all-distinct: rows=2048 distinct=2048 checksum=49152
Measure the baseline with CodSpeed
Download the CodSpeed 5.7.0 Linux release and verify the archive before adding it to this shell's PATH. The expected digest is listed in GitHub's release metadata.
tools_dir="$(mktemp -d)"
asset=codspeed-runner-x86_64-unknown-linux-musl.tar.gz
(
cd "$tools_dir" || exit 1
curl -fLSs -o "$asset" \
"https://github.com/CodSpeedHQ/codspeed/releases/download/v5.7.0/$asset" &&
printf '%s %s\n' \
6cc4177e65cab1467c897991e8a9245dd825376f3f03cd1577c9df00dedf7d5f "$asset" |
sha256sum -c - &&
tar -xzf "$asset"
) && export PATH="$tools_dir/codspeed-runner-x86_64-unknown-linux-musl:$PATH"
codspeed --version
Put this codspeed.yml in the lab root. Keep the benchmark names as you change the program. Two names give you two baseline comparisons instead of one result that depends on whichever fixture you ran.
benchmarks:
- name: duplicate-burst
exec: ./target/release/pr-cardinality duplicate-burst
- name: all-distinct
exec: ./target/release/pr-cardinality all-distinct
We'll use the CPU Simulation instrument because the question is how much CPU work a single-process computation does, not how long a production request takes. For the local exercise, 5.7.0 has a debug-only --skip-upload option. It lets you retain the profiles without signing in or creating a hosted result. Keep the CLI pinned for this path. The GitHub Actions setup below uses the regular upload path instead.
Save the helper as measure.sh. It tests and rebuilds the current code, runs both commands through CodSpeed, and pulls the Ir summary from each program's profile. Ir is Callgrind's instruction-read event count, a count of executed instructions in the profile, not milliseconds or the efficiency number in CodSpeed's hosted report (Callgrind manual, CodSpeed CPU Simulation metrics).
#!/usr/bin/env bash
set -euo pipefail
tag="${1:?Usage: bash measure.sh baseline|linear|bounded}"
case "$tag" in
baseline|linear|bounded) ;;
*) printf 'Unknown run label: %s\n' "$tag" >&2; exit 2 ;;
esac
cargo +1.95.0 test --locked --offline
cargo +1.95.0 build --release --locked --offline
profiles="$(mktemp -d "$PWD/target/codspeed-${tag}.XXXXXX")"
printf 'Profiles: %s\n' "$profiles"
codspeed run -m simulation --skip-upload --profile-folder "$profiles"
awk '
FNR == 1 { workload = ""; field = 0; printed = 0 }
$1 == "cmd:" && $2 == "./target/release/pr-cardinality" && NF == 3 {
workload = $3
}
$1 == "events:" { for (i = 2; i <= NF; i++) if ($i == "Ir") field = i }
$1 == "summary:" && workload != "" && field && !printed && $field > 0 {
printf "%s: %s Ir\n", workload, $field
count[workload]++
printed = 1
}
END {
if (count["duplicate-burst"] != 1 || count["all-distinct"] != 1) {
print "Expected one nonzero Ir summary per workload" > "/dev/stderr"
exit 1
}
}
' "$profiles"/*.out | LC_ALL=C sort
Run the baseline and save its output. The argument labels a run. It doesn't select an algorithm, so leave the tree implementation in place for this first command.
bash measure.sh baseline
The last two lines should be nonzero Ir counts, one for each workload. If that doesn't happen, stop here. Check that you're in the directory with codspeed.yml, that codspeed --version reports 5.7.0, and that your environment can prepare the simulator. codspeed setup -m simulation is the standalone setup command in this version. No dashboard response is expected when upload is disabled.
Try the patch that looks faster
Replace src/dedupe.rs with the linear implementation. A Vec fits the first fixture well because the list of values we've seen stays short. What happens to the cost of contains if each new ID is absent from the list?
#[inline(never)]
pub fn count_distinct(ids: &[u32]) -> usize {
let mut seen = Vec::with_capacity(16);
for &id in ids {
if !seen.contains(&id) {
seen.push(id);
}
}
seen.len()
}
bash measure.sh linear
All four tests passed. The duplicate burst dropped from 3,127,282 to 2,379,940 Ir, about 23.90% fewer instruction references. If we stopped at that benchmark, we'd miss that the all-distinct input went from 17,245,209 to 56,511,822 Ir. An input where each search misses makes the repeated linear scan do quadratic membership work as the batch grows.
Find where the work went
For a local look, paste the directory printed after Profiles: by the linear run. Select the .out file for the program, not the launcher or CodSpeed's harness. If callgrind_annotate is installed, it can summarize the profile by instruction count (Callgrind annotation options).
read -r -p "Profiles directory from the linear run: " profiles
for profile in "$profiles"/*.out; do
if grep -Eq '^cmd:[[:space:]]+\./target/release/pr-cardinality all-distinct$' "$profile"; then
compatible="$(mktemp)"
sed '/^cfni=/d' "$profile" > "$compatible"
callgrind_annotate --show=Ir --threshold=99 --auto=no "$compatible" |
sed -n '18,32p'
rm -f -- "$compatible"
fi
done
The sed filter removes only cfni= metadata records from a temporary copy. The stock annotator warned about those records in the checked environment, and the original CodSpeed profile stays intact. The all-distinct linear profile showed 56,511,822 program Ir; one row for the inlined Rust slice comparison in count_distinct accounted for 34,897,920 of them, or 61.75%. If you later upload the benchmarks, the base, head, and diff flamegraphs are another way to start that investigation.
Keep the fast path, then cap the scan
We want the short scan when the values keep repeating. We don't want to grow that scan for the entire replay. Give the Vec a limit of 16 distinct IDs and promote to a tree when you find the 17th. The current ID has already been found to be new, so the fallback loop must start at index, not index + 1.
Replace src/dedupe.rs one more time:
use std::collections::BTreeSet;
const SMALL_LIMIT: usize = 16;
#[inline(never)]
pub fn count_distinct(ids: &[u32]) -> usize {
let mut small = Vec::with_capacity(SMALL_LIMIT);
for (index, &id) in ids.iter().enumerate() {
if small.contains(&id) {
continue;
}
if small.len() == SMALL_LIMIT {
let mut seen = BTreeSet::new();
seen.extend(small);
for &remaining in &ids[index..] {
seen.insert(remaining);
}
return seen.len();
}
small.push(id);
}
small.len()
}
bash measure.sh bounded
Review all three results
These are observed local instruction references, not estimates of production latency. Three fresh CodSpeed invocations per implementation from the same working directory returned the same counts in that series. A rerun from another directory differed slightly in the totals and preserved the same ordering. The build was Rust 1.95.0 on x86-64 Ubuntu 26.04.1 with CodSpeed CLI 5.7.0 and its valgrind-3.26.0.codspeed14 simulator.
| Implementation | Duplicate burst Ir
|
Change vs. tree | All distinct Ir
|
Change vs. tree |
|---|---|---|---|---|
| Tree baseline | 3,127,282 | Reference | 17,245,209 | Reference |
| Linear scan | 2,379,940 | -23.90% | 56,511,822 | +227.70% |
| Bounded scan, then tree | 2,528,176 | -19.16% | 17,916,693 | +3.89% |
For this exercise, propose a review rule: keep the duplicate-burst improvement and allow at most 5% additional Ir on the all-distinct case. The linear patch fails that rule. The bounded patch passes, although it still does a little additional work on the all-distinct case. If your replay cannot tolerate that cost, the tree is the better choice until you find another option.
The percentages in the table are changes in Ir relative to the tree. They aren't the same as CodSpeed's hosted speed impact, which uses the selected instrument's performance measurement and a different formula (CodSpeed impact metrics). Don't copy the lab's 5% instruction-count budget into a dashboard threshold as though it measured the same thing.
Make the correctness test fail on purpose
Change &ids[index..] to &ids[index + 1..] for one run of cargo +1.95.0 test --locked --offline. This simulates dropping the ID that caused the promotion. In the checked mutation, the all-distinct test got 2,047 instead of 2,048, and the late-new-ID test got 16 instead of 17. Some simpler cases still passed because a skipped value happened to appear again.
Restore &ids[index..] and rerun bash measure.sh bounded. The tests should return to four passing before the script collects another profile. A smaller Ir count from an implementation that lost an ID is not an optimization.
Carry both workloads into a pull request
This part requires a GitHub repository you control and the CodSpeed GitHub App. The local benchmark runs above were executed. The hosted workflow below was checked with actionlint and against CodSpeed's action inputs, but wasn't uploaded or exercised against a connected repository for this lab.
Save this as .github/workflows/codspeed.yml. Keep Cargo.lock in the repository and add /target/ to .gitignore. Don't put a secret in the workflow. The job uses CodSpeed's OIDC configuration and skips pull requests from forks for this exercise. The run input on the CodSpeed action is deliberately omitted so the runner uses the commands in codspeed.yml (command benchmarks in CI, v5 action inputs).
name: CodSpeed benchmarks
on:
push:
branches: [main]
pull_request:
branches: [main]
workflow_dispatch:
permissions:
contents: read
jobs:
benchmarks:
if: github.event_name != 'pull_request' || github.event.pull_request.head.repo.full_name == github.repository
runs-on: ubuntu-24.04
permissions:
contents: read
id-token: write
steps:
- uses: actions/checkout@v7.0.0
with:
persist-credentials: false
- name: Use the pinned Rust toolchain
run: rustup toolchain install 1.95.0 --profile minimal
- name: Test and build the release binary
run: |
cargo +1.95.0 test --locked
cargo +1.95.0 build --release --locked
- name: Collect both workloads
uses: CodSpeedHQ/action@v5
with:
mode: simulation
runner-version: v5.7.0
-
Establish
main. Put the tree implementation,codspeed.yml, and the workflow onmainin a practice repository. Import that repository in CodSpeed. Run the workflow onmainand confirm a successful CodSpeed report with both benchmarks before continuing. A passing Actions job by itself does not prove you have a base report for comparison (baseline selection). -
Open a same-repository PR. Branch from the baseline and apply only the linear change in
src/dedupe.rs. In the CodSpeed report, inspect both named rows, the base and head revisions, and any warnings. A small change that produces no inline comment may still have a report you can open from the check. -
Rerun the fix against the same base. Commit the bounded version to the same PR without changing the fixture or benchmark names. Inspect the all-distinct row again. Don't assume the hosted values match the local
Ircounts. - Decide what should block a merge. Start by observing the two stable cases. Choose per-benchmark thresholds based on repeatability and the cost you can tolerate. CodSpeed can flag an individual benchmark independently of the overall headline. Require its performance status check only after the signal is useful (how individual regressions are reported).
If there is no valid comparison, first check that main has a successful report. Also check that the benchmark names and instrument match and that the runner versions are comparable. CodSpeed's v5 simulation change, for example, requires a fresh baseline for runs made with older versions (v5 release notes).
Try a third workload
Make a 2,048-ID fixture that repeats eight familiar values for most of the batch and introduces new IDs near the end. Before you run it, predict when the bounded version will promote. Add the case to codspeed.yml, check its exact distinct count in a test, and compare all three implementations again. A useful result to take back to your team is a table of the three workloads, two separate correctness and performance checks, and one sentence defending the merge decision.
For your own service, choose inputs by what changes the amount of work: the number of distinct keys, where matches occur, how skewed the values are, or when the fast path gives up. Start by holding the other variables still. If your real question involves I/O or user-facing latency, choose a representative end-to-end workload and an instrument that measures it; this CPU simulation is not that test (CodSpeed instrument selection).
When you're done, cargo +1.95.0 clean in this lab directory removes the builds and the local profiles under target/. Keep the profiles you want to review first. Nothing needs to be removed from CodSpeed for a local-only run.
Top comments (0)