Bug 545491 - Improved performance of ReferenceCollectionI20190422-1800I20190421-1800

The implementation of reference collection suffered from a couple
of quadratic lookup operations in its logic to determine, whether
the collection includes certain names.

Instead of doing a simple nested loop scanning of the given arrays,
we apply an algorithm based on the reduced runtime complexity of
binary searches.

The reference collections are long living objects that are far more
often queried than modified. Now we use a simple comparator to sort the
arrays by length and content. When the collection is asked whether it
contains another list of names, these names have to be interned. In
addition to the interning, we also sort the argument arrays. Now we
do have a total of three pairs of arrays, each of the paired arrays is
sorted by the same criteria. That allows to walk both arrays pairways
so even if the worst case, we do no longer need O(n*m) with
n=first.length and m = second.length, but only O(2*(n+m)) comparisons.
For longer arrays, we even use binary search logic to skip more than
one array index when we advance the iteration.

In our scenario, this reduced the accumulated time for invocations of
include from 90s to less than one second.

Change-Id: Ib35b4250ab34fbab55723ebe1f9ad345afca86dd
Signed-off-by: Sebastian Zarnekow <sebastian.zarnekow@gmail.com>
Signed-off-by: Andrey Loskutov <loskutov@gmx.de>

5 files changed, 612 insertions, 104 deletions

diff --git a/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/BuilderTests.java b/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/BuilderTests.java
index dd134b94dd..41bd69c710 100644
--- a/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/BuilderTests.java
+++ b/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/BuilderTests.java
@@ -542,6 +542,7 @@ public class BuilderTests extends TestCase {
 			GetResourcesTests.class,
 			FriendDependencyTests.class,
 			ReferenceCollectionTest.class,
+			StateTest.class,
 			TestAttributeBuilderTests.class,
 			Bug530366Test.class,
 			Bug531382Test.class,
diff --git a/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/ReferenceCollectionTest.java b/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/ReferenceCollectionTest.java
index 2cfbb371fb..c60d73f6b7 100644
--- a/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/ReferenceCollectionTest.java
+++ b/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/ReferenceCollectionTest.java
@@ -1,5 +1,5 @@
 /*******************************************************************************
- * Copyright (c) 2000, 2015 IBM Corporation and others.
+ * Copyright (c) 2019 Sebastian Zarnekow and others.
  *
  * This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License 2.0
@@ -9,7 +9,7 @@
  * SPDX-License-Identifier: EPL-2.0
  *
  * Contributors:
- *     IBM Corporation - initial API and implementation
+ *     Sebastian Zarnekow - initial API and implementation
  *******************************************************************************/
 package org.eclipse.jdt.core.tests.builder;
 
@@ -77,8 +77,7 @@ public class ReferenceCollectionTest extends BuilderTests {
 		}
 	}
 
-	// Disabled due bug 545491 comment 15
-	public void XtestInternQualifiedNamesSorts_01() {
+	public void testInternQualifiedNamesSorts_01() {
 		char[][][] qualifiedNames = new char[][][] {
 			CharOperation.splitOn('.', "java.lang.RuntimeException".toCharArray()),
 			CharOperation.splitOn('.', "a.a.a".toCharArray()),
@@ -97,8 +96,7 @@ public class ReferenceCollectionTest extends BuilderTests {
 				toStringArray(internQualifiedNames));
 	}
 
-	// Disabled due bug 545491 comment 15
-	public void XtestInternQualifiedNamesSorts_02() {
+	public void testInternQualifiedNamesSorts_02() {
 		char[][][] qualifiedNames = new char[][][] {
 			CharOperation.splitOn('.', "java.lang.RuntimeException".toCharArray()),
 			CharOperation.splitOn('.', "a.a.a".toCharArray()),
@@ -124,8 +122,7 @@ public class ReferenceCollectionTest extends BuilderTests {
 				toStringArray(internQualifiedNames));
 	}
 
-	// Disabled due bug 545491 comment 15
-	public void XtestInternSimpleNamesSorts_01() {
+	public void testInternSimpleNamesSorts_01() {
 		char[][] simpleNames = new char[][] {
 			"Throwable".toCharArray(),
 			"aaa".toCharArray(),
@@ -142,8 +139,7 @@ public class ReferenceCollectionTest extends BuilderTests {
 				toStringArray(internSimpleNames));
 	}
 
-	// Disabled due bug 545491 comment 15
-	public void XtestInternSimpleNamesSorts_02() {
+	public void testInternSimpleNamesSorts_02() {
 		char[][] simpleNames = new char[][] {
 			"aaa".toCharArray(),
 			"bbb".toCharArray(),
@@ -291,8 +287,7 @@ public class ReferenceCollectionTest extends BuilderTests {
 		assertFalse(other.includes(refColl.getQualifiedNameReferences(), refColl.getSimpleNameReferences(), refColl.getRootReferences()));
 	}
 
-	// Disabled due bug 545491 comment 15
-	public void XtestAddDependencies() {
+	public void testAddDependencies() {
 		TestableReferenceCollection refColl = new TestableReferenceCollection(null, null, null);
 
 		String[] array = new String[] {"a.b.c.D"};
diff --git a/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/StateTest.java b/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/StateTest.java
new file mode 100644
index 0000000000..e33bc200fd
--- /dev/null
+++ b/org.eclipse.jdt.core.tests.builder/src/org/eclipse/jdt/core/tests/builder/StateTest.java
@@ -0,0 +1,175 @@
+/*******************************************************************************
+ * Copyright (c) 2019 Sebastian Zarnekow and others.
+ *
+ * This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License 2.0
+ * which accompanies this distribution, and is available at
+ * https://www.eclipse.org/legal/epl-2.0/
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ *
+ * Contributors:
+ *     Sebastian Zarnekow - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.jdt.core.tests.builder;
+
+import static org.junit.Assert.assertArrayEquals;
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.lang.reflect.Field;
+import java.util.Arrays;
+
+import org.eclipse.core.resources.IProject;
+import org.eclipse.core.runtime.CoreException;
+import org.eclipse.core.runtime.IPath;
+import org.eclipse.jdt.core.JavaModelException;
+import org.eclipse.jdt.core.compiler.CharOperation;
+import org.eclipse.jdt.core.tests.util.Util;
+import org.eclipse.jdt.internal.compiler.util.SimpleLookupTable;
+import org.eclipse.jdt.internal.core.JavaModelManager;
+import org.eclipse.jdt.internal.core.JavaModelManager.PerProjectInfo;
+import org.eclipse.jdt.internal.core.builder.JavaBuilder;
+import org.eclipse.jdt.internal.core.builder.ReferenceCollection;
+import org.eclipse.jdt.internal.core.builder.State;
+
+import junit.framework.Test;
+
+public class StateTest extends BuilderTests {
+
+	public StateTest(String name) {
+		super(name);
+	}
+
+	public static Test suite() {
+		return buildTestSuite(StateTest.class);
+	}
+
+	public void testWriteAndReadState() throws JavaModelException, Exception {
+		IPath interfaceProjectPath = env.addProject("Interface"); //$NON-NLS-1$
+		env.addExternalJars(interfaceProjectPath, Util.getJavaClassLibs());
+
+		IPath implementationProjectPath = env.addProject("Implementation"); //$NON-NLS-1$
+		env.addExternalJars(implementationProjectPath, Util.getJavaClassLibs());
+		env.addClassFolder(implementationProjectPath, interfaceProjectPath, false);
+
+		env.addClass(interfaceProjectPath, "a", "Interfaze", //$NON-NLS-1$ //$NON-NLS-2$
+			"package a;\n" +
+			"public interface Interfaze {\n" +
+			"	void callMe();\n" +
+			"}" //$NON-NLS-1$
+		);
+
+		env.addClass(interfaceProjectPath, "c", "Impl1", //$NON-NLS-1$ //$NON-NLS-2$
+			"package c;\n" +
+			"import a.Interfaze;\n" +
+			"public class Impl1 implements Interfaze {\n" +
+			"	@Override\n" +
+			"	public void callMe() {\n" +
+			"	}\n" +
+			"}"
+		);
+
+		env.addClass(implementationProjectPath, "b", "Impl2", //$NON-NLS-1$ //$NON-NLS-2$
+				"package b;\n" +
+				"import a.Interfaze;\n" +
+				"public class Impl2 implements Interfaze {\n" +
+				"	@Override\n" +
+				"	public void callMe() {\n" +
+				"	}\n" +
+				"}" //$NON-NLS-1$
+			);
+		fullBuild();
+
+		writeReadAndCompareReferences(interfaceProjectPath);
+		writeReadAndCompareReferences(implementationProjectPath);
+	}
+
+	private void writeReadAndCompareReferences(IPath projectPath)
+			throws JavaModelException, IOException, CoreException {
+		JavaModelManager javaModelManager = JavaModelManager.getJavaModelManager();
+		IProject project = env.getProject(projectPath);
+		PerProjectInfo info = javaModelManager.getPerProjectInfoCheckExistence(project);
+		ByteArrayOutputStream outputStream = new ByteArrayOutputStream();
+		State savedState = (State) info.savedState;
+		JavaBuilder.writeState(savedState, new DataOutputStream(outputStream));
+		byte[] bytes = outputStream.toByteArray();
+		State readState = JavaBuilder.readState(project, new DataInputStream(new ByteArrayInputStream(bytes)));
+		SimpleLookupTable readReferences = readState.getReferences();
+		assertEqualLookupTables(savedState.getReferences(), readReferences);
+	}
+
+	private void assertEqualLookupTables(SimpleLookupTable expectation, SimpleLookupTable actual) {
+		assertEquals(expectation.elementSize, actual.elementSize);
+		Object[] expectedKeys = expectation.keyTable;
+		for(int i = 0; i < expectedKeys.length; i++) {
+			Object key = expectedKeys[i];
+			if (key != null) {
+				ReferenceCollection actualReferenceCollection = (ReferenceCollection) actual.get(key);
+				ReferenceCollection expectedReferenceCollection = (ReferenceCollection) expectation.valueTable[i];
+				assertEqualReferenceCollections(expectedReferenceCollection, actualReferenceCollection);
+			}
+		}
+	}
+
+	private void assertEqualReferenceCollections(ReferenceCollection expectedReferenceCollection,
+			ReferenceCollection actualReferenceCollection) {
+		{
+			char[][] expected = getSimpleNameReferences(expectedReferenceCollection);
+			char[][] actual = getSimpleNameReferences(actualReferenceCollection);
+			assertArrayEquals(toStringArray(expected), toStringArray(actual));
+		}
+		{
+			char[][] expected = getRootReferences(expectedReferenceCollection);
+			char[][] actual = getRootReferences(actualReferenceCollection);
+			assertArrayEquals(toStringArray(expected), toStringArray(actual));
+		}
+		{
+			char[][][] expected = getQualifiedNameReferences(expectedReferenceCollection);
+			char[][][] actual = getQualifiedNameReferences(actualReferenceCollection);
+			assertArrayEquals(toStringArray(expected), toStringArray(actual));
+		}
+	}
+
+	private static String[] toStringArray(char[][][] qualifiedNameReferences) {
+		return Arrays.stream(qualifiedNameReferences).map(a -> CharOperation.toString(a)).toArray(String[]::new);
+	}
+
+	private static String[] toStringArray(char[][] qualifiedNameReferences) {
+		return Arrays.stream(qualifiedNameReferences).map(a -> CharOperation.charToString(a)).toArray(String[]::new);
+	}
+
+	char[][][] getQualifiedNameReferences(ReferenceCollection collection) {
+		try {
+			Field fld = ReferenceCollection.class.getDeclaredField("qualifiedNameReferences");
+			fld.setAccessible(true);
+			return (char[][][]) fld.get(collection);
+		} catch (NoSuchFieldException | SecurityException | IllegalArgumentException | IllegalAccessException e) {
+			throw new RuntimeException(e);
+		}
+	}
+
+	char[][] getSimpleNameReferences(ReferenceCollection collection) {
+		try {
+			Field fld = ReferenceCollection.class.getDeclaredField("simpleNameReferences");
+			fld.setAccessible(true);
+			return (char[][]) fld.get(collection);
+		} catch (NoSuchFieldException | SecurityException | IllegalArgumentException | IllegalAccessException e) {
+			throw new RuntimeException(e);
+		}
+	}
+
+	char[][] getRootReferences(ReferenceCollection collection) {
+		try {
+			Field fld = ReferenceCollection.class.getDeclaredField("rootReferences");
+			fld.setAccessible(true);
+			return (char[][]) fld.get(collection);
+		} catch (NoSuchFieldException | SecurityException | IllegalArgumentException | IllegalAccessException e) {
+			throw new RuntimeException(e);
+		}
+	}
+
+}
diff --git a/org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/ReferenceCollection.java b/org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/ReferenceCollection.java
index 8b5e24646e..0b47eda2bc 100644
--- a/org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/ReferenceCollection.java
+++ b/org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/ReferenceCollection.java
@@ -11,17 +11,25 @@
  * Contributors:
  *     IBM Corporation - initial API and implementation
  *     Tim Hanson <thanson@bea.com> - fix for https://bugs.eclipse.org/bugs/show_bug.cgi?id=137634
+ *     Sebastian Zarnekow - Contribution for
+ *								Bug 545491 - Poor performance of ReferenceCollection with many source files
  *******************************************************************************/
 package org.eclipse.jdt.internal.core.builder;
 
+import java.util.Arrays;
+import java.util.Comparator;
 import java.util.Set;
+import java.util.stream.Collectors;
 
 import org.eclipse.jdt.core.compiler.CharOperation;
+import org.eclipse.jdt.internal.compiler.lookup.CompilationUnitScope;
 import org.eclipse.jdt.internal.compiler.lookup.TypeConstants;
 
 public class ReferenceCollection {
 
-char[][][] qualifiedNameReferences; // contains no simple names as in just 'a' which is kept in simpleNameReferences instead
+// contains no simple names as in just 'a' which is kept in simpleNameReferences instead
+// TODO after #addDependencies, it will contain simple names, though. See ReferenceCollectionTest
+char[][][] qualifiedNameReferences;
 char[][] simpleNameReferences;
 char[][] rootReferences;
 
@@ -31,51 +39,64 @@ protected ReferenceCollection(char[][][] qualifiedNameReferences, char[][] simpl
 	this.rootReferences = internSimpleNames(rootReferences, false);
 }
 
+/**
+ * Add the given fully qualified names to this reference collection.
+ * Subsequent queries of {@link #includes(char[][][], char[][], char[][])} will report true
+ * if the given names intersect with one of the added type name dependencies.
+ *
+ * @see CompilationUnitScope#recordQualifiedReference
+ */
 public void addDependencies(String[] typeNameDependencies) {
 	// if each qualified type name is already known then all of its subNames can be skipped
 	// and its expected that very few qualified names in typeNameDependencies need to be added
 	// but could always take 'p1.p2.p3.X' and make all qualified names 'p1' 'p1.p2' 'p1.p2.p3' 'p1.p2.p3.X', then intern
-	char[][][] qNames = new char[typeNameDependencies.length][][];
-	for (int i = typeNameDependencies.length; --i >= 0;)
-		qNames[i] = CharOperation.splitOn('.', typeNameDependencies[i].toCharArray());
-	qNames = internQualifiedNames(qNames, false);
-
-	next : for (int i = qNames.length; --i >= 0;) {
-		char[][] qualifiedTypeName = qNames[i];
-		while (!includes(qualifiedTypeName)) {
-			if (!includes(qualifiedTypeName[qualifiedTypeName.length - 1])) {
-				int length = this.simpleNameReferences.length;
-				System.arraycopy(this.simpleNameReferences, 0, this.simpleNameReferences = new char[length + 1][], 0, length);
-				this.simpleNameReferences[length] = qualifiedTypeName[qualifiedTypeName.length - 1];
-			}
-			if (!insideRoot(qualifiedTypeName[0])) {
-				int length = this.rootReferences.length;
-				System.arraycopy(this.rootReferences, 0, this.rootReferences = new char[length + 1][], 0, length);
-				this.rootReferences[length] = qualifiedTypeName[0];
+	next: for(String typeNameDependency: typeNameDependencies) {
+		char[][] qualifiedTypeName = CharOperation.splitOn('.', typeNameDependency.toCharArray());
+		if (!isWellKnownQualifiedName(qualifiedTypeName)) {
+			int qLength = qualifiedTypeName.length;
+			QualifiedNameSet internedNames = InternedQualifiedNames[qLength <= MaxQualifiedNames ? qLength - 1 : 0];
+			qualifiedTypeName = internSimpleNames(qualifiedTypeName, false, false);
+			qualifiedTypeName = internedNames.add(qualifiedTypeName);
+			int idx;
+			while ((idx = Arrays.binarySearch(this.qualifiedNameReferences, qualifiedTypeName, CHAR_CHAR_ARR_COMPARATOR)) < 0) {
+				this.simpleNameReferences = ensureContainedInSortedOrder(this.simpleNameReferences, qualifiedTypeName[qualifiedTypeName.length - 1]);
+				this.rootReferences = ensureContainedInSortedOrder(this.rootReferences, qualifiedTypeName[0]);
+
+				int length = this.qualifiedNameReferences.length;
+				idx = -(idx+1);
+				char[][][] newArray = new char[length + 1][][];
+				insertIntoArray(this.qualifiedNameReferences, this.qualifiedNameReferences = newArray, qualifiedTypeName, idx);
+
+				qualifiedTypeName = CharOperation.subarray(qualifiedTypeName, 0, qualifiedTypeName.length - 1);
+				char[][][] temp = internQualifiedNames(new char[][][] {qualifiedTypeName}, false);
+				if (temp == EmptyQualifiedNames)
+					continue next; // qualifiedTypeName is a well known name
+				qualifiedTypeName = temp[0];
 			}
-			int length = this.qualifiedNameReferences.length;
-			System.arraycopy(this.qualifiedNameReferences, 0, this.qualifiedNameReferences = new char[length + 1][][], 0, length);
-			this.qualifiedNameReferences[length] = qualifiedTypeName;
-
-			qualifiedTypeName = CharOperation.subarray(qualifiedTypeName, 0, qualifiedTypeName.length - 1);
-			char[][][] temp = internQualifiedNames(new char[][][] {qualifiedTypeName}, false);
-			if (temp == EmptyQualifiedNames)
-				continue next; // qualifiedTypeName is a well known name
-			qualifiedTypeName = temp[0];
 		}
 	}
 }
 
 public boolean includes(char[] simpleName) {
-	for (int i = 0, l = this.simpleNameReferences.length; i < l; i++)
-		if (simpleName == this.simpleNameReferences[i]) return true;
-	return false;
+	boolean result = sortedArrayContains(this.simpleNameReferences, simpleName, CHAR_ARR_COMPARATOR);
+	if (REFERENCE_COLLECTION_DEBUG) {
+		assertIncludes(result, simpleName);
+	}
+	return result;
 }
 
 public boolean includes(char[][] qualifiedName) {
-	for (int i = 0, l = this.qualifiedNameReferences.length; i < l; i++)
-		if (qualifiedName == this.qualifiedNameReferences[i]) return true;
-	return false;
+	boolean result = sortedArrayContains(this.qualifiedNameReferences, qualifiedName, CHAR_CHAR_ARR_COMPARATOR);
+	if (REFERENCE_COLLECTION_DEBUG) {
+		assertIncludes(result, qualifiedName);
+	}
+	return result;
+}
+
+private static String qualifiedNamesToString(char[][][] qualifiedNames) {
+	if (qualifiedNames == null)
+		return "null"; //$NON-NLS-1$
+	return Arrays.stream(qualifiedNames).map(CharOperation::toString).collect(Collectors.joining(",")); //$NON-NLS-1$
 }
 
 /**
@@ -86,82 +107,157 @@ public boolean includes(char[][][] qualifiedNames, char[][] simpleNames) {
 }
 
 public boolean includes(char[][][] qualifiedNames, char[][] simpleNames, char[][] rootNames) {
-	// if either collection of names is null, it means it contained a well known name so we know it already has a match
+	boolean result = doIncludes(qualifiedNames, simpleNames, rootNames);
+	if (REFERENCE_COLLECTION_DEBUG) {
+		assertIncludes(result, qualifiedNames, simpleNames, rootNames);
+	}
+	return result;
+}
+
+private boolean doIncludes(char[][][] qualifiedNames, char[][] simpleNames, char[][] rootNames) {
 	if (rootNames != null) {
-		boolean foundRoot = false;
-		for (int i = 0, l = rootNames.length; !foundRoot && i < l; i++)
-			foundRoot = insideRoot(rootNames[i]);
-		if (!foundRoot)
+		if (!includesRootName(rootNames))
 			return false;
 	}
+	// if either collection of names is null, it means it contained a well known name so we know it already has a match
 	if (simpleNames == null || qualifiedNames == null) {
 		if (simpleNames == null && qualifiedNames == null) {
 			if (JavaBuilder.DEBUG)
 				System.out.println("Found well known match"); //$NON-NLS-1$
 			return true;
 		} else if (qualifiedNames == null) {
-			for (int i = 0, l = simpleNames.length; i < l; i++) {
-				if (includes(simpleNames[i])) {
-					if (JavaBuilder.DEBUG)
-						System.out.println("Found match in well known package to " + new String(simpleNames[i])); //$NON-NLS-1$
-					return true;
-				}
-			}
-		} else {
-			for (int i = 0, l = qualifiedNames.length; i < l; i++) {
-				char[][] qualifiedName = qualifiedNames[i];
-				if (qualifiedName.length == 1 ? includes(qualifiedName[0]) : includes(qualifiedName)) {
-					if (JavaBuilder.DEBUG)
-						System.out.println("Found well known match in " + CharOperation.toString(qualifiedName)); //$NON-NLS-1$
-					return true;
-				}
-			}
+			return includesSimpleName(simpleNames);
+		}
+		return includesQualifiedName(qualifiedNames);
+	}
+
+	if (simpleNames.length <= qualifiedNames.length) {
+		return includesSimpleName(simpleNames) && includesQualifiedName(qualifiedNames);
+	} else {
+		return includesQualifiedName(qualifiedNames) && includesSimpleName(simpleNames);
+	}
+}
+
+public boolean insideRoot(char[] rootName) {
+	boolean result = sortedArrayContains(this.rootReferences, rootName, CHAR_ARR_COMPARATOR);
+	if (REFERENCE_COLLECTION_DEBUG) {
+		if (result != debugIncludes(rootName)) {
+			String message = "Mismatch: " + String.valueOf(rootName) + (result ? " should not " : " should ") + " be included in "  //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
+					+ Arrays.asList(CharOperation.toStrings(this.rootReferences));
+			throw new IllegalStateException(message);
 		}
+	}
+	return result;
+}
+
+private static <T> boolean sortedArrayContains(T[] array, T element, Comparator<? super T> comparator) {
+	int l = array.length;
+	if (l < BINARY_SEARCH_THRESHOLD) {
+		for (int i = 0; i < l; i++)
+			if (element == array[i]) return true;
 		return false;
 	}
+	return Arrays.binarySearch(array, element, comparator) >= 0;
+}
 
-	int sLength = simpleNames.length;
-	int qLength = qualifiedNames.length;
-	if (sLength <= qLength) {
-		for (int i = 0; i < sLength; i++) {
-			if (includes(simpleNames[i])) {
-				for (int j = 0; j < qLength; j++) {
-					char[][] qualifiedName = qualifiedNames[j];
-					if (qualifiedName.length == 1 ? includes(qualifiedName[0]) : includes(qualifiedName)) {
-						if (JavaBuilder.DEBUG)
-							System.out.println("Found match in " + CharOperation.toString(qualifiedName) //$NON-NLS-1$
-								+ " to " + new String(simpleNames[i])); //$NON-NLS-1$
-						return true;
-					}
+private boolean includesSimpleName(char[][] simpleNames) {
+	return intersects(simpleNames, this.simpleNameReferences, CHAR_ARR_COMPARATOR);
+}
+
+private boolean includesQualifiedName(char[][][] qualifiedNames) {
+	if (intersects(qualifiedNames, this.qualifiedNameReferences, CHAR_CHAR_ARR_COMPARATOR)) {
+		return true;
+	}
+	char[][] maybeSimpleName;
+	for(int i = qualifiedNames.length - 1; i >= 0 && (maybeSimpleName = qualifiedNames[i]).length == 1; i--) {
+		if (includes(maybeSimpleName[0])) {
+			return true;
+		}
+	}
+	return false;
+}
+
+private boolean includesRootName(char[][] rootNames) {
+	return intersects(rootNames, this.rootReferences, CHAR_ARR_COMPARATOR);
+}
+
+// TODO there may be better thresholds available for different scenarios
+private static final int BINARY_SEARCH_THRESHOLD = 16;
+private static <T> boolean intersects(T[] firstSortedArr, T[] secondSortedArr, Comparator<? super T> comparator) {
+	/*
+	 * Both arrays are sorted, so we can walk them in pairs.
+	 * Using binary search for the remaining array elements to figure the next
+	 * interesting index can greatly reduce the runtime cost for arrays that do
+	 * have more than a few elements.
+	 */
+	for(int i = 0, l = firstSortedArr.length, j = 0, k = secondSortedArr.length; i < l && j < k;) {
+		T firstElement = firstSortedArr[i];
+		T secondElement = secondSortedArr[j];
+		int compare = comparator.compare(firstElement, secondElement);
+		if (compare == 0) {
+			return true;
+		} else if (compare < 0) {
+			/*
+			 * left side is smaller than the right side, but not exactly the right side.
+			 * Take the next element from the left and proceed.
+			 *
+			 * If the number of remaining elements in the first array is sufficiently big,
+			 * attempt a binary search for the second element to possibly skip a few elements.
+			 */
+			i++;
+			if (l - i > BINARY_SEARCH_THRESHOLD) {
+				i = Arrays.binarySearch(firstSortedArr, i, l, secondElement, comparator);
+				if (i >= 0) {
+					return true;
 				}
-				return false;
+				i = -(i + 1);
 			}
-		}
-	} else {
-		for (int i = 0; i < qLength; i++) {
-			char[][] qualifiedName = qualifiedNames[i];
-			if (qualifiedName.length == 1 ? includes(qualifiedName[0]) : includes(qualifiedName)) {
-				for (int j = 0; j < sLength; j++) {
-					if (includes(simpleNames[j])) {
-						if (JavaBuilder.DEBUG)
-							System.out.println("Found match in " + CharOperation.toString(qualifiedName) //$NON-NLS-1$
-								+ " to " + new String(simpleNames[j])); //$NON-NLS-1$
-						return true;
-					}
+		} else {
+			/*
+			 * the inverse logic is applied here
+			 */
+			j++;
+			if (k - j > BINARY_SEARCH_THRESHOLD) {
+				j = Arrays.binarySearch(secondSortedArr, j, k, firstElement, comparator);
+				if (j >= 0) {
+					return true;
 				}
-				return false;
+				j = -(j + 1);
 			}
 		}
 	}
 	return false;
 }
 
-public boolean insideRoot(char[] rootName) {
-	for (int i = 0, l = this.rootReferences.length; i < l; i++)
-		if (rootName == this.rootReferences[i]) return true;
-	return false;
+// Generifying this appears to be pointless since arracopy takes an Object array anyways.
+private static void insertIntoArray(Object[] src, Object[] target, Object entry, int idx) {
+	System.arraycopy(src, 0, target, 0, idx);
+	target[idx] = entry;
+	System.arraycopy(src, idx, target, idx+1, src.length - idx);
+}
+
+private static char[][] ensureContainedInSortedOrder(char[][] sortedArray, char[] entry) {
+	int idx = Arrays.binarySearch(sortedArray, entry, CHAR_ARR_COMPARATOR);
+	if (idx < 0) {
+		idx = -(idx + 1);
+		char[][] result = new char[sortedArray.length + 1][];
+		insertIntoArray(sortedArray, result, entry, idx);
+		return result;
+	}
+	return sortedArray;
 }
 
+private static boolean isWellKnownQualifiedName(char[][] qualifiedName) {
+	for (int i = 0, m = WellKnownQualifiedNames.length, qLength = qualifiedName.length; i < m; i++) {
+		char[][] wellKnownName = WellKnownQualifiedNames[i];
+		if (qLength > wellKnownName.length)
+			break; // all remaining well known names are shorter
+		if (CharOperation.equals(qualifiedName, wellKnownName)) {
+			return true;
+		}
+	}
+	return false;
+}
 
 // When any type is compiled, its methods are verified for certain problems
 // the MethodVerifier requests 3 well known types which end up in the reference collection
@@ -228,17 +324,38 @@ public static char[][][] internQualifiedNames(StringSet qualifiedStrings) {
 	return internQualifiedNames(result, false);
 }
 
+/**
+ * <strong>Note</strong>: this method may change order of the result data, the new array is always sorted.
+ */
 public static char[][][] internQualifiedNames(char[][][] qualifiedNames) {
 	return internQualifiedNames(qualifiedNames, false);
 }
 
+/**
+ * Use a flyweight cache for the char arrays to avoid duplicated arrays with the same contents.
+ * After calling this method, identity comparison on the array contents of the resulting array
+ * will work for arrays with equal content.
+ * <p>
+ * <strong>Note</strong>: this method may change order of the result data, the new array is always sorted.
+ * <p>
+ * Optionally drops very common qualified names from the array to spare some bytes.
+ *
+ * @return a new array with interned elements.
+ */
 public static char[][][] internQualifiedNames(char[][][] qualifiedNames, boolean keepWellKnown) {
+	return internQualifiedNames(qualifiedNames, keepWellKnown, true);
+}
+
+static char[][][] internQualifiedNames(char[][][] qualifiedNames, boolean keepWellKnown, boolean doSort) {
 	if (qualifiedNames == null) return EmptyQualifiedNames;
 	int length = qualifiedNames.length;
 	if (length == 0) return EmptyQualifiedNames;
 
 	char[][][] keepers = new char[length][][];
+	char[][] prev = null;
+	boolean isSorted = true;
 	int index = 0;
+
 	next : for (int i = 0; i < length; i++) {
 		char[][] qualifiedName = qualifiedNames[i];
 		int qLength = qualifiedName.length;
@@ -248,6 +365,13 @@ public static char[][][] internQualifiedNames(char[][][] qualifiedNames, boolean
 				break; // all remaining well known names are shorter
 			if (CharOperation.equals(qualifiedName, wellKnownName)) {
 				if (keepWellKnown) {
+					// This code is duplicated to encourage the JIT to inline more stuff
+					if (doSort && isSorted) {
+						if (prev != null && compareCharCharArray(prev, qualifiedName) > 0) {
+							isSorted = false;
+						}
+						prev = qualifiedName;
+					}
 					keepers[index++] = wellKnownName;
 				}
 				continue next;
@@ -258,17 +382,69 @@ public static char[][][] internQualifiedNames(char[][][] qualifiedNames, boolean
 		// InternedQualifiedNames[1] is for size 2...
 		// InternedQualifiedNames[6] is for size 7
 		QualifiedNameSet internedNames = InternedQualifiedNames[qLength <= MaxQualifiedNames ? qLength - 1 : 0];
-		qualifiedName = internSimpleNames(qualifiedName, false);
+		qualifiedName = internSimpleNames(qualifiedName, false, false);
+		// This code is duplicated to encourage the JIT to inline more stuff
+		if (doSort && isSorted) {
+			if (prev != null && compareCharCharArray(prev, qualifiedName) > 0) {
+				isSorted = false;
+			}
+			prev = qualifiedName;
+		}
 		keepers[index++] = internedNames.add(qualifiedName);
 	}
 	if (length > index) {
 		if (index == 0) return EmptyQualifiedNames;
 		System.arraycopy(keepers, 0, keepers = new char[index][][], 0, index);
 	}
+	if (doSort && !isSorted) {
+		Arrays.sort(keepers, CHAR_CHAR_ARR_COMPARATOR);
+	}
 	return keepers;
 }
 
 /**
+ * Compares the two char arrays.
+ * Longer arrays are considered to be smaller than shorter arrays.
+ * Arrays with the same length are compared char by char lexicographically.
+ *
+ * @see Character#compare(char, char)
+ */
+private static int compareCharArray(char[] left, char[] right){
+	if (left == right) {
+		return 0;
+	}
+	int l = left.length;
+	int diff = right.length - l;
+	if (diff == 0) {
+		for(int i = 0; i < l && (diff = left[i] - right[i]) == 0; i++) {
+			// all logic is in the loop header
+		}
+	}
+	return diff;
+}
+private static final Comparator<char[]> CHAR_ARR_COMPARATOR = ReferenceCollection::compareCharArray;
+
+/**
+ * Compares the two char-char arrays.
+ * Longer arrays are considered to be smaller than shorter arrays.
+ * Arrays with the same length are compared according to the logic in {@link #compareCharArray(char[], char[])}.
+ */
+static int compareCharCharArray(char[][] left, char[][]right) {
+	if (left == right) {
+		return 0;
+	}
+	int l = left.length;
+	int diff = right.length - l;
+	if (diff == 0) {
+		for(int i = 0; i < l && (diff = compareCharArray(left[i], right[i])) == 0; i++) {
+			// all logic is in the loop header
+		}
+	}
+	return diff;
+}
+private static final Comparator<char[][]> CHAR_CHAR_ARR_COMPARATOR = ReferenceCollection::compareCharCharArray;
+
+/**
  * @deprecated
  */
 public static char[][] internSimpleNames(Set<String> simpleStrings) {
@@ -301,13 +477,28 @@ public static char[][] internSimpleNames(StringSet simpleStrings, boolean remove
 			result[--length] = strings[i].toCharArray();
 	return internSimpleNames(result, removeWellKnown);
 }
-
+/**
+ * Use a flyweight cache for the char arrays to avoid duplicated arrays with the same contents.
+ * After calling this method, identity comparison on the array contents of the resulting array
+ * will work for arrays with equal content.
+ * <p>
+ * <strong>Note</strong>: this method may change order of the result data, the new array is always sorted.
+ * <p>
+ * Optionally drops very common qualified names from the array to spare some bytes.
+ *
+ * @return a new array with interned elements.
+ */
 public static char[][] internSimpleNames(char[][] simpleNames, boolean removeWellKnown) {
+	return internSimpleNames(simpleNames, removeWellKnown, true);
+}
+static char[][] internSimpleNames(char[][] simpleNames, boolean removeWellKnown, boolean doSort) {
 	if (simpleNames == null) return EmptySimpleNames;
 	int length = simpleNames.length;
 	if (length == 0) return EmptySimpleNames;
 
 	char[][] keepers = new char[length][];
+	char[] prev = null;
+	boolean isSorted = true;
 	int index = 0;
 	next : for (int i = 0; i < length; i++) {
 		char[] name = simpleNames[i];
@@ -317,8 +508,16 @@ public static char[][] internSimpleNames(char[][] simpleNames, boolean removeWel
 			if (sLength > wellKnownName.length)
 				break; // all remaining well known names are shorter
 			if (CharOperation.equals(name, wellKnownName)) {
-				if (!removeWellKnown)
-					keepers[index++] = WellKnownSimpleNames[j];
+				if (!removeWellKnown) {
+					keepers[index++] = wellKnownName;
+					// This code is duplicated to encourage the JIT to inline more stuff
+					if (doSort && isSorted) {
+						if (prev != null && compareCharArray(prev, name) > 0) {
+							isSorted = false;
+						}
+						prev = name;
+					}
+				}
 				continue next;
 			}
 		}
@@ -328,11 +527,144 @@ public static char[][] internSimpleNames(char[][] simpleNames, boolean removeWel
 		// InternedSimpleNames[29] is for size 29
 		NameSet internedNames = InternedSimpleNames[sLength < MaxSimpleNames ? sLength : 0];
 		keepers[index++] = internedNames.add(name);
+		// This code is duplicated to encourage the JIT to inline more stuff
+		if (doSort && isSorted) {
+			if (prev != null && compareCharArray(prev, name) > 0) {
+				isSorted = false;
+			}
+			prev = name;
+		}
 	}
 	if (length > index) {
 		if (index == 0) return EmptySimpleNames;
 		System.arraycopy(keepers, 0, keepers = new char[index][], 0, index);
 	}
+	if (doSort && !isSorted) {
+		Arrays.sort(keepers, CHAR_ARR_COMPARATOR);
+	}
 	return keepers;
 }
+
+// DEBUG code below
+public static boolean REFERENCE_COLLECTION_DEBUG = false;
+
+private void assertIncludes(boolean expectation, char[] simpleName) {
+	if (expectation != debugIncludes(simpleName)) {
+		String message = "Mismatch: " + String.valueOf(simpleName) + (expectation ? " should not " : " should ") + " be included in "  //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
+				+ Arrays.asList(CharOperation.toStrings(this.simpleNameReferences));
+		throw new IllegalStateException(message);
+	}
+}
+
+private void assertIncludes(boolean expectation, char[][] qualifiedName) {
+	if (expectation != debugIncludes(qualifiedName)) {
+		String message = "Mismatch: " + CharOperation.toString(qualifiedName) + (expectation ? " should not " : " should ") + " be included in "  //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
+				+ qualifiedNamesToString(this.qualifiedNameReferences);
+		throw new IllegalStateException(message);
+	}
+}
+
+private void assertIncludes(boolean expectation, char[][][] qualifiedNames, char[][] simpleNames, char[][] rootNames) {
+	if (expectation != debugIncludes(qualifiedNames, simpleNames, rootNames)) {
+		String message = String.format("Mismatched includes(..): ReferenceCollection([%s], %s, %s).includes([%s], %s, %s)", //$NON-NLS-1$
+				qualifiedNamesToString(this.qualifiedNameReferences),
+				Arrays.toString(CharOperation.toStrings(this.simpleNameReferences)),
+				Arrays.toString(CharOperation.toStrings(this.rootReferences)),
+				qualifiedNamesToString(qualifiedNames),
+				Arrays.toString(CharOperation.toStrings(simpleNames)),
+				Arrays.toString(CharOperation.toStrings(rootNames))
+		);
+		throw new IllegalStateException(message);
+	}
+}
+
+private boolean debugIncludes(char[][][] qualifiedNames, char[][] simpleNames, char[][] rootNames) {
+	// if either collection of names is null, it means it contained a well known name so we know it already has a match
+	if (rootNames != null) {
+		boolean foundRoot = false;
+		for (int i = 0, l = rootNames.length; !foundRoot && i < l; i++)
+			foundRoot = debugInsideRoot(rootNames[i]);
+		if (!foundRoot)
+			return false;
+	}
+	if (simpleNames == null || qualifiedNames == null) {
+		if (simpleNames == null && qualifiedNames == null) {
+			if (JavaBuilder.DEBUG)
+				System.out.println("Found well known match"); //$NON-NLS-1$
+			return true;
+		} else if (qualifiedNames == null) {
+			for (int i = 0, l = simpleNames.length; i < l; i++) {
+				if (debugIncludes(simpleNames[i])) {
+					if (JavaBuilder.DEBUG)
+						System.out.println("Found match in well known package to " + new String(simpleNames[i])); //$NON-NLS-1$
+					return true;
+				}
+			}
+		} else {
+			for (int i = 0, l = qualifiedNames.length; i < l; i++) {
+				char[][] qualifiedName = qualifiedNames[i];
+				if (qualifiedName.length == 1 ? debugIncludes(qualifiedName[0]) : debugIncludes(qualifiedName)) {
+					if (JavaBuilder.DEBUG)
+						System.out.println("Found well known match in " + CharOperation.toString(qualifiedName)); //$NON-NLS-1$
+					return true;
+				}
+			}
+		}
+		return false;
+	}
+
+	int sLength = simpleNames.length;
+	int qLength = qualifiedNames.length;
+	if (sLength <= qLength) {
+		for (int i = 0; i < sLength; i++) {
+			if (debugIncludes(simpleNames[i])) {
+				for (int j = 0; j < qLength; j++) {
+					char[][] qualifiedName = qualifiedNames[j];
+					if (qualifiedName.length == 1 ? debugIncludes(qualifiedName[0]) : debugIncludes(qualifiedName)) {
+						if (JavaBuilder.DEBUG)
+							System.out.println("Found match in " + CharOperation.toString(qualifiedName) //$NON-NLS-1$
+								+ " to " + new String(simpleNames[i])); //$NON-NLS-1$
+						return true;
+					}
+				}
+				return false;
+			}
+		}
+	} else {
+		for (int i = 0; i < qLength; i++) {
+			char[][] qualifiedName = qualifiedNames[i];
+			if (qualifiedName.length == 1 ? debugIncludes(qualifiedName[0]) : debugIncludes(qualifiedName)) {
+				for (int j = 0; j < sLength; j++) {
+					if (debugIncludes(simpleNames[j])) {
+						if (JavaBuilder.DEBUG)
+							System.out.println("Found match in " + CharOperation.toString(qualifiedName) //$NON-NLS-1$
+								+ " to " + new String(simpleNames[j])); //$NON-NLS-1$
+						return true;
+					}
+				}
+				return false;
+			}
+		}
+	}
+	return false;
+}
+
+private boolean debugInsideRoot(char[] rootName) {
+	for (int i = 0, l = this.rootReferences.length; i < l; i++)
+		if (rootName == this.rootReferences[i]) return true;
+	return false;
+}
+
+private boolean debugIncludes(char[] simpleName) {
+	for (int i = 0, l = this.simpleNameReferences.length; i < l; i++)
+		if (simpleName == this.simpleNameReferences[i]) return true;
+	return false;
+}
+
+private boolean debugIncludes(char[][] qualifiedName) {
+	for (int i = 0, l = this.qualifiedNameReferences.length; i < l; i++)
+		if (qualifiedName == this.qualifiedNameReferences[i]) return true;
+	return false;
+}
+
 }
diff --git a/org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/State.java b/org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/State.java
index a57cc107e6..7afd3dc085 100644
--- a/org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/State.java
+++ b/org.eclipse.jdt.core/model/org/eclipse/jdt/internal/core/builder/State.java
@@ -13,6 +13,8 @@
  *     Stephan Herrmann - Contribution for
  *								Bug 440477 - [null] Infrastructure for feeding external annotations into compilation
  *     Karsten Thoms - Bug 532505
+ *     Sebastian Zarnekow - Contribution for
+ *								Bug 545491 - Poor performance of ReferenceCollection with many source files
  *******************************************************************************/
 package org.eclipse.jdt.internal.core.builder;
 
@@ -387,8 +389,11 @@ static State read(IProject project, DataInputStream in) throws IOException, Core
 	for (int i = 0; i < length; i++)
 		newState.recordLocatorForType(in.readUTF(), internedTypeLocators[in.readInt()]);
 
-	char[][] internedRootNames = ReferenceCollection.internSimpleNames(readNames(in), false);
-	char[][] internedSimpleNames = ReferenceCollection.internSimpleNames(readNames(in), false);
+	/*
+	 * Here we read global arrays of names for the entire project - do not mess up the ordering while interning
+	 */
+	char[][] internedRootNames = ReferenceCollection.internSimpleNames(readNames(in), false /* keep well known */, false /* do not sort */);
+	char[][] internedSimpleNames = ReferenceCollection.internSimpleNames(readNames(in), false /* keep well known */, false /* do not sort */);
 	char[][][] internedQualifiedNames = new char[length = in.readInt()][][];
 	for (int i = 0; i < length; i++) {
 		int qLength = in.readInt();
@@ -397,7 +402,7 @@ static State read(IProject project, DataInputStream in) throws IOException, Core
 			qName[j] = internedSimpleNames[in.readInt()];
 		internedQualifiedNames[i] = qName;
 	}
-	internedQualifiedNames = ReferenceCollection.internQualifiedNames(internedQualifiedNames, false);
+	internedQualifiedNames = ReferenceCollection.internQualifiedNames(internedQualifiedNames, false /* drop well known */, false /* do not sort */);
 
 	newState.references = new SimpleLookupTable(length = in.readInt());
 	for (int i = 0; i < length; i++) {