IETF Logo Mail Archive

Re: [Cbor] Ordering of items in the prefix table

Michael Richardson <mcr+ietf@sandelman.ca> Sat, 05 September 2020 03:10 UTC

Return-Path: <mcr+ietf@sandelman.ca>
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 98CB43A112B for <cbor@ietfa.amsl.com>; Fri, 4 Sep 2020 20:10:19 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Level:
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
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 rCVt53R-_N3d for <cbor@ietfa.amsl.com>; Fri, 4 Sep 2020 20:10:18 -0700 (PDT)
Received: from tuna.sandelman.ca (tuna.sandelman.ca [IPv6:2607:f0b0:f:3:216:3eff:fe7c:d1f3]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 2E6BC3A112A for <cbor@ietf.org>; Fri, 4 Sep 2020 20:10:18 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1]) by tuna.sandelman.ca (Postfix) with ESMTP id 97887389AD for <cbor@ietf.org>; Fri, 4 Sep 2020 22:49:09 -0400 (EDT)
Received: from tuna.sandelman.ca ([127.0.0.1]) by localhost (localhost [127.0.0.1]) (amavisd-new, port 10024) with LMTP id q2gxitDelOk5 for <cbor@ietf.org>; Fri, 4 Sep 2020 22:49:09 -0400 (EDT)
Received: from sandelman.ca (obiwan.sandelman.ca [209.87.249.21]) by tuna.sandelman.ca (Postfix) with ESMTP id C2788389A6 for <cbor@ietf.org>; Fri, 4 Sep 2020 22:49:08 -0400 (EDT)
Received: from localhost (localhost [IPv6:::1]) by sandelman.ca (Postfix) with ESMTP id 5CE9063E for <cbor@ietf.org>; Fri, 4 Sep 2020 23:10:15 -0400 (EDT)
From: Michael Richardson <mcr+ietf@sandelman.ca>
To: "cbor@ietf.org" <cbor@ietf.org>
In-Reply-To: <9C89B5D9-010A-4E72-AC53-5CC1C2473B84@arm.com>
References: <008d01d67c48$d25c4440$7714ccc0$@augustcellars.com> <29638.1598639086@localhost> <B7320B50-BB7D-4E0C-BA11-E35B69F90867@tzi.org> <17395.1598652378@localhost> <841AA64E-647F-49BF-B760-A6F5041DDC14@tzi.org> <9C89B5D9-010A-4E72-AC53-5CC1C2473B84@arm.com>
X-Mailer: MH-E 8.6+git; nmh 1.7+dev; GNU Emacs 26.1
X-Face: $\n1pF)h^`}$H>Hk{L"x@)JS7<%Az}5RyS@k9X%29-lHB$Ti.V>2bi.~ehC0; <'$9xN5Ub# z!G,p`nR&p7Fz@^UXIn156S8.~^@MJ*mMsD7=QFeq%AL4m<nPbLgmtKK-5dC@#:k
MIME-Version: 1.0
Content-Type: multipart/signed; boundary="=-=-="; micalg="pgp-sha512"; protocol="application/pgp-signature"
Date: Fri, 04 Sep 2020 23:10:15 -0400
Message-ID: <31736.1599275415@localhost>
Archived-At: <https://mailarchive.ietf.org/arch/msg/cbor/66IP8InjJy0vj4uwdeU2gXC1BeY>
Subject: Re: [Cbor] Ordering of items in the prefix table
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: Sat, 05 Sep 2020 03:10:20 -0000

Brendan Moran <Brendan.Moran@arm.com> wrote:
    > I’ve been thinking about how dictionaries and nested tables interact. I
    > have been wondering about the possibility of using references that
    > overflow the nearest table to handle nesting. For the nesting-only
    > case, this is straight-forward: when the decoder encounters a
    > reference, it first checks to see if the reference fits in the nearest
    > table. If it overflows the number of elements in that table, the size
    > of the table is subtracted from the reference, then the decoder checks
    > the next-nearest table.

That's a good idea, and it allows the shorter references to be reused.
It also allows for locality, so we no longer have to worry about the global
frequency, but some local frequency of use.

--
Michael Richardson <mcr+IETF@sandelman.ca>   . o O ( IPv6 IøT consulting )
           Sandelman Software Works Inc, Ottawa and Worldwide

v2.23.0 | Report a Bug | By Email