Skip to content
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

Merged
merged 17 commits into from Jun 3, 2019

Conversation

gregw
Copy link
Contributor

@gregw gregw commented May 21, 2019

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!

Benchmark length size lookups mostly Score
ListVsTrieBenchmark.testMap 11 12 1 nears 2,383,311
ListVsTrieBenchmark.testMap 11 12 1 misses 2,325,697
ListVsTrieBenchmark.testMap 11 12 1 hits 2,271,474
ListVsTrieBenchmark.testList 11 12 1 nears 2,236,174
ListVsTrieBenchmark.testList 11 12 1 hits 2,225,551
ListVsTrieBenchmark.testList 11 12 1 misses 2,203,521
ListVsTrieBenchmark.testTreeTrie 11 12 1 nears 1,423,354
ListVsTrieBenchmark.testTreeTrie 11 12 1 hits 1,356,713
ListVsTrieBenchmark.testTreeTrie 11 12 1 misses 1,349,678
ListVsTrieBenchmark.testArrayTrie 11 12 1 hits 1,150,452
ListVsTrieBenchmark.testArrayTrie 11 12 1 misses 1,149,095
ListVsTrieBenchmark.testArrayTrie 11 12 1 nears 1,138,353
Benchmark length size lookups mostly Score
ListVsTrieBenchmark.testMap 11 12 10 hits 1,936,905
ListVsTrieBenchmark.testMap 11 12 10 misses 1,587,259
ListVsTrieBenchmark.testMap 11 12 10 nears 1,559,876
ListVsTrieBenchmark.testTreeTrie 11 12 10 nears 1,331,736
ListVsTrieBenchmark.testTreeTrie 11 12 10 misses 1,304,307
ListVsTrieBenchmark.testList 11 12 10 hits 1,123,292
ListVsTrieBenchmark.testArrayTrie 11 12 10 misses 1,104,399
ListVsTrieBenchmark.testTreeTrie 11 12 10 hits 1,102,755
ListVsTrieBenchmark.testArrayTrie 11 12 10 nears 1,085,943
ListVsTrieBenchmark.testArrayTrie 11 12 10 hits 1,060,308
ListVsTrieBenchmark.testList 11 12 10 misses 840,148
ListVsTrieBenchmark.testList 11 12 10 nears 763,328
Benchmark length size lookups mostly Score
ListVsTrieBenchmark.testMap 11 12 20 hits 1,459,364
ListVsTrieBenchmark.testTreeTrie 11 12 20 misses 1,200,398
ListVsTrieBenchmark.testMap 11 12 20 misses 1,184,881
ListVsTrieBenchmark.testTreeTrie 11 12 20 nears 1,147,371
ListVsTrieBenchmark.testMap 11 12 20 nears 1,128,912
ListVsTrieBenchmark.testArrayTrie 11 12 20 misses 1,059,139
ListVsTrieBenchmark.testArrayTrie 11 12 20 nears 1,019,500
ListVsTrieBenchmark.testArrayTrie 11 12 20 hits 978,893
ListVsTrieBenchmark.testTreeTrie 11 12 20 hits 922,937
ListVsTrieBenchmark.testList 11 12 20 hits 832,529
ListVsTrieBenchmark.testList 11 12 20 misses 487,945
ListVsTrieBenchmark.testList 11 12 20 nears 444,695

gregw added 2 commits May 21, 2019 12:39
Benchmark possible HttpFields lookup mechanisms

Signed-off-by: Greg Wilkins <gregw@webtide.com>
Better default HttpFields size with TODOs to tune.

Signed-off-by: Greg Wilkins <gregw@webtide.com>
@gregw gregw requested review from joakime and sbordet May 21, 2019 11:00
@gregw
Copy link
Contributor Author

gregw commented May 21, 2019

Note also that HttpFields must be ordered AND support multiple fields of the same name!
So a simple Map will not work. I will benchmark LinkedHashMap of Lists and perhaps a List with a Map fast path for single fields.

Use LinkedHashMap<List<Pair>>

Signed-off-by: Greg Wilkins <gregw@webtide.com>
@joakime
Copy link
Contributor

joakime commented May 21, 2019

All fields ordered? or just fields with the same name?

@gregw
Copy link
Contributor Author

gregw commented May 21, 2019

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 LinkedHashMap become better. By 20 lookups, the LinkedHashMap is definitely better, but only by a small margin and I would expect at a cost of more garbage.

Benchmark lookups mostly size Score
ListVsTrieBenchmark.testList 1 hits 12 2,191,808
ListVsTrieBenchmark.testList 1 misses 12 2,160,590
ListVsTrieBenchmark.testList 1 nears 12 2,053,833
ListVsTrieBenchmark.testSortedMap 1 misses 12 1,573,145
ListVsTrieBenchmark.testSortedMap 1 nears 12 1,444,541
ListVsTrieBenchmark.testSortedMap 1 hits 12 1,314,410
Benchmark lookups mostly size Score
ListVsTrieBenchmark.testSortedMap 10 hits 12 1,127,522
ListVsTrieBenchmark.testSortedMap 10 nears 12 1,089,492
ListVsTrieBenchmark.testList 10 hits 12 1,071,642
ListVsTrieBenchmark.testSortedMap 10 misses 12 1,035,947
ListVsTrieBenchmark.testList 10 misses 12 777,916
ListVsTrieBenchmark.testList 10 nears 12 722,910
Benchmark lookups mostly size Score
ListVsTrieBenchmark.testSortedMap 20 hits 12 910,975
ListVsTrieBenchmark.testSortedMap 20 misses 12 804,953
ListVsTrieBenchmark.testSortedMap 20 nears 12 799,627
ListVsTrieBenchmark.testList 20 hits 12 709,598
ListVsTrieBenchmark.testList 20 misses 12 450,087
ListVsTrieBenchmark.testList 20 nears 12 415,702

instrumented HttpFields

Signed-off-by: Greg Wilkins <gregw@webtide.com>
@gregw
Copy link
Contributor Author

gregw commented May 21, 2019

After instrumenting HttpFields to count iterations, hits and misses you see the results below hitting the demo base test webapp.
There are many HttpFields created that are not accessed at all (probably responses). Those that are accessed are missed as often (or more) than hit and combined accesses are < 10, often < 5.

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.

iterations=0 hits=0 misses=3
iterations=4 hits=3 misses=3
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=3
iterations=4 hits=3 misses=3
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=0
iterations=4 hits=1 misses=3
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=3
iterations=4 hits=3 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=0
iterations=5 hits=1 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=0
iterations=5 hits=1 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=0
iterations=3 hits=1 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=3
iterations=4 hits=3 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=3
iterations=4 hits=3 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=0
iterations=5 hits=1 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=0
iterations=5 hits=1 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=1 misses=0
iterations=4 hits=1 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=3
iterations=4 hits=3 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=2
iterations=4 hits=2 misses=2
iterations=0 hits=0 misses=0
iterations=1 hits=0 misses=0
iterations=3 hits=1 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=2
iterations=4 hits=2 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=0
iterations=3 hits=4 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=2
iterations=4 hits=2 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=2
iterations=4 hits=2 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=2
iterations=4 hits=2 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=0
iterations=5 hits=1 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=3
iterations=3 hits=3 misses=3
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=2
iterations=4 hits=2 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=3
iterations=6 hits=3 misses=7
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=2
iterations=4 hits=2 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=0
iterations=5 hits=1 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=0
iterations=3 hits=1 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=2
iterations=4 hits=2 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=2
iterations=4 hits=2 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=3
iterations=4 hits=3 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=0
iterations=5 hits=1 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=3
iterations=3 hits=3 misses=2
iterations=0 hits=0 misses=0
iterations=0 hits=0 misses=3
iterations=4 hits=3 misses=2
iterations=0 hits=0 misses=0

@joakime
Copy link
Contributor

joakime commented May 21, 2019

If you are attempting to see what a real world setup would look like, then add ...

  • CrossOriginFilter
  • GzipHandler
  • RedirectHandler
  • SecureRequestCustomizer

... to your execution path.

Perhaps add a RequestDispatcher.forward() or .include() too.

added iteration test to benchmark

Signed-off-by: Greg Wilkins <gregw@webtide.com>
@gregw
Copy link
Contributor Author

gregw commented May 21, 2019

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!

Benchmark lookups mostly Score
ListVsMapBenchmark.testList 1 iterate 3,624,855
ListVsMapBenchmark.testList 1 hits 2,597,275
ListVsMapBenchmark.testList 1 misses 2,587,123
ListVsMapBenchmark.testSortedMap 1 misses 1,416,899
ListVsMapBenchmark.testSortedMap 1 hits 1,411,645
ListVsMapBenchmark.testSortedMap 1 iterate 1,220,511
Benchmark lookups mostly Score
ListVsMapBenchmark.testList 10 iterate 1,861,768
ListVsMapBenchmark.testList 10 hits 1,397,822
ListVsMapBenchmark.testSortedMap 10 hits 1,189,547
ListVsMapBenchmark.testSortedMap 10 misses 1,163,632
ListVsMapBenchmark.testList 10 misses 796,025
ListVsMapBenchmark.testSortedMap 10 iterate 754,102
Benchmark lookups mostly Score
ListVsMapBenchmark.testList 20 iterate 1,365,352
ListVsMapBenchmark.testSortedMap 20 hits 1,001,441
ListVsMapBenchmark.testSortedMap 20 misses 945,087
ListVsMapBenchmark.testList 20 hits 900,301
ListVsMapBenchmark.testSortedMap 20 iterate 585,534
ListVsMapBenchmark.testList 20 misses 510,674

@gregw
Copy link
Contributor Author

gregw commented May 21, 2019

@joakime the demo-base test-webapp has gzip and secure-request customise already, which I think is probably middle of the road.
CrossOriginFilter looks like it could be optimised to use iteration better.

@gregw
Copy link
Contributor Author

gregw commented May 21, 2019

So I think I'm calling this as List with iterative lookup is best:

  • much better for the response case where we just add and do very few lookups.
  • much better at <=10 lookups, which appears to be moderately reasonable.
  • even with > 10 lookups, the iterative lookup technique is a big win.

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.

remove HttpFields instrumentation

Signed-off-by: Greg Wilkins <gregw@webtide.com>
@sbordet
Copy link
Contributor

sbordet commented May 21, 2019

I have doubts about what you're testing.
You are not really testing HttpFields, but just list and map mechanics.
Furthermore, the pair "value" is a simple integer which is not a realistic case... this will likely affect the L1 cache depending on the length of the field value.
The map benchmark seems to be doing a lot more than the list benchmark, so I'm not sure we're comparing apples to apples?

@joakime
Copy link
Contributor

joakime commented May 21, 2019

Here's the behavior of the method calls on HttpFields during a websocket upgrade testcase in the spring-framework.

The request

{
    "mode": "request"
    "initial_state":
request.iterator()
request.Itr().hasNext()
}
request.add((HttpField) Sec-WebSocket-Key: 46IJ0AE76cBrovGilwilIA==)
request.add((HttpField) Connection: Upgrade)
request.add((HttpField) Sec-WebSocket-Version: 13)
request.add((HttpField) Host: localhost:37143)
request.add((HttpField) Upgrade: websocket)
request.add((HttpField) Sec-WebSocket-Protocol: echo-v1)
request.contains((HttpHeader) Connection, (String) close)
request.getFieldNames()
request.getFieldNamesCollection()
request.iterator()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.getValues((String) Connection)
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.nextElement()
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.hasMoreElements()
request.getValues((String) Sec-WebSocket-Key)
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.nextElement()
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.hasMoreElements()
request.getValues((String) Sec-WebSocket-Version)
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.nextElement()
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.hasMoreElements()
request.getValues((String) Host)
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.nextElement()
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.hasMoreElements()
request.getValues((String) Upgrade)
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.nextElement()
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.hasMoreElements()
request.getValues((String) Sec-WebSocket-Protocol)
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.nextElement()
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.hasMoreElements()
request.get((HttpHeader) Content-Type)
request.getField((HttpHeader) Content-Length)
request.get((String) Upgrade)
request.get((String) Connection)
request.iterator()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.getFieldNames()
request.getFieldNamesCollection()
request.iterator()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.getValues((String) Connection)
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.nextElement()
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.hasMoreElements()
request.getValues((String) Sec-WebSocket-Key)
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.nextElement()
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.hasMoreElements()
request.getValues((String) Sec-WebSocket-Version)
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.nextElement()
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.hasMoreElements()
request.getValues((String) Host)
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.nextElement()
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.hasMoreElements()
request.getValues((String) Upgrade)
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.nextElement()
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.hasMoreElements()
request.getValues((String) Sec-WebSocket-Protocol)
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.nextElement()
request.enumerationOfStringValues.hasMoreElements()
request.enumerationOfStringValues.hasMoreElements()
request.get((HttpHeader) Content-Type)
request.getQualityCSV((HttpHeader) Accept-Language)
request.getQualityCSV((HttpHeader) Accept-Language, (ToIntFunction<String>) null)
request.iterator()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.Itr().next()
request.Itr().hasNext()
request.clear()
request.clear()

And the response

{
    "mode": "response"
    "initial_state":
response.iterator()
response.Itr().hasNext()
}
response.contains((HttpHeader) Date)
response.put((HttpField) Date: Tue, 21 May 2019 21:06:40 GMT)
response.add((HttpField) Date: Tue, 21 May 2019 21:06:40 GMT)
response.put((String) Sec-WebSocket-Protocol, (String) echo-v1)
response.put((HttpField) Sec-WebSocket-Protocol: echo-v1)
response.add((HttpField) Sec-WebSocket-Protocol: echo-v1)
response.put((String) Sec-WebSocket-Extensions, (String) null)
response.remove((String) Sec-WebSocket-Extensions)
response.put((String) Server, (String) null)
response.remove((String) Server)
response.put((String) Upgrade, (String) null)
response.remove((String) Upgrade)
response.getFieldNamesCollection()
response.iterator()
response.Itr().hasNext()
response.Itr().next()
response.Itr().hasNext()
response.Itr().next()
response.Itr().hasNext()
response.getValuesList((String) Date)
response.iterator()
response.Itr().hasNext()
response.Itr().next()
response.Itr().hasNext()
response.Itr().next()
response.Itr().hasNext()
response.getValuesList((String) Sec-WebSocket-Protocol)
response.iterator()
response.Itr().hasNext()
response.Itr().next()
response.Itr().hasNext()
response.Itr().next()
response.Itr().hasNext()
response.add((String) Connection, (String) Upgrade)
response.add((HttpField) Connection: Upgrade)
response.add((String) Sec-WebSocket-Accept, (String) hBGNoc46IKPNnwYmlsXYLT9eBjo=)
response.add((HttpField) Sec-WebSocket-Accept: hBGNoc46IKPNnwYmlsXYLT9eBjo=)
response.add((String) Server, (String) Jetty(9.4.19-SNAPSHOT))
response.add((HttpField) Server: Jetty(9.4.19-SNAPSHOT))
response.add((String) Upgrade, (String) WebSocket)
response.add((HttpField) Upgrade: WebSocket)
response.size()
response.getField((int) 0)
response.getField((int) 1)
response.getField((int) 2)
response.getField((int) 3)
response.getField((int) 4)
response.getField((int) 5)
response.clear()

@gregw
Copy link
Contributor Author

gregw commented May 22, 2019

@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?)

More benchmark variations

Signed-off-by: Greg Wilkins <gregw@webtide.com>
@gregw
Copy link
Contributor Author

gregw commented May 22, 2019

I've pushed some more benchmark variations... still get much the same results:

Benchmark lookups mostly Score
ListVsMapBenchmark.testArrayList 1 iterate 776,770
ListVsMapBenchmark.testArrayList 1 misses 758,297
ListVsMapBenchmark.testLinkedList 1 iterate 755,454
ListVsMapBenchmark.testArrayList 1 hits 750,474
ListVsMapBenchmark.testLinkedList 1 misses 704,943
ListVsMapBenchmark.testLinkedList 1 hits 680,872
ListVsMapBenchmark.testHashMapAndLinkedList 1 hits 617,642
ListVsMapBenchmark.testHashMapAndLinkedList 1 misses 605,431
ListVsMapBenchmark.testHashMapAndLinkedList 1 iterate 602,053
ListVsMapBenchmark.testLinkedHashMap 1 hits 584,061
ListVsMapBenchmark.testLinkedHashMap 1 misses 575,984
ListVsMapBenchmark.testLinkedHashMap 1 iterate 559,167
Benchmark lookups mostly Score
ListVsMapBenchmark.testLinkedList 10 iterate 619,839
ListVsMapBenchmark.testArrayList 10 iterate 592,107
ListVsMapBenchmark.testHashMapAndLinkedList 10 iterate 543,840
ListVsMapBenchmark.testHashMapAndLinkedList 10 misses 539,055
ListVsMapBenchmark.testLinkedHashMap 10 misses 517,202
ListVsMapBenchmark.testHashMapAndLinkedList 10 hits 497,922
ListVsMapBenchmark.testLinkedHashMap 10 hits 486,810
ListVsMapBenchmark.testLinkedList 10 hits 434,664
ListVsMapBenchmark.testArrayList 10 hits 432,753
ListVsMapBenchmark.testArrayList 10 misses 400,189
ListVsMapBenchmark.testLinkedHashMap 10 iterate 391,815
ListVsMapBenchmark.testLinkedList 10 misses 362,474
Benchmark lookups mostly Score
ListVsMapBenchmark.testLinkedList 20 iterate 562,170
ListVsMapBenchmark.testArrayList 20 iterate 523,025
ListVsMapBenchmark.testHashMapAndLinkedList 20 misses 480,811
ListVsMapBenchmark.testLinkedHashMap 20 misses 466,654
ListVsMapBenchmark.testHashMapAndLinkedList 20 hits 459,350
ListVsMapBenchmark.testHashMapAndLinkedList 20 iterate 445,489
ListVsMapBenchmark.testLinkedHashMap 20 hits 430,991
ListVsMapBenchmark.testLinkedList 20 hits 386,221
ListVsMapBenchmark.testArrayList 20 hits 378,875
ListVsMapBenchmark.testLinkedHashMap 20 iterate 315,690
ListVsMapBenchmark.testArrayList 20 misses 311,092
ListVsMapBenchmark.testLinkedList 20 misses 264,095

Even more benchmark variations

Signed-off-by: Greg Wilkins <gregw@webtide.com>
@gregw
Copy link
Contributor Author

gregw commented May 22, 2019

Even more benchmark variations pushed.... much the same results

Benchmark lookups mostly Score
ListVsMapBenchmark.testLinkedList 1 iterate 806,520
ListVsMapBenchmark.testArrayList 1 iterate 803,382
ListVsMapBenchmark.testArrayList 1 misses 754,772
ListVsMapBenchmark.testArrayList 1 hits 748,242
ListVsMapBenchmark.testLinkedList 1 hits 734,596
ListVsMapBenchmark.testLinkedList 1 misses 730,694
ListVsMapBenchmark.testHashMapAndLinkedList 1 iterate 648,045
ListVsMapBenchmark.testHashMapAndLinkedList 1 misses 636,411
ListVsMapBenchmark.testHashMapAndArrayList 1 iterate 630,963
ListVsMapBenchmark.testHashMapAndArrayList 1 hits 624,361
ListVsMapBenchmark.testHashMapAndLinkedList 1 hits 620,445
ListVsMapBenchmark.testLinkedHashMap 1 hits 618,490
ListVsMapBenchmark.testLinkedHashMap 1 misses 611,833
ListVsMapBenchmark.testHashMapAndArrayList 1 misses 600,205
ListVsMapBenchmark.testLinkedHashMap 1 iterate 575,414
Benchmark lookups mostly Score
ListVsMapBenchmark.testArrayList 10 iterate 583,054
ListVsMapBenchmark.testLinkedList 10 iterate 577,826
ListVsMapBenchmark.testLinkedHashMap 10 misses 551,597
ListVsMapBenchmark.testHashMapAndLinkedList 10 misses 546,192
ListVsMapBenchmark.testHashMapAndArrayList 10 misses 536,418
ListVsMapBenchmark.testHashMapAndLinkedList 10 hits 514,586
ListVsMapBenchmark.testArrayList 10 hits 511,510
ListVsMapBenchmark.testLinkedList 10 hits 504,194
ListVsMapBenchmark.testLinkedHashMap 10 hits 503,510
ListVsMapBenchmark.testHashMapAndArrayList 10 hits 497,992
ListVsMapBenchmark.testHashMapAndArrayList 10 iterate 486,570
ListVsMapBenchmark.testHashMapAndLinkedList 10 iterate 475,631
ListVsMapBenchmark.testArrayList 10 misses 458,104
ListVsMapBenchmark.testLinkedHashMap 10 iterate 389,969
ListVsMapBenchmark.testLinkedList 10 misses 389,884
Benchmark lookups mostly Score
ListVsMapBenchmark.testLinkedHashMap 20 misses 490,900
ListVsMapBenchmark.testLinkedList 20 iterate 488,853
ListVsMapBenchmark.testHashMapAndLinkedList 20 misses 487,171
ListVsMapBenchmark.testArrayList 20 iterate 481,132
ListVsMapBenchmark.testHashMapAndArrayList 20 misses 476,313
ListVsMapBenchmark.testHashMapAndLinkedList 20 hits 470,774
ListVsMapBenchmark.testHashMapAndArrayList 20 hits 454,978
ListVsMapBenchmark.testLinkedHashMap 20 hits 453,266
ListVsMapBenchmark.testArrayList 20 hits 423,687
ListVsMapBenchmark.testLinkedList 20 hits 413,173
ListVsMapBenchmark.testHashMapAndArrayList 20 iterate 399,199
ListVsMapBenchmark.testHashMapAndLinkedList 20 iterate 393,821
ListVsMapBenchmark.testArrayList 20 misses 323,233
ListVsMapBenchmark.testLinkedHashMap 20 iterate 302,472
ListVsMapBenchmark.testLinkedList 20 misses 252,512
Benchmark lookups mostly Score
ListVsMapBenchmark.testLinkedHashMap 30 hits 449,931
ListVsMapBenchmark.testLinkedHashMap 30 misses 445,065
ListVsMapBenchmark.testHashMapAndLinkedList 30 hits 442,824
ListVsMapBenchmark.testHashMapAndLinkedList 30 misses 435,508
ListVsMapBenchmark.testHashMapAndArrayList 30 hits 432,490
ListVsMapBenchmark.testHashMapAndArrayList 30 misses 425,628
ListVsMapBenchmark.testArrayList 30 iterate 398,379
ListVsMapBenchmark.testLinkedList 30 iterate 393,477
ListVsMapBenchmark.testArrayList 30 hits 344,850
ListVsMapBenchmark.testLinkedList 30 hits 340,174
ListVsMapBenchmark.testHashMapAndLinkedList 30 iterate 338,940
ListVsMapBenchmark.testHashMapAndArrayList 30 iterate 338,281
ListVsMapBenchmark.testArrayList 30 misses 250,429
ListVsMapBenchmark.testLinkedHashMap 30 iterate 237,362
ListVsMapBenchmark.testLinkedList 30 misses 194,300

@gregw
Copy link
Contributor Author

gregw commented May 22, 2019

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.

minor cleanups

Signed-off-by: Greg Wilkins <gregw@webtide.com>
@gregw gregw marked this pull request as ready for review May 22, 2019 11:01
@gregw
Copy link
Contributor Author

gregw commented May 22, 2019

@sbordet @joakime I think this should now be merged with the benchmark and some very minor cleanups.

@joakime
Copy link
Contributor

joakime commented May 22, 2019

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.

request.add((HttpField) Content-Type: multipart/form-data;boundary=HOcm3Dk3BwxfMYOPZcSP9WhhJFjD6QX3x_yPUmfn;charset=UTF-8)
request.add((HttpField) Content-Length: 17738)
request.add((HttpField) Host: localhost:43977)
request.add((HttpField) Connection: keep-alive)
request.add((HttpField) User-Agent: Apache-HttpClient/4.5.5 (Java/1.8.0_202))
request.add((HttpField) Accept-Encoding: gzip,deflate)
request.contains((HttpHeader) Connection, (String) close)
request.get((HttpHeader) Content-Type)
request.get((HttpHeader) Content-Type)
request.get((HttpHeader) Content-Type)
request.get((HttpHeader) Content-Type)
request.get((HttpHeader) Content-Type)
request.get((String) Origin)
request.get((String) Origin)
request.get((String) Origin)
request.get((HttpHeader) Content-Type)
request.get((HttpHeader) Content-Type)
request.get((String) Origin)
request.get((String) Origin)
request.get((HttpHeader) Content-Type)
request.get((HttpHeader) Content-Type)
request.get((HttpHeader) Content-Type)
request.get((HttpHeader) Content-Type)
request.get((HttpHeader) Content-Type)
request.get((HttpHeader) Content-Type)
request.get((HttpHeader) Content-Type)
request.get((HttpHeader) Content-Type)
request.get((HttpHeader) Content-Type)
request.get((HttpHeader) Content-Type)
request.get((HttpHeader) Content-Type)
request.get((HttpHeader) Content-Type)
request.getValues((String) Accept)
request.get((HttpHeader) Content-Type)
request.get((HttpHeader) Content-Type)
request.clear()
request.clear()

request.add((HttpField) Content-Type: multipart/form-data;boundary=Qaz9Sf_8S9ESPUnVe_HxG1mFJla7fCqTkhtBR9;charset=UTF-8)
request.add((HttpField) Content-Length: 17728)
request.add((HttpField) Host: localhost:43977)
request.add((HttpField) Connection: keep-alive)
request.add((HttpField) User-Agent: Apache-HttpClient/4.5.5 (Java/1.8.0_202))
request.add((HttpField) Accept-Encoding: gzip,deflate)
request.contains((HttpHeader) Connection, (String) close)
request.get((HttpHeader) Content-Type)
request.get((HttpHeader) Content-Type)
request.getField((HttpHeader) Content-Length)
request.get((String) Content-length)
request.get((String) Origin)
request.get((String) Origin)
request.get((String) Origin)
request.get((HttpHeader) Content-Type)
request.get((HttpHeader) Content-Type)
request.get((String) Origin)
request.get((String) Origin)
request.getValues((String) Accept)
request.clear()
request.clear()

response.contains((HttpHeader) Date)
response.put((HttpField) Date: Tue, 21 May 2019 21:24:01 GMT)
response.add((HttpField) Date: Tue, 21 May 2019 21:24:01 GMT)
response.get((String) Content-Type)
response.add((String) Location, (String) http://localhost:8080/test/Arjen/logo.jpg)
response.add((HttpField) Location: http://localhost:8080/test/Arjen/logo.jpg)
response.get((String) Content-Type)
response.containsKey((String) Cache-Control)
response.size()
response.getField((int) 0)
response.getField((int) 1)
response.clear()

response.contains((HttpHeader) Date)
response.put((HttpField) Date: Tue, 21 May 2019 21:24:01 GMT)
response.add((HttpField) Date: Tue, 21 May 2019 21:24:01 GMT)
response.get((String) Content-Type)
response.add((String) Location, (String) http://localhost:8080/test/Arjen/logo.jpg)
response.add((HttpField) Location: http://localhost:8080/test/Arjen/logo.jpg)
response.get((String) Content-Type)
response.containsKey((String) Cache-Control)
response.size()
response.getField((int) 0)
response.getField((int) 1)
response.clear()

@gregw
Copy link
Contributor Author

gregw commented May 22, 2019

@joakime yes "maniacal" is a good description of that.... I hope it is not our code?
Even then it is just over 20 accesses and so just into the zone where list is a ways of being best... but at least with a multipart post, the header processing will probably down among the noise.
Although, perhaps we could specially handle a few known fields like Content-Type?

@gregw
Copy link
Contributor Author

gregw commented May 22, 2019

@joakime actually I can see some improvements we can make to our multipart handling... we get contentType multiple times!...

gregw added 3 commits May 22, 2019 14:02
minor cleanups

Signed-off-by: Greg Wilkins <gregw@webtide.com>
cacheContent type and avoid unnecessary character encoding calculations

Signed-off-by: Greg Wilkins <gregw@webtide.com>
…81-HttpFieldsOptimize

Signed-off-by: Greg Wilkins <gregw@webtide.com>
@gregw
Copy link
Contributor Author

gregw commented May 23, 2019

@sbordet @joakime nudge

updates from review

Signed-off-by: Greg Wilkins <gregw@webtide.com>
@gregw gregw requested a review from sbordet May 23, 2019 10:34
@gregw
Copy link
Contributor Author

gregw commented May 30, 2019

@sbordet is this OK now?

gregw added 2 commits May 31, 2019 13:04
updates from review

Signed-off-by: Greg Wilkins <gregw@webtide.com>
@gregw gregw requested a review from sbordet May 31, 2019 11:19
@gregw
Copy link
Contributor Author

gregw commented Jun 3, 2019

@sbordet nudge

@sbordet sbordet merged commit 5ebd6d4 into jetty-9.4.x Jun 3, 2019
@sbordet sbordet deleted the jetty-9.4.x-3681-HttpFieldsOptimize branch June 3, 2019 14:52
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

3 participants