Re: [Cbor] Reminder and call for agenda: CBOR WG Virtual Meeting on 2023-05-31

[Anders Rundgren <[e-mail]>]

On 2023-05-27 6:09, Emile Cormier wrote:
> On Sat, May 27, 2023 at 12:47 AM Anders Rundgren <[e-mail] <mailto:[e-mail]>> wrote:
> 
>     My hands-on experience with deterministic encoding (using Java, C++, and JavaScript), indicates that it comes practically free of cost.   It only gets slightly more complex if provided as an option.
> 
> 
> I fail to see how deterministic encoding is free of cost when it comes to maps. For example, an ordered Map<int, T> in a programming language will be sorted numerically from most negative to most positive, whereas the order is different when sorted lexicographically by encoded bytes. So the encoded, unsorted map (or at least the encoded keys with back pointers) must be temporarily stored somewhere so that it can be sorted before being sent over the wire. This is not free! :-)

Right you are! This is indeed correct for encoders.  However, Ffor decoders deterministic encoding only requires saving the last key since keys [MUST] come in ascending order.

FWIW, I don't use Map objects in my high-level encoder implementations, only single linked lists + compare.  This is the only code that is slightly messy.

For very low-level encoders you may delegate the map sorting to the programmer 😱
https://github.com/cyberphone/D-CBOR/blob/main/d-cbor-4-constrained-devices.md
Ugly? Yes! Working? Presumably 😎

In case you want to test the proposed CBOR encoding scheme in practice, here is an on-line reference implementation:
https://test.webpki.org/csf-lab/convert

Anders