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

[Carsten Bormann <[e-mail]>]

Hi Joe,

please get well soon!

> On 11. Dec 2024, at 02:01, Joe Hildebrand <[e-mail]> wrote:
> 
> Does anyone else think that this is a LOT of tags to allocate for one thing?  Was there no other design that could achieve the goals?

A ton of tags.  I think some 335544318 or so of them.

Section 2.5 briefly addresses this [1].

[1]: https://www.ietf.org/archive/id/draft-ietf-cbor-packed-13.html#section-2.5


Let me point out that the way this was designed simply exercises a design pattern that has developed for CBOR.

In CBOR, tags have exactly one data item in its content.
For sharing tags, we can use that as an index into the table, so we have just one of them (number 6, in 1+0 space, where we add 16 direct sharing references from the 1+0 simple value space as well).

For argument-bearing tags, we have both the table index and the argument that need to be included.
This could be done putting these into an array, at the cost of one byte (0x82, that is).
Including the index in the tag number is a byte-saving workaround that now has been used in many places.
It means that we allocate a range of tag numbers and provide a function that computes the index out of the tag number (usually a subtraction).


Now, there is also the question whether we should expend the amount of tags we are registering here.
CBOR-packed is not really “one thing”, but a rather versatile mechanism that can be used in many ways (often by defining application-specific table-builders), so expending some of the tag reserve for this appears to be a good investment into the future.

Here is today’s tag-report:

range  used     %                 free                total
0 1+0    13 54.17                   11                   24
1 1+1    73 31.47                  159                  232
2 1+2  1087  1.67                64193                65280
3 1+4 65539  0.00           4294836221           4294901760
4 1+8     2  0.00 18446744069414584318 18446744069414584320

Expending about one fifth of the free 1+1 tags (and one tenth of the free 1+0 tags), as well as 80 % (!) of the 1+0 simple values, is a sizable investment, but I would consider that worthwhile given the above.  I don’t think the thirteenth of 1+2 and 1+4 each is oversized at all.

Grüße, Carsten


PS.:
If we talk about numbers, we can group the tags to be allocated into table building tags, of which we spend two (one 1+1 and one 1+2), special tags for function references, of which we spend three (1+1), and the approximately 335544318 we use for straight and inverted references (plus the one 1+0 for shared references).
Seems frugal to me :-)

Historical tidbit: 
an early form of cbor-packed was part of the initial design before we even named the format CBOR; we removed it from the proposal because that already was complex enough.  I’m quite happy that 11 years later this is still the way we want to address redundancy, but by now with a few refinements.