Subject: [Cbor] Maps: Need for additional compactness?

From: Christian Amsüss <[email-masked]>
Date: Wed, 9 Jun 2021 18:02:45 +0200

Hello Emile, hello Kio,
and hello CBOR group in general,

during the last CBOR interim meeting[1], the question as to how far we'd
like to go in map-like data structure optimization came up. These do not
relate to the information model (these variations are covered in tags),
but only to how data is put on the wire, so it'd be about variations of
not placing items into inner lists when avoidable, delta encoding for
ordered lists or other compression steps.

An idea floated during the meeting was go with the obvious encoding now,
and only go there later if use cases really need those.

What are your needs with respect to compactness? Does it suffice to
address the high-level (homogenity) aspects of map data structures?

BR
Christian

[1]
  minutes: https://datatracker.ietf.org/meeting/interim-2021-cbor-10/materials/minutes-interim-2021-cbor-10-202106021600-00
  relevant slides: https://datatracker.ietf.org/meeting/interim-2021-cbor-10/materials/slides-interim-2021-cbor-10-sessa-map-like-data-draft-bormann-cbor-cddl-map-like-data-00
  video: https://www.youtube.com/watch?v=IfrxbspRcQo
  ... and also from me: sorry for the time mismatch.

-- 
There's always a bigger fish.
  -- Qui-Gon Jinn

---

From: Emile Cormier <[email-masked]>
Date: Fri, 11 Jun 2021 19:19:37 -0300

Hi Everyone,

I've watched the recording of the meeting starting from the Map-like
slides. Here are my comments...

The MList encoding becomes a pessimization if there are few duplicate keys
and a large number of key-value pairs. It might not be so bad to assume
that keys tend to be generally short - they are often things like database
IDs.

The OMList encoding not allowing array values seems like a showstopper to
me.

For OEMList, I'm not clear on this part:

So [[“aaa”, 1], [“aaa”, 2], [“bbb”, 3], [“ccc”, [4]]] becomes [“aaa”, [1,
> 2], “bbb”, 3, [“ccc”, [[4]]]]
>

Is the resulting singleton array [“ccc”, [[4]]] used as an indicator so
that the decoder interprets [[4]] as the array [4] to be associated with
the key "ccc"? If so, how is the decoder supposed to distinguish this from
an array key in heterogeneous maps? This problem is more obvious if you
change the example to this:

[[“aaa”, 1], [“aaa”, 2], [“bbb”, [3]], [“ccc”, 4]] becomes [“aaa”, [1, 2],
[“bbb”, [[3]]], “ccc”, 4]

and a decoder interprets this as:
Key,     Value
"aaa",    1
"aaa",    2
[“bbb”, [[3]]],    "ccc"
4,    <missing value>

It seems to me the only way to avoid the possible pessimization of MList,
while also avoiding ambiguities with keys/values that can themselves be
arrays/maps, is to introduce a new CBOR special value (or "abuse" CBOR
break) to indicate the "shared key" special case. This has the disadvantage
that it can't be directly transcoded to JSON.

Another possibility would be to use a special tag so that [[“aaa”, 1],
[“aaa”, 2], [“bbb”, [3]], [“ccc”, 4]] becomes [“aaa”, <MultiValuesTag>[1,
2], [“bbb”, [3]], “ccc”, 4]. While this can be transcoded to JSON by
dropping the tag, an application consuming the resulting JSON would still
be vexed by the ambiguity of the (“aaa”, [1, 2]) pair even if it knows it's
decoding a multimap.

While the desire to avoid repeating duplicate keys is understandable, these
compression schemes lead to the following complications for a generic CBOR
encoding/decoding library:

1. For something like OEMList, when encoding a multimap, an encoder needs
to look ahead to see if there are multiple values associated with the same
key.

2. A simple SAX-like decoder can no longer emit alternating (key, value)
events without having to memorize the shared key, which can be a complex,
nested entity. This can be overcome by emitting a MultiMapValuesStart
"meta" event after emitting the shared key, and then the SAX handler knows
there will be multiple value events associated with the same key while
populating the multimap. MultiMapValuesStart then has to be treated as a
special state (along with the usual ArrayStart and MapStart) in the
decoder's state stack.

If there ends up being a viable compression scheme, the specification
should still allow an application to use the "naive" scheme with repeated
keys. If everyone agrees with this, then we should be able to proceed
without the optimized encodings and add them later, while preserving
backward compatibility with the naive scheme.

Cheers,
Emile Cormier

On Wed, Jun 9, 2021 at 1:03 PM Christian Amsüss <[email-masked]>
wrote:

>   minutes:
> https://datatracker.ietf.org/meeting/interim-2021-cbor-10/materials/minutes-interim-2021-cbor-10-202106021600-00
>   relevant slides:
> https://datatracker.ietf.org/meeting/interim-2021-cbor-10/materials/slides-interim-2021-cbor-10-sessa-map-like-data-draft-bormann-cbor-cddl-map-like-data-00
> _______________________________________________
> CBOR mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cbor
>

---

From: Carsten Bormann <[email-masked]>
Date: Sat, 12 Jun 2021 17:25:51 +0200

Hi Emile,

> The MList encoding becomes a pessimization if there are few duplicate keys and a large number of key-value pairs. It might not be so bad to assume that keys tend to be generally short - they are often things like database IDs.
> 
> The OMList encoding not allowing array values seems like a showstopper to me.

Yes, both MList and OMList are showing intermediate steps; I think only OEMList would be worth defining tags for.

> So [[“aaa”, 1], [“aaa”, 2], [“bbb”, 3], [“ccc”, [4]]] becomes [“aaa”, [1, 2], “bbb”, 3, [“ccc”, [[4]]]]

There are some spurious brackets here.  I think this should be:

[“aaa”, [1, 2], “bbb”, 3, “ccc”, [[4]]]

Basically the idea is:

Packing:
— For keys with only one value:
  — if that value is not an array, use the value
  — if that value *is* an array, enclose it into an array (what you call “singleton”).
— for keys with more than one value:
  — enclose all the values into a single array
Unpacking:
— for values that are not an array: use that as the single value for the key.
— for values that are an array: use each element of that array as values for the key.

> Is the resulting singleton array [“ccc”, [[4]]] used as an indicator so that the decoder interprets [[4]] as the array [4] to be associated with the key "ccc”?

No.  Any outer array is always removed when unpacking, regardless of how many elements are in there.

> If so, how is the decoder supposed to distinguish this from an array key in heterogeneous maps? This problem is more obvious if you change the example to this:
> 
> [[“aaa”, 1], [“aaa”, 2], [“bbb”, [3]], [“ccc”, 4]] becomes [“aaa”, [1, 2], [“bbb”, [[3]]], “ccc”, 4]
> 

Yes, doesn’t work with those superfluous brackets.  See above.

> It seems to me the only way to avoid the possible pessimization of MList, while also avoiding ambiguities with keys/values that can themselves be arrays/maps, is to introduce a new CBOR special value (or "abuse" CBOR break) to indicate the "shared key" special case. This has the disadvantage that it can't be directly transcoded to JSON.

I think OEMLists work well as described above.

> 1. For something like OEMList, when encoding a multimap, an encoder needs to look ahead to see if there are multiple values associated with the same key.

Yes.  I haven’t talked about Dittolists yet.

[[“aaa”, 1], [“aaa”, 2], [“bbb”, 3], [“ccc”, [4]]] 
becomes
[“aaa”, 1, *ditto*, 2, “bbb”, 3, “ccc”, [4]]

*ditto* might be a simple value we allocate specifically for this (one byte), e.g., simple(16).

The gain of a dittolist then is the (n-1)*(sizeof(key)-1) for a key used n times.
The gain of an OEMList is (n-1)*sizeof(key)-1, but then there is a loss of one byte for each array value that comes with a key that is used only once.
Which of these is better depends on the use case, but we are talking about adding or removing single bytes for certain cases.

Dittolists are definitely easier to stream, and I also think easier to implement (no special cases for array values).

In summary, to me it seems we might want to add OEMLists, Dittolists, both, or none of them.

Grüße, Carsten

---

From: Emile Cormier <[email-masked]>
Date: Mon, 14 Jun 2021 16:51:37 -0300

Something else that needs to be discussed/decided is whether we include
tags for list-like collections, like what I proposed in
https://github.com/ecorm/cbor-map-like/tree/with-lists

In that alternate proposal, I had included arbitrary key + uniform value
maps in order to maintain "one-hot" bit encoding for both the maps and
lists. If we don't want to include arbitrary key + uniform value maps to
save on 4 tags, the interpretation of the list tag bits will be more
complicated, but not terribly so.

On Fri, Jun 11, 2021 at 7:19 PM Emile Cormier <[email-masked]>
wrote:

> While the desire to avoid repeating duplicate keys is understandable,
> these compression schemes lead to the following complications for a generic
> CBOR encoding/decoding library:
>

---

From: Emile Cormier <[email-masked]>
Date: Tue, 15 Jun 2021 18:00:26 -0300

Hi Carsten,

Sorry for the late reply. Your message was flagged as spam for some reason
and I just found it recently.

Thanks for clarifying the OEMLists; they make sense to me now. My example
with the superfluous brackets was taken directly from your slides, so you
may want to consider fixing those slides if you plan on reusing them.

I'm not sure which would be easiest to decode between Dittolists and
OEMLists. With Dittolists, a SAX-like parser either has to "remember" the
last key (which is not trivial if the key is of arbitrary type), or it has
to look ahead after the value following the key to see if there's a Ditto
special value.

What vexes me for both the Dittolists and OEMLists is how I'm supposed to
transcode them into JSON in a multi-encoding environment, such as a WAMP
router (https://wamp-proto.org/). Consider the case where a JSON peer would
expect a multimap to be in the [[“aaa”, 1], [“aaa”, 2], [“bbb”, 3]] form
with repeated keys. My transcoder would therefore have to memorize each
inbound CBOR multimap key in case it needs to be repeated in the output
JSON array. I would have to store the keys in some sort of DOM tree-like
structure, because keys can be arrays or maps. This would ruin the
simplicity of my current CBOR-to-JSON transcoder.

On the other hand, if I assume that a JSON peer understands OEMLists, then
I can simply transcode each sub-entity of a CBOR OEMList as-is without
having to memorize anything.

I'll do some research on how multimaps are expected to be serialized in the
Javascript world. I'm guessing that there's really no consensus.

Cheers,
Emile Cormier

On Sat, Jun 12, 2021 at 12:25 PM Carsten Bormann <[email-masked]> wrote:

> Hi Emile,
>
> > The MList encoding becomes a pessimization if there are few duplicate
> keys and a large number of key-value pairs. It might not be so bad to
> assume that keys tend to be generally short - they are often things like
> database IDs.
> >
> Yes, both MList and OMList are showing intermediate steps; I think only
> OEMList would be worth defining tags for.
>
> the key "ccc”?
> > If so, how is the decoder supposed to distinguish this from an array key
> in heterogeneous maps? This problem is more obvious if you change the
> example to this:
> >
> > It seems to me the only way to avoid the possible pessimization of
> MList, while also avoiding ambiguities with keys/values that can themselves
> be arrays/maps, is to introduce a new CBOR special value (or "abuse" CBOR
> > 1. For something like OEMList, when encoding a multimap, an encoder
> needs to look ahead to see if there are multiple values associated with the
> same key.
>
> The gain of an OEMList is (n-1)*sizeof(key)-1, but then there is a loss of
> one byte for each array value that comes with a key that is used only once.
> Which of these is better depends on the use case, but we are talking about
> adding or removing single bytes for certain cases.
>
> Dittolists are definitely easier to stream, and I also think easier to
> implement (no special cases for array values).
>

---

From: Emile Cormier <[email-masked]>
Date: Tue, 15 Jun 2021 21:15:06 -0300

A quick search reveals that the MList encoding seems to be favored by
various JSON libraries when serializing multimaps. This allows the use of
JSON objects when string keys are used:

{"aaa", [1, 2], "bbb", [3]}

where 1 and 2 are distinct values under the duplicate "aaa" JSON key.

If CBOR were to adopt the same MList convention, then transcoding from CBOR
multimaps to JSON would be trivial. The overhead of one byte per multimap
key seems like an acceptable price to pay for better simplicity and
compatibility with JSON.

In the case of non-string keys I would personally prefer transcoding a CBOR
multimap to a JSON array of pairs:

[[100, [101, 102], [200, [201]]

where 101 and 102 are distinct values under the duplicate 100 key.

Before deciding anything, perhaps it would be a good idea to survey how
existing JSON libraries deal with maps that are not traditional JS objects
with unique string keys. This would minimize the "impedance mismatch"
between CBOR and JSON.

Cheers,
Emile Cormier

On Tue, Jun 15, 2021 at 6:00 PM Emile Cormier <[email-masked]>
wrote:

> router (https://wamp-proto.org/). Consider the case where a JSON peer
> would expect a multimap to be in the [[“aaa”, 1], [“aaa”, 2], [“bbb”, 3]]
> form with repeated keys. My transcoder would therefore have to memorize
> each inbound CBOR multimap key in case it needs to be repeated in the
> output JSON array. I would have to store the keys in some sort of DOM
> tree-like structure, because keys can be arrays or maps. This would ruin
> the simplicity of my current CBOR-to-JSON transcoder.
>
> I'll do some research on how multimaps are expected to be serialized in
> the Javascript world. I'm guessing that there's really no consensus.
>
> Cheers,
> Emile Cormier
>
>> > If so, how is the decoder supposed to distinguish this from an array
>> key in heterogeneous maps? This problem is more obvious if you change the
>> example to this:
>> >
>> The gain of an OEMList is (n-1)*sizeof(key)-1, but then there is a loss
>> of one byte for each array value that comes with a key that is used only
>> once.
>> Which of these is better depends on the use case, but we are talking
>> about adding or removing single bytes for certain cases.
>>