A price with no structure under it

This collection has a class that represents a sparse set of positions. Its bits() method returns r·low + 2r, which is Elias–Fano’s price. It has been used to size several structures across several strands and every number it produced has been reported as a size.

What it stores is an Int32Array of the positions. What it does for a rank is a binary search over that array.

It is a size model with no structure under it — an accounting for an object that does not exist anywhere in the code — and the two ways it differs from a real Elias–Fano array had never been checked, because nothing had built one to check against.

What it is right about #

The payload. On four sampling rates the model’s total and the structure’s payload agree to within a bit per thousand: 5,125 against 5,124, 3,078 against 3,077, 1,799 against 1,798, 1,032 against 1,031.

That agreement is not luck and it is not a coincidence either. It is the flat bottom of a shallow curve: the model splits at ⌈log₂(n/m)⌉ and the structure at the floor, and near the optimum the cost curve’s steps are single bits.

So a wrong parameter on a flat curve produced a right answer, for several strands, and nothing could have noticed from the outputs.

What it is wrong about, in bits #

The model charges r·low + 2r and calls the first term the payload.

The structure costs m·w for the low parts plus the high vector in full — its payload and its directory, because a select on it needs the directory and a structure whose select does not work is not a structure.

That directory is 596 bits at m = 513 in n = 16,385, against a structure of 3,905. The model omits 10.4%.

Across four rates the omission is 10.4%, 9.3%, 8.6%, 8.7% — stable, because the directory is a function of the vector’s length and the vector’s length is proportional to the payload.

Ten per cent is not enormous and it is the same omission as reporting a plain bit vector as n bits, which this collection has been careful about since an index larger than what it indexes. It is a real error in a number that has been used.

There is a temptation to describe the omission as “the model reports the payload and the structure reports the total”, which would make it a difference in convention rather than an error. It is not, and the distinction matters.

A payload is a meaningful quantity when the directory is separately accounted for somewhere. In this collection’s own accounting for a plain bit vector, bits() returns {payload, directory, total} and every caller that sums them uses the total. The model returns one number and calls it a total, and that number is the payload.

So the omission is not a convention; it is a number labelled as something it is not, being summed with numbers that are what they say. An index larger than what it indexes is where this collection started insisting that a reported size say what is in it, and this is a case of a size that said the wrong thing quietly.

What it is wrong about, in operations #

This is the part no measurement of bits could have found.

The structure’s rank1 is a select0 on the high vector to find the bucket, then a walk along the bucket comparing low parts. The bucket’s expected occupancy is one by construction, and the measured walk is 1.25 accesses.

The model’s rank1 is a binary search over m positions: ⌈log₂ 513⌉ = 10 steps.

A factor of eight on the operation, between two objects that price identically.

That is not an implementation detail of the model. It is what the model is: an array of positions is a perfectly good sparse-set representation whose rank is a search, and Elias–Fano is a different representation whose rank is a select and a constant walk. The model has the second’s price and the first’s behaviour.

Why the check has to be on operations #

Every check available in this strand before this one was a size check, and none of them could separate the two objects.

They report the same payload. They answer the same ranks with the same values. They accept the same sets. They are indistinguishable by any test of their outputs and by any measurement of their space to within ten per cent.

What separates them is a number that neither returns: how many steps a rank took.

So the check is an inequality on operation counts, and it is written to require the two to differ — a check requiring them to agree would be a check that a size model is a structure.

Measured over four hundred probes: 1.25 against 10, a ratio of 8.0.

The other half of the check #

An inequality between two objects’ costs can pass for the wrong reason — the counters could be charging different things — so the rejection test has a second half.

Two copies of the same structure, over the same set, probed identically, must report the same cost. If they did not, the counter would be measuring something other than the structure.

They do: identical access counts over two hundred probes.

So the check says two things together. The structure and the model differ, and two copies of the structure do not. Without the second, a difference between the two could be noise in the instrument rather than a property of the objects.

The factor of eight also moves with the set’s size, which the size error does not. A binary search is ⌈log₂ m⌉ steps, so on a set of eight thousand marks it is thirteen and on a set of five hundred it is ten. The structure’s bucket walk is 1.25 regardless — it depends on the density, which the low width holds at about one per bucket, and not on m.

So the gap grows logarithmically with the collection. On a million-row index sampling one in thirty-two, the model’s rank is fifteen steps and the structure’s is 1.25, a factor of twelve.

That is worth knowing because it is the direction that makes the two harder to tell apart from their sizes and easier to tell apart from their behaviour, which is the opposite of what an accounting error usually does.

Why a model survives #

It is worth asking how an accounting for a nonexistent object stays in a codebase across several strands, because the answer is not carelessness.

It was never wrong about the thing it was used for. Every use of the class was a size, and the size was right to a bit per thousand. A model that is right about its use is a model nothing complains about.

Its behaviour was never on a plate. The class’s rank1 was called by measurement code that did not count operations, so the binary search never appeared in a figure. What is not drawn is not noticed.

And there was nothing to compare it against. Elias–Fano did not exist in this collection until this strand. A model of a structure that has not been built cannot be checked against the structure, and the only available check is arithmetic — which it passes.

That third one is the general condition. A model is checkable when the thing it models exists; before that it is a formula, and a formula’s correctness is a matter of derivation rather than of measurement.

The general shape #

Two failure modes are being conflated in ordinary usage and this incident separates them.

A model that is wrong. Its formula does not describe the object. Caught by building the object and comparing.

A model that is right and is not an object. Its formula describes the object correctly and the code holding the formula behaves differently. Caught only by measuring the code’s behaviour, which nobody does to a model, because a model is understood to be a formula.

The second is the one here, and it arises specifically when a model is implemented as a class with methods. A model that were a function returning a number could not have this problem: nobody would call it to answer a rank.

That suggests a rule with some content: a size model should not have the interface of the thing it models. A class named SparseBits with rank1, select1 and bits invites being used as a sparse bit vector, and it is a size formula wearing a structure’s clothes.

Whether the fix is to rename it, to remove its query methods, or to replace it with the real structure is a judgement about what else uses it. What is not in doubt is that the two objects have been reported as one.

Three objects this collection has caught being one #

The pattern has now appeared three times in this collection, on three different kinds of object, and putting them together makes the class of defect legible.

A structure that still holds what it claims to have dropped. What the chain cost had to guard against an index that kept a previous-occurrence chain and promised not to read it — which has the same size as one that uses it. The guard is to make the object raise when asked, so that a structure claiming not to have something cannot answer as though it did.

A generator called through the wrong path. A registry built twice produces two module instances and two caches; both are correct, and the thing being measured is not the thing being shipped. Caught by making the registry a module rather than a value the configuration exports.

A price with no structure under it. This one. Caught by counting operations on both.

All three are cases where two objects are reported as one because the reporting instrument cannot separate them. The instruments differ — an exception, a module identity, an operation count — and the shape is identical: the check has to be on a property the two objects do not share, and the properties they do share are the ones anybody was looking at.

That is the useful abstraction. When two things are being treated as one, ask what they do not have in common, and check that.

What a correct model would look like #

Since the model is staying — several structures are sized through it and replacing every call site is more churn than the ten per cent justifies — it is worth writing what its formula should be.

The low parts: m·⌊log₂(n/m)⌋, with the floor rather than the ceiling. That is a bit per thousand and it is free to fix.

The high vector’s payload: m + n/2^w, which the model approximates as 2m. At the chosen width those are within a factor of about 1.4 of each other, and the exact form costs nothing to write.

The high vector’s directory: whatever the implementation’s rank structure costs, which for a two-level directory over a vector of length L is about L/b·log₂ L + L/sb·log₂ L bits. On this collection’s parameters that is the 8–10% measured.

Three terms rather than two, one of which depends on the implementation’s block sizes. That last dependence is the reason the model was written without it — a size model that has to know the directory’s parameters is a size model coupled to an implementation — and it is also the reason the omission is not a rounding.

The resolution this strand takes is to keep the model, correct its width, and have the structure report the total wherever a total is wanted. A model is then a model of the encoding and the object is the authority on the object, which is the division that should have existed from the start.

What has to be re-read #

The honest consequence is that every size this collection has quoted through that class is ten per cent low, and it is worth saying which those are.

The r-index’s predecessor structure over the phi anchors, which is r positions in n — sized by this class since a function with r pieces built it.

The run-length index’s run starts, and the per-symbol run-end vectors, which are the same shape and are what the index that stores the runs is priced from.

Each of those is one part of a larger structure, so the ten per cent is on a part rather than on a total. Whether it changes any conclusion drawn from those sizes is a question this strand does not chase, and the answer is almost certainly no: the comparisons those numbers appeared in were between structures both of which used the class.

That is the mild version of a bad situation. A systematic error in a component appearing on both sides of every comparison cancels, and the numbers are wrong in a way that does not move any of the orderings they were used to establish.

What building the structure was actually for #

There is a reading of this strand in which the Elias–Fano array was built to save bits and the model’s exposure was a by-product. The reverse is closer to what happened and it is worth recording.

The array was built because the array that says where is twice the samples found an n-bit term sitting inside an o(n) and asked what removing it would cost. That is a size question and the answer is fifteen per cent.

The model’s exposure followed from having something to compare against, and it is the smaller result in bits and the larger one in what it says about the collection’s own instruments. A number reported for several strands, by an object nobody had checked, because there was nothing to check it against.

The generalisable part is about when a model becomes checkable. Before the structure exists, a model’s correctness is a matter of derivation — somebody reads the formula and agrees with it. After the structure exists, it is a matter of measurement, and the two are not the same standard: a derivation checks the formula and a measurement checks the code.

This collection’s habit is measurement over derivation wherever both are available, and a model of an unbuilt structure is the one case where only derivation is. Which means it is the case where the habit is suspended, and the thing to do about that is to notice when it happens rather than to have a policy.

The operation the model would have been fine at #

There is a use for which the model’s behaviour is not merely acceptable but correct, and it is worth naming because it explains why the class was written the way it was.

A sparse bit vector’s select1(k) — where is the k-th one — is, for an array of positions, pos[k]: one read, constant time, no search. Elias–Fano’s is a select on the high vector plus a low read, which is more work.

So on a workload that is all selects and no ranks, the array of positions is the better structure, and it prices identically. The class is a good implementation of a sparse set for select-heavy use.

The marks are not that workload. A locate asks at at every LF step, which is a rank, and rank1 once at the end — the walk every occurrence at the same price measured. So the operation the marks need most is the one the model is eight times slower at, and the one it is faster at is asked once per occurrence.

That is a specific enough coincidence to be worth stating: the class is right about space, right about the operation nobody needs here, and wrong about the operation the structure is built around.

Which is a reasonable thing to have written, once, for a use that wanted selects. What made it a defect was the name and the reach: a class called after a bit vector, exported from a shared module, priced as an encoding it does not implement, and reached for by four structures across three strands because it was the sparse-set representation available.