Re: [Cbor] Record proposal

Kris Zyp <kriszyp@gmail.com> Tue, 21 September 2021 04:29 UTC

Return-Path: <kriszyp@gmail.com>
X-Original-To: cbor@ietfa.amsl.com
Delivered-To: cbor@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id B2F0F3A205C for <cbor@ietfa.amsl.com>; Mon, 20 Sep 2021 21:29:41 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level:
X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 22hcfOvowR-Z for <cbor@ietfa.amsl.com>; Mon, 20 Sep 2021 21:29:36 -0700 (PDT)
Received: from mail-ed1-x532.google.com (mail-ed1-x532.google.com [IPv6:2a00:1450:4864:20::532]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 992FC3A205E for <cbor@ietf.org>; Mon, 20 Sep 2021 21:29:36 -0700 (PDT)
Received: by mail-ed1-x532.google.com with SMTP id j13so69247633edv.13 for <cbor@ietf.org>; Mon, 20 Sep 2021 21:29:36 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=7VgrrmRAEJWGWJ8pkfoW9qduj4301w9YALycanfmvg8=; b=b9QfE2ledzCbVIE8+bA9IFey6bCF+IGbuQs82Gw4HGnS+8lGBcTWwHDEURDS9M8mdp t+565sNfkaQ7cQ/G/vBomcVSSQq3pBUl0rT7Myn5U9DjOHCxlb/bfMZZZgrNYhNib+h9 Cu9M4LUH1MKhbjd3YFpqm2+e8kJtUQrzw7AvikmIwZD4NnbKwfIvvieAmEOmS4pheNpo GoCtV3SxG0RmKjtNPTWdX7Ehc7SctekCyF4ueGwyV1a8q5kiYAIokZw7XSeVUOxvIvpP EGMqijLSiuo3Ey4ePuY2mZFtL0l91xstQXBfbh1SUnyPrSxPzR+4kIV/+gGNLdjeucc8 TWiw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=7VgrrmRAEJWGWJ8pkfoW9qduj4301w9YALycanfmvg8=; b=4YrIWLST1tV3mqSppJfOA8R50zxkmpsM+F1z+3+/OVgXd0NAQ5f356vKFVwLGuipaM JsXm968ddlSmWJWck55EAighVe/ZGwC+88CkFXOAfVP0D58ki4Uv1r0aq/06AzO+lu4s 09EwLFdsNT0z7TynJ5pPcJNuNc5C0gjIyKW33HyH7T46h2hfHynLj5kwBNvLM5krdlU+ dgjba3rIenLMxYXSsC/ODFo1991DK7fsYW3Y/JHZVQDs1NhyPetq8QnsqQIikdadEbBT VrFdyINTgkg2F9VBGIDNKraFj1k1i0zJ7bOWJ5m9oW/fozZhcOTuB3YHh6CeLdjdZ+Zb EROg==
X-Gm-Message-State: AOAM532IFaBUSZvgM5J20RlsCii5HClHB1q9+P8E3xa+cV/StJmFciEV wcARFbKABUhLLgxUV2PrhZaJlicu7wPXz0Y16YAMbNPQ
X-Google-Smtp-Source: ABdhPJy5/ePChhRNTThg2ajjyEYROJo0Q8O6lKGNptcFF5vpCwAA+0GeV1a++GPq7r8GI0dicxhqu6w6/Jo/ky9R4pA=
X-Received: by 2002:aa7:d850:: with SMTP id f16mr32977818eds.176.1632198574744; Mon, 20 Sep 2021 21:29:34 -0700 (PDT)
MIME-Version: 1.0
References: <8421F43D-E9ED-444F-A915-415F3AE59FA0@tzi.org> <YJJ+oJZ5YF/c14sv@hephaistos.amsuess.com> <41C02CBE-E7EC-4E61-889B-779EE561C632@tzi.org> <31190CB3-2EE9-4B92-BBC6-C29F71A11162@hxcore.ol> <CAEs2a6stR_0=eGP0Vx6z_9x7mf1pWJpRE8toTaSSmdWOQ+zsFA@mail.gmail.com> <C8000846-EEB7-4E2A-B909-298E479CFD62@tzi.org>
In-Reply-To: <C8000846-EEB7-4E2A-B909-298E479CFD62@tzi.org>
From: Kris Zyp <kriszyp@gmail.com>
Date: Mon, 20 Sep 2021 22:29:24 -0600
Message-ID: <CAEs2a6vNhrHhaiPUNtbJ68WYfbrprETPr+kmWNJgNXMSawyBig@mail.gmail.com>
To: Carsten Bormann <cabo@tzi.org>
Cc: Christian Amsüss <christian@amsuess.com>, "cbor@ietf.org" <cbor@ietf.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/cbor/xSIZrEUgRFjOjEf8noHSIaKl-LA>
Subject: Re: [Cbor] Record proposal
X-BeenThere: cbor@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "Concise Binary Object Representation \(CBOR\)" <cbor.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/cbor>, <mailto:cbor-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cbor/>
List-Post: <mailto:cbor@ietf.org>
List-Help: <mailto:cbor-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/cbor>, <mailto:cbor-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 21 Sep 2021 04:29:42 -0000

Did you ever get a chance to discuss this? Is there a next step for
this registry entry submission? By the way, I have been working on
implementing cbor-packed as well, which seems to complement the record
tag nicely.
Thanks,
Kris

On Thu, Jul 29, 2021 at 9:04 AM Carsten Bormann <cabo@tzi.org> wrote:
>
> Hi Kris,
>
> timely question — the CBOR meeting at IETF111 is tomorrow.
>
> My plan was to look at a corpus of SenML (RFC 8428) data to see whether your proposal would turn out to be useful there.  SenML is a spec that allows building “packs” of records, which in principle can be all different, but in reality fall into a small number of structural categories (e.g., you might have water flow, water temperature, and water pressure coming in from separate sensors, so you cannot readily combine them, but each sensor stream has records that always look the same).
>
> Of course, time ran out before this meeting, so I didn’t manage to do that yet.
>
> The SenML example is different from the CSV (RFC 4180/7111) example that comes to mind immediately in that the records go into different groups, while in a CSV Table all entries have the same structure (usually indicated in the first line in CSV’s text representation).
>
> I would be most happy if we could come up with something that fits SenML and CSV applications, but doesn’t create some of the processing model problems that might come up.  Having to run linear processing means that one cannot extract subsequences from an array, which is a bit like the effect SenML base fields have — most SenML packs have base fields only in the first record.  A hierarchical model (tag applies to its content) would mean at least subtrees are extractable, but there is going to be some redundancy between multiple record arrays — redundancy that cbor-packed could pack away.
>
> I’m not sure we will have much time for discussion tomorrow (1 hour meeting and 10 documents to look at :-), but we should continue on the list and create a proposal for one of the next CBOR interims (I’m actually going to be on vacation on 2021-08-11, but the one on 2021-08-25 would suit me).
>
> Grüße, Carsten
>
>
> > On 2021-07-29, at 02:39, Kris Zyp <kriszyp@gmail.com> wrote:
> >
> > I just wanted to check on the status of this, and if this registry
> > entry is still being considered?
> > Thank you,
> > Kris
> >
> > On Wed, May 5, 2021 at 9:11 AM <kriszyp@gmail.com> wrote:
> >>
> >> To try to clarify a little bit about my proposal, my intent with the record proposal was not primarily about minimizing the size of the encodings. I think that is a nice auxiliary benefit, but is not the primary purpose of the proposed tag. The primary purpose is to assign semantics indicating that a sequence of values should be understood as a structured record. I think this is complementary to tag 259, which indicates the opposite, a set of name-values to be interpreted a map structure. And I think this type of semantic application to a primitive data structure is the intent of tags, if I understand correctly.
> >>
> >> And the benefit of being able to use this type of tag/semantics is that encoders can more explicitly align encodings with language structures and class. And this can have much more of a significant impact on performance than space. Serializers can “stream” serialization of array or other sequences, that may be of indefinite length, without a prior knowledge of homogeneity, but still be able to use reuse structural information for any objects/elements that have the same structure, in a way that is easily optimized and can scale to arrays and other structures that may not be scannable ahead of time. For example, an encoder can keep a simple cache of class types that it has serialized and recognize that it has already serialized the record structure in a previous entity, and reference that rather reserializing the structure again. And this type of class/type cache can be significantly faster than doing cache lookups for every primitive value. Likewise, on deserialization, this provides an opportunity for a decoder to use a record reference to find and allocate/initialize exactly the correct class or structure, and then decode values directly into that structure.
> >>
> >> And my intent with suggesting this as a tag proposal is that hopefully this can simply be a rather unobtrusive addition the tag registry, keeping aligned with the intent and purpose of tag semantics, without trying to alter the direction CBOR itself at all.
> >>
> >>
> >>
> >> Thanks,
> >>
> >> Kris
> >>
> >>
> >>
> >> Sent from Mail for Windows 10
> >>
> >>
> >>
> >> From: Carsten Bormann
> >> Sent: May 5, 2021 6:50 AM
> >> To: Christian Amsüss
> >> Cc: cbor@ietf.org; Kris Zyp
> >> Subject: Re: [Cbor] Record proposal
> >>
> >>
> >>
> >> On 2021-05-05, at 13:16, Christian Amsüss <christian@amsuess.com> wrote:
> >>
> >>>
> >>
> >>> (And as much as I dislike being "the person to whom everything looks
> >>
> >>> like a nail", I'll probably ask about whether this fits in the general
> >>
> >>> model of packed CBOR, with the first entity setting up a single table
> >>
> >>> entry, and then the entries expanding a [] to a {}).
> >>
> >>
> >>
> >> There are two potential aspects to the proposed tag:
> >>
> >>
> >>
> >> * a more compact representation (which is all that cbor-packed is about)
> >>
> >>
> >>
> >> * semantic indication that a specific kind of record is being used
> >>
> >>
> >>
> >> Proposed Tag 105 currently does not have a place for further semantic indications, but one could be added.
> >>
> >>
> >>
> >> By the way, cbor-packed turns the example I gave in the referenced email into
> >>
> >>
> >>
> >> 51([["value", "name"], [], [],
> >>
> >>   [{simple(1): "one", simple(0): 1},
> >>
> >>    {simple(1): "two", simple(0): 2}, {simple(1): "three", simple(0): 3}]])
> >>
> >>
> >>
> >> Encoding-wise, the last array looks like this:
> >>
> >>
> >>
> >>      83                  # array(3)
> >>
> >>         a2               # map(2)
> >>
> >>            e1            # primitive(1)
> >>
> >>            63            # text(3)
> >>
> >>               6f6e65     # "one"
> >>
> >>            e0            # primitive(0)
> >>
> >>            01            # unsigned(1)
> >>
> >>         a2               # map(2)
> >>
> >>            e1            # primitive(1)
> >>
> >>            63            # text(3)
> >>
> >>               74776f     # "two"
> >>
> >>            e0            # primitive(0)
> >>
> >>            02            # unsigned(2)
> >>
> >>         a2               # map(2)
> >>
> >>            e1            # primitive(1)
> >>
> >>            65            # text(5)
> >>
> >>               7468726565 # "three"
> >>
> >>            e0            # primitive(0)
> >>
> >>            03            # unsigned(3)
> >>
> >>
> >>
> >> So the overhead here is one map head and two simple values per row.
> >>
> >> (Of course, that assumes that one-byte simple values are still available in the greater context this is in.)
> >>
> >>
> >>
> >> Even with a form of circumfix compression (e.g., mapping tables with parameters [1]), this is hard to beat encoding wise.
> >>
> >> The record proposal as is takes four bytes per row (1+2 tag, 1 array).
> >>
> >> This can be optimized significantly further only by amortizing the tag over more than one row, as my “CSV style” does, but that requires homogeneity.
> >>
> >>
> >>
> >> Grüße, Carsten
> >>
> >>
> >>
> >> [1]: https://datatracker.ietf.org/doc/draft-bormann-lpwan-cbor-template/
> >>
> >>
> >>
> >>
> >
> > _______________________________________________
> > CBOR mailing list
> > CBOR@ietf.org
> > https://www.ietf.org/mailman/listinfo/cbor
>