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

[Marco Tiloca <[e-mail]>]

Hi all,

Personally, I don't have an issue with the idea of (early) allocating 
such a large number of tags per se.

We are not running out of tag numbers, and even consuming one fourth of 
the remaining precious 1+1 tag numbers is in my opinion worth the 
achieved compression result (as Carsten's exercise also showed in his 
previous mail).

I also don't perceive the fundamental construct of packed CBOR as an 
abuse of the tag concept.

Best,
/Marco

On 2024-12-11 12:07, Carsten Bormann wrote:
> 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
>
> _______________________________________________
> CBOR mailing list [e-mail]
> To unsubscribe send an email [e-mail]

-- 
Marco Tiloca
Ph.D., Senior Researcher

Phone: [phone]

RISE Research Institutes of Sweden AB
Box 1263
164 29 Kista (Sweden)

Division: Digital Systems
Department: Computer Science
Unit: Cybersecurity

https://www.ri.se