New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Jetty 9.4.x 3681 http fields optimize #3682
Conversation
Note also that HttpFields must be ordered AND support multiple fields of the same name! |
All fields ordered? or just fields with the same name? |
Including ordering, the results are not so clear cut. Lists are definitely better for small number of lookup and it is only at over 10 lookups does a
|
After instrumenting HttpFields to count iterations, hits and misses you see the results below hitting the demo base test webapp. Frequently we iterate between 3 an 4 times, which is probably hiding many accesses with code like https://github.com/eclipse/jetty.project/blob/jetty-9.4.18.v20190429/jetty-server/src/main/java/org/eclipse/jetty/server/ResourceService.java#L490-L513, so probably need to evaluate if giving up an iteration is worth 4 lookups.
|
If you are attempting to see what a real world setup would look like, then add ...
... to your execution path. Perhaps add a RequestDispatcher.forward() or .include() too. |
I added an iteration test to the benchmark. It suggests (as expected) that iterating and looking for 4 headers at a time is a big win for lists and a big loser for maps. Edit: and the headline is that list with iterative lookup (4 headers) is faster than Map for 20 lookups!
|
@joakime the demo-base test-webapp has gzip and secure-request customise already, which I think is probably middle of the road. |
So I think I'm calling this as List with iterative lookup is best:
So I think our current code is good.... although we can probably modify the CORS filter and some other code to use the iterative lookup technique. |
I have doubts about what you're testing. |
Here's the behavior of the method calls on The request
And the response
|
…81-HttpFieldsOptimize
@sbordet I'm trying to benchmark just the lookup on the key and not any handling of the value. The handling of the value will be pretty much the same for all cases and I can't see how a long will be handled any differently to a reference to a string, but hey I'll give that a go. The test is looking at the fundamental data structures that would be used inside HttpField and I believe I'm comparing apples with apples... in fact I'm probably being a bit tougher on lists as I always start hits from halfway through and then increment, so the average hit position is going to be more than half way into the list - I'll change that to be truly random. EDIT: ah it was random as I shuffle the trial list after creating the hit trial list. The Map has a lot more to do because it has a lot more to do to keep an ordered list of multi keyed fields. It has to be a map of lists, while the list can just be a list! I even make life easy for the map case and assume that all lists of fields are only 1 long (which is mostly the case and only very few headers are actually repeated). And actually that is still a wrong data structure, because we lose the true ordering of the fields and only keep the relative ordering. So it really should be a HashMap of Lists and a separate List of all fields. Anyway - if you have any suggestions of how to improve the test - or other data structures setups you want to test, just say. @joakime a successful upgrade request/response is interesting, but they are moderately rare cases that we don't need to optimise for. The more interesting case is an upgrade filter that misses.... ie what does it need to look at just to decide that there is nothing to do. Also I'm not sure what I'm looking at in that trace, it looks like it is both the creation of the fields (the adds), and the two times the querying of them (all the headers are fetched twice?) |
I've pushed some more benchmark variations... still get much the same results:
|
Even more benchmark variations pushed.... much the same results
|
tl;dr; The array list is best for <10 lookups and still comparable for <20 lookups. At 30 lookups ArrayList is very ordinary, but using the iteration technique can at least make it not horrible. The evidence is that we mostly do <10 lookups and the simple array list is definitely the most memory efficient. We should stay with what we have and use iterative lookups whenever possible. |
The most maniacal usage I've seen so far from spring is during a multipart POST. This is the results of the instrumentation, seen on a single qtp thread.
|
@joakime yes "maniacal" is a good description of that.... I hope it is not our code? |
@joakime actually I can see some improvements we can make to our multipart handling... we get contentType multiple times!... |
…81-HttpFieldsOptimize Signed-off-by: Greg Wilkins <gregw@webtide.com>
jetty-http/src/main/java/org/eclipse/jetty/http/HttpFields.java
Outdated
Show resolved
Hide resolved
jetty-http/src/main/java/org/eclipse/jetty/http/HttpFields.java
Outdated
Show resolved
Hide resolved
jetty-server/src/main/java/org/eclipse/jetty/server/Request.java
Outdated
Show resolved
Hide resolved
jetty-server/src/main/java/org/eclipse/jetty/server/Request.java
Outdated
Show resolved
Hide resolved
…81-HttpFieldsOptimize
@sbordet is this OK now? |
jetty-http/src/main/java/org/eclipse/jetty/http/HttpFields.java
Outdated
Show resolved
Hide resolved
jetty-http/src/main/java/org/eclipse/jetty/http/HttpFields.java
Outdated
Show resolved
Hide resolved
jetty-http/src/main/java/org/eclipse/jetty/http/HttpFields.java
Outdated
Show resolved
Hide resolved
jetty-http/src/main/java/org/eclipse/jetty/http/HttpFields.java
Outdated
Show resolved
Hide resolved
jetty-http/src/main/java/org/eclipse/jetty/http/HttpFields.java
Outdated
Show resolved
Hide resolved
…81-HttpFieldsOptimize
@sbordet nudge |
Added a benchmark for #3681.
This benchmark compares a list, two Trie implementations and a Map for case insensitive lookup. It looks at 1, 10 and 20 lookups per iteration, with the looks ups being hits, misses or near misses (costs more in string check). The key length is 11 (average known headers) and the size of the structure is 12 (from chrome request). All the structures are created at the right size and don't need to be resized during building.
Results below show that Map is always better than List!!! Even on a single lookup (which is actually 3 lookups due to the benchmark), it is just a little better, and for 25 lookups, it's almost 4 times better!
The Tries obviously cost more to build as they are poor for a few lookups, but improve to be competitive with the Map by 25 lookups. I expect they would be best for more lookups, so we need to know how many lookups we do!