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 90901 - Performance of Line.Set.findLine(Line line)
Summary: Performance of Line.Set.findLine(Line line)
Status: RESOLVED DUPLICATE of bug 252310
Alias: None
Product: platform
Classification: Unclassified
Component: Text (show other bugs)
Version: 6.x
Hardware: PC Linux
: P2 blocker (vote)
Assignee: issues@editor
URL:
Keywords:
: 232205 232704 253357 (view as bug list)
Depends on:
Blocks: 223634
  Show dependency tree
 
Reported: 2006-12-11 16:07 UTC by Miloslav Metelka
Modified: 2015-09-29 13:49 UTC (History)
4 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 Miloslav Metelka 2006-12-11 16:07:24 UTC
We've scanned through org.openide.text.Line sources with Honza L. and correct me
if I'm wrong but the implementation of Line.Set.findLine(Line line) is very poor
regarding performance.

findLine() impl:

            Map<Line,Reference<Line>> lines = findWeakHashMap();

            synchronized (lines) {
                Reference<Line> r = lines.get(line);
                Line in = r != null ? r.get() : null;

                if (in == null) {
                    if (line instanceof DocumentLine) {
                        ((DocumentLine) line).init();
                    }

                    lines.put(line, new WeakReference<Line>(line));
                    in = line;
                }

                return in;
            }

findWeakHashMap() uses a weak hash map field defined in Line.Set:

    private Map<Line,Reference<Line>> whm;

So far so good.
The DocumentLine impls of hashCode() and equals() however are the following:


    public int hashCode() {
        return pos.getCloneableEditorSupport().hashCode();
    }

    public boolean equals(Object o) {
        if (o instanceof DocumentLine) {
            DocumentLine dl = (DocumentLine) o;

            if (dl.pos.getCloneableEditorSupport() ==
pos.getCloneableEditorSupport()) {
                return dl.getLineNumber() == getLineNumber();
            }
        }

        return false;
    }

That's a nightmare! As the hashCode() value will be the same for all the line
instances of a particular CES, all the DLs will lay in the same bucket of the
weak hash map degrading the map into a linked list. Moreover the code of
equals() calls getLineNumber() which is a non-trivial operation with
log2(docLength) complexity.
So in average each invocation of lines.get(line) will traverse a half of the
single-used bucket's entries of n Line instances present for the document i.e.
the complexity is n / 2 * log2(docLength) for each invocation of findLine().

As DocumentLine.getLines() is public and it uses LazyLines that use findLine()
in its indexOf() implementation, the code described above is used from the
public API and it should be improved.
 IMHO at least it might use a sorted vector of lines so the complexity would be
improved to log2(n) * log2(docLength) (not assuming array relocations and moves
inside the array but these could be reduced considerably by using a list with a
gap). Moreover the comparing algorithm could compare offsets
DocumentLine.pos.getOffset() instead of translating each offset to the line
number. This could be done for almost the whole binary search until the two
elements between the searched value should reside (or already resides). Then the
line numbers of the two lines could be determined and checked whether it matches
the requested one. So the performance then would only be ~ log2(n).
Comment 1 Petr Nejedly 2006-12-11 20:50:50 UTC
I'll certainly look into this. I recall finding similar problem (collapsed
hashap) somewhere in the openide/text before, but it was fixed AFAICT.
Comment 2 Antonin Nebuzelsky 2008-04-17 15:14:47 UTC
Reassigning to new module owner mslama.
Comment 3 Miloslav Metelka 2013-08-28 08:54:11 UTC
*** Bug 232205 has been marked as a duplicate of this bug. ***
Comment 4 Miloslav Metelka 2013-08-28 14:31:02 UTC
*** Bug 232704 has been marked as a duplicate of this bug. ***
Comment 5 Miloslav Metelka 2015-08-20 13:20:52 UTC
I would like to fix this in 8.1 since this is a serious problem in case of many registered Line objects.
Comment 6 Miloslav Metelka 2015-08-20 13:23:19 UTC
*** Bug 253357 has been marked as a duplicate of this bug. ***
Comment 7 Miloslav Metelka 2015-09-15 14:54:18 UTC
Added logging for bettern analyzing of the problem.
With
-J-Dorg.openide.text.Line.level=FINE
uses of Line.Set.findWeakHashMap() (or CES.findWeakHashMap()) can be monitored.
With FINER level number of Line.equals() can be monitored too.
 Removed some extra document locking e.g. extra locking during PROCESS_POSITIONS so there's certain performance improvement.

http://hg.netbeans.org/jet-main/rev/78e5e6dffc8f

Lines get created dynamically but for regular files there's no high number of line instances and Line.equals() comparisons. However if there are many "permanent" line instances e.g. breakpoints and bookmarks for the particular file the number can greatly increase.
Still working on the final fix.
Comment 8 Quality Engineering 2015-09-16 01:26:56 UTC
Integrated into 'main-silver', will be available in build *201509160002* on http://bits.netbeans.org/dev/nightly/ (upload may still be in progress)

Changeset: http://hg.netbeans.org/main-silver/rev/78e5e6dffc8f
User: Miloslav Metelka <mmetelka@netbeans.org>
Log: #90901 - Performance of Line.Set.findLine(Line line) - added logging and removed extra locking.
Comment 9 Miloslav Metelka 2015-09-29 13:49:56 UTC
Marking this as duplicate of issue 252310.

*** This bug has been marked as a duplicate of bug 252310 ***