Re: QCRAM Review Request: PR #1141

Ian Swett <ianswett@google.com> Mon, 12 March 2018 16:23 UTC

Return-Path: <ianswett@google.com>
X-Original-To: quic@ietfa.amsl.com
Delivered-To: quic@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 82CCC124C27 for <quic@ietfa.amsl.com>; Mon, 12 Mar 2018 09:23:53 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.709
X-Spam-Level:
X-Spam-Status: No, score=-2.709 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_FONT_LOW_CONTRAST=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, T_RP_MATCHES_RCVD=-0.01] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=google.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 bP5Hn0jd8cSh for <quic@ietfa.amsl.com>; Mon, 12 Mar 2018 09:23:51 -0700 (PDT)
Received: from mail-it0-x22d.google.com (mail-it0-x22d.google.com [IPv6:2607:f8b0:4001:c0b::22d]) (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 3DCB91275F4 for <quic@ietf.org>; Mon, 12 Mar 2018 09:23:47 -0700 (PDT)
Received: by mail-it0-x22d.google.com with SMTP id c11so11904647ith.4 for <quic@ietf.org>; Mon, 12 Mar 2018 09:23:47 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=lJnCFT/2kjiw0b3xCQGmoGWCNct+iVtOPFQwqditEyY=; b=MgeWHKtSMDGhfh8SnqVlj1RcmRis7gOrJA6ViPJ29Hj5Fo4SSXBgSEZzNwvR3ukJG0 zMbG6nUJMnLyEhqECR6RFq6oe2VoD/HN8WsMngNTF/DyuSR080MdO2YS/nOYf/0UI6AM DSnj+HfC2fDJ4ANULg4rcUlvUekPKxw1XvwSmXy3+sXmjJ+GqF/bew4mBolT+IWulQUq b+iyi2SaCoLF75ii7Z0hYp8cYRMwb++HApD3eYnYW1brPw0rKZd+F/nq6L00Hit8nMy7 GMMp14DK5jfrygsC9okjWiOLvJfkdt4KmRDTuqI8Avf52K3a2IAYB1/ZNYKpHWpiBTIT UTyw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=lJnCFT/2kjiw0b3xCQGmoGWCNct+iVtOPFQwqditEyY=; b=uU4wipXIiVcRdiSwUqGKVciKCetWrUcxkyQyvx6kVE5oFVeFKqwq17xlzewKdPG3NK GVubIfCg+ngUlVi+4PcMeDVAv2MEO6qn6MW9JJOeM569rYsHm/BmGHYqAXpQKTZiFDbr oOKVWUtIerSx9JZAhqwX/NoqCQnoZRQP85flDZ7oPCh4hqX5ejMY4RTZ7mutIHhuoP3k bDOPeSZSi5ZAw2aAq4DIehx8uAfNqvloM7JFMlbMS3c91Pho+r4+Ja39SYfqo77J+wuS tGa3OUbsPPjXeRKcBKvCOud+6VI8omMKVUpdj1h6uKvX7jXNOyIQH1Hwny6RdRaniTYC kAiA==
X-Gm-Message-State: AElRT7Er0YzM3985XgLcQlKRH+BCA2o3ylitNE4JMMUwkrLl4lTu8lN2 bZ2fpvUgp6Oie6KkGmPoqTJXjdriF6eDBHKP/hqtFg==
X-Google-Smtp-Source: AG47ELsgiOXEIIEqKYe3A4MSpXkvn1kpLdCDBk2m3c/bK3dluVdWKk3asCRwdj/o/kXV1TmDNXlSKjkkpaCPWYYRI10=
X-Received: by 10.36.55.70 with SMTP id r67mr9657214itr.40.1520871826310; Mon, 12 Mar 2018 09:23:46 -0700 (PDT)
MIME-Version: 1.0
References: <MWHPR08MB24325CADE88C887A869F65F1DAC60@MWHPR08MB2432.namprd08.prod.outlook.com> <CABkgnnWGWA7+e1DgmWT+MBDDSScoOyOg_RghhXgCNLaAOtTtPw@mail.gmail.com> <8FDB7B3D-E206-435F-9D74-22A18DC516F8@fb.com>
In-Reply-To: <8FDB7B3D-E206-435F-9D74-22A18DC516F8@fb.com>
From: Ian Swett <ianswett@google.com>
Date: Mon, 12 Mar 2018 16:23:35 +0000
Message-ID: <CAKcm_gOTLFBO5+rZMa98eXiWB1avh=-x+p90-dMFHbmg4X+PEA@mail.gmail.com>
Subject: Re: QCRAM Review Request: PR #1141
To: Alan Frindell <afrind@fb.com>
Cc: Martin Thomson <martin.thomson@gmail.com>, Mike Bishop <mbishop@evequefou.be>, IETF QUIC WG <quic@ietf.org>
Content-Type: multipart/alternative; boundary="001a1140b778f549e905673990f3"
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/Ijywq0HgpVahzwz8-kwCbJqL2TE>
X-BeenThere: quic@ietf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Main mailing list of the IETF QUIC working group <quic.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/quic>, <mailto:quic-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/quic/>
List-Post: <mailto:quic@ietf.org>
List-Help: <mailto:quic-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/quic>, <mailto:quic-request@ietf.org?subject=subscribe>
X-List-Received-Date: Mon, 12 Mar 2018 16:23:53 -0000

The table above is great, but is it also possible to estimate 'small
efficiency gains' in terms of %?

On Mon, Mar 12, 2018 at 11:58 AM Alan Frindell <afrind@fb.com>; wrote:

> I mentioned this on issue #1123, but will repeat it on the list.  I think
> redoing the instructions and string literal representation will limit code
> re-use between HPACK and QPACK (formerly called QCRAM).  Initial simulation
> of QPACK shows that it is pretty close to HPACK compression as is.  I’m
> more swayed by eliminating the possibility of sending an instruction in an
> invalid context (eg: a literal on the control stream), but on balance I
> prefer to keep the same instructions as HPACK.
>
>
>
> It would be great to hear from other implementers (eg folks not on the
> compression design committee) how they value code-reuse versus small
> efficiency gains and fewer error checks.
>
>
>
> -Alan
>
>
>
> *From: *QUIC <quic-bounces@ietf.org>; on behalf of Martin Thomson <
> martin.thomson@gmail.com>;
> *Date: *Thursday, March 1, 2018 at 8:15 PM
> *To: *Mike Bishop <mbishop@evequefou.be>;
> *Cc: *QUIC WG <quic@ietf.org>;
> *Subject: *Re: QCRAM Review Request: PR #1141
>
>
>
> I was a little surprised to see the savings here, modest though they are.
> Overall, this is overwhelmingly in the right direction.
>
>
>
> We might quibble on some of the details, but I would prefer to see this
> larger change made and then iterate where the details are less good (for
> instance, we might revisit the notion of octet alignment in other ways, or
> go back to strings starting on octet boundaries).
>
>
>
> On Thu, Mar 1, 2018 at 11:39 AM, Mike Bishop <mbishop@evequefou.be>; wrote:
>
> https://github.com/quicwg/base-drafts/pull/1141
>
>
>
> One suggestion from Martin’s implementation feedback that has been
> mentioned before is reworking the QCRAM instruction space.  The QCRAM draft
> uses the HPACK instructions, except that it cannibalizes table size changes
> for the Duplicate instruction.  That leads to some inefficiency with the
> separate streams, since you have to validate that instructions aren’t used
> on the wrong stream and some of the opcode space is wasted on each stream.
>
>
>
> This PR observes that each stream has a fully disjoint set of commands
> from the other:
>
>    - Table updates
>
>
>    - Insert with Name Reference from Static Table
>       - Insert with Name Reference from Dynamic Table
>       - Insert without Name Reference
>       - Duplicate
>       - Change table size
>
>
>    - Header blocks
>
>
>    - Indexed entry from Static
>       - Indexed entry from Dynamic
>       - Literal with Name Reference from Static Table
>       - Literal with Name Reference from Static Table, Never Indexed
>       - Literal with Name Reference from Dynamic Table
>       - Literal with Name Reference from Dynamic Table, Never Indexed
>       - Literal without Name Reference
>       - Literal without Name Reference, Never Indexed
>
>
>
> The PR takes advantage of the disjoint space to rework the opcodes in
> hopes of saving bytes on common instructions.  It does this in two ways:
>
>    - Uses a bit in the opcode to differentiate static versus dynamic
>    tables, instead of concatenating them
>
>
>    - Gives us the future option to make the static table longer without
>       hurting the dynamic table performance
>
>
>    - Uses a bit in the opcode to identify string literals, instead of
>    using a sentinel value of zero
>
>
>    - Requires modifying the HPACK string definition to not require byte
>       alignment at the beginning
>       - Gives us the future option to make the tables zero-based instead
>       of one-based
>       - Makes indexing easier to explain in a future PR
>
>
>
> Here’s the impact:
>
>
>
> *Operation*
>
> *HPACK*
>
> *QCRAM*
>
> *PR#1141*
>
> *Impact*
>
> *Table updates*
>
>
>
>
>
>
>
>
>
> *Insert with Name Reference from Static Table*
>
> “01” + index < 62
>
> “01” + index < 62
>
> “11” + index
>
> Same
>
> *Insert with Name Reference from Dynamic Table*
>
> “01” + index >= 62
>
> (one byte for first 2 entries, then 2 bytes)
>
> “01” + index >= 62
>
> (one byte for first 2 entries, then 2 bytes)
>
> “10” + index
>
> (one byte for first 64 entries)
>
> One byte saved for 62 of 64 most recent entries
>
> *Insert without Name Reference*
>
> “01000000”
>
> “01000000”
>
> “01”
>
>
>
> One byte saved for header names < 32 octets
>
> *Duplicate*
>
> Not supported
>
> “001” + index >= 62
>
> “000” + index
>
> Moot; you’re unlikely to duplicate recent entries
>
> *Change table size*
>
> “001”
>
> Not supported
>
> “001”
>
> Same
>
> *Header blocks*
>
>
>
>
>
>
>
>
>
> *Indexed entry from Static*
>
> “1” + index < 62
>
> “1” + index < 62
>
> “11” + index
>
> Same
>
> *Indexed entry from Dynamic*
>
> “1” + index >= 62
>
> “1” + index >= 62
>
> “10” + index
>
> One byte longer for indices 62-63
>
> *Literal with Name Reference from Static Table*
>
> “0000” + index < 62
>
> (two bytes for index > 15)
>
> “0000” + index < 62
>
> (two bytes for index > 15)
>
> “0001” + index
>
> Same
>
> *Literal with Name Reference from Static Table, Never Indexed*
>
> “0001” + index < 62
>
> (two bytes for index > 15)
>
> “0001” + index < 62
>
> (two bytes for index > 15)
>
> “0011” + index
>
> Same
>
> *Literal with Name Reference from Dynamic Table*
>
> “0000” + index >= 62
>
> (always 2+ bytes)
>
> “0000” + index >= 62
>
> (always 2+ bytes)
>
> “0000” + index
>
> One byte saved for first 15 entries
>
> *Literal with Name Reference from Dynamic Table, Never Indexed*
>
> “0001” + index > 62
>
> (always 2+ bytes)
>
> “0001” + index > 62
>
> (always 2+ bytes)
>
> “0010” + index
>
> One byte saved for first 15 entries
>
> *Literal without Name Reference*
>
> “00000000”
>
> “00000000”
>
> “010”
>
> One byte saved for header names < 16 octets
>
> *Literal without Name Reference, Never Indexed*
>
> “00010000”
>
> “00010000”
>
> “011”
>
> One byte saved for header names < 16 octets
>
>
>
> There’s been some churn on the PR today as Martin and I worked some of
> this out, so please give it a read (or another read) now and provide
> feedback.
>
>
>
> Thanks!
>
>
>