Discussion regarding a new 16-byte tape (comments invited)

Here is the first sketch of a proposal to have a (wider and flatter) 16-byte tape up from our current hybrid 8-byte tape. (This is issue https://github.com/lemire/simdjson/issues/361) In this new tape, all nodes would be represented with a single 16-byte value. Except for scopes (arrays and objects) that would contain two 16-byte values. The tape could be iterated efficiently in either order (forward and backward).

The tape would have an accompanying string tape, as currently, but the string tape would contain only UTF-8 string content, the strings would be appended one after the other. Currently, the string tape contains 32-bit length-prefixed strings. In the new model, the string length would be part of the tape.

Having exactly 16-byte values all the way ensures that we could navigate the document backward and forward without any problem. (Issue https://github.com/lemire/simdjson/issues/292 ) It can also improve performance when navigating in forward order since there is no possible misprediction when loading the next tape element.

We would support arbitrarily large JSON documents containing arbitrarily large strings.

The new string tape would be made of just valid UTF-8 string content, so we could do UTF-8 validation there, instead of doing it in stage 1 as is done currently. This could potentially improve the performance drastically. This is issue https://github.com/lemire/simdjson/issues/185

General formal of the tape elements

We would reserve a byte out of each tape element for an ASCII character identifying the nature of the node 't', 'f', 'n', 'l', 'u', 'd', '"', '{', '}', '[', ']' ,'r' (where 'r' stands for root)

Simple JSON values

Simple JSON nodes are represented with one tape element containing the type 'n', 't', 'f' and nothing else. This is massively wasteful of memory since we use one byte out of 16. But it is not clear what else to do without wasting performance.

Both 64-bit ARM and x64 can turn a 16-byte write into a single instruction, if the write to the tape is a constant value.

Integer and Double values

Numbers are already represented as 16-byte values on the tape, so that they would not change.

Integer values are represented as two 64-bit tape elements:

• The 64-bit value ('l' << 56) followed by the 64-bit integer value litterally. Integer values are assumed to be signed 64-bit values, using two's complement notation.
• The 64-bit value ('u' << 56) followed by the 64-bit integer value litterally. Integer values are assumed to be unsigned 64-bit values.

Float values are represented as two 64-bit tape elements:

• The 64-bit value ('d' << 56) followed by the 64-bit double value litterally in standard IEEE 754 notation.

We have 7 bytes of free space, but it is not clear what to do with it.

There are demands to support big integers and arbitrary-precision values. We could engineer a special secondary tape where such values are coded, and we could refer to this off-tape value.

Performance consideration: We store numbers of the main tape because we believe that locality of reference is helpful for performance.

Root node

Each JSON document will have two special tape elements representing a root node, one at the beginning and one at the end.

• The first 16-byte tape element contains the marker value 'r' and the location on the tape of the last root element as a 64-bit value.
• The last 16-byte tape element contains the value 'r'.

All of the parsed document is located between these two tape elements.

It might be possible to use the extra space leftover to store other useful information.

Hint: We can read the first tape element to determine the length of the tape.

Strings

We store string values using UTF-8 encoding with null termination on a separate tape. A string value is represented on the main tape as the 16-byte tape element with the marker '"' and a 64-bit pointer to the string tape. We use the remaining 7 bytes to store the length of the string. Thus we would limit strings within JSON documents to 2^58 bytes, but that's truly enormous.

Short strings (proposal)

We would introduce a "short string" type. It would be made of short strings, containing fewer than 16 bytes and not null-terminated. We would use null padding.

The benefit of these short strings is that they would fit in the main tape, so that they could drastically improve the performance when querying the documents. Many JSON documents are filled with short strings.

Arrays

JSON arrays are represented using two 16-byte tape elements.

• The first 16-byte tape element contains the value marker '['. We store the number of elements in the array. We store a pointer to second 16-byte tape element.
• The second 16-byte tape element contains the value ']'. We store the number of elements in the array. e a pointer to first 16-byte tape element.

All the content of the array is located between these two tape elements, including arrays and objects.

Knowing up front how many elements are in the array would solve issue https://github.com/lemire/simdjson/issues/308

Explanation: we need a first and last tape element if we are to be able to navigate the document in backward order.

Performance consideration: We can skip the content of an array entirely by accessing the first tape element, reading the payload and moving to the corresponding index on the tape.

Objects

JSON objects are represented using two 16-byte tape elements.

• The first 16-byte tape element contains the marker value '{'. We store the number of keys in the object. We store a pointer to second 16-byte tape element.
• The second 16-byte t tape element contains the marker value }'. We store the number of keys in the object. We store a pointer to first 16-byte tape element.

In-between these two tape elements, we alternate between key (which must be strings) and values. A value could be an object or an array.

All the content of the object is located between these two tape elements, including arrays and objects.

Performance consideration: We can skip the content of an object entirely by accessing the first tape element, reading the payload and moving to the corresponding index on the tape.

Trade-offs

A 16-byte tape would be able to support very large files whereas our 8-byte tape is limited to 4GB files. However, somewhat ironically, a 16-byte tape might use more memory and thus make page allocation more expensive, a bottleneck when processing large files (Doubling the size of the tape would make page allocation more expensive and could make the processing of large files much more expensive: https://github.com/lemire/simdjson/pull/443).

On some systems, memory allocation runs far slower than we can parse (e.g., 1.4GB/s), especially when using small pages.

cc @jkeiser

Start with this proposal and the linked issues 361, 292, 185, and 308 to understand the competing requirements for the tape format. No implementation files or tests are identified; the work is not ready until the design is resolved and a concrete implementation scope and completion criteria are agreed.