Skip to content

Instantly share code, notes, and snippets.

@dnickless
Created September 11, 2017 19:28
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 dnickless/eb4807d698b7032b625a8d04794e90d8 to your computer and use it in GitHub Desktop.
Save dnickless/eb4807d698b7032b625a8d04794e90d8 to your computer and use it in GitHub Desktop.
Compares the performance between the latest IndexOfAny implementation for two chars to test with a 4x unrolled version
using System;
using System.Diagnostics;
namespace StringPerformance
{
class Program
{
private static string _s;
static void Main(string[] args)
{
TestCorrectness();
_s = "Hello World Hello World Hello World Hello World Hello World Hello World Hello World";
Stopwatch sw = Stopwatch.StartNew();
int y = 0;
for (int i = 0; i < 10000000; i++)
{
// 4x unrolled using same pattern with goto as IndexOf() and LastIndexOf()
y = IndexOfAnyNew('a', 'b', 0, _s.Length);
}
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds + " " + y);
sw.Restart();
for (int i = 0; i < 10000000; i++)
{
// two times unrolled/current
y = IndexOfAny('a', 'b', 0, _s.Length);
}
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds + " " + y);
}
private static void TestCorrectness()
{
var strings = new string[] { string.Empty, "x", "test short", "test long test long test long test long test long test long test long test long test long test long test long test long test long test long test long test long test long test long test long " };
var chars = new char[] { 'a', 'b', 'c', 't', 'x', '\0', '0' };
foreach (var s in strings)
{
_s = s;
for (var i = 0; i < chars.Length - 1; i++)
{
if (IndexOfAny(chars[i], chars[i + 1], 0, s.Length) != IndexOfAnyNew(chars[i], chars[i + 1], 0, s.Length))
{
throw new Exception("implementations not matching");
}
}
}
}
public static unsafe int IndexOfAny(char value1, char value2, int startIndex, int count)
{
fixed (char* pChars = _s)
{
char* pCh = pChars + startIndex;
while (count > 0)
{
char c = *pCh;
if (c == value1 || c == value2)
return (int)(pCh - pChars);
// Possibly reads outside of count and can include null terminator
// Handled in the return logic
c = *(pCh + 1);
if (c == value1 || c == value2)
return count == 1 ? -1 : (int)(pCh - pChars) + 1;
pCh += 2;
count -= 2;
}
return -1;
}
}
public static unsafe int IndexOfAnyNew(char value1, char value2, int startIndex, int count)
{
fixed (char* pChars = _s)
{
char* pCh = pChars + startIndex;
while (count >= 4)
{
char c = *pCh;
if (c == value1 || c == value2) goto ReturnIndex;
c = *(pCh + 1);
if (c == value1 || c == value2) goto ReturnIndex1;
c = *(pCh + 2);
if (c == value1 || c == value2) goto ReturnIndex2;
c = *(pCh + 3);
if (c == value1 || c == value2) goto ReturnIndex3;
count -= 8;
pCh += 8;
}
while (count > 0)
{
char c = *pCh;
if (c == value1 || c == value2) goto ReturnIndex;
count--;
pCh++;
}
return -1;
ReturnIndex3: pCh++;
ReturnIndex2: pCh++;
ReturnIndex1: pCh++;
ReturnIndex:
return (int)(pCh - pChars);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment