mirror of
https://github.com/hanzoai/laya.git
synced 2026-10-30 19:33:31 +00:00
`_IDENTIFIER` strips dot- and @-joined tokens (`github.com`, `[email protected]`, `v1.2.3`) before `_WORD` counts function words: [\w-]*(?:[.@][\w-]+)+ The greedy prefix is retried at every offset inside a run of word characters, and each attempt rescans the run before failing on the absent `[.@]`. That is quadratic in the run's length. `analyse()` runs inside `predict()` on the default routing path -- no `model`, no `lang` -- and `state_text` hands it up to 4000 characters: Router.route(), 4000 chars of prose 1.8 ms Router.route(), 4000 chars of one token 206.3 ms _IDENTIFIER.sub alone, 50 000 chars 30 678.0 ms Scoped honestly: that 114x is the routing component in isolation, not the request. Against the published 33 ms/question on a T4 the request goes from ~35 ms to ~239 ms -- about 7x, with routing rising from 5% to 86% of the call -- and on a box where inference costs 300 ms it is nearer 1.7x. Routing runs inside the same single-worker pool as the forward pass, behind the same lock, so the cost is throughput directly: ~29 req/s falls to ~4 req/s on those numbers. `/v1/systemone` needs no credential unless LAYA_API_KEY is set. The unambiguous case needs no threat model at all: `latin_profile` and `guess_latin_language` are public and take unbounded text, where 50 000 characters of one token cost ~31 s. The fix is a leading lookbehind, `(?<![\w-])`, which removes no match. `[\w-]` and `[.@]` are disjoint, so a greedy prefix starting inside a run consumes to exactly the same separator as one starting at the run's start: the two always succeed or fail together, and a leftmost match can therefore only ever begin at a run start. Failing offsets inside a run now cost O(1) instead of O(n). 50 000 chars 30 678 ms -> 1.79 ms 20 000 chars 4 860 ms -> 0.73 ms 4 000 chars 205 ms -> 0.14 ms ordinary prose 0.45 ms -> 0.18 ms Behaviour is unchanged rather than nearly unchanged, which is why a lookbehind was chosen over bounding the quantifiers: a bound leaves the overflow of a long run behind as a residue token, `_WORD` counts it, and `latin_profile` gates on `len(words) < 4`, so three real words plus one residue can flip a route. The tests assert parity against the previous pattern directly -- 33 identifier and edge cases plus 20 000 randomised strings, zero differences, including `"a"*200 + ".example.com"` and a 64-character RFC 5321 local part. laya-ts carried the identical pattern at `src/lang.ts:121`, reached by the same `latinProfile` <- `analyse` <- `router.ts` path with the same 4000-character cap, so the shipped npm package had the same exposure: 50 000 characters took 1540 ms on node 20, now 0.26 ms. Same one-line fix, same parity evidence. Checks: ruff and compileall clean; tests/test_hooks_api.py 115 passed (public API untouched); Python suite unchanged against main (41 files pass, the same 6 skip for missing optional deps or a checkpoint); laya-ts 207 tests pass and tsc --noEmit is clean. Both new suites are wired into ci.yml -- the Python one into the Linux list and the Windows loop, the TypeScript one is picked up by `npm test`. Every complexity assertion is set to fail the previous pattern, not merely to pass comfortably: 8 of 8 fail on a revert in Python, 6 of 6 in TypeScript, and the measured scaling ratio moves from 16.2 to under 4.
151 lines
6.7 KiB
Python
151 lines
6.7 KiB
Python
"""Regression: stripping identifiers must stay linear in the length of a word-character run.
|
|
|
|
`_IDENTIFIER` removes dot- and @-joined tokens (`github.com`, `[email protected]`, `v1.2.3`)
|
|
before `_WORD` counts function words. Without the leading lookbehind, the greedy `[\\w-]*`
|
|
is retried at every offset inside a run of word characters and each attempt rescans the
|
|
run before failing on the absent `[.@]` -- quadratic in the run's length:
|
|
|
|
4 000 characters of one token 205 ms (0.45 ms for prose of the same size)
|
|
50 000 characters of one token 30 678 ms
|
|
|
|
`analyse()` runs on the default routing path -- no `model`, no `lang` -- once per request,
|
|
and `state_text` hands it up to 4000 characters, so an unauthenticated caller of
|
|
`POST /v1/systemone` could buy ~115x the CPU of a normal request. `latin_profile` and
|
|
`guess_latin_language` take unbounded text, where the same input costs ~31 s.
|
|
|
|
The lookbehind removes no match: `[\\w-]` and `[.@]` are disjoint, so an attempt from
|
|
inside a run consumes to exactly the same separator as an attempt from the run's start,
|
|
and the two always succeed or fail together. The parity block below is the evidence --
|
|
it is checked against the previous pattern, not against hand-written expectations.
|
|
|
|
Run: python tests/test_identifier_complexity.py
|
|
"""
|
|
import os
|
|
import re
|
|
import sys
|
|
import time
|
|
|
|
sys.path.insert(0, os.path.dirname(os.path.dirname(os.path.abspath(__file__))))
|
|
|
|
from laya.lang import _IDENTIFIER, analyse, latin_profile # noqa: E402
|
|
|
|
# The pattern as it was before the lookbehind, kept here so parity is asserted against
|
|
# the real previous behaviour rather than against expectations someone typed out.
|
|
_PREVIOUS = re.compile(r"[\w-]*(?:[.@][\w-]+)+", re.UNICODE)
|
|
|
|
PASS, FAIL = [], []
|
|
|
|
|
|
def check(name, got, want):
|
|
if got == want:
|
|
PASS.append(name)
|
|
else:
|
|
FAIL.append("%s: got %r, want %r" % (name, got, want))
|
|
|
|
|
|
def ok(name, cond, extra=""):
|
|
if cond:
|
|
PASS.append(name)
|
|
else:
|
|
FAIL.append("%s%s" % (name, (" -> " + str(extra)) if extra else ""))
|
|
|
|
|
|
# ---------------------------------------------------------------- parity ----
|
|
# Every identifier the pattern exists to strip, plus the shapes that tempt a
|
|
# bounded-quantifier fix into leaving a residue token behind.
|
|
PARITY = [
|
|
"github.com", "[email protected]", "v1.2.3", "U.S.A.", "arrivato.", "a.b", "a@b",
|
|
"sub.domain.co.uk", "[email protected]", "192.168.0.1", "-a.b-", "_x.y_",
|
|
"foo..bar", ".com", "a.", "@a", "a@", "e.g.", "Ü.Ö", "naïve.café", "a-b.c-d",
|
|
"x-a.b", "9.9", "a..b", "a.-b", "a-.b-.c", "", ".", "@",
|
|
"Contact [email protected] or github.com/acme for v2.10.1 details.",
|
|
"No identifiers here at all just words",
|
|
# A local part at RFC 5321's 64-character limit, and a run past any plausible bound:
|
|
# a length-bounded pattern strips only part of these and leaves the rest as a word.
|
|
"a" * 64 + "@example.com",
|
|
"a" * 200 + ".example.com",
|
|
"grazie mille per " + "wzqxk" * 15 + ".example.com",
|
|
]
|
|
for token in PARITY:
|
|
check("parity/%r" % (token[:34],), _IDENTIFIER.sub(" ", token), _PREVIOUS.sub(" ", token))
|
|
|
|
# Randomised differential test: the two patterns must agree on everything.
|
|
import random # noqa: E402
|
|
|
|
random.seed(11)
|
|
_ALPHABETS = ["aA1._@- ", "._@-", "áéÜß._@-", "abcXYZ019._@- -_"]
|
|
mismatch = None
|
|
for i in range(20_000):
|
|
alphabet = _ALPHABETS[i % len(_ALPHABETS)]
|
|
s = "".join(random.choice(alphabet) for _ in range(random.randint(0, 60)))
|
|
if _IDENTIFIER.sub(" ", s) != _PREVIOUS.sub(" ", s):
|
|
mismatch = s
|
|
break
|
|
ok("parity/20 000 random strings agree with the previous pattern",
|
|
mismatch is None, repr(mismatch))
|
|
|
|
# Detection behaviour, not just the regex.
|
|
check("a state of two domains is still not prose",
|
|
analyse({"body": "github.com acme.com"})["language"], None)
|
|
check("the routing answer for ordinary prose is unchanged",
|
|
analyse({"body": "The customer was billed twice and wants a refund"})["is_english"], True)
|
|
|
|
|
|
# ------------------------------------------------------------ complexity ----
|
|
def elapsed(fn, *a):
|
|
started = time.perf_counter()
|
|
fn(*a)
|
|
return time.perf_counter() - started
|
|
|
|
|
|
# Ceilings are set to fail the previous pattern rather than merely to be generous.
|
|
# Previous cost / ceiling / current cost, measured on a 2023 laptop:
|
|
# 4 000 chars 205 ms / 50 ms / 0.14 ms (~350x headroom)
|
|
# 20 000 chars 4 860 ms / 1.00 s / 0.73 ms (~1370x headroom)
|
|
for n, ceiling in ((4_000, 0.05), (20_000, 1.00)):
|
|
took = elapsed(_IDENTIFIER.sub, " ", "a" * n)
|
|
ok("%d word characters strip in under %.0f ms (took %.1f ms)" % (n, ceiling * 1000, took * 1000),
|
|
took < ceiling, "%.1f ms" % (took * 1000))
|
|
|
|
# Hyphens and underscores are word characters here too, so the run can be built from them,
|
|
# and a single trailing separator must not reopen the quadratic path.
|
|
for label, text in (("hyphens", "a-" * 10_000),
|
|
("underscores", "a_" * 10_000),
|
|
("one trailing dot", "a" * 20_000 + ".")):
|
|
took = elapsed(_IDENTIFIER.sub, " ", text)
|
|
ok("%s: 20k strips in under 1 s (took %.1f ms)" % (label, took * 1000), took < 1.0,
|
|
"%.1f ms" % (took * 1000))
|
|
|
|
# Scaling, which is machine-independent in a way a wall-clock ceiling is not: linear work
|
|
# quadruples with the input, quadratic work grows sixteenfold. 8 sits between the two.
|
|
small = min(elapsed(_IDENTIFIER.sub, " ", "a" * 5_000) for _ in range(3))
|
|
large = min(elapsed(_IDENTIFIER.sub, " ", "a" * 20_000) for _ in range(3))
|
|
ratio = large / small if small > 0 else 0
|
|
ok("4x the input costs under 8x the time, ratio %.1f (linear ~4, quadratic ~16)" % ratio,
|
|
ratio < 8, "ratio %.1f (%.2f ms -> %.2f ms)" % (ratio, small * 1000, large * 1000))
|
|
|
|
# The public entry point a request actually reaches. Compared against prose of the same
|
|
# size rather than a wall-clock ceiling: at 4000 characters the gap between quadratic and
|
|
# linear is only a few-fold, which CI jitter can cover, but the ratio against prose is
|
|
# ~1x when the work is linear and ~100x when it is not.
|
|
_PROSE_4K = ("The customer was billed twice and wants a refund. " * 80)[:4_000]
|
|
|
|
|
|
def _best(state, reps=3):
|
|
return min(elapsed(analyse, state) for _ in range(reps))
|
|
|
|
|
|
token_cost = _best({"body": "a" * 4_000})
|
|
prose_cost = _best({"body": _PROSE_4K})
|
|
ratio_4k = token_cost / max(prose_cost, 1e-5)
|
|
ok("one long token costs about what prose of the same size costs (ratio %.1f)" % ratio_4k,
|
|
ratio_4k < 10, "%.2f ms vs %.2f ms" % (token_cost * 1000, prose_cost * 1000))
|
|
took = elapsed(latin_profile, "a" * 50_000)
|
|
ok("latin_profile() on 50k of one token is under 1 s (took %.1f ms)" % (took * 1000),
|
|
took < 1.0, "%.1f ms" % (took * 1000))
|
|
|
|
print("\n%d passed, %d failed" % (len(PASS), len(FAIL)))
|
|
for f in FAIL:
|
|
print(" FAIL " + f)
|
|
sys.exit(1 if FAIL else 0)
|