Last active
October 25, 2024 05:12
-
-
Save aarondandy/820a2d900f414879a3e6fbf4ec471e7c to your computer and use it in GitHub Desktop.
Just messing around, seeing how to reverse strings faster. Add benchmarkdotnet. Use C# 7.3, Core2.1+. Build Release.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Buffers; | |
using System.Collections.Generic; | |
using System.Net.Http; | |
using System.Runtime.CompilerServices; | |
using System.Runtime.InteropServices; | |
using System.Text; | |
using System.Threading; | |
using BenchmarkDotNet.Attributes; | |
using BenchmarkDotNet.Running; | |
namespace ReverseStringBenchmark | |
{ | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
BenchmarkRunner.Run<ReverseTests>(); | |
} | |
} | |
[SimpleJob, RankColumn, MemoryDiagnoser] | |
public class ReverseTests | |
{ | |
static Lazy<string> SomeLongBitOfText = new Lazy<string>(() => | |
new HttpClient() | |
.GetStringAsync(@"https://raw.githubusercontent.com/hunspell/hunspell/6014af96eb5830103261b803ed9b90fc5d360440/tests/suggestiontest/List_of_common_misspellings.txt") | |
.GetAwaiter().GetResult()); | |
private string[] textValues; | |
//[Params(1, 100, 1_000_000)] | |
public int TestIterations { get; set; } = 100; | |
[GlobalSetup] | |
public void Setup() | |
{ | |
textValues = SomeLongBitOfText.Value.Split(", \t\r\n".ToCharArray(), StringSplitOptions.RemoveEmptyEntries); | |
} | |
[Benchmark(Baseline = true)] | |
public void ToCharArrayReverse() | |
{ | |
for (var iteration = 0; iteration < TestIterations; iteration++) | |
{ | |
var textValue = textValues[iteration % textValues.Length]; | |
var result = ToCharArrayReverse(textValue); | |
} | |
} | |
static string ToCharArrayReverse(string textValue) | |
{ | |
var charArray = textValue.ToCharArray(); | |
Array.Reverse(charArray); | |
return new string(charArray); | |
} | |
[Benchmark] | |
public void StringBuilderReverse() | |
{ | |
for (var iteration = 0; iteration < TestIterations; iteration++) | |
{ | |
var textValue = textValues[iteration % textValues.Length]; | |
var result = StringBuilderReverse(textValue); | |
} | |
} | |
static string StringBuilderReverse(string textValue) | |
{ | |
if (textValue == null || textValue.Length <= 1) | |
{ | |
return textValue; | |
} | |
var builder = new StringBuilder(textValue); | |
var swapOtherIndexOffset = textValue.Length - 1; | |
var stopIndex = textValue.Length / 2; | |
for (int i = 0, otherIndex = swapOtherIndexOffset; i < stopIndex; i++, otherIndex--) | |
{ | |
var c = builder[i]; | |
builder[i] = builder[otherIndex]; | |
builder[otherIndex] = c; | |
} | |
return builder.ToString(); | |
} | |
[Benchmark] | |
public void StringBuilderPoolReverse() | |
{ | |
for (var iteration = 0; iteration < TestIterations; iteration++) | |
{ | |
var textValue = textValues[iteration % textValues.Length]; | |
var result = StringBuilderPoolReverse(textValue); | |
} | |
} | |
static string StringBuilderPoolReverse(string textValue) | |
{ | |
if (textValue == null || textValue.Length <= 1) | |
{ | |
return textValue; | |
} | |
var rented = Interlocked.Exchange(ref PooledStringBuilder, null); | |
if (rented == null || rented.Capacity < textValue.Length) | |
{ | |
rented = new StringBuilder(textValue.Length); | |
} | |
else | |
{ | |
rented.Clear(); | |
} | |
for (var i = textValue.Length - 1; i >= 0; i--) | |
{ | |
rented.Append(textValue[i]); | |
} | |
var result = rented.ToString(); | |
Interlocked.CompareExchange(ref PooledStringBuilder, rented, null); | |
return result; | |
} | |
[Benchmark] | |
public void MemoryPoolReverse() | |
{ | |
for (var iteration = 0; iteration < TestIterations; iteration++) | |
{ | |
var textValue = textValues[iteration % textValues.Length]; | |
var result = MemoryPoolReverse(textValue); | |
} | |
} | |
static string MemoryPoolReverse(string textValue) | |
{ | |
using (var mo = MemoryPool<char>.Shared.Rent(textValue.Length)) | |
{ | |
var buffer = mo.Memory.Span.Slice(0, textValue.Length); | |
for (int i = 0, sourceIndex = textValue.Length - 1; i < buffer.Length; i++, sourceIndex--) | |
{ | |
buffer[i] = textValue[sourceIndex]; | |
} | |
return buffer.ToString(); | |
} | |
} | |
[Benchmark] | |
public void HomeBakedShittyMemoryPoolReverse() | |
{ | |
for (var iteration = 0; iteration < TestIterations; iteration++) | |
{ | |
var textValue = textValues[iteration % textValues.Length]; | |
var result = HomeBakedShittyMemoryPoolReverse(textValue); | |
} | |
} | |
static string HomeBakedShittyMemoryPoolReverse(string textValue) | |
{ | |
var rented = Interlocked.Exchange(ref ShittyMemoryPool, null); | |
if (rented == null || rented.Length < textValue.Length) | |
{ | |
rented = new char[textValue.Length]; | |
} | |
for (int i = 0, sourceIndex = textValue.Length - 1; i < textValue.Length; i++, sourceIndex--) | |
{ | |
rented[i] = textValue[sourceIndex]; | |
} | |
var result = new string(rented, 0, textValue.Length); | |
Interlocked.CompareExchange(ref ShittyMemoryPool, rented, null); | |
return result; | |
} | |
[Benchmark] | |
public void HomeBakedShittyMemoryPoolSpanReverse() | |
{ | |
for (var iteration = 0; iteration < TestIterations; iteration++) | |
{ | |
var textValue = textValues[iteration % textValues.Length]; | |
var result = HomeBakedShittyMemoryPoolSpanReverse(textValue); | |
} | |
} | |
static string HomeBakedShittyMemoryPoolSpanReverse(string textValue) | |
{ | |
var rented = Interlocked.Exchange(ref ShittyMemoryPool, null); | |
if (rented == null || rented.Length < textValue.Length) | |
{ | |
rented = new char[textValue.Length]; | |
} | |
var buffer = rented.AsSpan().Slice(0, textValue.Length); | |
for (int i = 0, sourceIndex = textValue.Length - 1; i < buffer.Length; i++, sourceIndex--) | |
{ | |
buffer[i] = textValue[sourceIndex]; | |
} | |
var result = buffer.ToString(); | |
Interlocked.CompareExchange(ref ShittyMemoryPool, rented, null); | |
return result; | |
} | |
[Benchmark] | |
public void CreateReverse() | |
{ | |
for (var iteration = 0; iteration < TestIterations; iteration++) | |
{ | |
var textValue = textValues[iteration % textValues.Length]; | |
var result = CreateReverse(textValue); | |
} | |
} | |
static string CreateReverse(string textValue) => | |
string.Create(textValue.Length, textValue, CreateReverse_DoerThingy); | |
static void CreateReverse_DoerThingy(Span<char> buffer, string original) | |
{ | |
for (int index = 0, reverseIndex = buffer.Length - 1; index < buffer.Length; index++, reverseIndex--) | |
{ | |
buffer[index] = original[reverseIndex]; | |
} | |
} | |
[Benchmark] | |
public void CreateReverseButABitMoreSpanny() | |
{ | |
for (var iteration = 0; iteration < TestIterations; iteration++) | |
{ | |
var textValue = textValues[iteration % textValues.Length]; | |
var result = CreateReverseButABitMoreSpanny(textValue); | |
} | |
} | |
static string CreateReverseButABitMoreSpanny(string textValue) => | |
string.Create(textValue.Length, textValue.AsMemory(), CreateReverseButABitMoreSpanny_DoerThingy); | |
static void CreateReverseButABitMoreSpanny_DoerThingy(Span<char> buffer, ReadOnlyMemory<char> original) | |
{ | |
var originalSpan = original.Span; | |
for (int index = 0, reverseIndex = buffer.Length - 1; index < buffer.Length; index++, reverseIndex--) | |
{ | |
buffer[index] = originalSpan[reverseIndex]; | |
} | |
} | |
[Benchmark] | |
public void UnsafeMutableString() | |
{ | |
for (var iteration = 0; iteration < TestIterations; iteration++) | |
{ | |
var textValue = textValues[iteration % textValues.Length]; | |
var result = UnsafeMutableString(textValue); | |
} | |
} | |
unsafe static string UnsafeMutableString(string textValue) | |
{ | |
var newTextValue = new string(textValue); | |
var indexLimit = newTextValue.Length / 2; | |
fixed (char* p = newTextValue) | |
{ | |
for (int i = 0, otherI = newTextValue.Length - 1; i < indexLimit; i++, otherI--) | |
{ | |
var swap = p[i]; | |
p[i] = p[otherI]; | |
p[otherI] = swap; | |
} | |
} | |
return newTextValue; | |
} | |
[Benchmark] | |
public void UnsafeMutableSwapString() | |
{ | |
for (var iteration = 0; iteration < TestIterations; iteration++) | |
{ | |
var textValue = textValues[iteration % textValues.Length]; | |
var result = UnsafeMutableSwapString(textValue); | |
} | |
} | |
unsafe static string UnsafeMutableSwapString(string textValue) | |
{ | |
var newTextValue = new string(textValue); | |
var indexLimit = newTextValue.Length / 2; | |
fixed (char* p = newTextValue) | |
{ | |
for (int i = 0, otherI = newTextValue.Length - 1; i < indexLimit; i++, otherI--) | |
{ | |
Swap(ref p[i], ref p[otherI]); | |
} | |
} | |
return newTextValue; | |
} | |
[Benchmark] | |
public void UnsafeMutableSpanString() | |
{ | |
for (var iteration = 0; iteration < TestIterations; iteration++) | |
{ | |
var textValue = textValues[iteration % textValues.Length]; | |
var result = UnsafeMutableSpanString(textValue); | |
} | |
} | |
unsafe static string UnsafeMutableSpanString(string textValue) | |
{ | |
var newTextValue = new string(textValue); | |
fixed (char* p = newTextValue) | |
{ | |
new Span<char>(p, newTextValue.Length).Reverse(); | |
} | |
return newTextValue; | |
} | |
static char[] ShittyMemoryPool; | |
static StringBuilder PooledStringBuilder; | |
[MethodImpl(MethodImplOptions.AggressiveInlining)] | |
static void Swap(ref char a, ref char b) | |
{ | |
var temp = a; | |
a = b; | |
b = temp; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment