[Cbor] Abandon cbor-packed (Re: Early allocation for packed CBOR)

[Vadim Goncharov <[e-mail]>]

On Sun, 15 Dec 2024 07:39:52 +0100
Carsten Bormann <[e-mail]> wrote:

> Hi Vadim,
> 
> > On 15. Dec 2024, at 04:24, Vadim Goncharov
> > <[e-mail]> wrote:
> > 
> > The problem is that cbor-packed does not achieve good compression
> > at all. For 2017's CBOR source of 1210 bytes, tag 25/256 method
> > achieves 904 bytes (note it's forced for 3 bytes per even shortest
> > reference, in contrast to cbor-packed cheating with single byte)
> > and cbor-packed claims 793 for same method and 564 with prefixes -
> > while even limited LZF achieves 425..435 bytes (depends on key
> > order) and less limited LZ4 variants get 404..416 bytes.  
> 
> There is no doubt that classical data compression will give you
> smaller encoded sizes than packed CBOR. But you already know where to
> find deflate, brotli, or zstd; the latter with some nice additions
> such as dictionaries. Trying to hyper-optimize Packed CBOR (e.g., by
> changing everything :-) is out of scope, as you always can go to

If changes to it are "out of scope", then entire draft must be
abandoned as absolutely inadequate and dangerous precedent.

There was long message from Christopher Allen on Wednesday, where is
your response to valid arguments in it?

> well-established classic data compression for that.
> 
> CBOR packed is just solving a different problem [1]:
> 
> >> This specification describes Packed CBOR, a simple transformation
> >> of a CBOR data item into another CBOR data item that is almost as
> >> easy to consume as the original CBOR data item. A separate
> >> decompression step is therefore often not required at the
> >> recipient.  
> 
> [1]:
> https://www.ietf.org/archive/id/draft-ietf-cbor-packed-13.html#section-abstract-3

This is simply not true. Neither cbor-packed is "simple" transformation
nor it is "easy to consume" - in fact, LED example in draft
demonstrates splitting one string to five (!) chunks, using recursion.
It leads to complex algorithms to work with such data, *especially* for
constrained implementations.

Where is your proof? Do you have a real implementation able to work
with such very crunhed data?

> Different from classical data compression, there is no need to
> unpack/decompress Packed CBOR before using the data.  (Many
> applications will want to do that anyway, but the point is that APIs
> that make sense for constrained implementations can easily get by
> without.) 

No, they can't. There is no "wide applicability area" for cbor-packed,
the opposite is true - it's suitable only in some niche.

> Packed CBOR is valid CBOR, so it can be embedded into other
> CBOR data and processed by generic decoders/encoders (*).

No, it can't. It is absolutely useless after generic decoder which
don't understand how to use it. And this is true for *any* tags not
merely signifying data type but trying to extend CBOR - e.g.
compression using tags 25/256 by Marc A. Lehmann is built-in into
codec, being transparent for application. And this method is really
simple and suitable for constrained implementations, in contrast to
cbor-packed.

BTW, I had talk with him, as he has Compress::LZF [1] module which is
more lightweight than LZ4 (offsets are 8192 bytes max, so less memory),
and he suggested https://github.com/atomicobject/heatshrink (LZSS
variant) for really constrained environments - just hundred of bytes of
memory.

[1] https://metacpan.org/pod/Compress::LZF 
~200 lines of C encoder
https://metacpan.org/release/MLEHMANN/Compress-LZF-3.8/source/lzf_c_best.c
& decoder
https://metacpan.org/release/MLEHMANN/Compress-LZF-3.8/source/lzf_d.c

> Obviously, not everyone needs Packed CBOR, so I can understand some
> haggling about tag space, in particular for the 40 code points the
> draft acquires for the referencing tags from the 1+1 space (plus
> three function tags and one basic table setup tag). I believe this
> number is appropriate, given that the reference tags are pretty

The main problem of which we all angry is stealing so much tag/simple
scarce space for *NO* real benefit. Packed CBOR is VERY ineffective,
yet wastes so much tags. The same task can be achieved without using so
many short tags, thus cbor-packed must be either fixed or abandoned.
I've not even mentioned yet other problems with draft, like using of
Undefined instead of (at least) tag 31, or - more serious- not
supporting CBOR sequences.

> universal/future-proof as they can be used with table setup
> mechanisms we haven’t even invented yet.

What? Draft lacks this extensibility - setup tags don't have any
alternatives, e.g. specifying dictionary ID/hash, like in zlib etc.

> $ tag-report.rb
> range  used     %                 free                total
> 0 1+0    13 54.17                   11                   24
> 1 1+1    73 31.47                  159                  232
[..] 
> (*) And, yes, it would be interesting to come up with a design for
> instead using the 24 unused bit combinations (ai=28..30), but that,
> again, cannot be used as part of valid CBOR; it’s more like a CBOR
> 2.0 project.

Absolutely not. It is very simple to retain compatibility - "modified"
CBOR is just wrapped into bstring/array under tag. Like this CDDL-like:

   CBAR-CBOR = #6.10([atoms, bytedict, CBAR, checksum])  ; Tag 0x0a for
   "Atom" / #6.10(CBAR)    ; binary string - everything other setup
   earlier

   atomarr = [ + atom ]    ; "atom" is like in X11 sense - number of string
   atom = bstr             ; raw value
        / #6.10(bstr)      ; itself CBAR - definition uses previous
   atoms / any             ; valid CBOR fragment to substitute

   atoms = atomarr / uint / bstr, ; atoms array (mb empty) or their hash
   bytedict = bstr / uint,        ; (zlib) dictionary (mb empty) / it's hash
   CBAR = bstr .size (3..),       ; may have tag for additional pass e.g. zlib
   ? checksum = uint

Here, extensibility point is left via additional types, not yet
specified but intended to. Actual compressed data in CBAR bytestring is
that modified CBOR, so CBOR parsing code may be reused, without
constraints of being compatible with non-understanding decoders. Being
mostly CBOR satisfies goal of implementation API where application gets
pointer and length to data in original CBOR without copying - the only
looking reasonable goal of cbor-packed... modulo it's not achievable in
practice in any scheme involving splitting streams. And see, valid
CBOR with no giant ranges of tags and 27 codepoints available!

Trying to be "just CBOR" is the most design flaw of cbor-packed - it
leads to inefficient compression, it leads to wasteful efforts, while
being meaningless.

-- 
WBR, @nuclight