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 64174 - EditableProperties is slow
Summary: EditableProperties is slow
Status: RESOLVED FIXED
Alias: None
Product: projects
Classification: Unclassified
Component: Ant Project (show other bugs)
Version: 4.x
Hardware: All All
: P2 blocker (vote)
Assignee: Jesse Glick
URL:
Keywords: PERFORMANCE
Depends on:
Blocks:
 
Reported: 2005-09-13 05:51 UTC by Torbjorn Norbye
Modified: 2010-03-30 22:05 UTC (History)
2 users (show)

See Also:
Issue Type: DEFECT
Exception Reporter:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Torbjorn Norbye 2005-09-13 05:51:08 UTC
I've been doing some performance tuning of Creator lately, and looking
at performance hotspots on various user actions, such as project open.

I found a bottleneck in NetBeans that I think is accidental; it's
related to

ant/project/src/org/netbeans/spi/project/support/ant/EditableProperties.java

First, look at this:

    private boolean alphabetize = true; 

    ...

    /**
     * Creates empty instance which items will not be sorted by default.
     */
    public EditableProperties() {
        items = new ArrayList();
        itemIndex = new HashMap();
    }

NOTE: Even though the Javadoc for the null constructor says that the
list will NOT be sorted by default, the sorting flag (alphabetize) is
set to true. All lists are set to sort by default!

Take a look at this constructor (which I believe is the performance
culprit; I didn't have line numbers in my profiled output to
disambiguate the constructors but I do see that for most of the
calls to addItems it's coming from one of the constructors):

    /**
     * Creates new instance from an existing one.
     * @param ep an instance of EditableProperties
     */
    EditableProperties(EditableProperties ep) {
        this();
        Iterator it = ep.items.iterator();
        while (it.hasNext()) {
            Item item = (Item)it.next();
            addItem((Item)item.clone(), false);
        }
    }

Again, it will use sorting by default, and it's iteratively inserting
numbers from one list into another. If you look at addItem(), you'll
see that its sorted-insert operation is very slow - it's doing an
ArrayList search, followed by an ArrayList insert (which will on the
average cause half of the elements in the array to have to be moved).

Thus, the EditableProperties copy constructor has complexity O(n^2) !

At first I thought perhaps the behavior of sorting was accidental -
somebody left the flag on after some debugging. But I see in the CVS
checkin comment that this was done to improve VCS interaction
behaviors; presumably keeping the property lists sorted will minimize
the changes in updates in CVS.  (I'm not sure why since the hashcodes
for Strings seem stable too, but there probably are other reasons I'm
not thinking of. And in any case, an alphabetical order seems more
readable if not less diff-prone.)

So if the sorting behavior needs to be kept, there are still easy things
to do to improve the performance here.  If we except addItem() to be
called a lot (from outside of the class), then we should use a different
data storage than an ArrayList, such that it supports faster inserts.

However, if it's really only from copies (and in my scenario, that's 
what the stacktraces are telling me), then the copy constructors should
simply be rewritten.

For example, if ep (the EditableProperties object being copied) also has
the alphabetize flag set, then the properties are already sorted, so we
can simply iterate over its items ArrayList, clone each object and 
append it to our ArrayList. No need to call addItem() to do this. 
If on the other hand the EditableProperties object to be copied doesn't
have alphabetize=true, then we should copy out all its items, put them
in our ArrayList and then sort the whole array list using Collections.sort.

(And obviously, the javadoc for the constructors need to reflect what
the sorting-default is.)

(Observed in 4.1 but I see the code in 5.0 is identical.)
Comment 1 Jesse Glick 2005-09-14 00:10:59 UTC
OK, copy constructor performance should be fixable, and I will take a look at
why sorting is always on - probably a mistake at some point.
Comment 2 Antonin Nebuzelsky 2005-09-23 12:26:13 UTC
BTW, profiler shows EditableProperties.load() as a hotspot (2.5% time) during
startup with all netbeans projects open. It would be very nice to have this
method optimized.
Comment 3 Jesse Glick 2005-10-28 23:08:29 UTC
It's true that the default constructor is supposed to not sort, according to its
Javadoc. In fact it never behaved this way! I will fix it to behave according to
the Javadoc, but update clients to request sorting anyway.
Comment 4 Jesse Glick 2005-10-29 00:27:14 UTC
I will change the copy constructor to do a raw deep copy of fields rather than
inserting keys one by one. Should be faster. cloneProperties() is called
whenever you retrieve or store EP instances via AntProjectHelper, for safety
reasons, so this should improve project load time. (If it needs to be improved
more, it would be possible to use a copy-on-write strategy, but that would be
more work to do.)

Will also use a linked list for the items, which ought to make add operations
run faster. Don't know if I can speed up load(InputStream). Maybe, if it is
found to be doing something wasteful.
Comment 5 Jesse Glick 2005-10-29 05:17:24 UTC
Updating clients to explicitly ask for alphabetization:

committed   * Up-To-Date  1.14       
ant/project/src/org/netbeans/spi/project/support/ant/GeneratedFilesHelper.java
committed   * Up-To-Date  1.12       
apisupport/project/src/org/netbeans/modules/apisupport/project/suite/BrandingSupport.java
committed   * Up-To-Date  1.11       
apisupport/project/src/org/netbeans/modules/apisupport/project/universe/LocalizedBundleInfo.java
committed   * Up-To-Date  1.8        
j2ee/blueprints/src/org/netbeans/modules/j2ee/blueprints/ui/projects/J2eeSampleProjectGenerator.java
committed   * Up-To-Date  1.92       
web/project/src/org/netbeans/modules/web/project/WebProject.java
committed   * Up-To-Date  1.6        
web/project/src/org/netbeans/modules/web/project/api/WebProjectUtilities.java
Comment 6 Jesse Glick 2005-10-29 05:20:02 UTC
Fixing default constructor, and implementing described performance improvements:

committed   * Up-To-Date  1.14       
ant/project/src/org/netbeans/spi/project/support/ant/EditableProperties.java
committed   * Up-To-Date  1.13       
ant/project/test/unit/src/org/netbeans/spi/project/support/ant/EditablePropertiesTest.java

Tor, verification would be appreciated, and feel free to open additional bugs w/
patches if possible for any other problems you find.
Comment 7 Jesse Glick 2010-03-30 22:05:26 UTC
*** Bug 155856 has been marked as a duplicate of this bug. ***