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] Created: (HARMONY-5853) [classlib][util] Performance improvement in Timer
Date Fri, 30 May 2008 09:19:45 GMT
[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.


Mime
View raw message