Skip to content

Commit 2ed95c9

Browse files
amirhadadiahadadinormanmaurer
authored
Optimize HpackStaticTable by using a perfect hash function (#12713)
Motivation: HpackStaticTable performance can be improved by using a perfect hash function. Modifications: Use 2 tables, one for mapping header name -> index and one for mapping header name + value -> index. Choose the tables and the hash function in such a way that each entry maps to a single hash bucket. Results: Benchmark (optimized) Mode Cnt Score Error Units HpackStaticTableBenchmark.lookupHttp false avgt 10 15.998 ± 1.646 ns/op HpackStaticTableBenchmark.lookupHttp true avgt 10 10.457 ± 0.274 ns/op HpackStaticTableBenchmark.lookupHttps false avgt 10 20.942 ± 1.365 ns/op HpackStaticTableBenchmark.lookupHttps true avgt 10 10.618 ± 0.138 ns/op HpackStaticTableBenchmark.lookupNameOnlyMatch false avgt 10 13.710 ± 0.273 ns/op HpackStaticTableBenchmark.lookupNameOnlyMatch true avgt 10 3.156 ± 0.052 ns/op HpackStaticTableBenchmark.lookupNoNameMatch false avgt 10 3.528 ± 0.047 ns/op HpackStaticTableBenchmark.lookupNoNameMatch true avgt 10 3.145 ± 0.031 ns/op Caveats: This implementation couples HpackStaticTable implementation to the implementation of AsciiString.hashCode, relying on the values it returns for the static table headers to yield a perfect hash function. If AsciiString.hashCode implementation changes, HpackStaticTable implementation will also need to change. Moreover, if AsciiString.hashCode can return different values on different platforms (maybe due to endianness) or in general in different jvm instances, then it invalidates the approach taken here (or at least makes its implementation much more complex). Co-authored-by: ahadadi <ahadadi@outbrain.com> Co-authored-by: Norman Maurer <norman_maurer@apple.com>
1 parent b31e7f2 commit 2ed95c9

3 files changed

Lines changed: 186 additions & 60 deletions

File tree

‎codec-http2/src/main/java/io/netty/handler/codec/http2/HpackStaticTable.java‎

Lines changed: 95 additions & 60 deletions
Original file line numberDiff line numberDiff line change
@@ -31,8 +31,8 @@
3131
*/
3232
package io.netty.handler.codec.http2;
3333

34-
import io.netty.handler.codec.UnsupportedValueConverter;
3534
import io.netty.util.AsciiString;
35+
import io.netty.util.internal.PlatformDependent;
3636

3737
import java.util.Arrays;
3838
import java.util.List;
@@ -117,9 +117,53 @@ private static HpackHeaderField newHeaderField(String name, String value) {
117117
return new HpackHeaderField(AsciiString.cached(name), AsciiString.cached(value));
118118
}
119119

120-
private static final CharSequenceMap<Integer> STATIC_INDEX_BY_NAME = createMap();
120+
// The table size and bit shift are chosen so that each hash bucket contains a single header name.
121+
private static final int HEADER_NAMES_TABLE_SIZE = 1 << 9;
121122

122-
private static final int MAX_SAME_NAME_FIELD_INDEX = maxSameNameFieldIndex();
123+
private static final int HEADER_NAMES_TABLE_SHIFT = PlatformDependent.BIG_ENDIAN_NATIVE_ORDER ? 22 : 18;
124+
125+
// A table mapping header names to their associated indexes.
126+
private static final HeaderNameIndex[] HEADER_NAMES = new HeaderNameIndex[HEADER_NAMES_TABLE_SIZE];
127+
static {
128+
// Iterate through the static table in reverse order to
129+
// save the smallest index for a given name in the table.
130+
for (int index = STATIC_TABLE.size(); index > 0; index--) {
131+
HpackHeaderField entry = getEntry(index);
132+
int bucket = headerNameBucket(entry.name);
133+
HeaderNameIndex tableEntry = HEADER_NAMES[bucket];
134+
if (tableEntry != null && !equalsVariableTime(tableEntry.name, entry.name)) {
135+
// Can happen if AsciiString.hashCode changes
136+
throw new IllegalStateException("Hash bucket collision between " +
137+
tableEntry.name + " and " + entry.name);
138+
}
139+
HEADER_NAMES[bucket] = new HeaderNameIndex(entry.name, index, entry.value.length() == 0);
140+
}
141+
}
142+
143+
// The table size and bit shift are chosen so that each hash bucket contains a single header.
144+
private static final int HEADERS_WITH_NON_EMPTY_VALUES_TABLE_SIZE = 1 << 6;
145+
146+
private static final int HEADERS_WITH_NON_EMPTY_VALUES_TABLE_SHIFT =
147+
PlatformDependent.BIG_ENDIAN_NATIVE_ORDER ? 0 : 6;
148+
149+
// A table mapping headers with non-empty values to their associated indexes.
150+
private static final HeaderIndex[] HEADERS_WITH_NON_EMPTY_VALUES =
151+
new HeaderIndex[HEADERS_WITH_NON_EMPTY_VALUES_TABLE_SIZE];
152+
static {
153+
for (int index = STATIC_TABLE.size(); index > 0; index--) {
154+
HpackHeaderField entry = getEntry(index);
155+
if (entry.value.length() > 0) {
156+
int bucket = headerBucket(entry.value);
157+
HeaderIndex tableEntry = HEADERS_WITH_NON_EMPTY_VALUES[bucket];
158+
if (tableEntry != null) {
159+
// Can happen if AsciiString.hashCode changes
160+
throw new IllegalStateException("Hash bucket collision between " +
161+
tableEntry.value + " and " + entry.value);
162+
}
163+
HEADERS_WITH_NON_EMPTY_VALUES[bucket] = new HeaderIndex(entry.name, entry.value, index);
164+
}
165+
}
166+
}
123167

124168
/**
125169
* The number of header fields in the static table.
@@ -138,82 +182,73 @@ static HpackHeaderField getEntry(int index) {
138182
* -1 if the header field name is not in the static table.
139183
*/
140184
static int getIndex(CharSequence name) {
141-
Integer index = STATIC_INDEX_BY_NAME.get(name);
142-
if (index == null) {
143-
return NOT_FOUND;
144-
}
145-
return index;
185+
HeaderNameIndex entry = getEntry(name);
186+
return entry == null ? NOT_FOUND : entry.index;
146187
}
147188

148189
/**
149190
* Returns the index value for the given header field in the static table. Returns -1 if the
150191
* header field is not in the static table.
151192
*/
152193
static int getIndexInsensitive(CharSequence name, CharSequence value) {
153-
int index = getIndex(name);
154-
if (index == NOT_FOUND) {
194+
if (value.length() == 0) {
195+
HeaderNameIndex entry = getEntry(name);
196+
return entry == null || !entry.emptyValue ? NOT_FOUND : entry.index;
197+
}
198+
int bucket = headerBucket(value);
199+
HeaderIndex header = HEADERS_WITH_NON_EMPTY_VALUES[bucket];
200+
if (header == null) {
155201
return NOT_FOUND;
156202
}
157-
158-
// Compare values for the first name match
159-
HpackHeaderField entry = getEntry(index);
160-
if (equalsVariableTime(value, entry.value)) {
161-
return index;
203+
if (equalsVariableTime(header.name, name) && equalsVariableTime(header.value, value)) {
204+
return header.index;
162205
}
206+
return NOT_FOUND;
207+
}
163208

164-
// Note this assumes all entries for a given header field are sequential.
165-
index++;
166-
while (index <= MAX_SAME_NAME_FIELD_INDEX) {
167-
entry = getEntry(index);
168-
if (!equalsVariableTime(name, entry.name)) {
169-
// As far as fields with the same name are placed in the table sequentially
170-
// and INDEX_BY_NAME returns index of the fist position, - it's safe to
171-
// exit immediately.
172-
return NOT_FOUND;
173-
}
174-
if (equalsVariableTime(value, entry.value)) {
175-
return index;
176-
}
177-
index++;
209+
private static HeaderNameIndex getEntry(CharSequence name) {
210+
int bucket = headerNameBucket(name);
211+
HeaderNameIndex entry = HEADER_NAMES[bucket];
212+
if (entry == null) {
213+
return null;
178214
}
215+
return equalsVariableTime(entry.name, name) ? entry : null;
216+
}
179217

180-
return NOT_FOUND;
218+
private static int headerNameBucket(CharSequence name) {
219+
return bucket(name, HEADER_NAMES_TABLE_SHIFT, HEADER_NAMES_TABLE_SIZE - 1);
181220
}
182221

183-
// create a map CharSequenceMap header name to index value to allow quick lookup
184-
private static CharSequenceMap<Integer> createMap() {
185-
int length = STATIC_TABLE.size();
186-
@SuppressWarnings("unchecked")
187-
CharSequenceMap<Integer> ret = new CharSequenceMap<Integer>(true,
188-
UnsupportedValueConverter.<Integer>instance(), length);
189-
// Iterate through the static table in reverse order to
190-
// save the smallest index for a given name in the map.
191-
for (int index = length; index > 0; index--) {
192-
HpackHeaderField entry = getEntry(index);
193-
CharSequence name = entry.name;
194-
ret.set(name, index);
222+
private static int headerBucket(CharSequence value) {
223+
return bucket(value, HEADERS_WITH_NON_EMPTY_VALUES_TABLE_SHIFT, HEADERS_WITH_NON_EMPTY_VALUES_TABLE_SIZE - 1);
224+
}
225+
226+
private static int bucket(CharSequence s, int shift, int mask) {
227+
return (AsciiString.hashCode(s) >> shift) & mask;
228+
}
229+
230+
private static final class HeaderNameIndex {
231+
final CharSequence name;
232+
final int index;
233+
final boolean emptyValue;
234+
235+
HeaderNameIndex(CharSequence name, int index, boolean emptyValue) {
236+
this.name = name;
237+
this.index = index;
238+
this.emptyValue = emptyValue;
195239
}
196-
return ret;
197240
}
198241

199-
/**
200-
* Returns the last position in the array that contains multiple
201-
* fields with the same name. Starting from this position, all
202-
* names are unique. Similar to {@link #getIndexInsensitive(CharSequence, CharSequence)} method
203-
* assumes all entries for a given header field are sequential
204-
*/
205-
private static int maxSameNameFieldIndex() {
206-
final int length = STATIC_TABLE.size();
207-
HpackHeaderField cursor = getEntry(length);
208-
for (int index = length - 1; index > 0; index--) {
209-
HpackHeaderField entry = getEntry(index);
210-
if (equalsVariableTime(entry.name, cursor.name)) {
211-
return index + 1;
212-
} else {
213-
cursor = entry;
214-
}
242+
private static final class HeaderIndex {
243+
final CharSequence name;
244+
final CharSequence value;
245+
final int index;
246+
247+
HeaderIndex(CharSequence name, CharSequence value, int index) {
248+
this.name = name;
249+
this.value = value;
250+
this.index = index;
215251
}
216-
return length;
217252
}
218253

219254
// singleton

‎codec-http2/src/test/java/io/netty/handler/codec/http2/HpackStaticTableTest.java‎

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
/*
2+
* Copyright 2022 The Netty Project
3+
*
4+
* The Netty Project licenses this file to you under the Apache License, version 2.0 (the
5+
* "License"); you may not use this file except in compliance with the License. You may obtain a
6+
* copy of the License at:
7+
*
8+
* https://www.apache.org/licenses/LICENSE-2.0
9+
*
10+
* Unless required by applicable law or agreed to in writing, software distributed under the License
11+
* is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
12+
* or implied. See the License for the specific language governing permissions and limitations under
13+
* the License.
14+
*/
15+
16+
package io.netty.handler.codec.http2;
17+
18+
import io.netty.util.AsciiString;
19+
import org.junit.jupiter.api.Test;
20+
21+
import static org.junit.jupiter.api.Assertions.assertEquals;
22+
23+
public class HpackStaticTableTest {
24+
25+
@Test
26+
public void testEmptyHeaderName() {
27+
assertEquals(-1, HpackStaticTable.getIndex(""));
28+
}
29+
30+
@Test
31+
public void testMissingHeaderName() {
32+
assertEquals(-1, HpackStaticTable.getIndex("missing"));
33+
}
34+
35+
@Test
36+
public void testExistingHeaderName() {
37+
assertEquals(6, HpackStaticTable.getIndex(":scheme"));
38+
}
39+
40+
@Test
41+
public void testMissingHeaderNameAndValue() {
42+
assertEquals(-1, HpackStaticTable.getIndexInsensitive("missing", "value"));
43+
}
44+
45+
@Test
46+
public void testMissingHeaderNameButValueExists() {
47+
assertEquals(-1, HpackStaticTable.getIndexInsensitive("missing", "https"));
48+
}
49+
50+
@Test
51+
public void testExistingHeaderNameAndValueFirstMatch() {
52+
assertEquals(6, HpackStaticTable.getIndexInsensitive(":scheme", "http"));
53+
}
54+
55+
@Test
56+
public void testExistingHeaderNameAndValueSecondMatch() {
57+
assertEquals(7, HpackStaticTable.getIndexInsensitive(
58+
AsciiString.cached(":scheme"), AsciiString.cached("https")));
59+
}
60+
61+
@Test
62+
public void testExistingHeaderNameAndEmptyValueMismatch() {
63+
assertEquals(-1, HpackStaticTable.getIndexInsensitive(":scheme", ""));
64+
}
65+
66+
@Test
67+
public void testExistingHeaderNameAndEmptyValueMatch() {
68+
assertEquals(27, HpackStaticTable.getIndexInsensitive("content-language", ""));
69+
}
70+
71+
@Test
72+
public void testExistingHeaderNameButMissingValue() {
73+
assertEquals(-1, HpackStaticTable.getIndexInsensitive(":scheme", "missing"));
74+
}
75+
76+
}

‎microbench/src/main/java/io/netty/handler/codec/http2/HpackStaticTableBenchmark.java‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -43,6 +43,9 @@ public class HpackStaticTableBenchmark extends AbstractMicrobenchmark {
4343
private static final CharSequence X_CONTENT_ENCODING =
4444
new AsciiString("x-content-encoding".getBytes(CharsetUtil.US_ASCII), false);
4545
private static final CharSequence X_GZIP = new AsciiString("x-gzip".getBytes(CharsetUtil.US_ASCII), false);
46+
private static final CharSequence SCHEME = new AsciiString(":scheme".getBytes(CharsetUtil.US_ASCII), false);
47+
private static final CharSequence HTTP = new AsciiString("http".getBytes(CharsetUtil.US_ASCII), false);
48+
private static final CharSequence HTTPS = new AsciiString("https".getBytes(CharsetUtil.US_ASCII), false);
4649
private static final CharSequence STATUS = new AsciiString(":status".getBytes(CharsetUtil.US_ASCII), false);
4750
private static final CharSequence STATUS_200 = new AsciiString("200".getBytes(CharsetUtil.US_ASCII), false);
4851
private static final CharSequence STATUS_500 = new AsciiString("500".getBytes(CharsetUtil.US_ASCII), false);
@@ -79,6 +82,18 @@ public int lookupNameOnlyMatchBeginTable() {
7982
return HpackStaticTable.getIndexInsensitive(AUTHORITY, AUTHORITY_NETTY);
8083
}
8184

85+
@Benchmark
86+
@BenchmarkMode(Mode.AverageTime)
87+
public int lookupHttp() {
88+
return HpackStaticTable.getIndexInsensitive(SCHEME, HTTP);
89+
}
90+
91+
@Benchmark
92+
@BenchmarkMode(Mode.AverageTime)
93+
public int lookupHttps() {
94+
return HpackStaticTable.getIndexInsensitive(SCHEME, HTTPS);
95+
}
96+
8297
@Benchmark
8398
@BenchmarkMode(Mode.AverageTime)
8499
public int lookupNameOnlyMatchEndTable() {

0 commit comments

Comments
 (0)