Changeset 18973 in josm

Timestamp:

2024-02-12T18:12:15+01:00 (3 months ago)

Author:

taylor.smock

Message:

Fix #23468: Improve performance in the Validator tree window

A large number of entries in the validator tree would cause the UI to lock for
significant periods of time when switching to a layer with many errors. Most of
the time spent was in AlphanumComparator.compare.

We need to use AlphanumComparator since String.compare would improperly sort
strings with accented characters.

The performance optimizations for this patch come from the following locations:

• Extracting string chunk comparison to its own method (which can be compiled to native code)
• Using String.substring instead of a StringBuilder when getting a string chunk for comparison

Both of those methods may be compiled to native code, but absent code compilation,
the performance improvements are as follows (as measured using an overpass
download of Mesa County, Colorado):

• -86.4% CPU usage (3.366s to 0.459s)
• -99.9% memory allocations (2.37 GB to 2.07 MB)

File:

• trunk/src/org/openstreetmap/josm/tools/AlphanumComparator.java (modified) (4 diffs)

trunk/src/org/openstreetmap/josm/tools/AlphanumComparator.java

@@ -75 +75 @@
      */
     private static String getChunk(String s, int slength, int marker) {
-        StringBuilder chunk = new StringBuilder();
+        final int startMarker = marker;
         char c = s.charAt(marker);
-        chunk.append(c);
         marker++;
         if (Character.isDigit(c)) {
@@ -85 +84 @@
                     break;
                 }
-                chunk.append(c);
                 marker++;
             }
@@ -94 +92 @@
                     break;
                 }
-                chunk.append(c);
                 marker++;
             }
         }
-        return chunk.toString();
+        return s.substring(startMarker, marker);
+    }
+
+    /**
+     * Check if a string is ASCII only
+     * @param string The string to check
+     * @param stringLength The length of the string (for performance reasons)
+     * @return {@code true} if the string only contains ascii characters
+     */
+    private static boolean isAscii(String string, int stringLength) {
+        for (int i = 0; i < stringLength; i++) {
+            char c = string.charAt(i);
+            if (c >= 128) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    /**
+     * Compare two string chunks
+     * @param thisChunk The first chunk to compare
+     * @param thisChunkLength The length of the first chunk (for performance reasons)
+     * @param thatChunk The second chunk to compare
+     * @param thatChunkLength The length of the second chunk (for performance reasons)
+     * @return The {@link Comparator} result
+     */
+    private static int compareChunk(String thisChunk, int thisChunkLength, String thatChunk, int thatChunkLength) {
+        int result;
+        if (Character.isDigit(thisChunk.charAt(0)) && Character.isDigit(thatChunk.charAt(0))) {
+            // Simple chunk comparison by length.
+            result = thisChunkLength - thatChunkLength;
+            // If equal, the first different number counts
+            if (result == 0) {
+                for (int i = 0; i < thisChunkLength; i++) {
+                    result = thisChunk.charAt(i) - thatChunk.charAt(i);
+                    if (result != 0) {
+                        return result;
+                    }
+                }
+            }
+        } else {
+            // Check if both chunks are ascii only
+            if (isAscii(thisChunk, thisChunkLength) && isAscii(thatChunk, thatChunkLength)) {
+                return thisChunk.compareTo(thatChunk);
+            }
+            // Instantiate the collator
+            Collator compareOperator = Collator.getInstance();
+            // Compare regardless of accented letters
+            compareOperator.setStrength(Collator.SECONDARY);
+            result = compareOperator.compare(thisChunk, thatChunk);
+        }
+        return result;
     }
 
@@ -117 +166 @@
 
         while (thisMarker < s1Length && thatMarker < s2Length) {
-            String thisChunk = getChunk(s1, s1Length, thisMarker);
-            thisMarker += thisChunk.length();
+            final String thisChunk = getChunk(s1, s1Length, thisMarker);
+            final int thisChunkLength = thisChunk.length();
+            thisMarker += thisChunkLength;
 
             String thatChunk = getChunk(s2, s2Length, thatMarker);
-            thatMarker += thatChunk.length();
+            final int thatChunkLength = thatChunk.length();
+            thatMarker += thatChunkLength;
 
             // If both chunks contain numeric characters, sort them numerically
-            int result;
-            if (Character.isDigit(thisChunk.charAt(0)) && Character.isDigit(thatChunk.charAt(0))) {
-                // Simple chunk comparison by length.
-                int thisChunkLength = thisChunk.length();
-                result = thisChunkLength - thatChunk.length();
-                // If equal, the first different number counts
-                if (result == 0) {
-                    for (int i = 0; i < thisChunkLength; i++) {
-                        result = thisChunk.charAt(i) - thatChunk.charAt(i);
-                        if (result != 0) {
-                            return result;
-                        }
-                    }
-                }
-            } else {
-                // Instantiate the collator
-                Collator compareOperator = Collator.getInstance();
-                // Compare regardless of accented letters
-                compareOperator.setStrength(Collator.SECONDARY);
-                result = compareOperator.compare(thisChunk, thatChunk);
-            }
+            int result = compareChunk(thisChunk, thisChunkLength, thatChunk, thatChunkLength);
 
             if (result != 0) {