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

[Martin Buchholz]

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


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

Martin



> 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