Repository navigation
Description
Tracking issue for the SoA offset-table and any-typed field work. Nothing here is proposed upstream yet.
Branch
spec/soa-offset-table-count, pushed, three commits, stacked on NeuroJSON#40:
418fe3delement type marker —[$mS]/[$mH], sinceoffset-stringandoffset-highprechad identical productions99b18c7explicit offset count —[$m#U4S], index width derived from the count rather than the offset typec2101bcvalue buffer as an optimized byte array, so it states its own byte length
+93/−44 across Binary_JData_Specification.md and one line of schema/bjdata_format_schema.json. Example 2 drops from 13 to 10 bytes per record on identical data, entirely from the narrower index.
PR body is written but the PR is not opened. Draft lives outside the repo at ~/.claude/projects/-Users-nebkat-Work-Troo-bjdata/drafts/pr-soa-offset-table.md.
Settled while working through it
Recording these so they do not get re-litigated.
Offset mode is an indirection, not positional addressing. Both njv and loadbj read the index out of the record and use it to index the table, so several records may share a span. The spec text describes only the case where they do not.
The spec's N is ambiguous rather than wrong. It appears only in the storage-structure diagram; one line binds it to the records, while N+1 offsets and an index range of 0..N-1 read as the span count. The two coincide only when nothing is shared. The actual gap is that nothing declares the table's size, so a decoder has the record count and little else to go on.
The count is the number of offsets, so [$m#U4S] is 4 offsets delimiting 3 values. That keeps $<type>#<count> a literally well-formed optimized-array header, at the cost of the fencepost being visible when writing a schema by hand.
Index width derives from the count by the rule dictionary mode already uses. Offset width tracks buffer size, index width tracks value count, and the two are unrelated.
The buffer is a full optimized array including the leading [, costing 6 header bytes rather than 4. That is what makes it readable by a generic BJData parser, which was the reason for using B at all.
elem-type is a lens over raw bytes rather than a mode selector, which makes it an extension point rather than a one-off fix.
Dictionary and offset modes are close on size once the table can shrink. The real difference is operational: a dictionary needs the full value set before it can pick an index width, while an offset table is single-pass and seekable.
To rebuild
The A any-typed field proposal was lost when /private/tmp was wiped. It was never committed. Design as it stood:
[$m#U6A], with the value buffer holding complete BJData values, each carrying its own type marker. Since no BJData value occupies zero bytes, a zero-length span is spare vocabulary: it means the field is absent from that record, while a one-byte span holding Z means present-and-null. That covers optional, nullable and any-typed in one mechanism with no presence bitmap. Purely additive — a schema not using A encodes identically. Depends on the elem-type slot from 418fe3d, so it stacks on this branch.
Also worth considering
A fixed-width lens would give ragged numeric arrays: [$m#U4d], with the element count per record implied by span_length / 8. SoA currently only expresses fixed-length arrays, so per-record variable-length numeric data means leaving SoA entirely. Probably more valuable to NeuroJSON's workload than A is, and it costs nothing per record beyond the offset.
Blocking / open
NeuroJSON#40 has been open since 13 Sep and is unmerged. This branch stacks on it, so a PR opened now would show all five commits.
Both reference decoders read exactly count + 1 offsets and take index width from the offset marker, so both need updating for the first two commits.
There is SoA work in Troo/pybj dated 11 Oct that I have not looked at. If it touched offset-table decoding it should be reconciled before any of this lands.
Two smaller spec notes, not yet proposed
Dictionary entries repeat the uint length-type marker per entry ([U][6][active]). Hoisting a single length type for the whole dictionary would cut per-entry overhead from 2 bytes to 1 for short values.
The "O(1) lookup for string values" listed under dictionary mode holds only once a decoder has walked the length-prefixed entries to build an index; it is not O(1) directly against mapped bytes, whereas an offset table is. Worth qualifying in the text.
Size comparison, for reference
Once the table can shrink, the two modes store the same per-record index and differ only in how the side table is encoded. Dictionary costs M*(1+s) for M length-prefixed entries, where s is the width of an individual length; offset costs (M+1)*w, where w must cover the whole buffer. For short values (s=1) that is 2M against (M+1)*w, so the crossover is w against 1+s: offsets win at w=1, tie at w=2, and cost 2-4x more at w=4 or w=8. Since w grows with total buffer size while s tracks individual value size, dictionary encoding pulls further ahead as the field grows — which is why the case for offset mode rests on seekability and single-pass encoding rather than on size.
Separately, for deduplication against no deduplication at all: a dictionary beats storing every value when L*(N-U) > c*U, i.e. when the duplication ratio N/U exceeds 1 + c/L for mean value length L and per-entry overhead c. At L=10 that is any ratio above about 1.2, so repetition pays off quickly.
Implementation references
Line numbers are against viewer/njv.py at this repo's HEAD and lib/matlab/jsonlab pinned at 7b38ce69.
Indirection, reading the index from the record rather than using its position: njv.py:337-339, njv.py:305-309, loadbj.m:1156-1158.
Index width taken from the offset marker: njv.py:233-235, loadbj.m:708-711. Both also hardcode the field type as string, so H has no path through offset mode.
Table read as exactly count + 1 entries: njv.py:270, loadbj.m:930. Buffer length from the final offset: loadbj.m:935.
Encoder side in savebj.m: mode selection at 753 (dictionary when nunique/nrecords <= 0.5 and nunique <= 65535), 765 (fixed when maxlen <= 255), 774 (offset otherwise, offset type from mininttype(sum(lens))); dictionary index width from mininttype(nunique) at 756; offset indices written as uint32(0:nrecords-1) at 855; table and buffer built over every value without deduplication at 1109-1110.
lib/dart/dart-bjdata has no SoA support.
Activity