EPollArrayWrapper.release should be O(N), not O(N^2)
martinrb at google.com
Tue Nov 3 14:42:06 PST 2009
This is a bug report with fix. Please review.
Synopsis: EPollArrayWrapper.release should be O(N), not O(N^2)
In a recent email, I said
"no one is really using LinkedList
in performance-sensitive production code, eh?"
That's completely false, of course.
We noticed a server spending 90% of its CPU time in LinkedList.get.
That was not really LinkedList's fault, although the changes in
6897553: LinkedList facelift
may produce marginal improvements.
The real problem is the O(N^2) traversal of the updateList in
Optimize EPollArrayWrapper.release. Make LinkedList traversal
O(N) instead of O(N*N).
I'm generally skeptical of the data structures used here, but
this change is low-hanging fruit.
I'm sure further improvements are possible.
My colleague Igor Chernychev has contributed a nice
reproduction of this performance problem,
included with the fix.
Please advise about the best home for this test,
and perhaps how to turn it into a "real" jtreg test
(which is always hard for performance tests,
and especially for those that need network resources).
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the nio-dev