One byte at offset −13: column attributes in C

There is a byte at offset -13 of every array Amber allocates. On a fresh vector it is zero. Set it to one and a linear scan over five million elements becomes a binary search: 4.23 seconds becomes 1.9 milliseconds, with the same input, the same code path from your side, and an identical answer.

That byte is the whole of Amber's column attributes. This post is what it means, where it came from, which kernels are allowed to believe it, and why "metadata" is exactly the wrong word for it.

What an attribute actually is

An attribute is not a description of a column. It is a promise, made by whoever set it, that the column satisfies a structural property — and a licence for the kernel to skip the work of proving that property itself.

The distinction matters because it decides what happens when the promise is false. A description that is wrong is merely stale. A promise that is wrong produces a wrong answer — quietly, at speed. Amber does not verify the promise on every read, because verifying it costs exactly what believing it saves.

The whole point of carrying an attribute is not having to re-derive it.

— comment in src/a.c, next to the as-of join kernel

So the interface is built so that the normal way of producing a sorted column also sets the flag. asc sets `s. xasc sets it on the column it sorted by. gentq stamps both `s on time and `p on sym. You reach for `sa by hand only when you are asserting something about data that arrived already ordered — from a partitioned store, say, or a tickerplant that guarantees sequence.

Where the byte lives

K's object header sits before the payload and every field is a negative offset. From src/a.h:

#define _n(x)  (*(U *)((x)- 4))  //length
#define _r(x)  (*(U *)((x)- 8))  //refcount
#define _T(x)  (*(UC*)((x)- 9))  //type(hdr)
#define _k(x)  (*(UC*)((x)-10))  //arity(for funcs)
#define _E(x)  (*(UC*)((x)-11))  //adverb(for tr)
#define _O(x)  (*(UC*)((x)-12))  //scroffset(for symbol lists)
#define _at(x) (*(UC*)((x)-13))  //amber attribute: 0=none 1=sorted(`s)

Byte -13 was unused for every type that is not a function. So the attribute costs nothing: no extra allocation, no second structure to keep in sync, no pointer to chase. It is already in the cache line the kernel is about to touch anyway, because the header and the payload share one.

Setting it is four nearly identical one-liners in src/a.c:

Z A1(qsa,UC t=_t(x);P(_tP(x)||!LH(tG,t,tS),x)x=mut(x);_at(x)=1;x)//`s sorted
Z A1(qua,UC t=_t(x);P(_tP(x)||!LH(tG,t,tS),x)x=mut(x);_at(x)=2;x)//`u unique
Z A1(qpa,UC t=_t(x);P(_tP(x)||!LH(tG,t,tS),x)x=mut(x);_at(x)=3;x)//`p parted
Z A1(qga,UC t=_t(x);P(_tP(x)||!LH(tG,t,tS),x)x=mut(x);_at(x)=4;x)//`g grouped

Read one of them: if the value is a packed atom or not a type that can carry an attribute, return it unchanged; otherwise take a mutable copy (refcount discipline — you may not stamp a value someone else is holding) and write the byte.

No index is built. No data is moved. No validation is performed. That last one is deliberate and worth being explicit about: `sa on an unsorted vector is a lie you are allowed to tell, and the engine will believe you. This is exactly how kdb+ behaves, and the alternative — an O(n) check on every set — would make stamping a hundred-million-row column as expensive as sorting it.

Reading it: kernel selection in fnd()

Here is where the byte earns its keep. src/f.c, the find primitive:

B srt = !_tP(x) && xt!=tF && xt!=tS && (_at(x)==1 || _at(x)==3);
TY(fGL)*f = (srt ? G(&bGL,bHL,bIL,bLL)
                 : G(&fGL,fHL,fIL,fLL))[xw-3];

Two lines. srt is true when the left argument carries `s (1) or `p (3). If it does, f points into the b-family — bGL, bHL, bIL, bLL, one per integer width — which binary-search. If it does not, f points into the f-family, which does not. Everything after that line is identical: same loop, same output vector, same semantics.

The width suffix (G/H/I/L — 8, 16, 32, 64 bits) is selected from the column's own type in the same expression, because Amber stores an integer vector in the narrowest type that holds every element. So 1 2 3 is physically int8, and the search that runs over it is the int8 search, comparing four times as many elements per cache line as a naive int64 column would.

Why `p takes the same path as `s

Because a parted column is a sorted column for search purposes. "Equal values are contiguous" is weaker than "non-decreasing" in general — `p permits 3 3 1 1 2 — but for finding the boundaries of a run, a binary search over the run structure works either way, and the practical case that produces `p is a symbol column that was sorted and then had its runs noted. Treating them together is one fewer branch in the hot path.

Why floats and symbols are excluded

xt!=tF && xt!=tS. Floats are out because 0n and the infinities do not order the way a naive comparison expects and I would rather be correct than clever. Symbols are out because a symbol column stores interned 32-bit ids and the ids are allocated in first-seen order, not alphabetical order — a symbol column that looks sorted to a human is not sorted in the representation the kernel compares. Grouping and joining on symbols is fast for a different reason (they are integers), and that is enough.

The numbers

bench.k measures ? (find) on identical data, sorted-attributed versus not. It builds one vector, makes a second from the same values with the attribute dropped, checks the two results are identical, and times both. The assertion that they agree is in the benchmark, not in a comment.

Look at the shape of the last column rather than its magnitude. The speedup grows with n, because one side is O(n·m) and the other is O(m·log n). A headline number from one size tells you almost nothing; the slope tells you whether the system degrades gracefully as the tape grows or falls off a cliff on exactly the busy day when it matters.

The one that is not like the others

`g — grouped — does not accelerate ?. It asserts that a group index exists, and the index is what does the work. In fin.k that is three functions and they are three lines:

gidx:{=x}                        / index of a vector:  value -> positions
bysym:{[t]=t`sym}                / per-symbol row positions of a table
symrows:{[t;g;s]atr[t;g s]}      / O(1): the rows of t for symbol s

= is K's group primitive: it returns a dictionary from distinct value to the vector of positions where it occurs. Build it once, and every subsequent "give me AAPL's rows" is a dictionary lookup followed by an index — no scan, no comparison, no matter how many symbols there are or how many rows each has.

gentq 100000
g:bysym trades                   / build the index once
#symrows[trades;g;`AAPL]         / O(1) thereafter

bench-fin.k measures that against a linear filter and reports roughly 20,000×. It is a less interesting number than it sounds, because it is really measuring "a hash lookup versus a full scan" — the honest version is that grouping is what you want when you will slice the same table by the same key many times, and a scan is fine if you will do it once.

Seeing them

A promise you cannot inspect is a promise nobody will trust. Attributes are visible from the first release, in two places.

`at v                            / read the attribute: `s `u `p `g or `
meta trades                      / the `a` column of the metadata table

c     | t a
------|-----
sym   | s p
time  | j s
px    | f
sz    | i

meta's third column is {`at x}'value d — the attribute of each column, mapped. Nine characters of the definition, and it is the single most useful diagnostic in the language: if a query is unexpectedly slow, meta is where you look first, and the answer is almost always an empty a column.

Where attributes are believed elsewhere

Find is the headline, but it is not the only place. Three more, in increasing order of how much they matter.

The as-of join skips a proof

aj needs to know that its right-hand table's rows are grouped into contiguous runs by symbol and ordered by time inside each run. Establishing that from scratch is a pass over the data. Instead, ajsorted asks the columns:

ajsorted:{[c;t] … g0:*gc; `ajs(gc; d tc; $[1=#gc; in[`at g0;`s`p]; 0b])}
ajord:{[c;t]$[ajsorted[c;t]; t; xasc[c;t]]}

If the grouping column already carries `s or `p, the third argument to the C kernel is true and the kernel skips the pass that would have proved it. If not, the table is sorted first — correctly, just more slowly. The comment in src/a.c next to the flag reads: "an attributed column lets us skip it outright — the whole point of carrying an attribute is not having to re-derive it."

The attribute survives the wire

When the binary serializer arrived in 1.9.3, the attribute byte went into the format explicitly:

ATTRIBUTES.  _at(x) (0=none, 1=`s#-sorted) rides in the attr byte for every
heap type, so a sorted column stays sorted across the wire and keeps the
O(log n) binary-search path in fnd() on the far side.

Which sounds like a footnote and is not. A column that arrives from a peach worker, or from a file in a partitioned store, or from a tickerplant log, would otherwise lose its promise at the boundary — and the receiving side would have to re-establish it with a sort, per message, forever. amber-tick's store writes one file per column in exactly this format, with `s# stamped on time, so a partition loads and is immediately ready for an as-of join.

A sorted result stays sorted

Some operations produce a result that is provably ordered. Where that is true, the attribute is propagated rather than dropped, so the next operation gets it for free. In src/v.c, after a kernel that emits values in ascending run order:

_at(z) = 1;                   // result IS sorted: keep `s#

One line. It is the kind of thing that is easy to forget and expensive to forget, because the cost of dropping an attribute is not paid where you dropped it — it is paid three operations later, in code that looks fine.

What attributes do not do

Being honest about the boundary is more useful than the speedups.

• They do not make anything correct. Every kernel returns the same answer with or without them. If a query gives a different result once you add `s#, that is a bug in Amber or a false promise from you, and either way something is wrong.
• They do not survive arbitrary transformation. Add a constant to a sorted column and the result is still sorted, but the general case is not provable cheaply, so most operations drop the attribute rather than guess. Re-stamp after a transformation you know preserves order.
• They are not free to establish. Setting the byte is free. Sorting the two hundred million rows so that the byte is true is not. The right time to pay it is once, at ingest, as part of writing the store — which is why gentq sets both attributes and why amber-tick lays its partitions out sorted by (sym, time).
• They do not help symbols or floats find faster. See above.

An unrelated 32×, and why it is in this post

In 1.9.2 I found that x?y on unattributed integer vectors was a linear scan of x for every element of y — O(#x · #y). The comparative benchmark's inner join, one million left keys probed against a thousand sparse right keys, was therefore five hundred million comparisons: 180.95 ms, 126× the C baseline, and Amber's worst cell in the table by a wide margin.

The fix builds an index over x once, in whichever of two shapes fits the data:

Both fill backwards, so the lowest index wins and ?'s first-occurrence semantics stay exact. Result: 180.95 ms → 5.66 ms, 32×.

I am putting it in the attributes post because of the last clause of that change: neither index is built unless it beats the scan it replaces, and `s#-sorted x keeps its existing O(log m) binary search.

That is the design rule, stated by a counter-example. The index is a fallback for when you did not tell the engine anything. The attribute is you telling it something, and it still wins — no allocation, no build pass, no cache footprint beyond the data itself, and it survives serialisation, which an index built on the fly does not.

Using them

In practice it is three habits.

/ 1. sort with xasc — it stamps the attributes for you
trades:xasc[`sym`time; trades]
quotes:xasc[`sym`time; quotes]
meta trades                        / check: sym -> p, time -> s

/ 2. build a group index when you will slice the same table repeatedly
g:bysym trades
symrows[trades;g;`AAPL]

/ 3. when a query is slow, look at meta before you look at anything else

And one habit for anyone loading data from outside: if your store already guarantees an order — because a tickerplant sequenced it, or because you wrote the partition sorted — say so explicitly with `sa rather than re-sorting to re-derive something you already know. That is the case the whole mechanism exists for.

Why this is the post I most wanted to write

Everything else in this series is code: a parser change, a kernel, a wire format, a line editor. Attributes are barely code at all. Four one-line setters, two lines of kernel selection, one byte in a header that was already there.

What they are instead is a contract — a place in the design where the system lets you say something you know and be rewarded for it, rather than re-deriving it on your behalf every time because it does not trust you. The whole of the performance story that follows in post four is downstream of that: the as-of join is fast because it is allowed to assume the layout, and it is allowed to assume the layout because there is somewhere to record that you promised it.

One byte. Nobody has to look for it.