Bug 570896 - [performance] Improve AliasManager LocationMap compare
Avoid memory allocation during compare
Part 2: changed implementation:
The compare is a memory hot spot. The old implementation used new
instances of Path during each compare and thus a lot of ephemeral String
memory allocation which did presssure the GC. The new implementation
avoids memory allocation at all by comparing the path string without
splitting it into several String instances.
Also the old Path constructor performed some non needed normalization of
path strings which are not needed for already normalized URI path
strings.
Also fixed compare contract sgn(compare(x, y)) == -sgn(compare(y, x))
in case of Exceptions
For compatibility the new version is only used for LocalFile.
Bug: 570896
Change-Id: I10a454af867ab3141d1f1ca33e55e4d0b6b26e85
Signed-off-by: jkubitz <jkubitz-eclipse@gmx.de>
diff --git a/bundles/org.eclipse.core.filesystem/META-INF/MANIFEST.MF b/bundles/org.eclipse.core.filesystem/META-INF/MANIFEST.MF
index ca7d90b..0043677 100644
--- a/bundles/org.eclipse.core.filesystem/META-INF/MANIFEST.MF
+++ b/bundles/org.eclipse.core.filesystem/META-INF/MANIFEST.MF
@@ -2,7 +2,7 @@
Bundle-ManifestVersion: 2
Bundle-Name: %pluginName
Bundle-SymbolicName: org.eclipse.core.filesystem; singleton:=true
-Bundle-Version: 1.8.0.qualifier
+Bundle-Version: 1.9.0.qualifier
Bundle-Localization: plugin
Require-Bundle: org.eclipse.equinox.common;bundle-version="[3.2.0,4.0.0)",
org.eclipse.equinox.registry;bundle-version="[3.2.0,4.0.0)",
diff --git a/bundles/org.eclipse.core.filesystem/src/org/eclipse/core/filesystem/IFileStore.java b/bundles/org.eclipse.core.filesystem/src/org/eclipse/core/filesystem/IFileStore.java
index 4512fbb..b90cfa7 100644
--- a/bundles/org.eclipse.core.filesystem/src/org/eclipse/core/filesystem/IFileStore.java
+++ b/bundles/org.eclipse.core.filesystem/src/org/eclipse/core/filesystem/IFileStore.java
@@ -565,4 +565,33 @@
* @see EFS#getStore(URI)
*/
public URI toURI();
+
+ /**
+ * Compares this store to other store of same FileSystem. Comparison has to be
+ * based on segments, so that paths with the most segments in common will always
+ * be adjacent. This is equivalent to the natural order on the path strings,
+ * with the extra condition that the path separator is ordered before all other
+ * characters. (Ex: "/foo" < "/foo/zzz" < "/fooaaa").
+ *
+ * @since org.eclipse.core.filesystem 1.9
+ */
+ public default int compareTo(IFileStore other) {
+ // compare based on URI path segment values
+ URI uri1;
+ URI uri2;
+ try {
+ uri1 = this.toURI();
+ } catch (Exception e1) {
+ // protect against misbehaving 3rd party code in file system implementations
+ uri1 = null;
+ }
+ try {
+ uri2 = other.toURI();
+ } catch (Exception e2) {
+ // protect against misbehaving 3rd party code in file system implementations
+ uri2 = null;
+ }
+ // use old slow compare for compatibility reason. Does have a memory hotspot see bug 570896
+ return URIUtil.comparePathUri(uri1, uri2);
+ }
}
\ No newline at end of file
diff --git a/bundles/org.eclipse.core.filesystem/src/org/eclipse/core/filesystem/URIUtil.java b/bundles/org.eclipse.core.filesystem/src/org/eclipse/core/filesystem/URIUtil.java
index bf0f55e..d138894 100644
--- a/bundles/org.eclipse.core.filesystem/src/org/eclipse/core/filesystem/URIUtil.java
+++ b/bundles/org.eclipse.core.filesystem/src/org/eclipse/core/filesystem/URIUtil.java
@@ -175,6 +175,150 @@
}
/**
+ * Compares URIs by normalized IPath
+ * This is the old slow implementation and has a memory hotspot see bug 570896. Prefer to use compareNormalisedUri!
+ * @since org.eclipse.core.filesystem 1.9
+ */
+ public static int comparePathUri(URI uri1, URI uri2) {
+ if (uri1 == null && uri2 == null)
+ return 0;
+ int compare;
+ // Fixed compare contract sgn(compare(x, y)) == -sgn(compare(y, x))
+ // in case of Exceptions:
+ if ((compare = nullsLast(uri1, uri2)) != 0)
+ return compare;
+ // compare hosts
+ compare = compareStringOrNull(uri1.getHost(), uri2.getHost());
+ if (compare != 0)
+ return compare;
+ // compare user infos
+ compare = compareStringOrNull(uri1.getUserInfo(), uri2.getUserInfo());
+ if (compare != 0)
+ return compare;
+ // compare ports
+ int port1 = uri1.getPort();
+ int port2 = uri2.getPort();
+ if (port1 != port2)
+ return port1 - port2;
+
+ IPath path1 = new Path(uri1.getPath());
+ IPath path2 = new Path(uri2.getPath());
+ // compare devices
+ compare = compareStringOrNull(path1.getDevice(), path2.getDevice());
+ if (compare != 0)
+ return compare;
+ // compare segments
+ int segmentCount1 = path1.segmentCount();
+ int segmentCount2 = path2.segmentCount();
+ for (int i = 0; (i < segmentCount1) && (i < segmentCount2); i++) {
+ compare = path1.segment(i).compareTo(path2.segment(i));
+ if (compare != 0)
+ return compare;
+ }
+ //all segments are equal, so compare based on number of segments
+ compare = segmentCount1 - segmentCount2;
+ if (compare != 0)
+ return compare;
+ //same number of segments, so compare query
+ return compareStringOrNull(uri1.getQuery(), uri2.getQuery());
+ }
+
+ /**
+ * Compares already normalized URIs
+ * This is a fast implementation without memory allocation (Bug 570896).
+ * note: if pathes contain different segment count this is != uri1.compareNormalisedUri(uri2)
+ * @since org.eclipse.core.filesystem 1.9
+ */
+ public static int compareNormalisedUri(URI uri1, URI uri2) {
+ if (uri1 == null && uri2 == null)
+ return 0;
+ int c;
+ if ((c = nullsLast(uri1, uri2)) != 0)
+ return c;
+ // avoid to use IPath here due to high ephemeral memory allocation (Bug 570896)
+ if ((c = compareStringOrNull(uri1.getAuthority(), uri2.getAuthority())) != 0)
+ return c;
+ if ((c = compareStringOrNull(uri1.getScheme(), uri2.getScheme())) != 0)
+ return c;
+ if ((c = comparePathSegments(uri1.getPath(), uri2.getPath())) != 0)
+ return c;
+ if ((c = compareStringOrNull(uri1.getQuery(), uri2.getQuery())) != 0)
+ return c;
+ return c;
+ }
+
+ static int nullsLast(Object c1, Object c2) {
+ if (c1 == null) {
+ if (c2 == null)
+ return 0;
+ return 1;
+ }
+ if (c2 == null)
+ return -1;
+ return 0;
+ }
+
+ static int comparePathSegments(String p1, String p2) {
+ int compare;
+ compare = compareSlashFirst(p1, p2);
+ if (compare != 0)
+ return compare;
+ // all segments are equal, so compare based on number of segments
+ int segmentCount1 = countCharButNotAtEnd(p1, '/');
+ int segmentCount2 = countCharButNotAtEnd(p2, '/');
+ compare = segmentCount1 - segmentCount2;
+ return compare;
+ }
+
+ static int compareSlashFirst(String value, String other) {
+ int len1 = value.length();
+ int len2 = other.length();
+ int lim = Math.min(len1, len2);
+ for (int k = 0; k < lim; k++) {
+ char c1 = value.charAt(k);
+ char c2 = other.charAt(k);
+ if (c1 != c2) {
+ // '/' first
+ if (c1 == '/')
+ return -1;
+ if (c2 == '/')
+ return 1;
+ return c1 - c2;
+ }
+ }
+ // ignore "/" at the end
+ if (value.endsWith("/")) //$NON-NLS-1$
+ len1 -= 1;
+ if (other.endsWith("/")) //$NON-NLS-1$
+ len2 -= 1;
+ return len1 - len2;
+ }
+
+ static int countCharButNotAtEnd(String str, char c) {
+ int count = 0;
+ for (int i = 0; i < str.length() - 1; i++) {
+ if (str.charAt(i) == c)
+ count++;
+ }
+ return count;
+ }
+
+ /**
+ * Compares two strings that are possibly null.
+ * @since org.eclipse.core.filesystem 1.9
+ */
+ public static int compareStringOrNull(String string1, String string2) {
+ if (string1 == null) {
+ if (string2 == null)
+ return 0;
+ return 1;
+ }
+ if (string2 == null)
+ return -1;
+ return string1.compareTo(string2);
+ }
+
+ /**
* Private constructor to prevent instantiation.
*/
private URIUtil() {
diff --git a/bundles/org.eclipse.core.filesystem/src/org/eclipse/core/internal/filesystem/local/LocalFile.java b/bundles/org.eclipse.core.filesystem/src/org/eclipse/core/internal/filesystem/local/LocalFile.java
index 5652d7a..1f11c28 100644
--- a/bundles/org.eclipse.core.filesystem/src/org/eclipse/core/internal/filesystem/local/LocalFile.java
+++ b/bundles/org.eclipse.core.filesystem/src/org/eclipse/core/internal/filesystem/local/LocalFile.java
@@ -469,4 +469,10 @@
}
return this.uri;
}
+
+ @Override
+ public int compareTo(IFileStore other) {
+ // override with fast implementation:
+ return URIUtil.compareNormalisedUri(this.toURI(), other.toURI());
+ }
}
diff --git a/bundles/org.eclipse.core.resources/src/org/eclipse/core/internal/resources/AliasManager.java b/bundles/org.eclipse.core.resources/src/org/eclipse/core/internal/resources/AliasManager.java
index ac8301a..8c2ede7 100644
--- a/bundles/org.eclipse.core.resources/src/org/eclipse/core/internal/resources/AliasManager.java
+++ b/bundles/org.eclipse.core.resources/src/org/eclipse/core/internal/resources/AliasManager.java
@@ -22,10 +22,12 @@
import java.util.*;
import org.eclipse.core.filesystem.EFS;
import org.eclipse.core.filesystem.IFileStore;
+import org.eclipse.core.filesystem.URIUtil;
import org.eclipse.core.internal.events.ILifecycleListener;
import org.eclipse.core.internal.events.LifecycleEvent;
import org.eclipse.core.internal.localstore.FileSystemResourceManager;
-import org.eclipse.core.internal.utils.*;
+import org.eclipse.core.internal.utils.FileUtil;
+import org.eclipse.core.internal.utils.Messages;
import org.eclipse.core.resources.*;
import org.eclipse.core.runtime.*;
import org.eclipse.osgi.util.NLS;
@@ -128,7 +130,7 @@
/**
* Map of FileStore->IResource OR FileStore->ArrayList of (IResource)
*/
- private final SortedMap<IFileStore, Object> map = new TreeMap<>(getComparator());
+ private final SortedMap<IFileStore, Object> map = new TreeMap<>(AliasManager::compareUri);
/**
* Adds the given resource to the map, keyed by the given location.
@@ -485,84 +487,20 @@
}
/**
- * Returns the comparator to use when sorting the locations map. Comparison
- * is based on segments, so that paths with the most segments in common will
- * always be adjacent. This is equivalent to the natural order on the path
- * strings, with the extra condition that the path separator is ordered
- * before all other characters. (Ex: "/foo" < "/foo/zzz" < "/fooaaa").
+ * Returns the compare result when sorting the locations map. Comparison is
+ * based on segments, so that paths with the most segments in common will always
+ * be adjacent. This is equivalent to the natural order on the path strings,
+ * with the extra condition that the path separator is ordered before all other
+ * characters. (Ex: "/foo" < "/foo/zzz" < "/fooaaa").
*/
- Comparator<IFileStore> getComparator() {
- return (store1, store2) -> {
- //scheme takes precedence over all else
- int compare = compareStringOrNull(store1.getFileSystem().getScheme(), store2.getFileSystem().getScheme());
+ static int compareUri(IFileStore store1, IFileStore store2) {
+ // scheme takes precedence over all else
+ int compare = URIUtil.compareStringOrNull(store1.getFileSystem().getScheme(),
+ store2.getFileSystem().getScheme());
if (compare != 0)
return compare;
- // compare based on URI path segment values
- final URI uri1;
- final URI uri2;
- try {
- uri1 = store1.toURI();
- uri2 = store2.toURI();
- } catch (Exception e) {
- //protect against misbehaving 3rd party code in file system implementations
- Policy.log(e);
- return 1;
- }
- return compareUri(uri1, uri2);
- };
+ return store1.compareTo(store2);
}
- public static int compareUri(URI uri1, URI uri2) {
- int compare;
- // compare hosts
- compare = compareStringOrNull(uri1.getHost(), uri2.getHost());
- if (compare != 0)
- return compare;
- // compare user infos
- compare = compareStringOrNull(uri1.getUserInfo(), uri2.getUserInfo());
- if (compare != 0)
- return compare;
- // compare ports
- int port1 = uri1.getPort();
- int port2 = uri2.getPort();
- if (port1 != port2)
- return port1 - port2;
-
- IPath path1 = new Path(uri1.getPath());
- IPath path2 = new Path(uri2.getPath());
- // compare devices
- compare = compareStringOrNull(path1.getDevice(), path2.getDevice());
- if (compare != 0)
- return compare;
- // compare segments
- int segmentCount1 = path1.segmentCount();
- int segmentCount2 = path2.segmentCount();
- for (int i = 0; (i < segmentCount1) && (i < segmentCount2); i++) {
- compare = path1.segment(i).compareTo(path2.segment(i));
- if (compare != 0)
- return compare;
- }
- //all segments are equal, so compare based on number of segments
- compare = segmentCount1 - segmentCount2;
- if (compare != 0)
- return compare;
- //same number of segments, so compare query
- return compareStringOrNull(uri1.getQuery(), uri2.getQuery());
- }
-
- /**
- * Compares two strings that are possibly null.
- */
- private static int compareStringOrNull(String string1, String string2) {
- if (string1 == null) {
- if (string2 == null)
- return 0;
- return 1;
- }
- if (string2 == null)
- return -1;
- return string1.compareTo(string2);
-
- }
@Override
public void handleEvent(LifecycleEvent event) {
diff --git a/tests/org.eclipse.core.tests.resources/src/org/eclipse/core/tests/internal/alias/BasicAliasTest.java b/tests/org.eclipse.core.tests.resources/src/org/eclipse/core/tests/internal/alias/BasicAliasTest.java
index 344f994..cebe393 100644
--- a/tests/org.eclipse.core.tests.resources/src/org/eclipse/core/tests/internal/alias/BasicAliasTest.java
+++ b/tests/org.eclipse.core.tests.resources/src/org/eclipse/core/tests/internal/alias/BasicAliasTest.java
@@ -21,6 +21,7 @@
import java.util.stream.Collectors;
import org.eclipse.core.filesystem.EFS;
import org.eclipse.core.filesystem.IFileStore;
+import org.eclipse.core.filesystem.URIUtil;
import org.eclipse.core.internal.resources.*;
import org.eclipse.core.resources.*;
import org.eclipse.core.runtime.*;
@@ -311,7 +312,7 @@
for (URI u1 : uriList) {
for (URI u2 : uriList) {
if (!u1.equals(u2)) {
- assertTrue("1.0", 0 != AliasManager.compareUri(u1, u2));
+ assertTrue("1.0", 0 != URIUtil.compareNormalisedUri(u1, u2));
}
}
}
@@ -376,16 +377,28 @@
assertPreOrdered(urisStrings);
}
+ /* Bug570896 */
+ public void testCompareUriNulls() throws URISyntaxException {
+ // fragments should NOT be distinct! Even though they might not be used:
+ String[] urisStrings = { //
+ "scheme://authority/path?query#fragment", //
+ "s:///?#", //
+ "s:///?#", //
+ "s:///", //
+ "", "", null, null,
+ };
+ assertPreOrdered(urisStrings);
+ }
private void assertPreOrdered(String[] urisStrings) {
List<URI> uriList = Arrays.asList(urisStrings).stream().map(t -> {
try {
- return new URI(t);
+ return t == null ? null : new URI(t);
} catch (URISyntaxException e) {
throw new RuntimeException(e);
}
}).collect(Collectors.toList());
// stable sort:
- List<URI> sorted = uriList.stream().sorted(AliasManager::compareUri).collect(Collectors.toList());
+ List<URI> sorted = uriList.stream().sorted(URIUtil::compareNormalisedUri).collect(Collectors.toList());
// proof sort order did not change
assertEquals("1.0", uriList, sorted);
}
