1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at https://mozilla.org/MPL/2.0/.
//! Guard against the rescanning encoder of spec Section 6.6.
//!
//! The prefix scan may look ahead MAX_DP_ANALYSIS_BYTES bytes while step 4
//! consumes as few as 4, so an encoder that redoes the scan from scratch on
//! every iteration performs up to 512 byte inspections per input byte. Bounded
//! lookahead keeps that linear rather than quadratic, but the constant factor
//! is still what this section exists to prevent.
//!
//! Pseudorandom bytes are the worst case: no prefix reaches
//! MIN_PASSTHROUGH_BYTES and no run reaches MIN_FILL_BYTES, so every iteration
//! takes the block-mode branch and advances 4 bytes, while a naive
//! implementation rescans the full window each time.
//!
//! Both tests here are timing-based, which means they have to survive
//! interference -- not only from a shared CI runner but from the rest of this
//! suite, which the harness runs alongside them on however many cores the
//! machine has.
//!
//! The growth check therefore does not time a small input against a large one.
//! Comparing a short measurement with a long one is not a fair comparison on a
//! busy machine: a measurement that fits inside a scheduler time slice is often
//! not preempted at all, while one twice as long is preempted nearly every time
//! and then waits for its next turn behind everything else runnable. Measured
//! that way a *linear* encoder came out at 3.8 on a threshold of 3.0, and
//! systematically rather than occasionally -- the longer measurement is never
//! the lucky one, so taking the minimum of several tries does not remove it.
//!
//! What it does instead: two calls over the smaller input against one call over
//! the doubled one -- the same bytes either way, so the same time either way --
//! interleaved, over and over, with the fastest pass on each side taken. Equal
//! length gives both sides the same chance at a pass the scheduler leaves
//! alone; taking the fastest keeps the ones it did not. The result is about 1
//! for a linear encoder and about 2 for a quadratic one, and the check is run
//! against deliberately quadratic work as well, so that it cannot quietly
//! become a check that nothing can fail.
//!
//! Measured on a four-core machine: no failure in 10 runs of the whole suite
//! idle, 10 with four other cores' worth of load, or 10 with eight, in debug
//! and in release. The design before this one failed 2 in 8 runs idle.
use ;
use StdRng;
use ;
use crate::;
const SCAN_DENSE_SIZE: usize = 128 * 1024;
const TIME_LIMIT: Duration = from_secs;
/// Bytes the growth check compares at: this many against twice this many.
///
/// Small, and deliberately so. The check is about the encoder's cost per byte
/// at two sizes, and inputs large enough to leave cache bring the memory system
/// into the comparison instead -- page faults on a freshly grown output buffer,
/// a working set that fits at one size and not at the other. How *long* each
/// measurement takes is set below by how many times it runs, which is the knob
/// that does not change what is being measured.
const GROWTH_SIZE: usize = 32 * 1024;
/// How long the measurement should take. Not a timer-resolution floor: it is
/// this long because the two sides have to be interleaved many times over for
/// the scheduler to treat them alike (see [`growth_ratio`]).
const BUDGET: Duration = from_millis;
/// However slow one call is, this many interleavings, so that each side gets
/// several chances at an undisturbed sample.
const MIN_PAIRS: usize = 24;
/// However fast one call is, no more than this many, as a guard against a first
/// measurement so short that the count runs away.
const MAX_PAIRS: usize = 1 << 20;
/// The same bytes in one call against two: linear predicts ~1.0, quadratic
/// ~2.0. Halfway between is the decision point.
const MAX_GROWTH: f64 = 1.5;
/// Input on which no prefix ever reaches MIN_PASSTHROUGH_BYTES.
/// Calls over `2 * GROWTH_SIZE` scan-dense bytes against twice as many calls
/// over `GROWTH_SIZE` of them, as a ratio: about 1 for work that is linear in
/// its input, about 2 for work that is quadratic.
///
/// The two sides cover the same number of bytes and take about the same time,
/// and they are interleaved -- two small calls, then one large one, over and
/// over -- with the fastest pass on each side kept. That is the whole design,
/// and it is what makes the ratio survive a busy machine.
///
/// Timing one long call against one short one does not survive it. The short
/// measurement often fits inside a scheduler time slice and is not preempted at
/// all, while the long one is preempted and then waits for its turn behind
/// everything else runnable -- a factor of nearly two between two halves of a
/// *linear* encoder. That is systematic rather than noise, so taking the
/// minimum of several tries does not remove it: the longer measurement is never
/// the lucky one. Interleaved, the two sides meet the same scheduler over the
/// same stretch of wall clock, and each side's fastest pass is taken -- the
/// sample the scheduler happened to leave alone, which both sides have the same
/// chance at because their passes are the same length.
///
/// The number of pairs comes from one timing, so that the measurement takes
/// about [`BUDGET`] in a release build as well as a debug one, where the same
/// work is nearly two orders of magnitude apart.
// wall-clock, and an interpreter has none
// wall-clock, and an interpreter has none
/// Deliberately quadratic: it walks the buffer again every [`RESCAN_STRIDE`]
/// bytes, which is the shape of the rescanning encoder spec section 6.6
/// forbids, at a scale that runs in milliseconds.
/// The check above guards the encoder only for as long as it can still fail,
/// and a timing check on a moving target is exactly the kind that stops being
/// able to: the code gets faster, or the measurement gets looser to keep a busy
/// machine happy, and what is left is a check nothing can trip. So the same
/// measurement is run against work that *is* quadratic, and has to come out on
/// the other side of the same threshold.
// wall-clock, and an interpreter has none
/// The other direction: one long representable run, which Dynamic Passthrough
/// takes MAX_DP_ANALYSIS_BYTES at a time.
// wall-clock, and an interpreter has none