harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Jim Yu (JIRA)" <j...@apache.org>
Subject [jira] Commented: (HARMONY-5853) [classlib][util] Performance improvement in Timer
Date Fri, 30 May 2008 10:41:45 GMT

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


Mime
View raw message