follow the ICU User Guide recommendation to optimize the perf of InvariantCultureIgnoreCase on Linux (#24889)

* follow the ICU User Guide recommendation to optimize the perf of InvariantCultureIgnoreCase on Linux:

1. try to guess the max size and call ucol_getSortKey just once
2. if the buffer is not big enough, call the method again providing the actual sort key length

* handle 0 case

* handle integer overflow

* shorten the time the buffers are pinned

* use the cheapest pinning

* code review fixes: don't use variable length stackalloc, don't copy text from docs (licensing) + don't try to go with the fast path when it would require allocating more managed memory for big strings

* simplify the condition

1 files changed, 36 insertions, 17 deletions

diff --git a/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.Unix.cs b/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.Unix.cs
index c915c9d227..cea2fcf88d 100644
--- a/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.Unix.cs
+++ b/src/System.Private.CoreLib/shared/System/Globalization/CompareInfo.Unix.cs
@@ -852,33 +852,52 @@ namespace System.Globalization
                 return 0;
             }
 
-            fixed (char* pSource = source)
-            {
-                int sortKeyLength = Interop.Globalization.GetSortKey(_sortHandle, pSource, source.Length, null, 0, options);
+            // according to ICU User Guide the performance of ucol_getSortKey is worse when it is called with null output buffer
+            // the solution is to try to fill the sort key in a temporary buffer of size equal 4 x string length
+            // 1MB is the biggest array that can be rented from ArrayPool.Shared without memory allocation
+            int sortKeyLength = (source.Length > 1024 * 1024 / 4) ? 0 : 4 * source.Length;
 
-                byte[]? borrowedArr = null;
-                Span<byte> span = sortKeyLength <= 512 ?
-                    stackalloc byte[512] :
-                    (borrowedArr = ArrayPool<byte>.Shared.Rent(sortKeyLength));
+            byte[]? borrowedArray = null;
+            Span<byte> sortKey = sortKeyLength <= 1024
+                ? stackalloc byte[1024]
+                : (borrowedArray = ArrayPool<byte>.Shared.Rent(sortKeyLength));
 
-                fixed (byte* pSortKey = &MemoryMarshal.GetReference(span))
+            fixed (char* pSource = &MemoryMarshal.GetReference(source))
+            {
+                fixed (byte* pSortKey = &MemoryMarshal.GetReference(sortKey))
                 {
-                    if (Interop.Globalization.GetSortKey(_sortHandle, pSource, source.Length, pSortKey, sortKeyLength, options) != sortKeyLength)
+                    sortKeyLength = Interop.Globalization.GetSortKey(_sortHandle, pSource, source.Length, pSortKey, sortKey.Length, options);
+                }
+
+                if (sortKeyLength > sortKey.Length) // slow path for big strings
+                {
+                    if (borrowedArray != null)
                     {
-                        throw new ArgumentException(SR.Arg_ExternalException);
+                        ArrayPool<byte>.Shared.Return(borrowedArray);
                     }
-                }
 
-                int hash = Marvin.ComputeHash32(span.Slice(0, sortKeyLength), Marvin.DefaultSeed);
+                    sortKey = (borrowedArray = ArrayPool<byte>.Shared.Rent(sortKeyLength));
 
-                // Return the borrowed array if necessary.
-                if (borrowedArr != null)
-                {
-                    ArrayPool<byte>.Shared.Return(borrowedArr);
+                    fixed (byte* pSortKey = &MemoryMarshal.GetReference(sortKey))
+                    {
+                        sortKeyLength = Interop.Globalization.GetSortKey(_sortHandle, pSource, source.Length, pSortKey, sortKey.Length, options);
+                    }
                 }
+            }
+
+            if (sortKeyLength == 0 || sortKeyLength > sortKey.Length) // internal error (0) or a bug (2nd call failed) in ucol_getSortKey
+            {
+                throw new ArgumentException(SR.Arg_ExternalException);
+            }
+
+            int hash = Marvin.ComputeHash32(sortKey.Slice(0, sortKeyLength), Marvin.DefaultSeed);
 
-                return hash;
+            if (borrowedArray != null)
+            {
+                ArrayPool<byte>.Shared.Return(borrowedArray);
             }
+
+            return hash;
         }
 
         private static CompareOptions GetOrdinalCompareOptions(CompareOptions options)