You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by "Aleksey Shipilev (JIRA)" <ji...@apache.org> on 2007/09/27 18:18:50 UTC
[jira] Created: (HARMONY-4869) [classlib][nio][performance]
Selector improvements: moving from O(n) to O(1) at Java layer
[classlib][nio][performance] Selector improvements: moving from O(n) to O(1) at Java layer
------------------------------------------------------------------------------------------
Key: HARMONY-4869
URL: https://issues.apache.org/jira/browse/HARMONY-4869
Project: Harmony
Issue Type: Improvement
Components: Classlib
Environment: all
Reporter: Aleksey Shipilev
Attachments: selectors-JL-O1.patch
Current implementation of java.nio.channels.Selector is O(n) for Selector.select() operation.
There are several causes:
1. keys is the HashSet, so we spend time on iterating over it
2. keys are iterated on every select() to prepare the readable and writable arrays for native call
This patch includes a bunch of optimizations:
1. Creates hashCode() and equals() for SelectionKeyImpl to get rid of calling _native_ identityHashCode()
2. Changes the internal representation of keys to SelectionKeyImpl[] and adds logic for on-the-fly maintenance
3. Adds on-the-fly maintenance for readable and writable arrays, making them prepared right away for every select()
4. Adds indexes for easy mapping of keys<->FD
5. Optimizes hotpath in processResults().
Keeping in mind that count(register) <= count(select), we sure that moving maintenance to register() is performance-safe.
Thus, we simplify Selector.select() from being O(n) to O(1) in the Java layer.
Overall Selector.select() call is still O(n) because of portlib and native layers - to be optimized later.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Assigned: (HARMONY-4869) [classlib][nio][performance]
Selector improvements: moving away from O(n) at Java layer, part 1
Posted by "Tim Ellison (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-4869?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tim Ellison reassigned HARMONY-4869:
------------------------------------
Assignee: Tim Ellison
> [classlib][nio][performance] Selector improvements: moving away from O(n) at Java layer, part 1
> -----------------------------------------------------------------------------------------------
>
> Key: HARMONY-4869
> URL: https://issues.apache.org/jira/browse/HARMONY-4869
> Project: Harmony
> Issue Type: Improvement
> Components: Classlib
> Environment: all
> Reporter: Aleksey Shipilev
> Assignee: Tim Ellison
> Attachments: selectors-JL-O1.patch
>
>
> Current implementation of java.nio.channels.Selector is O(n) for Selector.select() operation.
> There are several causes:
> 1. "keys" is the HashSet, so we spend time on iterating over it
> 2. "keys" are iterated on every select() to prepare the readable and writable arrays for native call
> This patch includes a bunch of optimizations:
> 1. Creates hashCode() and equals() for SelectionKeyImpl to get rid of calling _native_ identityHashCode()
> 2. Changes the internal representation of keys to SelectionKeyImpl[] and adds logic for on-the-fly maintenance
> 3. Adds on-the-fly maintenance for readable and writable arrays, making them prepared right away for every select()
> 4. Adds indexes for easy mapping "keys<->FD"
> 5. Optimizes hotpath in processResults().
> Keeping in mind that count(register) <= count(select), we sure that moving key set maintenance to register() is performance-safe.
> Thus, we simplify one part of Selector.select() call from being O(n) in the Java layer. There are also processResults() scales as O(n) and still portlib and native layers too - they're going to be optimized later too.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-4869) [classlib][nio][performance]
Selector improvements: moving away from O(n) at Java layer, part 1
Posted by "Aleksey Shipilev (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-4869?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Aleksey Shipilev updated HARMONY-4869:
--------------------------------------
Description:
Current implementation of java.nio.channels.Selector is O(n) for Selector.select() operation.
There are several causes:
1. keys is the HashSet, so we spend time on iterating over it
2. keys are iterated on every select() to prepare the readable and writable arrays for native call
This patch includes a bunch of optimizations:
1. Creates hashCode() and equals() for SelectionKeyImpl to get rid of calling _native_ identityHashCode()
2. Changes the internal representation of keys to SelectionKeyImpl[] and adds logic for on-the-fly maintenance
3. Adds on-the-fly maintenance for readable and writable arrays, making them prepared right away for every select()
4. Adds indexes for easy mapping of keys<->FD
5. Optimizes hotpath in processResults().
Keeping in mind that count(register) <= count(select), we sure that moving maintenance to register() is performance-safe.
Thus, we simplify one part Selector.select() from being O(n) in the Java layer, not saying about processResults() - to be optimized later. Overall Selector.select() call is still O(n) because of portlib and native layers - to be optimized later too.
was:
Current implementation of java.nio.channels.Selector is O(n) for Selector.select() operation.
There are several causes:
1. keys is the HashSet, so we spend time on iterating over it
2. keys are iterated on every select() to prepare the readable and writable arrays for native call
This patch includes a bunch of optimizations:
1. Creates hashCode() and equals() for SelectionKeyImpl to get rid of calling _native_ identityHashCode()
2. Changes the internal representation of keys to SelectionKeyImpl[] and adds logic for on-the-fly maintenance
3. Adds on-the-fly maintenance for readable and writable arrays, making them prepared right away for every select()
4. Adds indexes for easy mapping of keys<->FD
5. Optimizes hotpath in processResults().
Keeping in mind that count(register) <= count(select), we sure that moving maintenance to register() is performance-safe.
Thus, we simplify Selector.select() from being O(n) to O(1) in the Java layer.
Overall Selector.select() call is still O(n) because of portlib and native layers - to be optimized later.
Summary: [classlib][nio][performance] Selector improvements: moving away from O(n) at Java layer, part 1 (was: [classlib][nio][performance] Selector improvements: moving from O(n) to O(1) at Java layer)
> [classlib][nio][performance] Selector improvements: moving away from O(n) at Java layer, part 1
> -----------------------------------------------------------------------------------------------
>
> Key: HARMONY-4869
> URL: https://issues.apache.org/jira/browse/HARMONY-4869
> Project: Harmony
> Issue Type: Improvement
> Components: Classlib
> Environment: all
> Reporter: Aleksey Shipilev
> Attachments: selectors-JL-O1.patch
>
>
> Current implementation of java.nio.channels.Selector is O(n) for Selector.select() operation.
> There are several causes:
> 1. keys is the HashSet, so we spend time on iterating over it
> 2. keys are iterated on every select() to prepare the readable and writable arrays for native call
> This patch includes a bunch of optimizations:
> 1. Creates hashCode() and equals() for SelectionKeyImpl to get rid of calling _native_ identityHashCode()
> 2. Changes the internal representation of keys to SelectionKeyImpl[] and adds logic for on-the-fly maintenance
> 3. Adds on-the-fly maintenance for readable and writable arrays, making them prepared right away for every select()
> 4. Adds indexes for easy mapping of keys<->FD
> 5. Optimizes hotpath in processResults().
> Keeping in mind that count(register) <= count(select), we sure that moving maintenance to register() is performance-safe.
> Thus, we simplify one part Selector.select() from being O(n) in the Java layer, not saying about processResults() - to be optimized later. Overall Selector.select() call is still O(n) because of portlib and native layers - to be optimized later too.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Resolved: (HARMONY-4869) [classlib][nio][performance]
Selector improvements: moving away from O(n) at Java layer, part 1
Posted by "Tim Ellison (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-4869?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tim Ellison resolved HARMONY-4869.
----------------------------------
Resolution: Fixed
Thanks Aleksey.
Patch applied with minor code formatting changes(*) to NIO module at repo revision r586000.
Please check it was applied as you expected.
(*) Tabs yuk!
> [classlib][nio][performance] Selector improvements: moving away from O(n) at Java layer, part 1
> -----------------------------------------------------------------------------------------------
>
> Key: HARMONY-4869
> URL: https://issues.apache.org/jira/browse/HARMONY-4869
> Project: Harmony
> Issue Type: Improvement
> Components: Classlib
> Environment: all
> Reporter: Aleksey Shipilev
> Assignee: Tim Ellison
> Attachments: selectors-JL-O1.patch
>
>
> Current implementation of java.nio.channels.Selector is O(n) for Selector.select() operation.
> There are several causes:
> 1. "keys" is the HashSet, so we spend time on iterating over it
> 2. "keys" are iterated on every select() to prepare the readable and writable arrays for native call
> This patch includes a bunch of optimizations:
> 1. Creates hashCode() and equals() for SelectionKeyImpl to get rid of calling _native_ identityHashCode()
> 2. Changes the internal representation of keys to SelectionKeyImpl[] and adds logic for on-the-fly maintenance
> 3. Adds on-the-fly maintenance for readable and writable arrays, making them prepared right away for every select()
> 4. Adds indexes for easy mapping "keys<->FD"
> 5. Optimizes hotpath in processResults().
> Keeping in mind that count(register) <= count(select), we sure that moving key set maintenance to register() is performance-safe.
> Thus, we simplify one part of Selector.select() call from being O(n) in the Java layer. There are also processResults() scales as O(n) and still portlib and native layers too - they're going to be optimized later too.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Closed: (HARMONY-4869) [classlib][nio][performance] Selector
improvements: moving away from O(n) at Java layer, part 1
Posted by "Aleksey Shipilev (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-4869?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Aleksey Shipilev closed HARMONY-4869.
-------------------------------------
> [classlib][nio][performance] Selector improvements: moving away from O(n) at Java layer, part 1
> -----------------------------------------------------------------------------------------------
>
> Key: HARMONY-4869
> URL: https://issues.apache.org/jira/browse/HARMONY-4869
> Project: Harmony
> Issue Type: Improvement
> Components: Classlib
> Environment: all
> Reporter: Aleksey Shipilev
> Assignee: Tim Ellison
> Attachments: selectors-JL-O1.patch
>
>
> Current implementation of java.nio.channels.Selector is O(n) for Selector.select() operation.
> There are several causes:
> 1. "keys" is the HashSet, so we spend time on iterating over it
> 2. "keys" are iterated on every select() to prepare the readable and writable arrays for native call
> This patch includes a bunch of optimizations:
> 1. Creates hashCode() and equals() for SelectionKeyImpl to get rid of calling _native_ identityHashCode()
> 2. Changes the internal representation of keys to SelectionKeyImpl[] and adds logic for on-the-fly maintenance
> 3. Adds on-the-fly maintenance for readable and writable arrays, making them prepared right away for every select()
> 4. Adds indexes for easy mapping "keys<->FD"
> 5. Optimizes hotpath in processResults().
> Keeping in mind that count(register) <= count(select), we sure that moving key set maintenance to register() is performance-safe.
> Thus, we simplify one part of Selector.select() call from being O(n) in the Java layer. There are also processResults() scales as O(n) and still portlib and native layers too - they're going to be optimized later too.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-4869) [classlib][nio][performance]
Selector improvements: moving from O(n) to O(1) at Java layer
Posted by "Aleksey Shipilev (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-4869?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Aleksey Shipilev updated HARMONY-4869:
--------------------------------------
Attachment: selectors-JL-O1.patch
The patch.
> [classlib][nio][performance] Selector improvements: moving from O(n) to O(1) at Java layer
> ------------------------------------------------------------------------------------------
>
> Key: HARMONY-4869
> URL: https://issues.apache.org/jira/browse/HARMONY-4869
> Project: Harmony
> Issue Type: Improvement
> Components: Classlib
> Environment: all
> Reporter: Aleksey Shipilev
> Attachments: selectors-JL-O1.patch
>
>
> Current implementation of java.nio.channels.Selector is O(n) for Selector.select() operation.
> There are several causes:
> 1. keys is the HashSet, so we spend time on iterating over it
> 2. keys are iterated on every select() to prepare the readable and writable arrays for native call
> This patch includes a bunch of optimizations:
> 1. Creates hashCode() and equals() for SelectionKeyImpl to get rid of calling _native_ identityHashCode()
> 2. Changes the internal representation of keys to SelectionKeyImpl[] and adds logic for on-the-fly maintenance
> 3. Adds on-the-fly maintenance for readable and writable arrays, making them prepared right away for every select()
> 4. Adds indexes for easy mapping of keys<->FD
> 5. Optimizes hotpath in processResults().
> Keeping in mind that count(register) <= count(select), we sure that moving maintenance to register() is performance-safe.
> Thus, we simplify Selector.select() from being O(n) to O(1) in the Java layer.
> Overall Selector.select() call is still O(n) because of portlib and native layers - to be optimized later.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HARMONY-4869) [classlib][nio][performance]
Selector improvements: moving away from O(n) at Java layer, part 1
Posted by "Aleksey Shipilev (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-4869?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12535870 ]
Aleksey Shipilev commented on HARMONY-4869:
-------------------------------------------
On the test from HARMONY-4879 at 16x Tulsa 3.2Ghz / SLES 9.2:
Harmony-r576670-clean:
<us...@box> ~/jre-r576670-clean/bin/java -Xms512m -Xmx512m -Xem:server selectnow 2000 10000 10
Server: Opening selector
Server: Opening server
Client: 2000 connections
Client: 10000 requests
Client: 10 iterations
Client: connections established: 2000/2000
Client: all clients are connected. I go to sleep forever...
Server: all clients are connected
Server: Ready to serve
Server: iteration: 1/10 selectNow's: 10000 elapsed: 27036 millis
Server: iteration: 2/10 selectNow's: 10000 elapsed: 27027 millis
Server: iteration: 3/10 selectNow's: 10000 elapsed: 27021 millis
Server: iteration: 4/10 selectNow's: 10000 elapsed: 27177 millis
Server: iteration: 5/10 selectNow's: 10000 elapsed: 26842 millis
Server: iteration: 6/10 selectNow's: 10000 elapsed: 26855 millis
Server: iteration: 7/10 selectNow's: 10000 elapsed: 26903 millis
Server: iteration: 8/10 selectNow's: 10000 elapsed: 26896 millis
Server: iteration: 9/10 selectNow's: 10000 elapsed: 26872 millis
Server: iteration: 10/10 selectNow's: 10000 elapsed: 26892 millis
Harmony-r576670-4869:
<us...@box> ~/jre-r576670-work/bin/java -Xms512m -Xmx512m -Xem:server -cp selectnow 2000 10000 10
Server: Opening selector
Server: Opening server
Client: 2000 connections
Client: 10000 requests
Client: 10 iterations
Client: connections established: 2000/2000
Client: all clients are connected. I go to sleep forever...
Server: all clients are connected
Server: Ready to serve
Server: iteration: 1/10 selectNow's: 10000 elapsed: 13728 millis
Server: iteration: 2/10 selectNow's: 10000 elapsed: 13682 millis
Server: iteration: 3/10 selectNow's: 10000 elapsed: 13564 millis
Server: iteration: 4/10 selectNow's: 10000 elapsed: 13521 millis
Server: iteration: 5/10 selectNow's: 10000 elapsed: 13490 millis
Server: iteration: 6/10 selectNow's: 10000 elapsed: 13513 millis
Server: iteration: 7/10 selectNow's: 10000 elapsed: 13694 millis
Server: iteration: 8/10 selectNow's: 10000 elapsed: 13570 millis
Server: iteration: 9/10 selectNow's: 10000 elapsed: 13568 millis
Server: iteration: 10/10 selectNow's: 10000 elapsed: 13517 millis
Up to 2x boost.
> [classlib][nio][performance] Selector improvements: moving away from O(n) at Java layer, part 1
> -----------------------------------------------------------------------------------------------
>
> Key: HARMONY-4869
> URL: https://issues.apache.org/jira/browse/HARMONY-4869
> Project: Harmony
> Issue Type: Improvement
> Components: Classlib
> Environment: all
> Reporter: Aleksey Shipilev
> Attachments: selectors-JL-O1.patch
>
>
> Current implementation of java.nio.channels.Selector is O(n) for Selector.select() operation.
> There are several causes:
> 1. "keys" is the HashSet, so we spend time on iterating over it
> 2. "keys" are iterated on every select() to prepare the readable and writable arrays for native call
> This patch includes a bunch of optimizations:
> 1. Creates hashCode() and equals() for SelectionKeyImpl to get rid of calling _native_ identityHashCode()
> 2. Changes the internal representation of keys to SelectionKeyImpl[] and adds logic for on-the-fly maintenance
> 3. Adds on-the-fly maintenance for readable and writable arrays, making them prepared right away for every select()
> 4. Adds indexes for easy mapping "keys<->FD"
> 5. Optimizes hotpath in processResults().
> Keeping in mind that count(register) <= count(select), we sure that moving key set maintenance to register() is performance-safe.
> Thus, we simplify one part of Selector.select() call from being O(n) in the Java layer. There are also processResults() scales as O(n) and still portlib and native layers too - they're going to be optimized later too.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HARMONY-4869) [classlib][nio][performance]
Selector improvements: moving away from O(n) at Java layer, part 1
Posted by "Aleksey Shipilev (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-4869?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12536257 ]
Aleksey Shipilev commented on HARMONY-4869:
-------------------------------------------
Thanks, Tim!
The patch is applied OK, 2.2x boost on the attached microtest achieved.
> [classlib][nio][performance] Selector improvements: moving away from O(n) at Java layer, part 1
> -----------------------------------------------------------------------------------------------
>
> Key: HARMONY-4869
> URL: https://issues.apache.org/jira/browse/HARMONY-4869
> Project: Harmony
> Issue Type: Improvement
> Components: Classlib
> Environment: all
> Reporter: Aleksey Shipilev
> Assignee: Tim Ellison
> Attachments: selectors-JL-O1.patch
>
>
> Current implementation of java.nio.channels.Selector is O(n) for Selector.select() operation.
> There are several causes:
> 1. "keys" is the HashSet, so we spend time on iterating over it
> 2. "keys" are iterated on every select() to prepare the readable and writable arrays for native call
> This patch includes a bunch of optimizations:
> 1. Creates hashCode() and equals() for SelectionKeyImpl to get rid of calling _native_ identityHashCode()
> 2. Changes the internal representation of keys to SelectionKeyImpl[] and adds logic for on-the-fly maintenance
> 3. Adds on-the-fly maintenance for readable and writable arrays, making them prepared right away for every select()
> 4. Adds indexes for easy mapping "keys<->FD"
> 5. Optimizes hotpath in processResults().
> Keeping in mind that count(register) <= count(select), we sure that moving key set maintenance to register() is performance-safe.
> Thus, we simplify one part of Selector.select() call from being O(n) in the Java layer. There are also processResults() scales as O(n) and still portlib and native layers too - they're going to be optimized later too.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-4869) [classlib][nio][performance]
Selector improvements: moving away from O(n) at Java layer, part 1
Posted by "Aleksey Shipilev (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-4869?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Aleksey Shipilev updated HARMONY-4869:
--------------------------------------
Description:
Current implementation of java.nio.channels.Selector is O(n) for Selector.select() operation.
There are several causes:
1. "keys" is the HashSet, so we spend time on iterating over it
2. "keys" are iterated on every select() to prepare the readable and writable arrays for native call
This patch includes a bunch of optimizations:
1. Creates hashCode() and equals() for SelectionKeyImpl to get rid of calling _native_ identityHashCode()
2. Changes the internal representation of keys to SelectionKeyImpl[] and adds logic for on-the-fly maintenance
3. Adds on-the-fly maintenance for readable and writable arrays, making them prepared right away for every select()
4. Adds indexes for easy mapping "keys<->FD"
5. Optimizes hotpath in processResults().
Keeping in mind that count(register) <= count(select), we sure that moving key set maintenance to register() is performance-safe.
Thus, we simplify one part of Selector.select() call from being O(n) in the Java layer. There are also processResults() scales as O(n) and still portlib and native layers too - they're going to be optimized later too.
was:
Current implementation of java.nio.channels.Selector is O(n) for Selector.select() operation.
There are several causes:
1. keys is the HashSet, so we spend time on iterating over it
2. keys are iterated on every select() to prepare the readable and writable arrays for native call
This patch includes a bunch of optimizations:
1. Creates hashCode() and equals() for SelectionKeyImpl to get rid of calling _native_ identityHashCode()
2. Changes the internal representation of keys to SelectionKeyImpl[] and adds logic for on-the-fly maintenance
3. Adds on-the-fly maintenance for readable and writable arrays, making them prepared right away for every select()
4. Adds indexes for easy mapping of keys<->FD
5. Optimizes hotpath in processResults().
Keeping in mind that count(register) <= count(select), we sure that moving maintenance to register() is performance-safe.
Thus, we simplify one part Selector.select() from being O(n) in the Java layer, not saying about processResults() - to be optimized later. Overall Selector.select() call is still O(n) because of portlib and native layers - to be optimized later too.
> [classlib][nio][performance] Selector improvements: moving away from O(n) at Java layer, part 1
> -----------------------------------------------------------------------------------------------
>
> Key: HARMONY-4869
> URL: https://issues.apache.org/jira/browse/HARMONY-4869
> Project: Harmony
> Issue Type: Improvement
> Components: Classlib
> Environment: all
> Reporter: Aleksey Shipilev
> Attachments: selectors-JL-O1.patch
>
>
> Current implementation of java.nio.channels.Selector is O(n) for Selector.select() operation.
> There are several causes:
> 1. "keys" is the HashSet, so we spend time on iterating over it
> 2. "keys" are iterated on every select() to prepare the readable and writable arrays for native call
> This patch includes a bunch of optimizations:
> 1. Creates hashCode() and equals() for SelectionKeyImpl to get rid of calling _native_ identityHashCode()
> 2. Changes the internal representation of keys to SelectionKeyImpl[] and adds logic for on-the-fly maintenance
> 3. Adds on-the-fly maintenance for readable and writable arrays, making them prepared right away for every select()
> 4. Adds indexes for easy mapping "keys<->FD"
> 5. Optimizes hotpath in processResults().
> Keeping in mind that count(register) <= count(select), we sure that moving key set maintenance to register() is performance-safe.
> Thus, we simplify one part of Selector.select() call from being O(n) in the Java layer. There are also processResults() scales as O(n) and still portlib and native layers too - they're going to be optimized later too.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.