Skip to content

Commit 6ec2e31

Browse files
authored
Merge pull request #4835 from Zac-HD/claude/hypothesis-3176-design-hr97hh
Improve target() when-to-optimise heuristic
2 parents 459cc24 + 0570b5b commit 6ec2e31

4 files changed

Lines changed: 274 additions & 13 deletions

File tree

‎hypothesis/RELEASE.rst‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
RELEASE_TYPE: patch
2+
3+
This release improves our heuristic for when to run the |Phase.target| phase,
4+
which optimises scores from :func:`hypothesis.target`. Behaviour is unchanged
5+
for :obj:`~hypothesis.settings.max_examples` below 1000. For larger budgets
6+
we now start optimising much earlier, and alternate between generation and
7+
optimisation for as long as scores keep improving, instead of running a
8+
single optimisation pass halfway through the run. Exploratory searches using
9+
:func:`~hypothesis.target` with a large budget should now make much better
10+
use of it (:issue:`3176`).

‎hypothesis/src/hypothesis/internal/conjecture/engine.py‎

Lines changed: 77 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -336,6 +336,14 @@ def __init__(
336336
)
337337
self.best_examples_of_observed_targets: dict[str, ConjectureResult] = {}
338338

339+
# Scheduling state for the target phase. For large max_examples we
340+
# interleave repeated optimisation passes with generation, aiming to
341+
# spend up to half the budget on optimisation in total - see
342+
# _should_optimise_now.
343+
self._target_valid_spent: int = 0
344+
self._next_optimise_at: float = math.inf
345+
self._best_scores_at_last_pass: dict[str, float] | None = None
346+
339347
# We keep the pareto front in the example database if we have one. This
340348
# is only marginally useful at present, but speeds up local development
341349
# because it means that large targets will be quickly surfaced in your
@@ -1268,8 +1276,16 @@ def generate_new_examples(self) -> None:
12681276
# the distribution towards small (and less powerful) examples. Flaky
12691277
# and loud health checks are better than silent performance degradation.
12701278
small_example_cap = min(self.settings.max_examples // 10, 50)
1271-
optimise_at = max(self.settings.max_examples // 2, small_example_cap + 1, 10)
1272-
ran_optimisations = False
1279+
# For small budgets we run a single optimisation pass halfway through
1280+
# the budget, which experience shows is roughly optimal. For larger
1281+
# budgets we instead start optimising early and interleave repeated
1282+
# passes with generation - see _should_optimise_now.
1283+
if self.settings.max_examples < 1000:
1284+
self._next_optimise_at = max(
1285+
self.settings.max_examples // 2, small_example_cap + 1, 10
1286+
)
1287+
else:
1288+
self._next_optimise_at = max(200, small_example_cap + 1)
12731289
self._switch_to_hypothesis_provider = False
12741290

12751291
while self.should_generate_more():
@@ -1353,13 +1369,8 @@ def generate_new_examples(self) -> None:
13531369
# actually exhausts our budget: It might finish running and we
13541370
# discover that actually we still could run a bunch more test cases
13551371
# if we want.
1356-
if (
1357-
self.valid_examples >= max(small_example_cap, optimise_at)
1358-
and not ran_optimisations
1359-
):
1360-
ran_optimisations = True
1361-
self._current_phase = "target"
1362-
self.optimise_targets()
1372+
if self._should_optimise_now():
1373+
self._run_optimise_pass()
13631374

13641375
def generate_mutations_from(self, data: ConjectureData | ConjectureResult) -> None:
13651376
# A thing that is often useful but rarely happens by accident is
@@ -1519,31 +1530,83 @@ def generate_mutations_from(self, data: ConjectureData | ConjectureResult) -> No
15191530
else:
15201531
failed_mutations += 1
15211532

1522-
def optimise_targets(self) -> None:
1533+
def _should_optimise_now(self) -> bool:
1534+
"""Decide whether to run an optimisation pass at this point in generation."""
1535+
if not self.should_optimise:
1536+
return False
1537+
if self.valid_examples >= self._next_optimise_at:
1538+
return True
1539+
# After the first pass, we should optimize if we have found a new best score from
1540+
# generation and we have the budget to continue optimizing.
1541+
return (
1542+
self._best_scores_at_last_pass is not None
1543+
and self.settings.max_examples >= 1000
1544+
and self._target_valid_spent < self.settings.max_examples // 2
1545+
and any(
1546+
score > self._best_scores_at_last_pass.get(target, NO_SCORE)
1547+
for target, score in self.best_observed_targets.items()
1548+
)
1549+
)
1550+
1551+
def _run_optimise_pass(self) -> None:
1552+
"""Run one optimisation pass, then schedule the next one."""
1553+
if self.settings.max_examples < 1000:
1554+
# We'll only ever run a single optimization pass in this case.
1555+
max_valid = None
1556+
else:
1557+
remaining = self.settings.max_examples // 2 - self._target_valid_spent
1558+
max_valid = self.valid_examples + min(max(200, remaining // 4), remaining)
1559+
self._current_phase = "target"
1560+
start_valid = self.valid_examples
1561+
improved = False
1562+
try:
1563+
improved = self.optimise_targets(max_valid=max_valid)
1564+
finally:
1565+
spent = self.valid_examples - start_valid
1566+
self._target_valid_spent += spent
1567+
# Alternate with generation on a fair-share schedule for as long
1568+
# as passes keep finding improvements and budget remains.
1569+
if (
1570+
max_valid is not None
1571+
and improved
1572+
and self._target_valid_spent < self.settings.max_examples // 2
1573+
):
1574+
self._next_optimise_at = self.valid_examples + spent
1575+
else:
1576+
self._next_optimise_at = math.inf
1577+
self._best_scores_at_last_pass = dict(self.best_observed_targets)
1578+
self._current_phase = "generate"
1579+
1580+
def optimise_targets(self, *, max_valid: int | None = None) -> bool:
15231581
"""If any target observations have been made, attempt to optimise them
1524-
all."""
1582+
all, stopping early if ``self.valid_examples`` reaches ``max_valid``.
1583+
Returns whether this made any improvements."""
15251584
if not self.should_optimise:
1526-
return
1585+
return False
15271586
from hypothesis.internal.conjecture.optimiser import Optimiser
15281587

15291588
# We want to avoid running the optimiser for too long in case we hit
15301589
# an unbounded target score. We start this off fairly conservatively
15311590
# in case interesting examples are easy to find and then ramp it up
15321591
# on an exponential schedule so we don't hamper the optimiser too much
15331592
# if it needs a long time to find good enough improvements.
1593+
improved = False
15341594
max_improvements = 10
15351595
while True:
15361596
prev_calls = self.call_count
15371597

15381598
any_improvements = False
15391599

15401600
for target, data in list(self.best_examples_of_observed_targets.items()):
1601+
if max_valid is not None and self.valid_examples >= max_valid:
1602+
return improved
15411603
optimiser = Optimiser(
15421604
self, data, target, max_improvements=max_improvements
15431605
)
15441606
optimiser.run()
15451607
if optimiser.improvements > 0:
15461608
any_improvements = True
1609+
improved = True
15471610

15481611
if self.interesting_examples:
15491612
break
@@ -1558,6 +1621,7 @@ def optimise_targets(self) -> None:
15581621

15591622
if prev_calls == self.call_count:
15601623
break
1624+
return improved
15611625

15621626
def pareto_optimise(self) -> None:
15631627
if self.pareto_front is not None:
@@ -1577,7 +1641,7 @@ def _run(self) -> None:
15771641
self._switch_to_hypothesis_provider = False
15781642
with self._log_phase_statistics("generate"):
15791643
self.generate_new_examples()
1580-
# We normally run the targeting phase mixed in with the generate phase,
1644+
# We normally run the target phase mixed in with the generate phase,
15811645
# but if we've been asked to run it but not generation then we have to
15821646
# run it explicitly on its own here.
15831647
if Phase.generate not in self.settings.phases:

‎hypothesis/tests/conjecture/test_optimiser.py‎

Lines changed: 118 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -218,6 +218,124 @@ def test(data):
218218
assert runner.best_observed_targets["m"] == 100
219219

220220

221+
def record_optimise_passes(runner):
222+
"""Record runner.valid_examples at the start of each optimisation pass."""
223+
testcase_counts = []
224+
original = runner.optimise_targets
225+
226+
def recording(**kwargs):
227+
testcase_counts.append(runner.valid_examples)
228+
return original(**kwargs)
229+
230+
runner.optimise_targets = recording
231+
return testcase_counts
232+
233+
234+
def test_small_budgets_run_a_single_pass_at_half_budget():
235+
def test(data):
236+
data.target_observations["n"] = data.draw_integer(0, 2**16 - 1)
237+
238+
runner = ConjectureRunner(test, settings=runner_settings, random=Random(0))
239+
testcase_counts = record_optimise_passes(runner)
240+
runner.run()
241+
242+
assert len(testcase_counts) == 1
243+
assert testcase_counts[0] >= 50
244+
245+
246+
def test_large_budgets_start_optimising_early():
247+
def test(data):
248+
data.target_observations["n"] = data.draw_integer(0, 2**16 - 1)
249+
250+
runner = ConjectureRunner(
251+
test, settings=settings(runner_settings, max_examples=2000), random=Random(0)
252+
)
253+
testcase_counts = record_optimise_passes(runner)
254+
runner.run()
255+
256+
assert testcase_counts[0] <= 250
257+
258+
259+
def scheduler_state_runner():
260+
"""A runner in the state just after an optimisation pass has finished."""
261+
runner = ConjectureRunner(
262+
lambda data: None,
263+
settings=settings(runner_settings, max_examples=2000),
264+
random=Random(0),
265+
)
266+
runner.valid_examples = 400
267+
runner._next_optimise_at = math.inf
268+
runner._best_scores_at_last_pass = {"n": 5.0}
269+
runner.best_observed_targets["n"] = 5.0
270+
return runner
271+
272+
273+
def test_reruns_when_generation_finds_a_new_best_score():
274+
runner = scheduler_state_runner()
275+
assert not runner._should_optimise_now()
276+
runner.best_observed_targets["n"] = 10.0
277+
assert runner._should_optimise_now()
278+
279+
280+
def test_reruns_on_fair_share_schedule():
281+
runner = scheduler_state_runner()
282+
runner._next_optimise_at = 400
283+
assert runner._should_optimise_now()
284+
runner._next_optimise_at = 401
285+
assert not runner._should_optimise_now()
286+
287+
288+
def test_does_not_rerun_once_target_budget_is_spent():
289+
runner = scheduler_state_runner()
290+
runner._target_valid_spent = 1000
291+
runner.best_observed_targets["n"] = 10.0
292+
assert not runner._should_optimise_now()
293+
294+
295+
def test_plateaued_score_does_not_rerun_optimiser():
296+
def test(data):
297+
data.draw_integer(0, 2**16 - 1)
298+
data.target_observations["n"] = 1.0
299+
300+
runner = ConjectureRunner(
301+
test, settings=settings(runner_settings, max_examples=2000), random=Random(0)
302+
)
303+
testcase_counts = record_optimise_passes(runner)
304+
runner.run()
305+
306+
assert len(testcase_counts) == 1
307+
308+
309+
def test_optimisation_pass_stops_at_its_valid_example_budget():
310+
def test(data):
311+
data.target_observations["n"] = data.draw_integer(0, 2**64 - 1)
312+
313+
runner = ConjectureRunner(
314+
test, settings=settings(runner_settings, max_examples=2000), random=Random(0)
315+
)
316+
runner.cached_test_function((0,))
317+
318+
# This score can always be improved, so without the max_valid ceiling
319+
# this pass would consume the entire run.
320+
max_valid = runner.valid_examples + 10
321+
assert runner.optimise_targets(max_valid=max_valid)
322+
assert runner.valid_examples <= max_valid + 100
323+
324+
325+
def test_optimisation_spend_is_bounded_for_large_budgets():
326+
def test(data):
327+
n = sum(data.draw_integer(0, 100) for _ in range(5))
328+
data.target_observations["n"] = n
329+
330+
runner = ConjectureRunner(
331+
test, settings=settings(runner_settings, max_examples=2000), random=Random(0)
332+
)
333+
runner.run()
334+
335+
# aim for roughly half the budget, with some per-pass overshoot allowed.
336+
assert runner._target_valid_spent <= 1500
337+
338+
221339
@given(nodes())
222340
@example(
223341
ChoiceNode(
Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
# This file is part of Hypothesis, which may be found at
2+
# https://github.com/HypothesisWorks/hypothesis/
3+
#
4+
# Copyright the Hypothesis Authors.
5+
# Individual contributors are listed in AUTHORS.rst and the git log.
6+
#
7+
# This Source Code Form is subject to the terms of the Mozilla Public License,
8+
# v. 2.0. If a copy of the MPL was not distributed with this file, You can
9+
# obtain one at https://mozilla.org/MPL/2.0/.
10+
11+
import pytest
12+
13+
from hypothesis import (
14+
HealthCheck,
15+
Phase,
16+
given,
17+
seed,
18+
settings,
19+
strategies as st,
20+
target,
21+
)
22+
23+
common_settings = {
24+
"database": None,
25+
"suppress_health_check": list(HealthCheck),
26+
"phases": [Phase.generate, Phase.target],
27+
}
28+
29+
30+
@pytest.mark.parametrize("seed_val", [0, 1, 2])
31+
def test_finds_threshold_bug_quickly_with_large_budget(seed_val):
32+
# check that we optimize sooner than halfway for large test case budgets.
33+
calls = 0
34+
found_at = None
35+
36+
@seed(seed_val)
37+
@settings(max_examples=10_000, **common_settings)
38+
@given(st.lists(st.integers(0, 1000)))
39+
def test(ls):
40+
nonlocal calls, found_at
41+
calls += 1
42+
target(min(sum(ls), 50_000))
43+
if sum(ls) >= 30_000:
44+
if found_at is None:
45+
found_at = calls
46+
raise AssertionError
47+
48+
with pytest.raises(AssertionError):
49+
test()
50+
assert found_at is not None
51+
assert found_at < 4_000
52+
53+
54+
@pytest.mark.parametrize("seed_val", [0, 1, 2])
55+
def test_reaches_high_scores_with_moderate_budget(seed_val):
56+
best = 0.0
57+
58+
@seed(seed_val)
59+
@settings(max_examples=2000, **common_settings)
60+
@given(st.lists(st.integers(0, 1000)))
61+
def test(ls):
62+
nonlocal best
63+
score = min(sum(ls), 100_000)
64+
best = max(best, score)
65+
target(score)
66+
67+
test()
68+
# generous margin to account for unrelated engine changes
69+
assert best >= 50_000

0 commit comments

Comments
 (0)