Add speed for alpha numeric sorting

1 files changed, 84 insertions, 46 deletions

diff --git a/MediaBrowser.Controller/Sorting/AlphanumComparator.cs b/MediaBrowser.Controller/Sorting/AlphanumComparator.cs
index 65dc120ca..de7f72d1c 100644
--- a/MediaBrowser.Controller/Sorting/AlphanumComparator.cs
+++ b/MediaBrowser.Controller/Sorting/AlphanumComparator.cs
@@ -1,94 +1,132 @@
+#nullable enable
+
+using System;
 using System.Collections.Generic;
-using System.Text;
-using MediaBrowser.Controller.Sorting;
 
 namespace MediaBrowser.Controller.Sorting
 {
-    public class AlphanumComparator : IComparer<string>
+    public class AlphanumComparator : IComparer<string?>
     {
-        public static int CompareValues(string s1, string s2)
+        public static int CompareValues(string? s1, string? s2)
         {
-            if (s1 == null || s2 == null)
+            if (s1 == null && s2 == null)
             {
                 return 0;
             }
+            else if (s1 == null)
+            {
+                return -1;
+            }
+            else if (s2 == null)
+            {
+                return 1;
+            }
 
-            int thisMarker = 0, thisNumericChunk = 0;
-            int thatMarker = 0, thatNumericChunk = 0;
+            int len1 = s1.Length;
+            int len2 = s2.Length;
 
-            while ((thisMarker < s1.Length) || (thatMarker < s2.Length))
+            // Early return for empty strings
+            if (len1 == 0 && len2 == 0)
             {
-                if (thisMarker >= s1.Length)
+                return 0;
+            }
+            else if (len1 == 0)
+            {
+                return -1;
+            }
+            else if (len2 == 0)
+            {
+                return 1;
+            }
+
+            int pos1 = 0;
+            int pos2 = 0;
+
+            do
+            {
+                int start1 = pos1;
+                int start2 = pos2;
+
+                bool isNum1 = char.IsDigit(s1[pos1++]);
+                bool isNum2 = char.IsDigit(s2[pos2++]);
+
+                while (pos1 < len1 && char.IsDigit(s1[pos1]) == isNum1)
                 {
-                    return -1;
+                    pos1++;
                 }
-                else if (thatMarker >= s2.Length)
+
+                while (pos2 < len2 && char.IsDigit(s2[pos2]) == isNum2)
                 {
-                    return 1;
+                    pos2++;
                 }
-                char thisCh = s1[thisMarker];
-                char thatCh = s2[thatMarker];
 
-                var thisChunk = new StringBuilder();
-                var thatChunk = new StringBuilder();
-                bool thisNumeric = char.IsDigit(thisCh), thatNumeric = char.IsDigit(thatCh);
+                var span1 = s1.AsSpan(start1, pos1 - start1);
+                var span2 = s2.AsSpan(start2, pos2 - start2);
 
-                while (thisMarker < s1.Length && char.IsDigit(thisCh) == thisNumeric)
+                if (isNum1 && isNum2)
                 {
-                    thisChunk.Append(thisCh);
-                    thisMarker++;
-
-                    if (thisMarker < s1.Length)
+                    // Trim leading zeros so we can compare the length
+                    // of the strings to find the largest number
+                    span1 = span1.TrimStart('0');
+                    span2 = span2.TrimStart('0');
+                    var span1Len = span1.Length;
+                    var span2Len = span2.Length;
+                    if (span1Len < span2Len)
                     {
-                        thisCh = s1[thisMarker];
+                        return -1;
                     }
-                }
-
-                while (thatMarker < s2.Length && char.IsDigit(thatCh) == thatNumeric)
-                {
-                    thatChunk.Append(thatCh);
-                    thatMarker++;
-
-                    if (thatMarker < s2.Length)
+                    else if (span1Len > span2Len)
                     {
-                        thatCh = s2[thatMarker];
+                        return 1;
                     }
-                }
+                    else if (span1Len >= 20) // Number is probably too big for a ulong
+                    {
+                        // Trim all the first digits that are the same
+                        int i = 0;
+                        while (i < span1Len && span1[i] == span2[i])
+                        {
+                            i++;
+                        }
 
+                        // If there are no more digits it's the same number
+                        if (i == span1Len)
+                        {
+                            continue;
+                        }
 
-                // If both chunks contain numeric characters, sort them numerically
-                if (thisNumeric && thatNumeric)
-                {
-                    if (!int.TryParse(thisChunk.ToString(), out thisNumericChunk)
-                        || !int.TryParse(thatChunk.ToString(), out thatNumericChunk))
+                        // Only need to compare the most significant digit
+                        span1 = span1.Slice(i, 1);
+                        span2 = span2.Slice(i, 1);
+                    }
+
+                    if (!ulong.TryParse(span1, out var num1)
+                        || !ulong.TryParse(span2, out var num2))
                     {
                         return 0;
                     }
-
-                    if (thisNumericChunk < thatNumericChunk)
+                    else if (num1 < num2)
                     {
                         return -1;
                     }
-
-                    if (thisNumericChunk > thatNumericChunk)
+                    else if (num1 > num2)
                     {
                         return 1;
                     }
                 }
                 else
                 {
-                    int result = thisChunk.ToString().CompareTo(thatChunk.ToString());
+                    int result = span1.CompareTo(span2, StringComparison.InvariantCulture);
                     if (result != 0)
                     {
                         return result;
                     }
                 }
+            } while (pos1 < len1 && pos2 < len2);
 
-            }
-
-            return 0;
+            return len1 - len2;
         }
 
+        /// <inheritdoc />
         public int Compare(string x, string y)
         {
             return CompareValues(x, y);