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

Martin Buchholz martinrb at google.com
Wed Nov 4 10:46:26 PST 2009

On Wed, Nov 4, 2009 at 00:56, Alan Bateman <Alan.Bateman at sun.com> wrote:

> Martin Buchholz wrote:
>> Hi Alan,
>> This is a bug report with fix.  Please review.
>> webrev:
>> http://cr.openjdk.java.net/~martin/webrevs/openjdk7/EPollArrayWrapper.release/<http://cr.openjdk.java.net/%7Emartin/webrevs/openjdk7/EPollArrayWrapper.release/><
>> http://cr.openjdk.java.net/%7Emartin/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.
> Thanks (Igor) for finding this. It slipped in with the changes for the
> complex issue that is 6693490. That fix isn't in any of Sun's production
> releases yet so that may, at least partially, explain why we haven't seen
> this before. Also, the pending update list isn't usually too long (depends
> on how the Selector is used of course) so it is possible this performance
> issue could have lurked for a long time.
> The short-term fix looks good to me and I've created this bug:
>  6897993: (se) Close or cancel performance issue when number of pending
> updates is high (lnx)
OK, I've renamed ExpensiveCancel to LotsOfCancels and regenerated the

> I'll also look to replace the list in milestone 6 as the close/cancel
> shouldn't be O(N).

We were thinking along those lines as well.
Perhaps a concurrent data structure could be used here as well?
I think Google engineers will help review.


> The test case looks very useful - maybe we should rename it to
> LotsOfCancels to be consistent with the naming of the other LotsOf* tests. I
> don't think it would be easy to turn this into a reliable jtreg test but I'd
> like to see it in the test suite for manual usage - I think you've done that
> in other places too.
> -Alan.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.openjdk.java.net/pipermail/nio-dev/attachments/20091104/b30f2977/attachment.html 

More information about the nio-dev mailing list