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.
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).
I'll certainly look into this. I recall finding similar problem (collapsed hashap) somewhere in the openide/text before, but it was fixed AFAICT.
Reassigning to new module owner mslama.
*** Bug 232205 has been marked as a duplicate of this bug. ***
*** Bug 232704 has been marked as a duplicate of this bug. ***
I would like to fix this in 8.1 since this is a serious problem in case of many registered Line objects.
*** Bug 253357 has been marked as a duplicate of this bug. ***
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.
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.
Marking this as duplicate of issue 252310. *** This bug has been marked as a duplicate of bug 252310 ***