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

[Emile Cormier <[e-mail]>]

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 <[e-mail]> 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.
> >
> > 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.
>
> > 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]]]]
>
> 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]
> >
> > and a decoder interprets this as:
> > Key,     Value
> > "aaa",    1
> > "aaa",    2
> > [“bbb”, [[3]]],    "ccc"
> > 4,    <missing value>
>
> 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
>
>