UI freeze when saving big file after find replace

[trancexpress]

To reproduce:

1. Generate a source file with: GenerateJava.zip
2. Copy it to a new Java project with default settings.
3. Find-replace in the file, replace "= 42" with "= 43" (this takes a while, another bug to report).
4. Save the file, this freezes the UI for about a minute (on a HP Z640 workstation).

[trancexpress]

I found 2 issues here:

1. SemanticHighlightingReconciler has hints about using a binary search in addPosition() and retainPositions() - those 2 methods will make work in a background thread run for a while. But its background work, its long but it doesn't block the UI.
2. SemanticHighlightingPresenterCore.update() is called once for every replacement. Within, it iterates over event.getDocument().getPositions(fCategory), for category SemanticHighlightingPresenterCore. There are many positions in this set (also linear to the amount of inner classes generated for the reproduction snippet). So this results in quadratic complexity, for that particular input snippet.

[trancexpress]

The binary search comments can be realized by something like this:

diff --git a/org.eclipse.jdt.ui/ui/org/eclipse/jdt/internal/ui/javaeditor/SemanticHighlightingReconciler.java b/org.eclipse.jdt.ui/ui/org/eclipse/jdt/internal/ui/javaeditor/SemanticHighlightingReconciler.java
index 72880716f8..b37468d960 100644
--- a/org.eclipse.jdt.ui/ui/org/eclipse/jdt/internal/ui/javaeditor/SemanticHighlightingReconciler.java
+++ b/org.eclipse.jdt.ui/ui/org/eclipse/jdt/internal/ui/javaeditor/SemanticHighlightingReconciler.java
@@ -15,6 +15,7 @@
 package org.eclipse.jdt.internal.ui.javaeditor;
 
 import java.util.ArrayList;
+import java.util.Collections;
 import java.util.List;
 
 import org.eclipse.swt.widgets.Display;
@@ -265,15 +266,37 @@ public class SemanticHighlightingReconciler implements IJavaReconcilingListener,
                private void addPosition(int offset, int length, Highlighting highlighting) {
                        boolean isExisting= false;
                        // TODO: use binary search
-                       for (int i= 0, n= fRemovedPositions.size(); i < n; i++) {
-                               HighlightedPosition position= (HighlightedPosition) fRemovedPositions.get(i);
-                               if (position == null)
-                                       continue;
-                               if (position.isEqual(offset, length, highlighting)) {
-                                       isExisting= true;
-                                       fRemovedPositions.set(i, null);
-                                       fNOfRemovedPositions--;
-                                       break;
+                       if (!fOffsetIndices.isEmpty()) {
+                               boolean oob = false;
+                               if (offset < fOffsetIndices.get(0).offset) {
+                                       oob = true;
+                               } else if (offset > fOffsetIndices.get(fOffsetIndices.size() - 1).offset) {
+                                       oob = true;
+                               }
+                               if (!oob) {
+                                       int startIndex = Collections.binarySearch(fOffsetIndices, Integer.valueOf(offset));
+                                       startIndex = Math.max(startIndex, 0);
+                                       startIndex = Math.min(startIndex, fRemovedPositions.size());
+                                       int endIndex = Collections.binarySearch(fOffsetIndices, Integer.valueOf(offset + 1));
+                                       startIndex = Math.max(endIndex, 0);
+                                       startIndex = Math.min(endIndex, fRemovedPositions.size());
+//                                     System.out.println("addPosition() searching in interval: [" + startIndex + ", " + fRemovedPositions.size() + ")"); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
+//                                     System.out.println("offset=" + offset + ", fOffsetIndices first=" + fOffsetIndices.get(0) + ", fOffsetIndices last=" + fOffsetIndices.get(fOffsetIndices.size() - 1)); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
+
+                                       for (int i= startIndex, n= endIndex; i < n; i++) {
+                                               HighlightedPosition position= (HighlightedPosition) fRemovedPositions.get(i);
+                                               if (position == null)
+                                                       continue;
+                                               if (position.offset > offset) {
+                                                       break;
+                                               }
+                                               if (position.isEqual(offset, length, highlighting)) {
+                                                       isExisting= true;
+                                                       fRemovedPositions.set(i, null);
+                                                       fNOfRemovedPositions--;
+                                                       break;
+                                               }
+                                       }
                                }
                        }
 
@@ -291,11 +314,26 @@ public class SemanticHighlightingReconciler implements IJavaReconcilingListener,
                @Override
                protected void retainPositions(int offset, int length) {
                        // TODO: use binary search
-                       for (int i= 0, n= fRemovedPositions.size(); i < n; i++) {
-                               HighlightedPosition position= (HighlightedPosition) fRemovedPositions.get(i);
-                               if (position != null && position.isContained(offset, length)) {
-                                       fRemovedPositions.set(i, null);
-                                       fNOfRemovedPositions--;
+                       if (!fOffsetIndices.isEmpty()) {
+                               boolean oob = false;
+                               if (offset + length < fOffsetIndices.get(0).offset) {
+                                       oob = true;
+                               } else if (offset > fOffsetIndices.get(fOffsetIndices.size() - 1).bound()) {
+                                       oob = true;
+                               }
+                               if (!oob) {
+                                       int endIndex = Collections.binarySearch(fOffsetIndices, Integer.valueOf(offset + length + 1));
+                                       endIndex = Math.max(endIndex, 0);
+                                       endIndex = Math.min(endIndex, fRemovedPositions.size());
+//                                     System.out.println("retainPositions() searching in interval: [" + 0 + ", " + endIndex + "), fRemovedPositions.size()=" + fRemovedPositions.size()); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
+//                                     System.out.println("offset=" + offset + ", fOffsetIndices first=" + fOffsetIndices.get(0) + ", fOffsetIndices last=" + fOffsetIndices.get(fOffsetIndices.size() - 1)); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
+                                       for (int i= 0, n= endIndex; i < n; i++) {
+                                               HighlightedPosition position= (HighlightedPosition) fRemovedPositions.get(i);
+                                               if (position != null && position.isContained(offset, length)) {
+                                                       fRemovedPositions.set(i, null);
+                                                       fNOfRemovedPositions--;
+                                               }
+                                       }
                                }
                        }
                }
@@ -339,8 +377,16 @@ public class SemanticHighlightingReconciler implements IJavaReconcilingListener,
 
        /** Background job's added highlighted positions */
        private List<Position> fAddedPositions= new ArrayList<>();
-       /** Background job's removed highlighted positions */
+       /** Background job's removed highlighted positions, sorted by offset */
        private List<Position> fRemovedPositions= new ArrayList<>();
+
+       private record OffsetIndex(int offset, int index, int length) implements Comparable<Integer> {
+               int bound() { return offset + length; }
+               @Override
+               public int compareTo(Integer o) { return Integer.compare(offset, o.intValue()); }
+       }
+       private List<OffsetIndex> fOffsetIndices = new ArrayList<>();
+
        /** Number of removed positions */
        private int fNOfRemovedPositions;
 
@@ -456,7 +502,17 @@ public class SemanticHighlightingReconciler implements IJavaReconcilingListener,
         * Start reconciling positions.
         */
        private void startReconcilingPositions() {
-               fJobPresenter.addAllPositions(fRemovedPositions);
+               fOffsetIndices.clear();
+               List<Position> positions = new ArrayList<>();
+               fJobPresenter.addAllPositions(positions);
+               Collections.sort(positions, (p1, p2) -> Integer.compare(p1.offset, p2.offset));
+               // go backward to overwrite indices for positions with equal offsets
+               for (int i = 0; i < positions.size(); ++i) {
+                       Position position = positions.get(i);
+                       fOffsetIndices.add(new OffsetIndex(Integer.valueOf(position.offset), i, Integer.valueOf(position.length)));
+               }
+               fRemovedPositions = positions;
+
                fNOfRemovedPositions= fRemovedPositions.size();
        }
 
@@ -523,6 +579,7 @@ public class SemanticHighlightingReconciler implements IJavaReconcilingListener,
         */
        private void stopReconcilingPositions() {
                fRemovedPositions.clear();
+               fOffsetIndices.clear();
                fNOfRemovedPositions= 0;
                fAddedPositions.clear();
        }

That doesn't fix the problem though (since its background work).

The retain method will need another array to speed it up, with different contents. Since the background work is fast already with this change, its probably not needed to do more there.

[trancexpress]

To clarify, I was using the find-replace dialog. Not the new overlay.

[fedejeanne]

I was also able to see the poor performance when using the new F&R overlay.

I don't see the same methods you mentioned but it's probably the same root cause:

[christianstaib]

Hi @trancexpress,

Thank you for your report.

@jannisCode and I have been looking into the issue but so far were unable to reproduce the UI freeze when saving the changed file. However, we experienced a UI freeze when replacing a lot of text and are currently trying to triangulate the problem and look into potential solutions.

Regarding the UI freeze when saving, could you please provide the Eclipse error log for it?

BR
Christian

[trancexpress]

Here is a log file from a freeze: log_gh1575.txt

[jukzi]

1. Generate a source file with: GenerateJava.zip

Could you please share a reproducing javafile that compiles without error? The example given results in "Too many constants, the constant pool for LargeJavaFile would exceed 65536 entries"

[christianstaib]

@jukzi While I was not successful in reproducing the mentioned error, I reduced the number of inner classes to 20k, which was still large enough to slow the find and replace operation but gave no errors.

[trancexpress]

1. Generate a source file with: GenerateJava.zip

Could you please share a reproducing javafile that compiles without error? The example given results in "Too many constants, the constant pool for LargeJavaFile would exceed 65536 entries"

You can also generate the files in this form:

package test;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;

public class GenerateJava {

	private static final String ROOT_PATH = "/tmp/testlargefile/";

	private static final int NUMBER_OF_INNER_CLASSES = 100;

	private static final String INDENT = "    ";

	public static void main(String[] args) throws IOException {
		Path path = createFile("LargeJavaFile.java");
		writeContents(path);
	}

	private static void writeContents(Path path) throws IOException {
		try (BufferedWriter writer = createWriter(path)) {
			writeClass(writer);
		}
	}

	private static void writeClass(BufferedWriter writer) throws IOException {
		writeLine(writer, "package test;");
		writeLine(writer);
		writeLine(writer, "public class LargeJavaFile {");
		writeLine(writer);
		int depth = 1;
		int n = NUMBER_OF_INNER_CLASSES;
		double currentPercent = 0.0;
		for (int i = 0; i < n; ++i) {
			writeSubclass(writer, i, depth);
			writeLine(writer);
			if (((double) i / (double)n) * 100.0 > currentPercent) {
				currentPercent += 1.0;
				System.out.println("Progress " + (int) currentPercent + "%...");
			}
		}
		writeLine(writer, "}");
	}

	private static void writeSubclass(BufferedWriter writer, int i, int depth) throws IOException {
		writeIndentedLine(writer, "public static class InnerClass" + i + " {", depth);
		writeSubclassContents(writer, i, depth + 1);
		writeIndentedLine(writer, "} // end of InnerClass" + i, depth);
	}

	private static void writeSubclassContents(BufferedWriter writer, int i, int depth) throws IOException {
		writeIndentedLine(writer, "public int x = 42;", depth);
		writeIndentedLine(writer, depth);
		writeIndentedLine(writer, "public void helloWorld() {", depth);
		writeIndentedLine(writer, "System.out.println(\"Hello World!\");", depth + 2);
		writeIndentedLine(writer, "System.out.println(\"In class \" + " + i + " + \", x=\" + x);", depth + 2);
		writeIndentedLine(writer, "}", depth);
		
	}

	private static void writeIndentedLine(BufferedWriter writer, String line, int depth) throws IOException {
		for (int i = 0; i < depth; ++i) {
			writer.write(INDENT);
		}
		writeLine(writer, line);
	}
	
	private static void writeIndentedLine(BufferedWriter writer, int depth) throws IOException {
		for (int i = 0; i < depth; ++i) {
			writer.write(INDENT);
		}
		writeLine(writer);
	}

	private static void writeLine(BufferedWriter writer, String line) throws IOException {
		writer.write(line);
		writeLine(writer);
	}
	
	private static void writeLine(BufferedWriter writer) throws IOException {
		writer.write(System.lineSeparator());
	}

	private static BufferedWriter createWriter(Path path) throws IOException {
		return new BufferedWriter(new FileWriter(path.toFile()));
	}

	private static Path createFile(String fileName) throws IOException {
		Path root = Paths.get(ROOT_PATH);
		Path filePath = root.resolve(fileName);
		Files.deleteIfExists(filePath);
		Files.deleteIfExists(root);
		Files.createDirectories(root);
		return Files.createFile(filePath);
	}

}

I found that adding highlighting positions starts with > 100 inner classes. So when debugging, less than 100 inner classes were not useful.

Last time I tried, the problem was also more easily debugged without the errors. Though in the original case we do have errors; we care about saving not been slow also for files with errors.

[christianstaib]

Hi @trancexpress,

thank you for the Code snippet.

With my (quite powerful) machine and Eclipse version i was unable to reproduce the the UI freeze when saving after search and replace. I tried 10 000 inner classes. Can you maybe produce a visualvm snippet of the the freeze?

[trancexpress]

Hi @trancexpress,

thank you for the Code snippet.

With my (quite powerful) machine and Eclipse version i was unable to reproduce the the UI freeze when saving after search and replace. I tried 10 000 inner classes. Can you maybe produce a visualvm snippet of the the freeze?

I also can't reproduce with:

Eclipse SDK
Version: 2025-03 (4.35)
Build id: I20250213-1800

I assume the freeze was fixed then, so closing this issue.