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

From: Brendan Moran <[email-masked]>
Date: Thu, 3 Sep 2020 10:22:27 +0000

> On 4 Aug 2020, at 20:28, Michael Richardson <[email-masked]> wrote:
>
>
> Brendan Moran <[email-masked]> wrote:
>>> Unless you mean that dictionaries should be sorted so that they always (can only)
>>> reference forward, and you can start at the current location in the current
>>> dictionary.
>
>> Possibly, but I’m not sure that’s universally advantageous. Remember
>> that we want high reference frequency items to be at the start. Suppose
>> that I have the prefixes [“https://“, “www.”, “files.”,
>> “domain.com”]. Clearly, I want to be able to compose these in one of
>> two ways:
>
> I agree that sorting by frequency of us has CPU advantages.
> I'm not sure that this is important enough ("premature optimization is the
> root of all evil").

Sorting by frequency of use only matters for the first handful of elements. This is not for CPU usage. It’s for size. Simple 0-15 are 1-byte references. Tag6(x) st. -24<x<24 are 2-byte references. -255 < x < 255 are 3-byte references.

I don’t care about sorting within the 1-byte references, 2-byte references, 3 byte references. If I have two values, one that appears 3 times and one that appears 300 times, I care that the 300-time reference is a 1-byte reference, not a 3-byte reference.

So sorting by frequency is important for compression.

> I think that I can put them together in any order in my CBOR, regardless of
> the order.  The ordering just restrictions how the internal reference in the
> dictionary can work, right?

Yes, I think that the draft should clearly define whether random access is permitted (loops possible) or forward references only (loops impossible).

If we care about compression, I would argue that random access is necessary, however that would cause additional complexity in loop detection.

> If you are saying that sometimes the compressor will be a constrained node,
> because CBOR is used outside of SUIT (who knew?), then I would like to
> retract my comment involving that five-letter word.

This comes back to the typical compression 3-way tradeoff: compression complexity vs. compression ratio vs. decompression complexity. Answering whether a constrained node will pack CBOR depends on the goal. Recognising the power consumption profiles of wireless sensor networks (e.g. LoRa) I think it’s reasonable to say that some lightweight compression is highly likely, since the active energy for transmit is very high compared to (almost any) microcontroller active energy. Then it becomes a memory complexity question. I think it’s unlikely that a wireless sensor node will try to compress a message that it can’t fit in memory. At least, not in LwM2M, CoAP, or MQTT, but maybe I’m missing something.

For wireless sensor nodes, I think the real question is code size for packing, not energy or memory. The really great thing about packed CBOR is that the document format is identical, regardless of how complex the encoder is. This will allow developers to tune packing algorithms for code size vs packing ratio vs memory vs. energy.

Brendan

IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

---

From: Michael Richardson <[email-masked]>
Date: Thu, 03 Sep 2020 14:44:14 -0400

> Sorting by frequency of use only matters for the first handful of
    > elements. This is not for CPU usage. It’s for size. Simple 0-15 are
    > 1-byte references. Tag6(x) st. -24<x<24 are 2-byte references. -255 < x
    > < 255 are 3-byte references.

Point. I was not thinking some of it through.
BUT, there is an assumption that the dictionary will be created and stored as
an array.  That's a pretty logical way.

But it could be stored as an flattened alist (aka: "ordered map", aka "ordered multi-map").
(It is probably stupid to have duplicate keys though)
In which case the size of the key and the order do not have to be tied up.
Content could always point "forward".

    > This comes back to the typical compression 3-way tradeoff: compression
    > complexity vs. compression ratio vs. decompression
    > complexity. Answering whether a constrained node will pack CBOR depends
    > on the goal. Recognising the power consumption profiles of wireless
    > sensor networks (e.g. LoRa) I think it’s reasonable to say that some

I think that LoRa is so incredibly constrained that it will have
pre-distributed dictionaries in which substrings are not discovered, but
which the code knows which key to use, by construction.
However, I recently learnt that there is some kind of point to point LoRA
which an support a mesh topology. Supposedly.  I am skeptical (unicast me)

    > For wireless sensor nodes, I think the real question is code size for
    > packing, not energy or memory. The really great thing about packed CBOR
    > is that the document format is identical, regardless of how complex the
    > encoder is. This will allow developers to tune packing algorithms for
    > code size vs packing ratio vs memory vs. energy.

Yes, I agree.  So in many cases some very stupid packers that get 90% of the
job done for the cases involved will be appropriate.  Someone will change
something and it will suddenly fail to work (using a lot more energy), but it
will be a local fault, which can be remedied with a local patch.

--
Michael Richardson <[email-masked]>, Sandelman Software Works
-= IPv6 IoT consulting =-