Newly added benchmarks description:

• headerMapImplEmulateH1toH2Upgrade - emulates the encodeHeaders (H2) code, when upgrading a request from H1 to H2.
• headerMapImplEmulateH2toH1Upgrade - emulates the decodeHeaders (H2) code, when upgrading a response from H2 to H1.
• headerMapImplRemovePrefix - emulates removal of varying number of headers with prefix, from a header-map that also has headers without the prefix.
• manyCountryRoutesLongHeaders - emulates the route matching code where there are 250 backends, and the routing is done using a header ("x-country"). A request with ~100 headers is dispatched, and its requested country header doesn't exist in any route. This causes the old headermap implementation to iterate over all header keys, and many comparisons of the "x-country" header.

Post-runtime configuration results:
Headermap benchmark results (average of 3 executions, more thresholds):

The manyCountryRoutesLongHeaders benchmark results:
Original headermap: 106606 ns
Lazymap-absl::flat_hash_map (threshold=0): 11615 ns
Lazymap-std::multimap (threshold=0): 25801 ns
Lazymap-absl::btree (threshold=0): 16017 ns

Pre-runtime configuration results:
Headermap benchmark results (average of 3 executions, more thresholds):

The manyCountryRoutesLongHeaders benchmark results:
Original headermap: 106606 ns
Lazymap-absl::flat_hash_map (threshold=0): 11424 ns
Lazymap-std::map (threshold=0): 26044 ns
Lazymap-std::multimap (threshold=0): 26759 ns
Lazymap-absl::btree (threshold=0): 15945 ns

Summary:

• Closer look at the microbenchmarks suggests that the threshold should be set to 2-3, and then the map should be used.
• In some microbenchmarks std::map is a bit faster than absl::flat_hash_map, while in others it is slower. For thresholds 2-3 it seems that absl::flat_hash_map is faster than std::map.
• The benchmarks emulating encodeHeaders and decodeHeaders suggests some penalty on the encoding emulation compared with the original headermap implementation. There isn't a clear winner between std::map and absl::flat_hash_map, but they seem to be almost on par (except maybe for the headerMapImplEmulateH2toH1Upgrade/50 test).
• The route matching benchmark shows ~10x improvement in this case when using absl::flat_hash_map. std::map is about 2.5x slower than absl::flat_hash_map.
• Using std::multimap or absl::btree_multimap mostly doesn't seem to improve the performance over absl::flat_hash_map. (Note that with std::multimap the removePrefix can be implemented more efficiently, and will have better performance in some instances).
• The current runtime configuration that executes per-headermap instance runtime call has a non-negligible performance penalty. This should be addressed in a future PR.

@mattklein123 @jmarantz @antoniovicente, please take a look.
This is mainly following @jmarantz earlier design.
I've added some tests to try to emulate possible scenarios.

your country-code test is a good one. What do we get when we use a std::map for that?

your country-code test is a good one. What do we get when we use a std::map for that?

That was @antoniovicente's idea (and I agree it is a good test). Compared to absl::flat_hash_map, std::map is 2.5x slower. I've also updated the comparison comment with this data.

@jmarantz Please let me know if you have any other ideas/questions.

Memory consumption: The original implementation (and the lazy map too) reserves memory for the custom headers in each request/response. Here is a breakdown of the memory usage (no custom defined headers other than the default ones):

• RequestHeaderMap:
  • static allocation: 1,010KiB for the Trie.
  • per-request: 460 bytes.
• ResponseHeaderMap:
  • static allocation: 546KiB for the Trie.
  • per-response: 258 bytes.

This pull request has been automatically marked as stale because it has not had activity in the last 7 days. It will be closed in 7 days if no further activity occurs. Please feel free to give a status update now, ping for review, or re-open when it's ready. Thank you for your contributions!

It'd be great to get this in. What's the next step?

Sorry, forgot to update this PR.
Summary so far:
Updated the lazy-map to use a runtime feature ("envoy.http.headermap.lazy_map_min_size"), and tried to introduce new removePrefix tests (couldn't find the tests you mentioned in previous non-merged PRs).
I haven't seen differences in these tests too, and realized that I need to reimplement removePrefix when using a BTree. Should be done by tomorrow.

Thanks LGTM. Going to to mark this exempt from stale bot until we land this.

Thanks for your patience. Can you merge main and then we can do a final pass on this and merge?

/wait

@mattklein123 latest main is now merged, PTAL.

/retest
(failed accessing homebrew's site)

Retrying Azure Pipelines, to retry CircleCI checks, use /retest-circle.
Retried failed jobs in: envoy-presubmit