Fix duplicate and biased thread picks in the wall-clock reservoir sampler - #844

What does this PR do?:

Fixes the skip step in ReservoirSampler (reservoirSampler.h). The wall-clock engines use it to choose which threads to signal on each tick.

• The sampler implements Algorithm L (Li, 1994). After an item is placed, the next candidate is one past that item plus a geometric skip. The code did target += skip and left out the +1. When the skip is 0, which happens often while the reservoir is still filling, the same input item gets placed again.
• The step now goes through a small advance(from, n, weight) helper that adds the +1.
• The helper also compares the skip as a double before converting it to int. A skip larger than INT_MAX, or the -inf you get when 1 - weight rounds to 1.0, ends the scan instead of hitting an undefined float-to-int conversion. That replaces the assert(target >= 0), so <cassert> is no longer included.
• The initial jump (_size + skip) was already correct and keeps the same behaviour.

Motivation:

The bug has been present since the sampler was added in #126. #794 changed the RNG but kept the same step. It has two effects on wall-clock sampling:

1. Duplicates. A tick can signal the same thread twice and use up a slot that should go to another thread.
2. Bias. The item just after the initial fill is chosen more often than the others. That item sits at a fixed position in ThreadFilter::collect() order, so the extra samples always go to the same thread.

A simulation of the exact loop with the default wall_threads_per_tick=16 gives:

A standalone probe built against the production header shows the same behaviour:

• n=4, k=1: per-item counts of 250494 / 313019 / 231992 / 204495 over 1M draws, where ~250000 each is expected.
• n=10, k=3: 35914 of 100000 samples contained a duplicate.

Sampling is only involved when there are more eligible threads than wall_threads_per_tick. With n <= k every thread is taken, and that path is unchanged.

Additional Notes:

• This is independent of feat(wall): support signal suppression for unfiltered threads #663. With precheck plus unfiltered wall tracking, feat(wall): support signal suppression for unfiltered threads #663 uses its own partial Fisher–Yates selector and bypasses this class. Every other configuration still calls reservoir.sample(), including the default and precheck in eager mode. The two PRs touch no common files.
• The existing ReservoirSampler tests only checked sample size, reuse and stream variation, which is why this went unnoticed.

How to test the change?:

New gtests in xorshift_ut.cpp, run on the production ReservoirSampler:

• ReservoirSamplerTest.SampleOfDistinctInputHasNoDuplicates: for (n, k) in {(4,1), (10,3), (17,16), (100,16), (2048,16), (16,16)}, every sample of distinct inputs has exactly k distinct values. After the fix this is deterministic, because target only ever increases.
• ReservoirSamplerTest.InclusionFrequencyIsUniform: per-item inclusion frequency stays within ±5% of k/n for (4,1), (10,3) and (40,16). The tolerance is far from the buggy values, so the address-derived seed doesn't make it flaky.

Results:

• Without the fix: duplicate selection for n=10 k=3, plus frequency failures on items 1–3 (n=4) and 0–2 (n=10).
• With the fix: :ddprof-lib:gtestDebug_xorshift_ut and :ddprof-lib:gtestRelease_xorshift_ut pass, 29/29 on macOS arm64.

For Datadog employees:

• If this PR touches code that signs or publishes builds or packages, or handles
  credentials of any kind, I've requested a security review (run the dd:platform-security-review
  skill, or file a request via the PSEC review form).
  bewaire also runs automatically on every PR.
• This PR doesn't touch any of that.
• JIRA: [JIRA-XXXX]

🤖 Generated with Claude Code