You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by "Jim Yu (JIRA)" <ji...@apache.org> on 2008/05/30 11:19:45 UTC
[jira] Created: (HARMONY-5853) [classlib][util] Performance
improvement in Timer
[classlib][util] Performance improvement in Timer
-------------------------------------------------
Key: HARMONY-5853
URL: https://issues.apache.org/jira/browse/HARMONY-5853
Project: Harmony
Issue Type: Improvement
Components: Classlib
Affects Versions: 5.0M6
Reporter: Jim Yu
Fix For: 5.0M7
Attachments: HARMONY-5853.diff
An performance improvement in Timer by using Binary-Heap intead of Binary Search Tree to manage tasks.
The main reason is that the inner class TimerImpl of Timer will launch a separate thread for each Timer. In this thread,
it will frequently call task = tasks.minimum(), which selects a task with the minimum 'when' field value from the
task manager. At present, the task manager's data structure is a Binary Search Tree. It needs to search the tree
from the root to get the node with the minimum value. The time complexity in worst case is the height of the tree.
If we use a Binary-Heap instead to manage the tasks, the node with minimum value is always the root. The time
complexity is O(1). Moreover, the performance of Binary-Heap for node insert and remove operation is also very
fast. Though Binary Search Tree has the advantage of searching a specific node, the search operation is happened
very seldom in the thread. Therefore, Binary-Heap excels Binary Search Tree in the total performace of task management.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (HARMONY-5853) [classlib][util] Performance
improvement in Timer
Posted by "Jim Yu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5853?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jim Yu updated HARMONY-5853:
----------------------------
Attachment: HARMONY-5853.diff
> [classlib][util] Performance improvement in Timer
> -------------------------------------------------
>
> Key: HARMONY-5853
> URL: https://issues.apache.org/jira/browse/HARMONY-5853
> Project: Harmony
> Issue Type: Improvement
> Components: Classlib
> Affects Versions: 5.0M6
> Reporter: Jim Yu
> Fix For: 5.0M7
>
> Attachments: HARMONY-5853.diff
>
>
> An performance improvement in Timer by using Binary-Heap intead of Binary Search Tree to manage tasks.
> The main reason is that the inner class TimerImpl of Timer will launch a separate thread for each Timer. In this thread,
> it will frequently call task = tasks.minimum(), which selects a task with the minimum 'when' field value from the
> task manager. At present, the task manager's data structure is a Binary Search Tree. It needs to search the tree
> from the root to get the node with the minimum value. The time complexity in worst case is the height of the tree.
> If we use a Binary-Heap instead to manage the tasks, the node with minimum value is always the root. The time
> complexity is O(1). Moreover, the performance of Binary-Heap for node insert and remove operation is also very
> fast. Though Binary Search Tree has the advantage of searching a specific node, the search operation is happened
> very seldom in the thread. Therefore, Binary-Heap excels Binary Search Tree in the total performace of task management.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HARMONY-5853) [classlib][util] Performance
improvement in Timer
Posted by "Aleksey Shipilev (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5853?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12601078#action_12601078 ]
Aleksey Shipilev commented on HARMONY-5853:
-------------------------------------------
That's impressive, thanks.
> [classlib][util] Performance improvement in Timer
> -------------------------------------------------
>
> Key: HARMONY-5853
> URL: https://issues.apache.org/jira/browse/HARMONY-5853
> Project: Harmony
> Issue Type: Improvement
> Components: Classlib
> Affects Versions: 5.0M6
> Reporter: Jim Yu
> Assignee: Sean Qiu
> Fix For: 5.0M7
>
> Attachments: HARMONY-5853.diff
>
>
> An performance improvement in Timer by using Binary-Heap intead of Binary Search Tree to manage tasks.
> The main reason is that the inner class TimerImpl of Timer will launch a separate thread for each Timer. In this thread,
> it will frequently call task = tasks.minimum(), which selects a task with the minimum 'when' field value from the
> task manager. At present, the task manager's data structure is a Binary Search Tree. It needs to search the tree
> from the root to get the node with the minimum value. The time complexity in worst case is the height of the tree.
> If we use a Binary-Heap instead to manage the tasks, the node with minimum value is always the root. The time
> complexity is O(1). Moreover, the performance of Binary-Heap for node insert and remove operation is also very
> fast. Though Binary Search Tree has the advantage of searching a specific node, the search operation is happened
> very seldom in the thread. Therefore, Binary-Heap excels Binary Search Tree in the total performace of task management.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Closed: (HARMONY-5853) [classlib][util] Performance
improvement in Timer
Posted by "Jim Yu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5853?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jim Yu closed HARMONY-5853.
---------------------------
> [classlib][util] Performance improvement in Timer
> -------------------------------------------------
>
> Key: HARMONY-5853
> URL: https://issues.apache.org/jira/browse/HARMONY-5853
> Project: Harmony
> Issue Type: Improvement
> Components: Classlib
> Affects Versions: 5.0M6
> Reporter: Jim Yu
> Assignee: Sean Qiu
> Fix For: 5.0M7
>
> Attachments: HARMONY-5853.diff
>
>
> An performance improvement in Timer by using Binary-Heap intead of Binary Search Tree to manage tasks.
> The main reason is that the inner class TimerImpl of Timer will launch a separate thread for each Timer. In this thread,
> it will frequently call task = tasks.minimum(), which selects a task with the minimum 'when' field value from the
> task manager. At present, the task manager's data structure is a Binary Search Tree. It needs to search the tree
> from the root to get the node with the minimum value. The time complexity in worst case is the height of the tree.
> If we use a Binary-Heap instead to manage the tasks, the node with minimum value is always the root. The time
> complexity is O(1). Moreover, the performance of Binary-Heap for node insert and remove operation is also very
> fast. Though Binary Search Tree has the advantage of searching a specific node, the search operation is happened
> very seldom in the thread. Therefore, Binary-Heap excels Binary Search Tree in the total performace of task management.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HARMONY-5853) [classlib][util] Performance
improvement in Timer
Posted by "Aleksey Shipilev (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5853?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12601054#action_12601054 ]
Aleksey Shipilev commented on HARMONY-5853:
-------------------------------------------
Hi, Jim.
Is there any benchmark to test these claims?
> [classlib][util] Performance improvement in Timer
> -------------------------------------------------
>
> Key: HARMONY-5853
> URL: https://issues.apache.org/jira/browse/HARMONY-5853
> Project: Harmony
> Issue Type: Improvement
> Components: Classlib
> Affects Versions: 5.0M6
> Reporter: Jim Yu
> Fix For: 5.0M7
>
> Attachments: HARMONY-5853.diff
>
>
> An performance improvement in Timer by using Binary-Heap intead of Binary Search Tree to manage tasks.
> The main reason is that the inner class TimerImpl of Timer will launch a separate thread for each Timer. In this thread,
> it will frequently call task = tasks.minimum(), which selects a task with the minimum 'when' field value from the
> task manager. At present, the task manager's data structure is a Binary Search Tree. It needs to search the tree
> from the root to get the node with the minimum value. The time complexity in worst case is the height of the tree.
> If we use a Binary-Heap instead to manage the tasks, the node with minimum value is always the root. The time
> complexity is O(1). Moreover, the performance of Binary-Heap for node insert and remove operation is also very
> fast. Though Binary Search Tree has the advantage of searching a specific node, the search operation is happened
> very seldom in the thread. Therefore, Binary-Heap excels Binary Search Tree in the total performace of task management.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Assigned: (HARMONY-5853) [classlib][util] Performance
improvement in Timer
Posted by "Sean Qiu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5853?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sean Qiu reassigned HARMONY-5853:
---------------------------------
Assignee: Sean Qiu
> [classlib][util] Performance improvement in Timer
> -------------------------------------------------
>
> Key: HARMONY-5853
> URL: https://issues.apache.org/jira/browse/HARMONY-5853
> Project: Harmony
> Issue Type: Improvement
> Components: Classlib
> Affects Versions: 5.0M6
> Reporter: Jim Yu
> Assignee: Sean Qiu
> Fix For: 5.0M7
>
> Attachments: HARMONY-5853.diff
>
>
> An performance improvement in Timer by using Binary-Heap intead of Binary Search Tree to manage tasks.
> The main reason is that the inner class TimerImpl of Timer will launch a separate thread for each Timer. In this thread,
> it will frequently call task = tasks.minimum(), which selects a task with the minimum 'when' field value from the
> task manager. At present, the task manager's data structure is a Binary Search Tree. It needs to search the tree
> from the root to get the node with the minimum value. The time complexity in worst case is the height of the tree.
> If we use a Binary-Heap instead to manage the tasks, the node with minimum value is always the root. The time
> complexity is O(1). Moreover, the performance of Binary-Heap for node insert and remove operation is also very
> fast. Though Binary Search Tree has the advantage of searching a specific node, the search operation is happened
> very seldom in the thread. Therefore, Binary-Heap excels Binary Search Tree in the total performace of task management.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (HARMONY-5853) [classlib][util] Performance
improvement in Timer
Posted by "Jim Yu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5853?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12601076#action_12601076 ]
Jim Yu commented on HARMONY-5853:
---------------------------------
Hi, Aleksey:
I write a test [1] to calculate the time of scheduling the tasks. The result shows my improvement will run much faster.
Output before improvement: Total time is:13666
Output after imprevement: Total time is:219
[1]
import java.util.Timer;
import java.util.TimerTask;
public class TimerPerformance {
public static void main(String[] args){
Timer timer = new Timer();
TimerTask[] tt = new TimerTask[100000];
for (int i = 0; i < tt.length; i++) {
tt[i] = new MockTimerTask();
}
long start = System.currentTimeMillis();
for (int i = 0; i < tt.length; i++) {
timer.schedule(tt[i],i);
tt[i].cancel();
}
timer.purge();
try{
Thread.currentThread().sleep(50);
}catch(Exception e){
e.printStackTrace();
}
System.out.println("Total time is:" + (System.currentTimeMillis() - start));
}
static class MockTimerTask extends TimerTask {
@Override
public void run() {
System.out.println("running...");
}
}
}
> [classlib][util] Performance improvement in Timer
> -------------------------------------------------
>
> Key: HARMONY-5853
> URL: https://issues.apache.org/jira/browse/HARMONY-5853
> Project: Harmony
> Issue Type: Improvement
> Components: Classlib
> Affects Versions: 5.0M6
> Reporter: Jim Yu
> Assignee: Sean Qiu
> Fix For: 5.0M7
>
> Attachments: HARMONY-5853.diff
>
>
> An performance improvement in Timer by using Binary-Heap intead of Binary Search Tree to manage tasks.
> The main reason is that the inner class TimerImpl of Timer will launch a separate thread for each Timer. In this thread,
> it will frequently call task = tasks.minimum(), which selects a task with the minimum 'when' field value from the
> task manager. At present, the task manager's data structure is a Binary Search Tree. It needs to search the tree
> from the root to get the node with the minimum value. The time complexity in worst case is the height of the tree.
> If we use a Binary-Heap instead to manage the tasks, the node with minimum value is always the root. The time
> complexity is O(1). Moreover, the performance of Binary-Heap for node insert and remove operation is also very
> fast. Though Binary Search Tree has the advantage of searching a specific node, the search operation is happened
> very seldom in the thread. Therefore, Binary-Heap excels Binary Search Tree in the total performace of task management.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Resolved: (HARMONY-5853) [classlib][util] Performance
improvement in Timer
Posted by "Sean Qiu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HARMONY-5853?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sean Qiu resolved HARMONY-5853.
-------------------------------
Resolution: Fixed
Thanks very much, Jim.
Patch has been integrated at r662384, please verify if it is fixed as you expected.
> [classlib][util] Performance improvement in Timer
> -------------------------------------------------
>
> Key: HARMONY-5853
> URL: https://issues.apache.org/jira/browse/HARMONY-5853
> Project: Harmony
> Issue Type: Improvement
> Components: Classlib
> Affects Versions: 5.0M6
> Reporter: Jim Yu
> Assignee: Sean Qiu
> Fix For: 5.0M7
>
> Attachments: HARMONY-5853.diff
>
>
> An performance improvement in Timer by using Binary-Heap intead of Binary Search Tree to manage tasks.
> The main reason is that the inner class TimerImpl of Timer will launch a separate thread for each Timer. In this thread,
> it will frequently call task = tasks.minimum(), which selects a task with the minimum 'when' field value from the
> task manager. At present, the task manager's data structure is a Binary Search Tree. It needs to search the tree
> from the root to get the node with the minimum value. The time complexity in worst case is the height of the tree.
> If we use a Binary-Heap instead to manage the tasks, the node with minimum value is always the root. The time
> complexity is O(1). Moreover, the performance of Binary-Heap for node insert and remove operation is also very
> fast. Though Binary Search Tree has the advantage of searching a specific node, the search operation is happened
> very seldom in the thread. Therefore, Binary-Heap excels Binary Search Tree in the total performace of task management.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.