Subject: [Cbor] Review draft-bormann-cbor-packed-00

From: Jim Schaad <[email-masked]>
Date: Wed, 15 Jul 2020 12:06:54 -0700

Carsten,

I am finding this document really hard to follow.  I am sure that we can get
it to read much better in the future.  Some of the issues that I am having
are:

1.  How the Tag 6 is used is dependent on the type of the embedded content
and this is not explained at all.  It took me a while to understand why
#6.6(0) was not a potential duplicate value between sections 2.1 and 2.2.

2.  I am trying to get a handle on where you think this would be used and
how much compression is going to give me.   Part of this is going to be a
question of how much compression is obtained and the difference between
optimal and reasonable.   For example, Tags 224-255 would end up with 2
bytes for the tag, plus the encoding of the suffixed data.  Moving to
#6.6([#, suffix]) ends up with 4 bytes plus the encoding of the suffix.
This means that you would want to save a minimum of 8 bytes in the prefix
rather than 4 bytes.  You are also going to have two bytes consumed in the
suffix table for strings.

3.  It would be really good to expand the example to include a case of
prefix compression as well.  This would make that concept much easier to
understand.

4. I am having a hard time figuring out how you are going to get a reference
loop because I was assuming that any shared items that would need to be
unpacked would have it's own dictionary defined.  This seems to imply that
shared items are using the same dictionary.   This needs an example.

5. Is there a reason not to switch to using '^' for exponentiation?  This is
the more mathematical one symbol.

6.  As we compose documents nested documents will become more frequent.  The
question is should the multiple levels be merged into a single compression
table.

7.  I am not happy about the complete abandonment of providing guidance for
a packing algorithm.  At a minimum things like doing advance computing on
compression, using pre-defined vocabularies (if not dictionaries) is most
likely usable.

8.  Should we provide an option to use an application defined dictionary as
that would pack even more at the penalty that the document could not be
unpacked without that dictionary.

Jim

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 15 Jul 2020 21:43:28 +0200

Hi Jim,

Thanks for this lightning feedback.  Let me try to answer as quickly...

> On 2020-07-15, at 21:06, Jim Schaad <[email-masked]> wrote:
> 
> Carsten,
> 
> I am finding this document really hard to follow.  

Yes.  It contains the specification, but not yet any tutorial material.
Way too few examples.

> I am sure that we can get
> it to read much better in the future.  

Absolutely.

> Some of the issues that I am having
> are:
> 

Yes.

Section 3, second paragraph says this, but that may be a little late…

(I always read the discussion before the normative part, so I just didn’t notice.)

> how much compression is going to give me.  

Use where?  Where simple data models exhibit too much sharing, or where the strings that go into those have too long common prefixes (which happens a lot in RDF-derived environments).
And the point is that there is no need for decompression at the consumer.

How much compression?  One data point:
http://www.w3.org/2017/07/wot-f2f/slides/w3c-serialization.pdf — slide 6.
1/3 off by sharing, ~ 1/5 more off by prefix compression. 47 % left.
(Deflate gives 29 %, so is 57 % of cbor-packed.)
A static dictionary would help some more.

> Part of this is going to be a
> optimal and reasonable.  

I you need optimal compression, go for LZ77 over the whole thing.
Cbor-packed is reasonable :-)

> For example, Tags 224-255 would end up with 2

Right.  That’s why the draft is a bit aggressive about obtaining 1-byte and 2-byte references.

> prefix compression as well.  This would make that concept much easier to

Yes.

> unpacked would have it's own dictionary defined.  

No, only the top level has shared/prefix items.
Shared/prefix item 5 could reference Shared/prefix item 5 (insert larger loop as needed).

E.g., shared item 0 could be “sold out”, and shared item 1 could be {“price”: 9.99, “stock”: simple(0)}.

> This seems to imply that

Right.  Half an example above.

> the more mathematical one symbol.

Yes. ^ is XOR in C.
In math, we do that differently.
Like 2⁶⁴ :-)  But the RFC editor won’t let me do that, I’m sure...

> question is should the multiple levels be merged into a single compression

Well, you could try it, and if it gets longer (because the references to a larger dictionary get larger), you don’t.

> compression, using pre-defined vocabularies (if not dictionaries) is most

Just putting the JSON object labels into a dictionary, sorting by number of use, and removing those that are not referenced often enough or where the references get larger than the actual strings, is often 80 % of the gain.
My little toy packer (250 LOC) simply tries to share *all* duplicate sub-items.  The fun comes in if a duplicate sub-item has a sub-item shared with another sub-item, which may make referencing the duplicate sub-item less optimal than just copying the sub-item.  I’m not sure my algorithm is very sane, but I like the output, and for the details that’s what we have BYGS (*) for.

> unpacked without that dictionary.

Yes.  The question is how that is obtained (from context?), and how the dictionary items are merged with those shared items listed in the item (the dictionary may or may not have the most frequently used shared items in the specific data item to be packed).  I wouldn’t want to COSE-sign a packed CBOR data item where it is hackable from where the dictionary came...

Grüße, Carsten

(*) Bright young grad students

---

From: Jim Schaad <[email-masked]>
Date: Thu, 16 Jul 2020 05:44:06 -0700

> -----Original Message-----
> From: CBOR <[email-masked]> On Behalf Of Carsten Bormann
> Sent: Wednesday, July 15, 2020 12:43 PM
> To: Jim Schaad <[email-masked]>
> Cc: [email-masked]; [email-masked]
> Subject: Re: [Cbor] Review draft-bormann-cbor-packed-00
> 
> Hi Jim,
> 
> > 5. Is there a reason not to switch to using '^' for exponentiation?
> > This is the more mathematical one symbol.
> 
> Yes. ^ is XOR in C.

Just the one item.  2<sup>64</sup> is what you are looking for.
> _______________________________________________
> CBOR mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cbor

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 16 Jul 2020 15:32:33 +0200

> Just the one item.  2<sup>64</sup> is what you are looking for.

Ah, right.

And the TXT substitution XML2RFC offers is broken.

Well, more text in the intro…

Grüße, Carsten

---

From: Jim Schaad <[email-masked]>
Date: Thu, 16 Jul 2020 07:01:58 -0700

> > 1.  How the Tag 6 is used is dependent on the type of the embedded
> > content and this is not explained at all.  It took me a while to
> > understand why

[JLS] I tend to read documents from the front to the back.  😊

> 
> > 2.  I am trying to get a handle on where you think this would be used
> > and how much compression is going to give me.
> 
> Use where?  Where simple data models exhibit too much sharing, or where the
> strings that go into those have too long common prefixes (which happens a lot
> in RDF-derived environments).
> (Deflate gives 29 %, so is 57 % of cbor-packed.) A static dictionary would help
> some more.

Yes, but are you willing to settle for ~30% rather than ~33% when looking at sharing.

> > question of how much compression is obtained and the difference
> > between optimal and reasonable.
> 
> > For example, Tags 224-255 would end up with 2 bytes for the tag, plus
> > the encoding of the suffixed data.  Moving to #6.6([#, suffix]) ends
> > up with 4 bytes plus the encoding of the suffix.
> > This means that you would want to save a minimum of 8 bytes in the
> > prefix rather than 4 bytes.  You are also going to have two bytes
> > consumed in the suffix table for strings.
> 

[JLS] And I think that good-enough could be less aggressive about this.

> 
> > 4. I am having a hard time figuring out how you are going to get a
> > reference loop because I was assuming that any shared items that would
> > need to be unpacked would have it's own dictionary defined.
> 

[JLS] Yes this is what I expected after coming across the recursion problem.  But this is now also becoming more complicated than just looking for common strings when building the compression tables.

> > 6.  As we compose documents nested documents will become more
> > frequent.  The question is should the multiple levels be merged into a
> > single compression table.
> 
> > 7.  I am not happy about the complete abandonment of providing
> > guidance for a packing algorithm.  At a minimum things like doing
> > advance computing on compression, using pre-defined vocabularies (if
> > not dictionaries) is most likely usable.
> 
> Just putting the JSON object labels into a dictionary, sorting by number of use,
> and removing those that are not referenced often enough or where the
> references get larger than the actual strings, is often 80 % of the gain.
> My little toy packer (250 LOC) simply tries to share *all* duplicate sub-items.
> The fun comes in if a duplicate sub-item has a sub-item shared with another
> sub-item, which may make referencing the duplicate sub-item less optimal
> than just copying the sub-item.  I’m not sure my algorithm is very sane, but I
> like the output, and for the details that’s what we have BYGS (*) for.

[JLS] Well - you might have BYGS but I don't have such a thing.  I suppose that some of it is also going to drop down to local knowledge of the space.  "We know these things tend to occur a lot - use them."

> 
> > 8.  Should we provide an option to use an application defined
> > dictionary as that would pack even more at the penalty that the
> > document could not be unpacked without that dictionary.
> 
> Yes.  The question is how that is obtained (from context?), and how the
> dictionary items are merged with those shared items listed in the item (the
> dictionary may or may not have the most frequently used shared items in the
> specific data item to be packed).  I wouldn’t want to COSE-sign a packed CBOR
> data item where it is hackable from where the dictionary came...

That raises an interesting question.  Should one only sign the unpacked rather than packed version?  At this point in time we do not have a lossy compression so that is probably not a required thing.  I had briefly be thinking about detached signatures where one might merge compressions.

Jim

---

From: Carsten Bormann <[email-masked]>
Date: Sun, 26 Jul 2020 03:00:42 +0200

> [JLS] I tend to read documents from the front to the back.  😊

OK, moved it to Section 2.

> Yes, but are you willing to settle for ~30% rather than ~33% when looking at sharing.

These are approximate numbers, so I’m not sure what you are aiming at here.

> [JLS] And I think that good-enough could be less aggressive about this.

The main reason to be a bit aggressive is that we should be avoiding artificial limitations.  On the other end of the spectrum, going for a 1+0 tag and a good number of 1+0 simple values is really worth it.

> [JLS] Yes this is what I expected after coming across the recursion problem. But this is now also becoming more complicated than just looking for common strings when building the compression tables.

You get some good compression from just doing sharing of strings.  It gets better by sharing some structures and some prefixes.

(I haven’t made a proposal how to share a “prefix” (subset) of a map.  That should help some more.)

>> Like 2⁶⁴ :-)  But the RFC editor won’t let me do that, I’m sure...

Went for <sup> and the inevitable text fallback.

> [JLS] Well - you might have BYGS but I don't have such a thing.  I suppose that some of it is also going to drop down to local knowledge of the space.  "We know these things tend to occur a lot - u…

OK, give me some time to polish my compressor so I don’t terminally turn myself into a clown in the data compression community :-)

But the basic idea is to look for sharing and prefix opportunities, and then strike those that don’t actually improve the representation size.  Sort by frequency of use, build the tables, and then build the rump from the tables.  
< 250 LOC if done at the level of aptitude I have for compression algorithms :-).

> That raises an interesting question.  Should one only sign the unpacked rather than packed version?  At this point in time we do not have a lossy compression so that is probably not a required thin…

Whatever is being signed needs to include the referenced dictionaries.
I think the building of these signing inputs needs to be part of the cbor-packed specification if we add referenced dictionaries to it.
Added a short note to the security considerations.

The small updates discussed are now in

Html: https://www.ietf.org/id/draft-bormann-cbor-packed-01.html
Diff: https://www.ietf.org/rfcdiff?url2=draft-bormann-cbor-packed-01

Grüße, Carsten