Skip to content

Instantly share code, notes, and snippets.

@aarondandy
Last active September 14, 2018 15:38
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save aarondandy/820a2d900f414879a3e6fbf4ec471e7c to your computer and use it in GitHub Desktop.
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.
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