Re: QCRAM Review Request: PR #1141
Martin Thomson <martin.thomson@gmail.com> Tue, 13 March 2018 02:40 UTC
Return-Path: <martin.thomson@gmail.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 BA89A124E15 for <quic@ietfa.amsl.com>; Mon, 12 Mar 2018 19:40:50 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.697
X-Spam-Level:
X-Spam-Status: No, score=-2.697 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_FONT_LOW_CONTRAST=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, 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 W74L_axZrFM1 for <quic@ietfa.amsl.com>; Mon, 12 Mar 2018 19:40:47 -0700 (PDT)
Received: from mail-oi0-x22a.google.com (mail-oi0-x22a.google.com [IPv6:2607:f8b0:4003:c06::22a]) (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 454D4120726 for <quic@ietf.org>; Mon, 12 Mar 2018 19:40:47 -0700 (PDT)
Received: by mail-oi0-x22a.google.com with SMTP id j79so14093545oib.12 for <quic@ietf.org>; Mon, 12 Mar 2018 19:40:47 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=12oIGmR0vbnffzcF5LsNVcalG1c2WfvO+kIUGF94ybA=; b=egOhnOTANzOAjre9qWQcQe9nSU6E0x9nSZGAf4oYw2x7AAv7e9O6QtccXeUKQNXOfP tUgmGJvm1q26KiiRwxvU+Drm0twYK1u3vQcvqZitBsUcuO+YBeA9AMQBGGX01BZOBCse Up3q4AyK2HSn6bF9sBBESizvUpBLAC5p00xBJWsOvHmNrH+yxEuRvcR0rGviSHHzNRLn L5uhRbytqCDDf01XZKH07+yLao0JZPKNG6YLB1TpnxWITJ8tdYGJg7gTxbe4P4zFWH+E SlLCucS894PsPFbe9BqKcpG4pDc7oJAqqLMs4mCpjrdRE1T2Sl3zlFN/dPD1YVTTMNMx AYZQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=12oIGmR0vbnffzcF5LsNVcalG1c2WfvO+kIUGF94ybA=; b=IEFbR+Armki3GDgPlVRmhe3bZ+IGNiQC0NV7gkvBvPhEencIky4ALhau5R7c+2tya5 Yy8NENeM1qdoTvF5p/zuE8fXCwj1tvIh3L6OBwm7YAlw2SnKcui8zxiokVuEjxCdvjtd PAwV/5dcuwZVqH8OJvz2JhwFVeLxF55uyOIK0+Gf0FBOpeFb2Q+BJPumtfCzCN59UJcP JW3QRPfUpwM9IkV6S28c3MCOg5+CENJb/9aBGQJuKHLcZzOaXV5nqeAT+F9SlNwOyxZE 0DwmXJgq3lCrilN9VL+ICBLC51hxrYEH3TuxqvSVeZk/p2J/vOT7StEqweGeyymDsJnB XMKg==
X-Gm-Message-State: AElRT7FKH2Ji2+H24FXqc7/IqTc+r9fCiO71t0b3ScCHgdmdoSyvPgrs DxPIv7LDu+wn/clRRvTa/WEFFTSNdUbQFo5pfsY=
X-Google-Smtp-Source: AG47ELvFcnuFmr1cx8bJHfOZ8xhvZ3jnK9XGvxIEp5wNq5RisfzvIu4/+lPaw5mGgVMnKV+ndL8uDouCtbzJDPs9nCg=
X-Received: by 10.202.84.132 with SMTP id i126mr5960255oib.295.1520908846513; Mon, 12 Mar 2018 19:40:46 -0700 (PDT)
MIME-Version: 1.0
Received: by 2002:a9d:1055:0:0:0:0:0 with HTTP; Mon, 12 Mar 2018 19:40:45 -0700 (PDT)
Received: by 2002:a9d:1055:0:0:0:0:0 with HTTP; Mon, 12 Mar 2018 19:40:45 -0700 (PDT)
In-Reply-To: <CAKcm_gOTLFBO5+rZMa98eXiWB1avh=-x+p90-dMFHbmg4X+PEA@mail.gmail.com>
References: <MWHPR08MB24325CADE88C887A869F65F1DAC60@MWHPR08MB2432.namprd08.prod.outlook.com> <CABkgnnWGWA7+e1DgmWT+MBDDSScoOyOg_RghhXgCNLaAOtTtPw@mail.gmail.com> <8FDB7B3D-E206-435F-9D74-22A18DC516F8@fb.com> <CAKcm_gOTLFBO5+rZMa98eXiWB1avh=-x+p90-dMFHbmg4X+PEA@mail.gmail.com>
From: Martin Thomson <martin.thomson@gmail.com>
Date: Tue, 13 Mar 2018 02:40:45 +0000
Message-ID: <CABkgnnV4Z_XkVAuiW8mfTRmVPOmEnRDOUAcB_xNTN8gsz6AJaw@mail.gmail.com>
Subject: Re: QCRAM Review Request: PR #1141
To: Ian Swett <ianswett@google.com>
Cc: Alan Frindell <afrind@fb.com>, Mike Bishop <mbishop@evequefou.be>, IETF QUIC WG <quic@ietf.org>
Content-Type: multipart/alternative; boundary="001a113d2c728845d00567422f9d"
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/XgwLulE6smiauz2fFbYydfGW5xY>
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: Tue, 13 Mar 2018 02:40:51 -0000
Efficiency gains are not especially relevant here. I think that the primary concern is which choice is best for those implementing the spec. FWIW, I disagree with Alan, I think that the impact of a change is minimal. We might discuss ways to wind back some of the changes Mike suggests, but I would be sad if we didn't at least fix the but where you have to discard invalid instructions. That is where this started. I also very much like using the bit to separate static and dynamic. That will let us fix that rotten static table. I care much less about the changes to strings though. (I expect the gains to be miniscule.) On 12 Mar. 2018 4:23 pm, "Ian Swett" <ianswett@google.com> wrote: > 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! >> >> >> >
- QCRAM Review Request: PR #1141 Mike Bishop
- Re: QCRAM Review Request: PR #1141 Martin Thomson
- Re: QCRAM Review Request: PR #1141 Alan Frindell
- Re: QCRAM Review Request: PR #1141 Ian Swett
- Re: QCRAM Review Request: PR #1141 Martin Thomson