The same occurrences, less bookkeeping

Eight patterns of six characters on a collection of eight near-identical copies — three thousand and seventy-two characters, two hundred and five phrases.

Both traversals examine 1,370 phrases for the first query, and 1,370 for the other. Identical, on every query.

Both report the same occurrences, in the same order, at the same positions.

What differs is what each holds while doing it.

The two structures #

The queue version holds a first-in-first-out list of occurrences to process and a set of every occurrence found so far. The set exists because a queue can reach a position along two paths, and the set stops it being reported twice.

The sweep version holds one sorted list and a cursor. Occurrences ahead of the cursor are pending; occurrences behind it are done; and a production is inserted at its sorted position, which every copy points right guarantees is ahead.

No set. A position cannot be processed twice, because the list holds no duplicates and the cursor only moves forward.

The measurement #

Per query, the visited set holds every occurrence found: 8, 7, 16, 31, 8, 8, 15, 7 across the eight patterns.

The sweep’s largest frontier is 4, 4, 11, 19, 4, 5, 9, 4.

Ratios of 2.00, 1.75, 1.45, 1.63, 2.00, 1.60, 1.67, 1.75.

So the sweep holds between a half and two thirds of what the queue holds, and the factor is a small constant rather than an asymptotic improvement.

The ratios are worth reading as a distribution rather than as an average, because they order themselves by the answer’s size.

The two-occurrence and seven-occurrence queries give 2.00 and 1.75. The sixteen-occurrence query gives 1.45 and the thirty-one-occurrence one gives 1.63.

So the factor is largest on the smallest answers, which is the opposite of what a saving would want. A query with two occurrences holds four positions in a set and two in a frontier — a saving of two positions, on a query that was cheap anyway.

That the factor does not grow with the answer is the whole of a constant factor, not a term, and it is visible here in the individual queries before any sweep.

Why the phrases examined are identical #

Both traversals do the same thing at each occurrence: walk the phrases in source order, stop when a source exceeds the current position, and produce a copy for every phrase whose source region contains it.

That inner loop is unchanged. What the sweep changes is only the order in which occurrences are visited, and every occurrence is visited exactly once either way — so the inner loop runs exactly as many times.

The equality is worth checking rather than assuming, because a traversal that changed the work would be a different comparison. It is: 1,370 against 1,370, and the same at every copy count.

That makes this a clean measurement of a bookkeeping change, with the work held fixed by construction rather than by argument.

What the frontier is #

The sweep’s frontier is the part of its sorted list ahead of the cursor — the occurrences known and not yet processed.

It starts as the primaries, grows as productions are inserted, and shrinks as the cursor advances. Its maximum over a query is what the plate reports.

On a collection of d near-identical copies the propagation is a chain: an occurrence in copy one produces one in copy two, which produces one in copy three, and so on. In text order that means the cursor is always near the front of the list, and the frontier is the productions that have run ahead of it.

A parse with nested repetition would give a different shape — a fan rather than a chain — and a larger frontier.

Both are proportional to the answer #

The plate’s important feature is that both lines rise, and rise together.

The visited set is the answer, by definition: every occurrence found is in it.

The frontier is a fraction of the answer, because on a chain propagation the productions run ahead of the cursor by a bounded amount and that amount is proportional to how many copies there are.

So the substitution removes a constant factor rather than a term. A constant factor, not a term is that result, and it is smaller than the deferral naming this work expected.

There is a shape of collection where the frontier would be much smaller than the answer, and it is worth naming so the constant is understood as a property of these collections rather than of the method.

Suppose the propagation is a long chain with no branching: occurrence one produces occurrence two, which produces three, and so on. In text order the cursor processes one, inserts two ahead, processes two, inserts three. The frontier is never more than one.

The visited set, meanwhile, holds all d of them.

So on a pure chain the factor would be d rather than 1.6 — an asymptotic saving rather than a constant one.

The collections measured here are not pure chains: a pattern in the base occurs in several places within each copy, so each occurrence produces several, and the frontier holds them all. That fan-out is what turns a would-be factor of d into a factor of 1.6.

Which shape a real collection has is not something this strand measures, and it is the question that decides whether the substitution is worth a constant or a term.

What a set costs that a list does not #

The factor of 1.6 is the count of positions held, and there is a second difference the count does not capture.

A hash set of positions has a load factor, a hash function and a memory layout; a sorted array of the same positions is contiguous. So the same number of positions costs more in a set than in a list, by whatever a hash table’s overhead is — typically a factor of two in memory and a scattered access pattern.

That is not measured here, because this collection charges bits held rather than bytes allocated. What can be said is that the substitution removes a hash table from a query’s inner loop and replaces it with a binary search into a sorted array, and the two have different constants that this instrument cannot see.

The comparison that is not one comparison is the habit that requires saying so: an operation count is a count of operations and the operations are not all the same size.

The order the answers come out in #

Both traversals produce their occurrences in an order and neither produces them sorted, which is worth stating because a caller might rely on it.

The queue produces breadth-first over the copy graph: all the occurrences at depth one, then all at depth two. In text terms that is scattered.

The sweep produces them in text order, because it processes them in text order and reports each as it goes.

So the sweep’s output is sorted and the queue’s is not, and both implementations sort at the end because the interface promises sorted occurrences.

That the sweep produces them sorted for free is a small additional saving nobody asked for: occ log occ comparisons removed, on an answer of thirty, which is nothing. It would be something on an answer of a million.

It is also a property a caller could come to rely on, which is the failure mode one set, three orders is about — a representation chosen for one reason supplying an order that becomes load-bearing. Here the order is a consequence of the traversal rather than of a representation, and it is stable in a way a code shape’s leaf order is not.

Against the structure it sits in #

The comparison worth making is between the query’s working memory and the index’s own size, because a structure whose whole claim is being proportional to the phrase count has a query holding something else.

At thirty-two copies over twelve thousand characters: the index is 20,640 bits and the visited set is 420. Two per cent of the structure, held during a query and released after.

At thirty-two copies the answer is thirty occurrences, so the set is thirty positions at fourteen bits. On a collection where a pattern occurs a thousand times it would be fourteen thousand bits, which is most of an index of this size.

So the working memory is proportional to the answer and the structure is proportional to the phrase count, and there is no relationship between the two. A query with many occurrences on a highly compressible collection holds far more than the index it is querying.

That is a genuine gap in how this family accounts for itself, and it is not specific to the visited set: any method reporting occ occurrences holds occ of something. What the sweep changes is the constant.

Putting the shared cost beside the differing one gives the honest proportion.

Per query on this collection, the two traversals each examine about seventeen hundred phrases. That is the propagation’s work, and it is unchanged.

Each also holds between four and thirty-one positions. That is the bookkeeping, and it differs by a factor of 1.6.

So the substitution changes a quantity that is two orders of magnitude smaller than the one it does not change. A reader looking for a speedup should look at the scan; a reader looking for a memory reduction has found one, and it is small.

The scan the order does not touch is where the larger quantity is attacked, and it gets a factor of nineteen — which is the number this strand actually has to offer on cost.

What the equality check is for #

The two traversals must report the same occurrences, and the check is on the occurrences rather than on their number.

That distinction matters because the two produce them in different orders — the queue in breadth-first order over the copy graph, the sweep in text order — so a comparison of counts would pass on a traversal that found a different set of the same size.

Measured: seventy-two comparisons across two corpora, three copy counts and three pattern lengths, fourteen hundred and seventy-one occurrences, every one matching.

A difference would not be a slower traversal; it would be a wrong answer. Which is why this is the primary check and the operation counts are secondary.

What a query holds, in general #

The comparison above raises a question this family’s accounting does not answer, and it is worth stating as an open one rather than pretending it is settled.

Every structure in this collection reports a size: bits held at rest, in parts, checked. None of them reports a query working set: bits held during a query and released.

For most of them that is fine, because the working set is a few registers. A backward search holds an interval. A locate holds a row and a step count. A rank walk holds a position.

Two structures in this slate break that: the document listing’s answer-so-far bitmap, which is d bits, and this propagation’s visited set, which is occ positions.

Both are proportional to something about the query rather than about the structure, and neither appears in any size the structure reports. So a system sizing its memory from these essays’ numbers would be sizing for the structures and not for the queries.

A document already in the answer is where the first of the two was found and where the trap in clearing it was recorded. What neither essay does is add a working-set column to the accounting, and doing so would be a change to every structure here.

That is a gap named rather than closed, and the reason to name it in this essay is that this is the one place where the working set is the entire subject.

What would make it a term #

Since the substitution is a constant here, it is worth saying what collection would make it more, because that is the question a reader with a different corpus has.

The frontier is the number of occurrences known and unprocessed at once. The visited set is the number found in total. So the ratio is (total found) over (peak pending), which is large when the propagation is deep and narrow and small when it is shallow and wide.

Deep and narrow: a chain of versions, each copying the previous one, where a pattern occurs once per version. Each occurrence produces exactly one, the frontier is one, and the ratio is the version count.

Shallow and wide: a base document copied d times in parallel, where each copy’s phrase points at the base. Every occurrence in the base produces d − 1 at once, the frontier is d − 1, and the ratio is about one.

The collections measured here are the second shape, because copiesOf builds each copy from the previous text as a whole rather than chaining phrase by phrase.

So the 1.6 is a measurement of a parallel-copy collection, and a versioned archive whose revisions each derive from the last would give a larger number. That is a plausible real shape and this strand does not measure it, which is worth admitting rather than generalising past.

What the sweep is not #

Two things it might be mistaken for.

It is not a faster propagation. The phrases examined are identical, so the dominant cost — the scan over phrase sources — is unchanged. The scan the order does not touch is where that cost is attacked, by a different change.

It is not a smaller index. The visited set is query state and the index reports the same size either way.

What it is: a traversal that needs less state, by an amount that is a constant factor, resting on a property of the parse that has to be checked because a parse without it loses occurrences silently.

Where the primaries come from #

The propagation starts with the primary occurrences and it is worth saying where those come from, because they are the sweep’s initial list and their number decides how much of the answer is not produced at all.

A primary occurrence crosses a phrase boundary. Finding them means splitting the pattern at each of its m − 1 split points and asking which boundaries have the left half ending at them and the right half starting at them — an intersection of two ranges, which the occurrences that cross a boundary measures.

On the collections here the primaries are one or two occurrences and the secondaries are the rest: at thirty-two copies, one primary and twenty-nine secondaries.

That ratio is the whole reason the propagation matters. A method finding one occurrence by search and twenty-nine by arithmetic is a method whose cost is dominated by the arithmetic, and the arithmetic is what both traversals perform.

It also explains why the sweep’s initial list is short. The frontier starts at one or two and grows only through production, so its maximum is entirely a property of the propagation’s shape rather than of the search.

Why it is worth doing anyway #

A constant factor of 1.6 on query working memory is a small result and there are two reasons to take the substitution.

It removes a structure. A hash set in an inner loop is a thing that can be got wrong, that allocates, and that has a load factor. A sorted list and a cursor have none of those.

And it makes a property explicit. The sweep’s guard states, at the point of every production, that a copy lies to the right — which is a fact about the parse that was previously implicit and unchecked. A parse that lost the property would now fail loudly rather than producing short answers.

That second is worth more than the memory. This collection has found the same class of defect twice in two strands — an ordering that a traversal depends on and nothing enforces — and the guard is what turns the dependence into something a gate can see.

The third reason is smaller and worth having: the sweep is easier to reason about. A queue with a visited set requires a reader to hold two invariants — that everything in the queue is unprocessed and that everything in the set has been produced — and to check that the two stay consistent. A cursor into a sorted list requires one: everything before the cursor is done.

That is not a measurement and it is the kind of thing this collection is usually suspicious of, since “simpler” is a judgement rather than a number. What makes it defensible here is that the simplification comes with a checkable claim attached — the ordering property — so the reduction in invariants is not a matter of taste but a consequence of a fact about the parse that the code now asserts.