{"action":"created","comment":{"url":"https://api.github.com/repos/netty/netty/pulls/comments/28894921","id":28894921,"diff_hunk":"@@ -377,117 +182,69 @@ public boolean containsTimeMillis(T name, long value) {\n     }\n \n     @Override\n-    public boolean contains(T name, T value, Comparator<? super T> comparator) {\n-        return contains(name, value, comparator, comparator);\n-    }\n-\n-    @Override\n-    public boolean contains(T name, T value,\n-            Comparator<? super T> keyComparator, Comparator<? super T> valueComparator) {\n-        checkNotNull(name, \"name\");\n-        checkNotNull(value, \"value\");\n-        checkNotNull(keyComparator, \"keyComparator\");\n-        checkNotNull(valueComparator, \"valueComparator\");\n-        int h = hashCodeGenerator.generateHashCode(name);\n-        int i = index(h);\n-        HeaderEntry e = entries.get(i);\n-        while (e != null) {\n-            if (e.hash == h &&\n-                    keyComparator.compare(e.name, name) == 0 &&\n-                    valueComparator.compare(e.value, value) == 0) {\n+    public boolean contains(T name, T value, Comparator<? super T> valueComparator) {\n+        List<T> values = getAll(name);\n+        for (T value0 : values) {\n+            if (valueComparator.compare(value, value0) == 0) {\n                 return true;\n             }\n-            e = e.next;\n         }\n         return false;\n     }\n \n     @Override\n-    public boolean containsObject(T name, Object value, Comparator<? super T> comparator) {\n-        return containsObject(name, value, comparator, comparator);\n-    }\n-\n-    @Override\n-    public boolean containsObject(T name, Object value, Comparator<? super T> keyComparator,\n-            Comparator<? super T> valueComparator) {\n-        return contains(\n-                name, valueConverter.convertObject(checkNotNull(value, \"value\")), keyComparator, valueComparator);\n-    }\n-\n-    @Override\n     public int size() {\n         return size;\n     }\n \n     @Override\n     public boolean isEmpty() {\n-        return head == head.after;\n+        return map.isEmpty();\n     }\n \n     @Override\n     public Set<T> names() {\n-        final Set<T> names = new TreeSet<T>(keyComparator);\n-\n-        HeaderEntry e = head.after;\n-        while (e != head) {\n-            names.add(e.name);\n-            e = e.after;\n-        }\n-\n-        return names;\n+        return Collections.unmodifiableSet(map.keySet());\n     }\n \n     @Override\n-    public List<T> namesList() {\n-        final List<T> names = new ArrayList<T>(size());\n-\n-        HeaderEntry e = head.after;\n-        while (e != head) {\n-            names.add(e.name);\n-            e = e.after;\n+    public Headers<T> add(T name, T value) {\n+        validateName(name);\n+        Object prevValue = map.put(name, value);\n+        size += 1;","path":"codec/src/main/java/io/netty/handler/codec/DefaultHeaders.java","position":431,"original_position":431,"commit_id":"f16680f86c8b88c487078f7151de091cf8d55f8f","original_commit_id":"f16680f86c8b88c487078f7151de091cf8d55f8f","user":{"login":"Scottmitch","id":7562868,"avatar_url":"https://avatars.githubusercontent.com/u/7562868?v=3","gravatar_id":"","url":"https://api.github.com/users/Scottmitch","html_url":"https://github.com/Scottmitch","followers_url":"https://api.github.com/users/Scottmitch/followers","following_url":"https://api.github.com/users/Scottmitch/following{/other_user}","gists_url":"https://api.github.com/users/Scottmitch/gists{/gist_id}","starred_url":"https://api.github.com/users/Scottmitch/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Scottmitch/subscriptions","organizations_url":"https://api.github.com/users/Scottmitch/orgs","repos_url":"https://api.github.com/users/Scottmitch/repos","events_url":"https://api.github.com/users/Scottmitch/events{/privacy}","received_events_url":"https://api.github.com/users/Scottmitch/received_events","type":"User","site_admin":false},"body":"`++size`?","created_at":"2015-04-22T17:24:40Z","updated_at":"2015-04-22T17:24:40Z","html_url":"https://github.com/netty/netty/pull/3681#discussion_r28894921","pull_request_url":"https://api.github.com/repos/netty/netty/pulls/3681","_links":{"self":{"href":"https://api.github.com/repos/netty/netty/pulls/comments/28894921"},"html":{"href":"https://github.com/netty/netty/pull/3681#discussion_r28894921"},"pull_request":{"href":"https://api.github.com/repos/netty/netty/pulls/3681"}}},"pull_request":{"url":"https://api.github.com/repos/netty/netty/pulls/3681","id":33792930,"html_url":"https://github.com/netty/netty/pull/3681","diff_url":"https://github.com/netty/netty/pull/3681.diff","patch_url":"https://github.com/netty/netty/pull/3681.patch","issue_url":"https://api.github.com/repos/netty/netty/issues/3681","number":3681,"state":"open","locked":false,"title":"Faster and more memory efficient headers for HTTP, HTTP/2 ...","user":{"login":"buchgr","id":1388179,"avatar_url":"https://avatars.githubusercontent.com/u/1388179?v=3","gravatar_id":"","url":"https://api.github.com/users/buchgr","html_url":"https://github.com/buchgr","followers_url":"https://api.github.com/users/buchgr/followers","following_url":"https://api.github.com/users/buchgr/following{/other_user}","gists_url":"https://api.github.com/users/buchgr/gists{/gist_id}","starred_url":"https://api.github.com/users/buchgr/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/buchgr/subscriptions","organizations_url":"https://api.github.com/users/buchgr/orgs","repos_url":"https://api.github.com/users/buchgr/repos","events_url":"https://api.github.com/users/buchgr/events{/privacy}","received_events_url":"https://api.github.com/users/buchgr/received_events","type":"User","site_admin":false},"body":"TL;DR;\r\nJust take a look at https://docs.google.com/spreadsheets/d/1ck3RQklyzEcCLlyJoqDXPCWRGVUuS-ArZf0etSXLVDQ/edit#gid=0 for perf comparison.\r\n\r\nMotivation:\r\n\r\nI noticed that the headers implementation in Netty for HTTP/2 uses quite a lot of memory\r\nand that also at least the performance of randomly accessing a header is quite poor. The main\r\nconcern however was memory usage, as profiling has shown that a DefaultHttp2Headers\r\nnot only use a lot of memory it also wastes a lot due to the underlying hashmaps having\r\nto be resized potentially several times as new headers are being inserted.\r\n\r\nThis is tracked as issue #3600.\r\n\r\nModifications:\r\n\r\nI started out doing some research regarding possible implementations and my first idea\r\nwas to simply implement the headers using two Object[], one for the names and one for\r\nthe values as well as an int[] to cache the hashcode. That way iteration and insertion\r\nwould be blazingly fast, while random access would be O(n). Surprisingly, this\r\nimplementation outperformed the current implementation even for random access up to a\r\nsize of roughly 32 header entries. However, after the IntObjectHashMap got a massive\r\nperformance improvement by @nmittler (#3627), random access performance was not\r\ncompetitive anymore and so I looked for alternatives.\r\n\r\nI was looking for a solution with decent memory usage, competitive performance and low\r\ncomplexity. That's how I arrived at the current implementation.\r\n\r\nI redesigned the DefaultHeaders to simply take a Map object in its constructor and\r\nreimplemented the class using only the Map primitives. That way the implementation\r\nis very concise and hopefully easy to understand and it allows each concrete headers\r\nimplementation to provide its own map or to even use a different headers implementation\r\nfor processing requests and writing responses i.e. incoming headers need to provide\r\nfast random access while outgoing headers need fast insertion and fast iteration. The\r\nnew implementation can support this with hardly any code changes i.e. provide\r\nDefaultHttpHeaders backed by a HashMap for incoming requests and provide ResponseHttpHeaders\r\nfor outgoing requests with a Map simply backed by an ArrayList for minimal memory usage\r\nand blazing fast insertion and iteration. This idea is not part of this PR though. It also comes\r\nwith the advantage that if the Netty project decides to add a third party collections library\r\nas a dependency, one can simply plug in one of those very fast and memory efficient map\r\nimplementations and get faster and smaller headers for free.\r\n\r\nFor now, I am using the JDK's TreeMap for HTTP and HTTP/2 default headers. While probably\r\nquite controversial I believe it's a decent choice for both protocols:\r\n - HTTP header names are case insensitive and the HttpHeaders interface allows them to be\r\n    used with any CharSequence e.g. AsciiString and String. In order to support this,\r\n    the current implementation uses a HashCodeGenerator and NameConverter interface,\r\n    which besides being problematic regarding the equals and hashCode() contract, is\r\n    also quite complex. A TreeMap doesn't need any of those as it can be passed a custom\r\n    Comparator. For now, I am simply using the case insensitive comparator already implemented\r\n    in AsciiString.\r\n - HTTP/2 Headers actually need to be ordered, namely all reserved header names must come\r\n    first when written on the wire. In order to support this, we currently do something like\r\n    the below before passing the headers to HPACK. In a TreeMap a small Comparator does the job.\r\n```java\r\nfor each reservedHeader in reservedHeaders\r\n  if headers.contains(reservedHeader)\r\n    write(reservedHeader)\r\nfor each header in headers:\r\n  if not reservedHeaders.contains(header):\r\n    write(header)\r\n```\r\n - When full, a HashMap needs to be resized. That means the two backing arrays have to be\r\n    thrown out, a new array must be allocated and all keys have to be rehashed. TreeMap does\r\n    not require any of this.\r\n - It has decent performance and memory usage and it's already in the JDK, we don't need to implement or\r\n    maintain it.\r\n\r\nI also added new tests, fixed (and introduced) some bugs and cleaned up the comments.\r\n\r\nResult:\r\n\r\n- Significantly fewer lines of code in the implementation. While the total commit is still\r\n  roughly 400 lines less, the actual implementation is a lot less. I just added some more\r\n  tests and microbenchmarks.\r\n\r\n- Overall performance is up. The current implementation should be significantly faster\r\n  for insertion and retrieval. However, it is slower when it comes to iteration. There is simply\r\n  no way a TreeMap can have the same iteration performance as a linked list (as used in the\r\n  current headers implementation). That's totally fine though, because when looking at the\r\n  benchmark results @ejona86 pointed out that the performance of the headers is completely\r\n  dominated by insertion, that is insertion is so significantly faster in the new implementation\r\n  that it does make up for several times the iteration speed. You can't iterate what you haven't\r\n  inserted. I am demonstrating that in this spreadsheet [1]. (Actually, iteration performance is\r\n  only down for HTTP, it's significantly improved for HTTP/2).\r\n\r\n- Memory is down. The implementation with TreeMap uses on avg ~30% less memory. It also does not\r\n  produce any garbage while being resized. In load tests for GRPC we have seen a memory reduction\r\n  of up to 1.2KB per RPC. I summarized the memory improvements in this spreadsheet [1]. The data\r\n  was generated by [2] using JOL.\r\n\r\nPS: There is still some work on the comments and the code to do, but I think the code is in good shape and ready for an initial review.\r\n\r\n[1] https://docs.google.com/spreadsheets/d/1ck3RQklyzEcCLlyJoqDXPCWRGVUuS-ArZf0etSXLVDQ/edit#gid=0\r\n[2] https://gist.github.com/buchgr/4458a8bdb51dd58c82b4","created_at":"2015-04-21T19:06:42Z","updated_at":"2015-04-22T17:24:40Z","closed_at":null,"merged_at":null,"merge_commit_sha":"0acd1b1f00fe760d21a45aa4ed438d5e05ae3b8b","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/netty/netty/pulls/3681/commits","review_comments_url":"https://api.github.com/repos/netty/netty/pulls/3681/comments","review_comment_url":"https://api.github.com/repos/netty/netty/pulls/comments{/number}","comments_url":"https://api.github.com/repos/netty/netty/issues/3681/comments","statuses_url":"https://api.github.com/repos/netty/netty/statuses/f16680f86c8b88c487078f7151de091cf8d55f8f","head":{"label":"buchgr:newheaders","ref":"newheaders","sha":"f16680f86c8b88c487078f7151de091cf8d55f8f","user":{"login":"buchgr","id":1388179,"avatar_url":"https://avatars.githubusercontent.com/u/1388179?v=3","gravatar_id":"","url":"https://api.github.com/users/buchgr","html_url":"https://github.com/buchgr","followers_url":"https://api.github.com/users/buchgr/followers","following_url":"https://api.github.com/users/buchgr/following{/other_user}","gists_url":"https://api.github.com/users/buchgr/gists{/gist_id}","starred_url":"https://api.github.com/users/buchgr/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/buchgr/subscriptions","organizations_url":"https://api.github.com/users/buchgr/orgs","repos_url":"https://api.github.com/users/buchgr/repos","events_url":"https://api.github.com/users/buchgr/events{/privacy}","received_events_url":"https://api.github.com/users/buchgr/received_events","type":"User","site_admin":false},"repo":{"id":17233219,"name":"netty","full_name":"buchgr/netty","owner":{"login":"buchgr","id":1388179,"avatar_url":"https://avatars.githubusercontent.com/u/1388179?v=3","gravatar_id":"","url":"https://api.github.com/users/buchgr","html_url":"https://github.com/buchgr","followers_url":"https://api.github.com/users/buchgr/followers","following_url":"https://api.github.com/users/buchgr/following{/other_user}","gists_url":"https://api.github.com/users/buchgr/gists{/gist_id}","starred_url":"https://api.github.com/users/buchgr/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/buchgr/subscriptions","organizations_url":"https://api.github.com/users/buchgr/orgs","repos_url":"https://api.github.com/users/buchgr/repos","events_url":"https://api.github.com/users/buchgr/events{/privacy}","received_events_url":"https://api.github.com/users/buchgr/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/buchgr/netty","description":"Netty project - an event-driven asynchronous network application framework","fork":true,"url":"https://api.github.com/repos/buchgr/netty","forks_url":"https://api.github.com/repos/buchgr/netty/forks","keys_url":"https://api.github.com/repos/buchgr/netty/keys{/key_id}","collaborators_url":"https://api.github.com/repos/buchgr/netty/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/buchgr/netty/teams","hooks_url":"https://api.github.com/repos/buchgr/netty/hooks","issue_events_url":"https://api.github.com/repos/buchgr/netty/issues/events{/number}","events_url":"https://api.github.com/repos/buchgr/netty/events","assignees_url":"https://api.github.com/repos/buchgr/netty/assignees{/user}","branches_url":"https://api.github.com/repos/buchgr/netty/branches{/branch}","tags_url":"https://api.github.com/repos/buchgr/netty/tags","blobs_url":"https://api.github.com/repos/buchgr/netty/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/buchgr/netty/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/buchgr/netty/git/refs{/sha}","trees_url":"https://api.github.com/repos/buchgr/netty/git/trees{/sha}","statuses_url":"https://api.github.com/repos/buchgr/netty/statuses/{sha}","languages_url":"https://api.github.com/repos/buchgr/netty/languages","stargazers_url":"https://api.github.com/repos/buchgr/netty/stargazers","contributors_url":"https://api.github.com/repos/buchgr/netty/contributors","subscribers_url":"https://api.github.com/repos/buchgr/netty/subscribers","subscription_url":"https://api.github.com/repos/buchgr/netty/subscription","commits_url":"https://api.github.com/repos/buchgr/netty/commits{/sha}","git_commits_url":"https://api.github.com/repos/buchgr/netty/git/commits{/sha}","comments_url":"https://api.github.com/repos/buchgr/netty/comments{/number}","issue_comment_url":"https://api.github.com/repos/buchgr/netty/issues/comments{/number}","contents_url":"https://api.github.com/repos/buchgr/netty/contents/{+path}","compare_url":"https://api.github.com/repos/buchgr/netty/compare/{base}...{head}","merges_url":"https://api.github.com/repos/buchgr/netty/merges","archive_url":"https://api.github.com/repos/buchgr/netty/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/buchgr/netty/downloads","issues_url":"https://api.github.com/repos/buchgr/netty/issues{/number}","pulls_url":"https://api.github.com/repos/buchgr/netty/pulls{/number}","milestones_url":"https://api.github.com/repos/buchgr/netty/milestones{/number}","notifications_url":"https://api.github.com/repos/buchgr/netty/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/buchgr/netty/labels{/name}","releases_url":"https://api.github.com/repos/buchgr/netty/releases{/id}","created_at":"2014-02-27T02:09:39Z","updated_at":"2015-03-10T20:55:16Z","pushed_at":"2015-04-22T06:05:00Z","git_url":"git://github.com/buchgr/netty.git","ssh_url":"git@github.com:buchgr/netty.git","clone_url":"https://github.com/buchgr/netty.git","svn_url":"https://github.com/buchgr/netty","homepage":"http://netty.io/","size":40769,"stargazers_count":1,"watchers_count":1,"language":"Java","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":2,"mirror_url":null,"open_issues_count":0,"forks":2,"open_issues":0,"watchers":1,"default_branch":"master"}},"base":{"label":"netty:master","ref":"master","sha":"ec6cd54f850638510e1fab7e15155b59afd6adf5","user":{"login":"netty","id":473791,"avatar_url":"https://avatars.githubusercontent.com/u/473791?v=3","gravatar_id":"","url":"https://api.github.com/users/netty","html_url":"https://github.com/netty","followers_url":"https://api.github.com/users/netty/followers","following_url":"https://api.github.com/users/netty/following{/other_user}","gists_url":"https://api.github.com/users/netty/gists{/gist_id}","starred_url":"https://api.github.com/users/netty/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/netty/subscriptions","organizations_url":"https://api.github.com/users/netty/orgs","repos_url":"https://api.github.com/users/netty/repos","events_url":"https://api.github.com/users/netty/events{/privacy}","received_events_url":"https://api.github.com/users/netty/received_events","type":"Organization","site_admin":false},"repo":{"id":1064563,"name":"netty","full_name":"netty/netty","owner":{"login":"netty","id":473791,"avatar_url":"https://avatars.githubusercontent.com/u/473791?v=3","gravatar_id":"","url":"https://api.github.com/users/netty","html_url":"https://github.com/netty","followers_url":"https://api.github.com/users/netty/followers","following_url":"https://api.github.com/users/netty/following{/other_user}","gists_url":"https://api.github.com/users/netty/gists{/gist_id}","starred_url":"https://api.github.com/users/netty/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/netty/subscriptions","organizations_url":"https://api.github.com/users/netty/orgs","repos_url":"https://api.github.com/users/netty/repos","events_url":"https://api.github.com/users/netty/events{/privacy}","received_events_url":"https://api.github.com/users/netty/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/netty/netty","description":"Netty project - an event-driven asynchronous network application framework","fork":false,"url":"https://api.github.com/repos/netty/netty","forks_url":"https://api.github.com/repos/netty/netty/forks","keys_url":"https://api.github.com/repos/netty/netty/keys{/key_id}","collaborators_url":"https://api.github.com/repos/netty/netty/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/netty/netty/teams","hooks_url":"https://api.github.com/repos/netty/netty/hooks","issue_events_url":"https://api.github.com/repos/netty/netty/issues/events{/number}","events_url":"https://api.github.com/repos/netty/netty/events","assignees_url":"https://api.github.com/repos/netty/netty/assignees{/user}","branches_url":"https://api.github.com/repos/netty/netty/branches{/branch}","tags_url":"https://api.github.com/repos/netty/netty/tags","blobs_url":"https://api.github.com/repos/netty/netty/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/netty/netty/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/netty/netty/git/refs{/sha}","trees_url":"https://api.github.com/repos/netty/netty/git/trees{/sha}","statuses_url":"https://api.github.com/repos/netty/netty/statuses/{sha}","languages_url":"https://api.github.com/repos/netty/netty/languages","stargazers_url":"https://api.github.com/repos/netty/netty/stargazers","contributors_url":"https://api.github.com/repos/netty/netty/contributors","subscribers_url":"https://api.github.com/repos/netty/netty/subscribers","subscription_url":"https://api.github.com/repos/netty/netty/subscription","commits_url":"https://api.github.com/repos/netty/netty/commits{/sha}","git_commits_url":"https://api.github.com/repos/netty/netty/git/commits{/sha}","comments_url":"https://api.github.com/repos/netty/netty/comments{/number}","issue_comment_url":"https://api.github.com/repos/netty/netty/issues/comments{/number}","contents_url":"https://api.github.com/repos/netty/netty/contents/{+path}","compare_url":"https://api.github.com/repos/netty/netty/compare/{base}...{head}","merges_url":"https://api.github.com/repos/netty/netty/merges","archive_url":"https://api.github.com/repos/netty/netty/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/netty/netty/downloads","issues_url":"https://api.github.com/repos/netty/netty/issues{/number}","pulls_url":"https://api.github.com/repos/netty/netty/pulls{/number}","milestones_url":"https://api.github.com/repos/netty/netty/milestones{/number}","notifications_url":"https://api.github.com/repos/netty/netty/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/netty/netty/labels{/name}","releases_url":"https://api.github.com/repos/netty/netty/releases{/id}","created_at":"2010-11-09T09:22:21Z","updated_at":"2015-04-22T13:23:21Z","pushed_at":"2015-04-22T16:36:56Z","git_url":"git://github.com/netty/netty.git","ssh_url":"git@github.com:netty/netty.git","clone_url":"https://github.com/netty/netty.git","svn_url":"https://github.com/netty/netty","homepage":"http://netty.io/","size":118443,"stargazers_count":4468,"watchers_count":4468,"language":"Java","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":2202,"mirror_url":null,"open_issues_count":261,"forks":2202,"open_issues":261,"watchers":4468,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/netty/netty/pulls/3681"},"html":{"href":"https://github.com/netty/netty/pull/3681"},"issue":{"href":"https://api.github.com/repos/netty/netty/issues/3681"},"comments":{"href":"https://api.github.com/repos/netty/netty/issues/3681/comments"},"review_comments":{"href":"https://api.github.com/repos/netty/netty/pulls/3681/comments"},"review_comment":{"href":"https://api.github.com/repos/netty/netty/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/netty/netty/pulls/3681/commits"},"statuses":{"href":"https://api.github.com/repos/netty/netty/statuses/f16680f86c8b88c487078f7151de091cf8d55f8f"}}}}