This Bugzilla instance is a read-only archive of historic NetBeans bug reports. To report a bug in NetBeans please follow the project's instructions for reporting issues.

Bug 27286 - Optimize Utilities.partialSort
Summary: Optimize Utilities.partialSort
Alias: None
Product: platform
Classification: Unclassified
Component: -- Other -- (show other bugs)
Version: 3.x
Hardware: PC Linux
: P3 blocker (vote)
Assignee: Jaroslav Tulach
Depends on:
Reported: 2002-09-12 23:06 UTC by Jesse Glick
Modified: 2008-12-22 19:36 UTC (History)
0 users

See Also:
Issue Type: TASK
Exception Reporter:

Description of the algorithm to detect "strongly connected components" in the graph (czech) (138.44 KB, patch)
2003-01-09 08:49 UTC, Jaroslav Tulach
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Jesse Glick 2002-09-12 23:06:29 UTC
With a proper algorithm to get correct asymptotic
behavior. The overhead of this method becomes
noticeable (though not terribly large) with a lot
of modules: mainly due to dependency sorting.
Comment 1 Jesse Glick 2002-09-12 23:07:20 UTC
Also take a look at times for
Comment 2 Jesse Glick 2002-12-17 20:02:02 UTC
May be more than I thought before; OptIt says that this line

Object elt2 = ();

is a hot spot.
Comment 3 Jesse Glick 2002-12-18 23:25:59 UTC
committed   * Up-To-Date  1.11        core/
committed   * Up-To-Date  1.11       
committed   * Up-To-Date  1.64       
committed   * Up-To-Date  1.49       
committed   * Up-To-Date  1.17       
committed   * Up-To-Date  1.25       
committed   * Up-To-Date  1.90        openide/
committed   * Up-To-Date  1.121      
committed   * Up-To-Date  1.42       
committed   * Up-To-Date  1.60       
committed   * Up-To-Date  1.9        
committed   * Up-To-Date  1.112      
added       * Up-To-Date  1.1        
Comment 4 Jaroslav Tulach 2003-01-07 10:38:29 UTC
In topological_sort_27286 branch (branch point is BLD200301070100)
there is a bit improved version of Utilities.topologicalSort that does
cycle detection and removes the necessity for topologicalSortError
method. On the other hand it introduces new exception that is thrown
in case a cycle is detected.

Reopened to let Jesse evaluate the new version and decide whether it
is better than the original.
Comment 5 Jaroslav Tulach 2003-01-09 08:47:19 UTC
Does the silence means that the branch should be integrated? Ok, I'll
do that tomorrow.
Comment 6 Jaroslav Tulach 2003-01-09 08:49:06 UTC
Created attachment 8487 [details]
Description of the algorithm to detect "strongly connected components" in the graph (czech)
Comment 7 Jesse Glick 2003-01-09 12:26:33 UTC
Sorry, I saw your work but did not get a chance to pay more attention.
I guess it is good - briefly looked at the branch. Did not try to
understand all of TopologicalSortException in detail, but will assume
it is right - tests look good.

Missing @since on TSE.

Also need to update all core + openide clients (incl. FolderList.main
which still uses old partialSort due to richer error reporting - can
now be replaced).
Comment 8 Jaroslav Tulach 2003-01-09 16:24:46 UTC
Thanks for comments, I'll integrate it.
Comment 9 Jaroslav Tulach 2003-01-10 10:47:33 UTC
new revision: 1.95
new revision: 1.127;
new revision: 1.63
new revision: 1.2
new revision: 1.119; 
cvs diff: is a new entry, no
new revision: 1.5
new revision: 1.68
new revision: 1.53