Natural Sort in Java, Performance Tuned

Published: 2015-10-11
Updated: 2016-12-14
Web: https://fritzthecat-blog.blogspot.com/2015/10/natural-sort-in-java-performance-tuning.html

How to performance-tune? How can we make some Java code run faster?
You guess right, there is no simple answer to this. Here are my tips.

Caching nearly always helps, and you might gain incredible performance boost from it with very few work. But it also can cause big problems. If caches are not released in time, they will contain wrong information, and thus generate errors. So you need to manage your caches in a safe way.
In case of natural sorting, caching statefulIterator instances is not a good idea, but caching the ready-made part-lists is.

Avoid loops. Avoid loops in loops. Avoid loops in loops in loops ....
This is not an easy task, because big hierarchies of method calls might hide a laborious program flow. Avoiding loops also means avoiding doing the same thing again and again, like splitting or parsing the same text or other input repeatedly, thus it is strongly related with caching.

Make things short. Break loops when continuing does not make sense any more. A classical example is the short circuit condition, built into most modern programming languages.
In case of natural sorting, in my first performance tuning I break the splitting of strings as soon as a difference occurs.

Remove unneeded things. Generally this refers to the agile You ain't gonna need it principle.
In case of natural sorting, distinguishing between separators and letters may be dispensable.

Look for synchronized sections. Thread-safe code has its drawbacks, it is slower than normal code, because it needs operating system resources for synchronization.

In old times it was also important to avoid the new operator, because this is an operating system call and thus may take time. But I do not believe this to be a significant any more today.

Generally I want to mention that performance tuning is nothing you should do when implementing new software. You should do that afterwards, and just where needed. You save much efforts by such a strategy. Do not forget that

PREMATURE OPTIMIZATION IS THE ROOT OF ALL EVIL

So how successful has my second natural sort tuning been? And which strategy helped?

• Tip: you find the full Java source code of the NaturalSortComparator4 on bottom of this page in a fold.

Caching

Caching brought my first naive sorter implementation instantly to an even better performance than the NaturalOrderComparator(that I named PoolPaourComparator here, after its authors Martin Pool and Pierre-Luc Paour). And that with just a few lines of code, using the Java Hashtable class.

    private Map<String,List<String>> cache = new Hashtable<>();
    
    /** Splits given string into a list of names and numbers. */
    private List<String> split(String string) {
        final List<String> cachedList = cache.get(string);
        if (cachedList != null)
            return cachedList;

        final List<String> list = new ArrayList<String>();

        ..... // scan into list

        
        cache.put(string, list);
        
        return list;
    }

You could also use HashMap for this. I use Hashtable when I know that there will be no null values in that map, in particular, when I want to detect putting null values, because this wouldn't make sense here. Thus using Hashtable is an implicit assertion.

Binding the cache to the Comparator instance makes it safe against error-prone usage. Precondition is that comparators are not cached and are always constructed newly (is a stateful comparator!).

Here is the benchmark after I applied this:

Alphabetical comparator yields 44 millis
PoolPaourComparator yields 708 millis
NaturalSortComparator yields 566 millis
NaturalSortComparator2 yields 1637 millis

It went down from 2.5 seconds to just 0.5 seconds!

Making Things Short

When I want to break loops, I need to implement dynamic iterators that do not read more than needed. This is what I did in my first performance tuning attempt. And it made the sorting two times faster.

Now the challenge appears to combine this with caching. When I tried it out, I found that caching stateful objects like Iterator instances is not recommendable in many situations. I got following error message from Java's TimSort:

Comparison method violates its general contract

This happened when a string was several times in the list to sort, and the second instance of the string got the same character-Iterator instance from cache as the first, and these two were compared to each other. As you can imagine, using the same iterator for two string representations at the same time does not work.

I tried to fix this bug by using System.identityHashCode(string) as hashing key. But then I dropped this strategy, because it turned out that caching the string-parts made up 99 % of the performance benefit. Splitting them only on demand and caching the Iterators made the code much more complicated and did not give a justifying result.

Remove Unneeded Things

I do not find much sense in distinguishing between letters and separators in a natural-sort comparator. Maybe I haven't seen certain use cases. But for now, I removed any code that made a distinction between separators and letters. I just scan for numbers and treat them according to their nature. Anything else is done alfabetically.

As a special tuning action I tried to not convert strings to numbers as long as possible. Fact is that you can compare numbers to each other by just comparing their length (assuming you removed leading zeros), and this does not require the (expensive) conversion of string to number.
But I also gave up this strategy. Again it made the code much more complex, and after some investigations I found out that although this optimization was used in fact, finally always the number was parsed anyway, so why not parse it right from start.

Result: NaturalSortComparator4

Following comparator can be configured to treat spaces to be significant, default it doesn't (ignores spaces). And it can be configured to compare case-sensitive (default is case-insensitive).

All compare-logic now is done in the Part class implementation (representing a string-split-part). It implements Java's Comparable interface, and it holds a numeric representation of any number-string for a fast comparison. Splitting strings is done in first place, because caching gained much more performance than doing the splits lazily in long and complicated code.

Here it is. It is a non-static inner class, to have access to the caseSensitive constructor parameter of its enclosing Comparator instance.

    /**
     * String part that implements a comparison according to its nature.
     */
    private class Part implements Comparable<Part>
    {
        private final String content;
        private final int leadingZeros;
        private final Long number;
        
        Part(boolean isNumber, String content) {
            int i = 0;
            if (isNumber)   // remove and count leading zeros when number
                while (i < content.length() && content.charAt(i) == '0')
                    i++;

            this.content = (i == 0) ? content : content.substring(i);
            this.leadingZeros = i;
            this.number = isNumber ? Long.valueOf(content) : null;
        }
        
        /**
         * Compares this part with given one, according to their nature
         * either as numbers or others. This has to be fast.
         */
        @Override
        public int compareTo(Part other) {
            if (number != null && other.number != null)  {
                final int result = number.compareTo(other.number);
                if (result != 0)
                    return result;
                
                return Integer.compare(leadingZeros, other.leadingZeros);
            }
            
            return caseSensitive
                    ? content.compareTo(other.content)
                    : content.compareToIgnoreCase(other.content);
        }
    }

The number field is evaluated in constructor when the Part is considered to be a number. Long.valueOf(content) would throw an exception when not. The count of leading zeros decides about a comparison when the numbers are equal: the more zeros are present, the more the string goes to end of list. The number then is used in compareTo() implementation of interface Comparator.
The inner class sees the field caseSensitive of its enclosing class, so it can do an according compareTo() or compareToIgnoreCase() call when the part is not a number.

Here is its enclosing class, called NaturalSortComparator4. All it needs to import comes from java.util.*.

public class NaturalSortComparator4 implements Comparator<String>
{
    
    ..... // inner class Part goes here
    
    
    private final boolean caseSensitive;
    private boolean ignoreSpaces;
    
    private Map<String,List<Part>> cache = new Hashtable<>();
    
    private final StringBuilder sb = new StringBuilder();

    
    /** Comparator that compares case-insensitive. */
    public NaturalSortComparator4() {
        this(false);
    }
    
    /** Comparator that treats case-sensitivity according to given parameter. */
    public NaturalSortComparator4(boolean caseSensitive) {
        this(caseSensitive, true);
    }
    
    /** Comparator that treats case-sensitivity according to given parameter, and optionally does not ignore spaces. */
    public NaturalSortComparator4(boolean caseSensitive, boolean ignoreSpaces) {
        this.caseSensitive = caseSensitive;
        this.ignoreSpaces = ignoreSpaces;
    }
    
    
    /**
     * Splits the given strings and compares them
     * by delegating to the Comparable parts.
     */
    @Override
    public int compare(String string1, String string2) {
        final Iterator<Part> iterator1 = split(string1).iterator();
        final Iterator<Part> iterator2 = split(string2).iterator();
        
        while (iterator1.hasNext() || iterator2.hasNext()) {
            // first has no more parts -> comes first
            if ( ! iterator1.hasNext() && iterator2.hasNext())
                return -1;
            
            // second has no more parts -> comes first
            if (iterator1.hasNext() && ! iterator2.hasNext())
                return 1;

            // compare next parts
            int result = iterator1.next().compareTo(iterator2.next());
            if (result != 0)    // found difference
                return result;
        }
        
        return 0;   // are equal
    }

    
    /** Splits given string into a list of numbers and other parts. */
    private List<Part> split(String string) {
        final List<Part> cachedList = cache.get(string);
        if (cachedList != null) // cache results to be fast
            return cachedList;
        
        final List<Part> list = new ArrayList<>();
        boolean digits = false;
        
        for (int i = 0; i < string.length(); i++) {
            final char c = string.charAt(i);
            final boolean ignore = (ignoreSpaces && Character.isWhitespace(c));
            final boolean isDigit = (ignore == false && Character.isDigit(c));
            
            if (isDigit != digits)    { // state change
                closeCurrentPart(list, digits);
                digits = isDigit;
            }
            
            if (ignore == false)
                sb.append(c);
        }
        closeCurrentPart(list, digits);
        
        cache.put(string, list);
        return list;
    }

    private void closeCurrentPart(List<Part> list, boolean digits) {
        if (sb.length() > 0)    { // close current string part
            list.add(new Part(digits, sb.toString()));
            sb.setLength(0);
        }
    }

}

The compare() method contains just the handling of the two involved iterators, nothing else. All comparison logic moved to class Part, and should be maintained there.

The split() method has become even simpler than it was before, but it now uses caching. It does not distinguish between letters and separators any more (add it there when you need it).

Here is my final benchmark:

Alphabetical comparator yields 44 millis
PoolPaourComparator yields 708 millis
NaturalSortComparator4 yields 339 millis

As copy & paste convenience I added the fold below.

▶Click on left-side arrow to see the full source code of the tuned natural-sort comparator.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

/**
 * Implements a natural sort order where numbers within names
 * are detected and evaluated as numbers, not strings.
 * Thus "a1", "a10", "a2" would be sorted as "a1", "a2", "a10".
 * See unit test for more examples.
 * 
 * @author fritzthecat Oct 2015
 */
public class NaturalSortComparator4 implements Comparator<String>
{
    /**
     * String part that implements a comparison according to its nature.
     */
    private class Part implements Comparable<Part>
    {
        private final String content;
        private final int leadingZeros;
        private final Long number;
        
        Part(boolean isNumber, String content) {
            int i = 0;
            if (isNumber)   // remove and count leading zeros when number
                while (i < content.length() && content.charAt(i) == '0')
                    i++;

            this.content = (i == 0) ? content : content.substring(i);
            this.leadingZeros = i;
            this.number = isNumber ? Long.valueOf(content) : null;
        }
        
        /**
         * Compares this part with given one, according to their nature
         * either as numbers or others. This has to be fast.
         */
        @Override
        public int compareTo(Part other) {
            if (number != null && other.number != null)  {
                final int result = number.compareTo(other.number);
                if (result != 0)
                    return result;
                
                return Integer.compare(leadingZeros, other.leadingZeros);
            }
            
            return caseSensitive
                    ? content.compareTo(other.content)
                    : content.compareToIgnoreCase(other.content);
        }
    }
    
    
    private final boolean caseSensitive;
    private boolean ignoreSpaces;
    
    private Map<String,List<Part>> cache = new Hashtable<>();
    
    private final StringBuilder sb = new StringBuilder();

    
    /** Comparator that compares case-insensitive. */
    public NaturalSortComparator4() {
        this(false);
    }
    
    /** Comparator that treats case-sensitivity according to given parameter. */
    public NaturalSortComparator4(boolean caseSensitive) {
        this(caseSensitive, true);
    }
    
    /** Comparator that treats case-sensitivity according to given parameter, and optionally does not ignore spaces. */
    public NaturalSortComparator4(boolean caseSensitive, boolean ignoreSpaces) {
        this.caseSensitive = caseSensitive;
        this.ignoreSpaces = ignoreSpaces;
    }
    
    
    /**
     * Splits the given strings and compares them
     * by delegating to the Comparable parts.
     */
    @Override
    public int compare(String string1, String string2) {
        final Iterator<Part> iterator1 = split(string1).iterator();
        final Iterator<Part> iterator2 = split(string2).iterator();
        
        while (iterator1.hasNext() || iterator2.hasNext()) {
            // first has no more parts -> comes first
            if ( ! iterator1.hasNext() && iterator2.hasNext())
                return -1;
            
            // second has no more parts -> comes first
            if (iterator1.hasNext() && ! iterator2.hasNext())
                return 1;

            // compare next parts
            int result = iterator1.next().compareTo(iterator2.next());
            if (result != 0)    // found difference
                return result;
        }
        
        return 0;   // are equal
    }

    
    /** Splits given string into a list of numbers and other parts. */
    private List<Part> split(String string) {
        final List<Part> cachedList = cache.get(string);
        if (cachedList != null) // cache results to be fast
            return cachedList;
        
        final List<Part> list = new ArrayList<>();
        boolean digits = false;
        
        for (int i = 0; i < string.length(); i++) {
            final char c = string.charAt(i);
            final boolean ignore = (ignoreSpaces && Character.isWhitespace(c));
            final boolean isDigit = (ignore == false && Character.isDigit(c));
            
            if (isDigit != digits)    { // state change
                closeCurrentPart(list, digits);
                digits = isDigit;
            }
            
            if (ignore == false)
                sb.append(c);
        }
        closeCurrentPart(list, digits);
        
        cache.put(string, list);
        return list;
    }

    private void closeCurrentPart(List<Part> list, boolean digits) {
        if (sb.length() > 0)    { // close current string part
            list.add(new Part(digits, sb.toString()));
            sb.setLength(0);
        }
    }

}

ɔ⃝ Fritz Ritzberger, 2015-10-11