1 file changed, 33 insertions, 0 deletions
diff --git a/tests/extensions/harness.lua b/tests/extensions/harness.lua
index 5084ab4..188d90f 100644
--- a/tests/extensions/harness.lua
+++ b/tests/extensions/harness.lua
@@ -301,6 +301,39 @@ function harness.excludes(name, haystack, needle)
 	end
 end
 
+-- Checks that a text four times as long costs about four times as much to
+-- run, as a linear pass does, where a quadratic one costs sixteen times as
+-- much. Timing one length against the other cancels out how fast the host
+-- is. Each timing repeats the run for at least 50 ms, and the two lengths
+-- take turns, keeping the fastest timing of each. A busy host can charge
+-- the process for time its CPU was taken away, which slows a timing but
+-- never speeds one up. A ratio under six is plainly linear and ends the
+-- turns, so only one near the bound takes all five before it can fail.
+-- Returns what the longer run gave back.
+function harness.stays_linear(name, run, make, length)
+	local texts = { make(length), make(4 * length) }
+	local fastest = { math.huge, math.huge }
+	local out
+	for _ = 1, 5 do
+		for i = 1, 2 do
+			local runs, started = 0, os.clock()
+			repeat
+				out = run(texts[i])
+				runs = runs + 1
+			until os.clock() - started >= 0.05
+			fastest[i] = math.min(fastest[i], (os.clock() - started) / runs)
+		end
+		if fastest[2] < 6 * fastest[1] then
+			break
+		end
+	end
+	local short, long = fastest[1], fastest[2]
+	harness.check(name, long < 10 * short,
+		string.format("%.4f s at length %d, then %.4f s at four times that",
+			short, length, long))
+	return out
+end
+
 -- A run that made no check proves nothing, so it fails as well.
 function harness.finish()
 	if failures > 0 then