Use std::vector instead of std::deque for HPACK and QPACK static table.
The static table is not mutated after initialization, and it does not need
iterator stability (tables pointing into its elements can be initialized after
the full static table is initialized), so the simplest, lightest container will
do.
PiperOrigin-RevId: 364626329
Change-Id: I2bbc8866744871d79189431ae87435d7e263c7f1
diff --git a/quic/core/qpack/qpack_header_table.h b/quic/core/qpack/qpack_header_table.h
index e2a1a9e..6a5e15a 100644
--- a/quic/core/qpack/qpack_header_table.h
+++ b/quic/core/qpack/qpack_header_table.h
@@ -32,7 +32,8 @@
// necessary transformations to and from relative indices and post-base indices.
class QUIC_EXPORT_PRIVATE QpackHeaderTable {
public:
- using EntryTable = spdy::HpackHeaderTable::EntryTable;
+ using StaticEntryTable = spdy::HpackHeaderTable::StaticEntryTable;
+ using DynamicEntryTable = spdy::HpackHeaderTable::DynamicEntryTable;
using NameValueToEntryMap = spdy::HpackHeaderTable::NameValueToEntryMap;
using NameToEntryMap = spdy::HpackHeaderTable::NameToEntryMap;
@@ -164,7 +165,7 @@
// QpackStaticTable singleton.
// Tracks QpackEntries by index.
- const EntryTable& static_entries_;
+ const StaticEntryTable& static_entries_;
// Tracks the unique static entry for a given header name and value.
const NameValueToEntryMap& static_index_;
@@ -176,7 +177,7 @@
// Queue of dynamic table entries, for lookup by index.
// |dynamic_entries_| owns the entries in the dynamic table.
- EntryTable dynamic_entries_;
+ DynamicEntryTable dynamic_entries_;
// An unordered set of QpackEntry pointers with a comparison operator that
// only cares about name and value. This allows fast lookup of the most
diff --git a/spdy/core/hpack/hpack_encoder_test.cc b/spdy/core/hpack/hpack_encoder_test.cc
index 3f0fbaa..a3a1bdc 100644
--- a/spdy/core/hpack/hpack_encoder_test.cc
+++ b/spdy/core/hpack/hpack_encoder_test.cc
@@ -22,7 +22,7 @@
public:
explicit HpackHeaderTablePeer(HpackHeaderTable* table) : table_(table) {}
- HpackHeaderTable::EntryTable* dynamic_entries() {
+ HpackHeaderTable::DynamicEntryTable* dynamic_entries() {
return &table_->dynamic_entries_;
}
diff --git a/spdy/core/hpack/hpack_header_table.cc b/spdy/core/hpack/hpack_header_table.cc
index d59257e..709f3ef 100644
--- a/spdy/core/hpack/hpack_header_table.cc
+++ b/spdy/core/hpack/hpack_header_table.cc
@@ -91,8 +91,8 @@
void HpackHeaderTable::EvictionSet(absl::string_view name,
absl::string_view value,
- EntryTable::iterator* begin_out,
- EntryTable::iterator* end_out) {
+ DynamicEntryTable::iterator* begin_out,
+ DynamicEntryTable::iterator* end_out) {
size_t eviction_count = EvictionCountForEntry(name, value);
*begin_out = dynamic_entries_.end() - eviction_count;
*end_out = dynamic_entries_.end();
diff --git a/spdy/core/hpack/hpack_header_table.h b/spdy/core/hpack/hpack_header_table.h
index 6a32eb8..6df9c50 100644
--- a/spdy/core/hpack/hpack_header_table.h
+++ b/spdy/core/hpack/hpack_header_table.h
@@ -37,6 +37,10 @@
public:
friend class test::HpackHeaderTablePeer;
+ // Use a lightweight, memory efficient container for the static table, which
+ // is initialized once and never changed after.
+ using StaticEntryTable = std::vector<HpackEntry>;
+
// HpackHeaderTable takes advantage of the deque property that references
// remain valid, so long as insertions & deletions are at the head & tail.
// This precludes the use of base::circular_deque.
@@ -44,7 +48,9 @@
// If this changes (we want to change to circular_deque or we start to drop
// entries from the middle of the table), this should to be a std::list, in
// which case |*_index_| can be trivially extended to map to list iterators.
- using EntryTable = std::deque<HpackEntry>;
+ //
+ // TODO(b/182349990): Change to a more memory efficient container.
+ using DynamicEntryTable = std::deque<HpackEntry>;
using NameValueToEntryMap = absl::flat_hash_map<HpackLookupEntry, size_t>;
using NameToEntryMap = absl::flat_hash_map<absl::string_view, size_t>;
@@ -91,8 +97,8 @@
// actually occurs. The set is returned via range [begin_out, end_out).
void EvictionSet(absl::string_view name,
absl::string_view value,
- EntryTable::iterator* begin_out,
- EntryTable::iterator* end_out);
+ DynamicEntryTable::iterator* begin_out,
+ DynamicEntryTable::iterator* end_out);
// Adds an entry for the representation, evicting entries as needed. |name|
// and |value| must not point to an entry in |dynamic_entries_| which is about
@@ -120,8 +126,8 @@
// HpackStaticTable singleton.
// Stores HpackEntries.
- const EntryTable& static_entries_;
- EntryTable dynamic_entries_;
+ const StaticEntryTable& static_entries_;
+ DynamicEntryTable dynamic_entries_;
// Tracks the index of the unique HpackEntry for a given header name and
// value. Keys consist of string_views that point to strings stored in
diff --git a/spdy/core/hpack/hpack_header_table_test.cc b/spdy/core/hpack/hpack_header_table_test.cc
index b3f761e..c1a357c 100644
--- a/spdy/core/hpack/hpack_header_table_test.cc
+++ b/spdy/core/hpack/hpack_header_table_test.cc
@@ -25,15 +25,15 @@
public:
explicit HpackHeaderTablePeer(HpackHeaderTable* table) : table_(table) {}
- const HpackHeaderTable::EntryTable& dynamic_entries() {
+ const HpackHeaderTable::DynamicEntryTable& dynamic_entries() {
return table_->dynamic_entries_;
}
- const HpackHeaderTable::EntryTable& static_entries() {
+ const HpackHeaderTable::StaticEntryTable& static_entries() {
return table_->static_entries_;
}
std::vector<HpackEntry*> EvictionSet(absl::string_view name,
absl::string_view value) {
- HpackHeaderTable::EntryTable::iterator begin, end;
+ HpackHeaderTable::DynamicEntryTable::iterator begin, end;
table_->EvictionSet(name, value, &begin, &end);
std::vector<HpackEntry*> result;
for (; begin != end; ++begin) {
@@ -97,7 +97,7 @@
// expecting no eviction to happen.
void AddEntriesExpectNoEviction(const HpackEntryVector& entries) {
for (auto it = entries.begin(); it != entries.end(); ++it) {
- HpackHeaderTable::EntryTable::iterator begin, end;
+ HpackHeaderTable::DynamicEntryTable::iterator begin, end;
table_.EvictionSet(it->name(), it->value(), &begin, &end);
EXPECT_EQ(0, distance(begin, end));
diff --git a/spdy/core/hpack/hpack_static_table.cc b/spdy/core/hpack/hpack_static_table.cc
index 260008b..7eeb745 100644
--- a/spdy/core/hpack/hpack_static_table.cc
+++ b/spdy/core/hpack/hpack_static_table.cc
@@ -20,18 +20,25 @@
size_t static_entry_count) {
QUICHE_CHECK(!IsInitialized());
- int insertion_count = 0;
+ static_entries_.reserve(static_entry_count);
+
for (const HpackStaticEntry* it = static_entry_table;
it != static_entry_table + static_entry_count; ++it) {
absl::string_view name(it->name, it->name_len);
absl::string_view value(it->value, it->value_len);
static_entries_.emplace_back(name, value);
- HpackEntry* entry = &static_entries_.back();
+ }
+
+ // |static_entries_| will not be mutated any more. Therefore its entries will
+ // remain stable even if the container does not have iterator stability.
+ int insertion_count = 0;
+ for (const auto& entry : static_entries_) {
auto result = static_index_.insert(std::make_pair(
- HpackLookupEntry{entry->name(), entry->value()}, insertion_count));
+ HpackLookupEntry{entry.name(), entry.value()}, insertion_count));
QUICHE_CHECK(result.second);
+
// Multiple static entries may have the same name, so inserts may fail.
- static_name_index_.insert(std::make_pair(entry->name(), insertion_count));
+ static_name_index_.insert(std::make_pair(entry.name(), insertion_count));
++insertion_count;
}
diff --git a/spdy/core/hpack/hpack_static_table.h b/spdy/core/hpack/hpack_static_table.h
index 296e050..346332e 100644
--- a/spdy/core/hpack/hpack_static_table.h
+++ b/spdy/core/hpack/hpack_static_table.h
@@ -33,7 +33,7 @@
bool IsInitialized() const;
// Accessors.
- const HpackHeaderTable::EntryTable& GetStaticEntries() const {
+ const HpackHeaderTable::StaticEntryTable& GetStaticEntries() const {
return static_entries_;
}
const HpackHeaderTable::NameValueToEntryMap& GetStaticIndex() const {
@@ -47,7 +47,7 @@
size_t EstimateMemoryUsage() const;
private:
- HpackHeaderTable::EntryTable static_entries_;
+ HpackHeaderTable::StaticEntryTable static_entries_;
// The following two members have string_views that point to strings stored in
// |static_entries_|.
HpackHeaderTable::NameValueToEntryMap static_index_;
diff --git a/spdy/core/hpack/hpack_static_table_test.cc b/spdy/core/hpack/hpack_static_table_test.cc
index 0d0c74b..f7506da 100644
--- a/spdy/core/hpack/hpack_static_table_test.cc
+++ b/spdy/core/hpack/hpack_static_table_test.cc
@@ -31,7 +31,7 @@
HpackStaticTableVector().size());
EXPECT_TRUE(table_.IsInitialized());
- const HpackHeaderTable::EntryTable& static_entries =
+ const HpackHeaderTable::StaticEntryTable& static_entries =
table_.GetStaticEntries();
EXPECT_EQ(kStaticTableSize, static_entries.size());
