Re: QCRAM Review Request: PR #1141

Alan Frindell <afrind@fb.com> Mon, 12 March 2018 15:57 UTC

Return-Path: <prvs=66098f063c=afrind@fb.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 0CFC4126DEE for <quic@ietfa.amsl.com>; Mon, 12 Mar 2018 08:57:55 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.719
X-Spam-Level:
X-Spam-Status: No, score=-2.719 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, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=fb.com header.b=QFYNrkSA; dkim=pass (1024-bit key) header.d=fb.onmicrosoft.com header.b=kDxGYdJI
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 tKHPgyAFgopl for <quic@ietfa.amsl.com>; Mon, 12 Mar 2018 08:57:53 -0700 (PDT)
Received: from mx0a-00082601.pphosted.com (mx0b-00082601.pphosted.com [67.231.153.30]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C90DD1275F4 for <quic@ietf.org>; Mon, 12 Mar 2018 08:57:52 -0700 (PDT)
Received: from pps.filterd (m0089730.ppops.net [127.0.0.1]) by m0089730.ppops.net (8.16.0.22/8.16.0.22) with SMTP id w2CFsbrp028067; Mon, 12 Mar 2018 08:57:49 -0700
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.com; h=from : to : cc : subject : date : message-id : references : in-reply-to : content-type : mime-version; s=facebook; bh=mfOC3pN5q8+NBcKkC1UMJTV4/XiZv8RlCRR5f1HEx30=; b=QFYNrkSA9+tkcb+5GfSoGGlXm5svlf/iFEweH3IEd6zFceHNybKQ4jlWq2nNFegUjAK7 FyJLQkUC656Ygh+2pFo9zsg0bbgchAQis9AwIss9s679m5m/n/HTYAqJdnzceaXEJpl7 k1rciBQ/oW88ipoNHgq0evXjkBbUwZicUFg=
Received: from mail.thefacebook.com ([199.201.64.23]) by m0089730.ppops.net with ESMTP id 2gnt9p8drq-2 (version=TLSv1 cipher=ECDHE-RSA-AES256-SHA bits=256 verify=NOT); Mon, 12 Mar 2018 08:57:48 -0700
Received: from NAM03-DM3-obe.outbound.protection.outlook.com (192.168.54.28) by o365-in.thefacebook.com (192.168.16.20) with Microsoft SMTP Server (TLS) id 14.3.361.1; Mon, 12 Mar 2018 08:57:47 -0700
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.onmicrosoft.com; s=selector1-fb-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version; bh=mfOC3pN5q8+NBcKkC1UMJTV4/XiZv8RlCRR5f1HEx30=; b=kDxGYdJIJQzmBjPRTM24hK1Okmms6sfKnLPDU/38rqscfSLUh+HFAo2tUqA14UTnrkZ5EdlyAzvhT/7RIbNHRKrWCfKpNyv22/P9QOxllb+OSDdH0I8uE384YmikB2QnxV4QxDRt/WhFT/sg2QVRtIpEmzQIuD/j2FyVRWNaPZc=
Received: from CY4PR15MB1927.namprd15.prod.outlook.com (10.174.54.148) by CY4PR15MB1895.namprd15.prod.outlook.com (10.174.54.140) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P256) id 15.20.548.13; Mon, 12 Mar 2018 15:57:45 +0000
Received: from CY4PR15MB1927.namprd15.prod.outlook.com ([fe80::112f:9340:b2f5:a72c]) by CY4PR15MB1927.namprd15.prod.outlook.com ([fe80::112f:9340:b2f5:a72c%18]) with mapi id 15.20.0548.021; Mon, 12 Mar 2018 15:57:44 +0000
From: Alan Frindell <afrind@fb.com>
To: Martin Thomson <martin.thomson@gmail.com>, Mike Bishop <mbishop@evequefou.be>
CC: QUIC WG <quic@ietf.org>
Subject: Re: QCRAM Review Request: PR #1141
Thread-Topic: QCRAM Review Request: PR #1141
Thread-Index: AQHTsd0Sg+PHAnqcr0mLR2aL48e8Y6PMXKQA
Date: Mon, 12 Mar 2018 15:57:44 +0000
Message-ID: <8FDB7B3D-E206-435F-9D74-22A18DC516F8@fb.com>
References: <MWHPR08MB24325CADE88C887A869F65F1DAC60@MWHPR08MB2432.namprd08.prod.outlook.com> <CABkgnnWGWA7+e1DgmWT+MBDDSScoOyOg_RghhXgCNLaAOtTtPw@mail.gmail.com>
In-Reply-To: <CABkgnnWGWA7+e1DgmWT+MBDDSScoOyOg_RghhXgCNLaAOtTtPw@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/10.9.0.180116
x-originating-ip: [2620:10d:c090:200::4:6b84]
x-ms-publictraffictype: Email
x-microsoft-exchange-diagnostics: 1; CY4PR15MB1895; 7:ksYl6c4nYIr6Fp+KjDNbWt9r12nPTxBzUGxYwzqF4fdb2y+bhn6JF1/JhWdoAjT3GvYzl5s2ooe59zt2uW6GSqJDyZjzr9p2nfTqw2FaGrHIuOsQmkGtM+PaySc1lY2XbFWdXWBLJJlQ5uCaEGa5h6U4R+Sr+1IoBZm/vhV2GkpseG4bcrO1IUEWpnzcO9nUddMb9Kgu1EV1ZfxFm+UeqyWX8y1kVtdm4RZHgov+HI/syrmWo+QbkEwAMBE2RFzG; 20:xH6pBKfECXNweSOdq5wOm5PBFNOyYPhVMHyB5MxneXX/dILkGDQHyB59x8Krep9qA9818epnsjPz1ArH2owg8ouMWwdFJjcayE/kmNg+XTksuNp5vZpzd8SqPYJChcXqBoLHhsUeaKd1TwsdQPNV554EMi5ts0S2GXWhuWeRCpE=
x-ms-exchange-antispam-srfa-diagnostics: SSOS;
x-ms-office365-filtering-correlation-id: 56ec19e4-4e4b-45b0-4d05-08d58831fea4
x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(7020095)(4652020)(5600026)(4604075)(3008032)(4534165)(4627221)(201703031133081)(201702281549075)(2017052603328)(7153060)(7193020); SRVR:CY4PR15MB1895;
x-ms-traffictypediagnostic: CY4PR15MB1895:
x-microsoft-antispam-prvs: <CY4PR15MB189503E45763C81F8A5AADEAA7D30@CY4PR15MB1895.namprd15.prod.outlook.com>
x-exchange-antispam-report-test: UriScan:(28532068793085)(166708455590820)(85827821059158)(21748063052155);
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(8121501046)(5005006)(3002001)(93006095)(93001095)(10201501046)(3231220)(11241501184)(944501244)(52105095)(6041310)(20161123564045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123560045)(20161123562045)(20161123558120)(6072148)(201708071742011); SRVR:CY4PR15MB1895; BCL:0; PCL:0; RULEID:; SRVR:CY4PR15MB1895;
x-forefront-prvs: 06098A2863
x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(376002)(396003)(39380400002)(366004)(39860400002)(346002)(189003)(199004)(6116002)(966005)(4326008)(2906002)(53946003)(39060400002)(82746002)(3660700001)(6486002)(76176011)(14454004)(105586002)(83716003)(53936002)(2950100002)(6246003)(86362001)(229853002)(3280700002)(68736007)(6436002)(478600001)(54896002)(33656002)(97736004)(6306002)(6512007)(236005)(316002)(7736002)(106356001)(5660300001)(110136005)(8676002)(25786009)(99286004)(46003)(2900100001)(58126008)(59450400001)(81156014)(36756003)(102836004)(5250100002)(606006)(8936002)(6506007)(53546011)(81166006)(186003)(559001)(579004); DIR:OUT; SFP:1102; SCL:1; SRVR:CY4PR15MB1895; H:CY4PR15MB1927.namprd15.prod.outlook.com; FPR:; SPF:None; PTR:InfoNoRecords; MX:1; A:1; LANG:en;
received-spf: None (protection.outlook.com: fb.com does not designate permitted sender hosts)
x-microsoft-antispam-message-info: zCoKiuAwS/orPmGlu8MsnlKwm51ptqLi8EPRgFhG7zKG6K25nGYYoCWL0NKdcz0CJQ00K2sBa8UbwXMTTCKEXSURTEulBIBxsjCPMy6O+tqpTQa1p/aLUrmH97iBq6+sIQO5A25sBadczsw4H8Om/KaN4qfy3NdAyOsxtQYfa+lCI5C7YnmjT80C3GBttggqmZSBESoVGUlp+pXP6UO7SNnDlR+GaThZC82IG8T7VOKBCJgM+ztDZWjuv2qQkT+ATIYJcqBkFZKbT+28T9ZsPWwI6NcT5APVG3dG5q5DzpO64pSr/nsCJj+cZYmUXq3kBRoCXOrxaqGq1+azuLcUQg==
spamdiagnosticoutput: 1:99
spamdiagnosticmetadata: NSPM
Content-Type: multipart/alternative; boundary="_000_8FDB7B3DE206435F9D7422A18DC516F8fbcom_"
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-Network-Message-Id: 56ec19e4-4e4b-45b0-4d05-08d58831fea4
X-MS-Exchange-CrossTenant-originalarrivaltime: 12 Mar 2018 15:57:44.8811 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 8ae927fe-1255-47a7-a2af-5f3a069daaa2
X-MS-Exchange-Transport-CrossTenantHeadersStamped: CY4PR15MB1895
X-OriginatorOrg: fb.com
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:, , definitions=2018-03-12_09:, , signatures=0
X-Proofpoint-Spam-Reason: safe
X-FB-Internal: Safe
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/1Yo8ns999MqG96T39OJX3ZYDkjM>
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 15:57:55 -0000

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