Re: QCRAM Review Request: PR #1141

Martin Thomson <martin.thomson@gmail.com> Fri, 02 March 2018 04:15 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 1086A120724 for <quic@ietfa.amsl.com>; Thu, 1 Mar 2018 20:15:05 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Level:
X-Spam-Status: No, score=-1.998 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_NONE=-0.0001, SPF_PASS=-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 1R6h2ab8KE40 for <quic@ietfa.amsl.com>; Thu, 1 Mar 2018 20:15:02 -0800 (PST)
Received: from mail-io0-x22f.google.com (mail-io0-x22f.google.com [IPv6:2607:f8b0:4001:c06::22f]) (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 971341241F5 for <quic@ietf.org>; Thu, 1 Mar 2018 20:15:02 -0800 (PST)
Received: by mail-io0-x22f.google.com with SMTP id 30so9547117iog.2 for <quic@ietf.org>; Thu, 01 Mar 2018 20:15:02 -0800 (PST)
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=id6MfgXgYh+6omF4M3Ygd465ssO1bCRev8ydowfvC6o=; b=GZJRtnzQMXeapVEGJI7iT2M71KI2gQv6zeYM2y3c5TqoOvCXWcQ5RIMJK7diu3S748 1iRnZD1408wRB4DeHVL9HzjZtF93NxWC3/F4cbYqGlhksAkNQ3ynPtQ/RI6JB94QGD1J abxB/PDi6NLsTVdB34srMc/J0OzWJXjq++uTCCU3J7wEKMgN4GGu+Q4VoAldR+9FwD5k BZcp5sP0Ato4TgWkA/tmrnAbDTluWOAkIeZ6tDeTs0dmMzkirsidw5hVz8DRvPuxAvsF eQIpHnWS3GP6RQZbnh2BjFlwAmAtYvcU8vjDqloUApXu/z3nBZXqoGD0mrMArC/boJ3/ MLKg==
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=id6MfgXgYh+6omF4M3Ygd465ssO1bCRev8ydowfvC6o=; b=kltKxy6DZBL/cqPHzQQkXpmdid8PK2q1zAQE4Dvgq1y5DwUUzONrQ2nWueYOkUTMRs fKB60gbJ6Ec9HI9PY1bsrxyMD6pZZiOxjpxDR2DL9ersASFdB9Ap+opIjtuNs3bOSohu JjZVokfX/dOx/1haubnmufqJ6zBcsc/+uyJZx8bYzKInlRk+p0IsCeDQo3dxEz6WOga1 Mbda7QiyIOiLzJ28+ncC7Y2Zgyz/xbdphbWJW4YDWf1YWJvAjOpZAfzfS1Gbx+AA4rAp lD+Ydox6iGMoQR6pGnoxf70Xf0Fo5Nn8pvZWE96SZt++/M4F8rQaD4GXGf+kOrk/aRsC MoIw==
X-Gm-Message-State: APf1xPCSxL6HgTIZB1nzmbkl+QmHxrAFE3q1LyxcyIS2F0Aq1O//AM+I RliLHZCIVIBVLFJCrkq+J+JkMFU46fVZX4Bpp3grTQ==
X-Google-Smtp-Source: AG47ELudwbwI9fKOD6cMPMjZ5K7MhOtle0h/sYc/qPwVW0P4AN6baeutNbJsmVpCJeSCTuI0I5iZW3dqS/e4L01A0jE=
X-Received: by 10.107.147.2 with SMTP id v2mr4974470iod.198.1519964101820; Thu, 01 Mar 2018 20:15:01 -0800 (PST)
MIME-Version: 1.0
Received: by 10.79.104.199 with HTTP; Thu, 1 Mar 2018 20:15:01 -0800 (PST)
In-Reply-To: <MWHPR08MB24325CADE88C887A869F65F1DAC60@MWHPR08MB2432.namprd08.prod.outlook.com>
References: <MWHPR08MB24325CADE88C887A869F65F1DAC60@MWHPR08MB2432.namprd08.prod.outlook.com>
From: Martin Thomson <martin.thomson@gmail.com>
Date: Fri, 2 Mar 2018 15:15:01 +1100
Message-ID: <CABkgnnWGWA7+e1DgmWT+MBDDSScoOyOg_RghhXgCNLaAOtTtPw@mail.gmail.com>
Subject: Re: QCRAM Review Request: PR #1141
To: Mike Bishop <mbishop@evequefou.be>
Cc: QUIC WG <quic@ietf.org>
Content-Type: multipart/alternative; boundary="001a1148d9345c470505666638d1"
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/iI6edOPzhkkjVcgCxKr9Ok83_9Q>
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: Fri, 02 Mar 2018 04:15:05 -0000

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!
>