WiP http: add lazy map for eliminating O(n) header operations.#9261
WiP http: add lazy map for eliminating O(n) header operations.#9261jmarantz wants to merge 18 commits intoenvoyproxy:masterfrom
Conversation
Signed-off-by: Joshua Marantz <jmarantz@google.com>
…more clearly. Signed-off-by: Joshua Marantz <jmarantz@google.com>
Signed-off-by: Joshua Marantz <jmarantz@google.com>
Signed-off-by: Joshua Marantz <jmarantz@google.com>
Signed-off-by: Joshua Marantz <jmarantz@google.com>
Signed-off-by: Joshua Marantz <jmarantz@google.com>
|
Speed-test comparison with no maps, with a flat_hash_map, and with a multi_map. To me it looks like with a reasonable # of headers, multi_map is the best choice.
|
…his adds complexity but makes common cases faster. Signed-off-by: Joshua Marantz <jmarantz@google.com>
|
An easier to read graph covering just the benchmarks that have O(N) growth with no map:
|
|
@jmarantz do you mind summarizing what we are doing/testing here? Also, as an aside, did you try the absl btree maps? They should be faster than the std maps AFAIK. |
|
I don't mind :) This is not really in shape to be a mergeable PR as it makes things strictly more complex. But I wanted to think quantitatively about the overhead have maintaining maps. FWIW we do see HeaderMap stuff show up in flame-graphs and it's not the lowest hanging fruit right now but it does come up. I suspect in our environment we have a bunch of non-O(1) headers, especially Set-Cookie which needs to stay O(N) as that's currently tied to coalescing. I haven't tried -- and didn't know about -- absl::btree . But one more thing is that the multi-map variant in this draft-PR could also allow for a fast (O(log n) + O(# matches)) impl of removePrefix(), though I don't know specifically if that's coming up as an issue. I thing my thoughts on plausible end-states include:
|
|
OK thanks makes sense to me. I think this is a worthwhile thing to investigate for sure. |
source/common/http/header_map_impl.h
Outdated
| struct HeaderEntryImpl; | ||
| using HeaderNode = std::list<HeaderEntryImpl>::iterator; | ||
| #if HEADER_MAP_USE_FLAT_HASH_MAP | ||
| using HeaderNodeVector = std::vector<HeaderNode>; |
There was a problem hiding this comment.
I would try https://github.com/abseil/abseil-cpp/blob/master/absl/container/inlined_vector.h here with a default size of 1 which would be the common case?
There was a problem hiding this comment.
good idea; I'll give that a try.
|
|
||
| HeaderMapImpl::HeaderLazyMap::iterator | ||
| HeaderMapImpl::HeaderList::find(absl::string_view key) const { | ||
| if (lazy_map_.empty()) { |
There was a problem hiding this comment.
Should this also use maybeMakeMap() to be consistent and also share the construction code?
There was a problem hiding this comment.
Yeah this could use a refactor; I'll clean that up.
|
Cool stuff just left some random comments from a quick read, will look more later. :) |
Signed-off-by: Joshua Marantz <jmarantz@google.com>
Signed-off-by: Joshua Marantz <jmarantz@google.com>
|
@jmarantz what are your thoughts on next steps for this PR? /wait-any |
|
Will be moving forward with this when I get some coding time :) I started experimenting with your suggestions and the inlined-vector improved things a bit, the btree didn't seem to help, but I would not say my experiments are conclusive. |
|
OK I will put this into waiting for now with no stalebot. Let us know when you feel ready to have a conversation about whether we want to go with this approach or not. |
Signed-off-by: Joshua Marantz <jmarantz@google.com>
Signed-off-by: Joshua Marantz <jmarantz@google.com>
Signed-off-by: Joshua Marantz <jmarantz@google.com>
Signed-off-by: Joshua Marantz <jmarantz@google.com>
…t break tests. Signed-off-by: Joshua Marantz <jmarantz@google.com>
Signed-off-by: Joshua Marantz <jmarantz@google.com>
…nings. Signed-off-by: Joshua Marantz <jmarantz@google.com>
Signed-off-by: Joshua Marantz <jmarantz@google.com>
|
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! |
|
This pull request has been automatically closed because it has not had activity in the last 14 days. Please feel free to give a status update now, ping for review, or re-open when it's ready. Thank you for your contributions! |
This is a continuation of #9261. Adding a map to headermap's HeaderList to access headers by key in O(1) instead of O(n). In addition some benchmarks that emulate encoding and decoding of headers, and route matching by headers are added. Signed-off-by: Adi Suissa-Peleg <adip@google.com>
For an explanation of how to fill out the fields, please see the relevant section
in PULL_REQUESTS.md
Description:
Risk Level:
Testing:
Docs Changes:
Release Notes:
[Optional Fixes #Issue]
[Optional Deprecated:]