needsrewrite

Overview ¶

Command needsrewrite decides whether a document is worth rewriting before rewriting it, which is the question a proxy asks thousands of times a second and mostly answers "no".

The cheap answer is a byte search: if the body cannot contain anything the handlers match, skip the rewrite. Two things make that harder than it sounds - one about cost and one about correctness - and both are measurable.

Cost first, and getting it cheap took three attempts, each of which I expected to be the answer. HTML tag names are case-insensitive, so the search has to be, and the usual way to write that lower-cases the body. On a 93 KB page with nothing in it to match, fastest of twenty:

                                             time   allocates
one bytes.Contains, case-sensitive (wrong)    26µs           0
ToLower then Contains, once per probe        157µs      98,304
fold the comparison, byte at a time          318µs           0
fold, skipping with bytes.IndexByte          150µs           0
fold, one pass, table on the byte after "<"   52µs           0
the rewrite this is avoiding                 175µs           -

The three surprises, in order. A hand-written fold loop is worse than lower-casing the whole document, because ToLower and Contains have vectorised implementations behind them and a byte-at-a-time loop does not. Skipping with IndexByte helps less than it looks like it should, because in HTML the "<" is exactly as dense as the tags are - that page has 6,000 of them, one every fifteen bytes - so there is little to skip and the work at each candidate is what counts. And searching once per probe is a full pass per probe on a miss, so three probes cost three scans while the rewrite is paid once.

What works is one pass with a 256-entry table on the byte after the bracket, which rejects almost every candidate with a lookup: 52µs against a 175µs rewrite, and nothing allocated. A gate that costs a third of what it saves is worth having; the first three attempts were not.

Correctness second, and it is one rule: the probe has to match a superset of what the handlers match, or the gate skips a document it should have rewritten - silently, since the whole point is that nothing runs. Being too broad only costs a wasted rewrite.

The rule bites in a way worth naming. A selector for images has to be `img,image`, because `<image>` is a spelling of `<img>` that the parser renames and this library reports as spelled (B155). A probe of "<img" is therefore not a superset of that selector, and a page whose only image is spelled `<image src=x>` would be skipped. The probe is "<im".