[Cbor] Re: Early allocation for packed CBOR (Re: Reminder: CBOR WG Virtual Meeting on 2024-12-11)

[Carsten Bormann <[e-mail]>]

On 11. Dec 2024, at 07:05, Joe Hildebrand <[e-mail]> wrote:
> 
> Short arrays are really cheap in CBOR.

Yes, but using the tag numbers is even cheaper.

For argument bearing tags, the current WG draft creates an overhead of +2 to +5 bytes:

+2 d8 xi arg (0..31 in 1+1 tag)
+3 d9 xi ii arg (32..4095 in 1+2 tag)
+5 da xi ii ii ii arg (4096..a lot in 1+4 tag)

(The x is supposed to indicate that we are of course only using part of the space.
ii is indicating both the index and whether this is a straight or inverted reference.)

Let’s do a quick design with fewer tags to compare:
We could lose the meaning of non-integer content to Tag 6 as a short entry 0 argument reference
and instead use the following construct for all argument references:

6([index, argument])
(Use negative integer for inverted references).
This leads to:

+3 c6 82 hn arg (0..23)
+4 c6 82 hn nn arg (24-~255)
+5 c6 82 hn nn nn arg (256..~65535)

➔ one byte more (or sometimes two).  Why do users of cbor-packed want to spend this byte?

(Zipf’s law makes likely that the first indexes have a higher impact.
A quick back of the envelope test with a Zipfian distribution for tables up to size 10000 tells me the second design costs about 1.22 bytes more per straight reference than the first; this is probably a bit tail-heavy, so the real impact will be closer to 1 byte.)

We could always do the 6([index, arg]) construct in the second design for the higher index numbers only, keeping the 1+1 allocations.
This will have a more limited impact, and would get rid of the cognitive impact of using millions of tags.
But there is no “technical” reason to do that. 

Grüße, Carsten