EPollArrayWrapper.release should be O(N), not O(N^2)

[Martin Buchholz]

Hi Alan,

This is a bug report with fix.  Please review.

webrev:
http://cr.openjdk.java.net/~martin/webrevs/openjdk7/EPollArrayWrapper.release/

Synopsis: EPollArrayWrapper.release should be O(N), not O(N^2)
Description:
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
EPollArrayWrapper.

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).

Thanks,

Martin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.openjdk.java.net/pipermail/nio-dev/attachments/20091103/00eb313b/attachment.html