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

[Carsten Bormann <[e-mail]>]

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