Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
[Config(typeof(Config))]
public class Program
{
static void Main(string[] args)
{
var summary = BenchmarkRunner.Run<Program>();
}
private class Config : ManualConfig
{
public Config()
{
Add(Job.Clr.WithLaunchCount(1));
Add(new GCDiagnoser());
}
}
[Params("Foo;Bar", "Foo;FooBar;Whatever", "Bar;blaat;foo", "blaat;foo;Bar", "foo;Bar;Blaat", "foo;FooBar;Blaat",
"Bar1;Bar2;Bar3;Bar4;Bar", "Bar1;Bar2;Bar3;Bar4;NoMatch", "Foo;FooBar;Whatever", "Some;Other;Really;Interesting;Tokens")]
public string Value { get; set; }
public string Match = "Bar";
private static char [] delimeter = new [] { ';' };
[Benchmark(Baseline = true)]
public bool StringSplit()
{
// To make is a fair comparision!
if (string.IsNullOrEmpty(Match)) return false;
if (string.IsNullOrEmpty(Value)) return false;
var tokens = Value.Split(delimeter);
foreach (var token in tokens)
{
if (token == Match)
return true;
}
return false;
}
[Benchmark]
public bool ContainsToken()
{
return ContainsToken(Value, Match);
}
[Benchmark]
public bool ContainsTokenXoofx()
{
return ContainsTokenXoofx(Value, Match);
}
[Benchmark]
public bool ContainsTokenXoofxUnsafe()
{
return ContainsTokenXoofxUnsafe(Value, Match);
}
[Benchmark]
public bool ContainsTokenHellBrick()
{
return ContainsTokenHellBrick(Value, Match);
}
[Benchmark]
public bool ContainsTokenMonty()
{
return ContainsTokenMonty(Value, Match);
}
/// <summary>
/// Code taken from https://twitter.com/Nick_Craver/status/722741298575319040
/// Checks whether the *entire* token exists, correctly handling seperators
/// (optional at start and end) so: "Foo;Bar" contains "Bar", but
/// "Foo;FooBar;Whatever" does not
/// </summary>
public static bool ContainsToken(string value, string token, char delimiter = ';')
{
if (string.IsNullOrEmpty(token)) return false;
if (string.IsNullOrEmpty(value)) return false;
int lastIndex = -1, idx, endIndex = value.Length - token.Length, tokenLength = token.Length;
while ((idx = value.IndexOf(token, lastIndex + 1)) > lastIndex)
{
lastIndex = idx;
if ((idx == 0 || (value[idx - 1] == delimiter))
&& (idx == endIndex || (value[idx + tokenLength] == delimiter)))
{
return true;
}
}
return false;
}
// See https://gist.github.com/mattwarren/f0594a9f3afa9377a4bbc2bcf8e573c5#gistcomment-1757392
public static bool ContainsTokenXoofx(string value, string token, char delimiter = ';')
{
if (string.IsNullOrEmpty(token)) return false;
if (string.IsNullOrEmpty(value)) return false;
int length = value.Length;
int tokenLength = token.Length;
for (int i = 0; i < length; i++)
{
for (int j = 0; j < tokenLength; j++, i++)
{
if (i >= length || value[i] != token[j])
{
goto next;
}
}
if ((i == length || (i < length && value[i] == delimiter)))
{
return true;
}
next:
i = value.IndexOf(delimiter, i);
if (i < 0)
{
break;
}
}
return false;
}
public unsafe static bool ContainsTokenXoofxUnsafe(string value, string token, char delimiter = ';')
{
if (string.IsNullOrEmpty(token)) return false;
if (string.IsNullOrEmpty(value)) return false;
int length = value.Length;
int tokenLength = token.Length;
int i = 0;
fixed (char* pValue = value)
fixed (char* pToken = token)
while (true)
{
for (int j = 0; j < tokenLength; j++, i++)
{
if (i >= length || pValue[i] != pToken[j])
{
goto next;
}
}
if (i == length || pValue[i] == delimiter)
{
return true;
}
next:
i = value.IndexOf(delimiter, i) + 1;
if (i == 0)
{
break;
}
}
return false;
}
public static unsafe bool ContainsTokenHellBrick(string value, string token, char delimiter = ';')
{
if (string.IsNullOrEmpty(token)) return false;
if (string.IsNullOrEmpty(value)) return false;
int length = value.Length;
int tokenLength = token.Length;
int currentTokenOffset = 0;
int maxTokenOffset = length - tokenLength;
while (currentTokenOffset <= maxTokenOffset)
{
int nextDelimiterOffset = value.IndexOf(delimiter, currentTokenOffset);
if (nextDelimiterOffset < 0)
nextDelimiterOffset = length;
if (tokenLength == nextDelimiterOffset - currentTokenOffset)
{
for (int i = 0; i < tokenLength; i++)
{
if (value[currentTokenOffset + i] != token[i])
goto next;
}
return true;
}
next:
currentTokenOffset = nextDelimiterOffset + 1;
}
return false;
}
public static bool ContainsTokenMonty(string value, string token, char delimiter = ';')
{
// this code assumes you're running x64
// it _works_ regardless, but some ifdef junk for x32
// would be handy if you care about ideal x32 perf
const int charsPerLong = sizeof(long) / sizeof(char); // 4
const int charsPerInt = sizeof(int) / sizeof(char); // 2
const int bytesPerChar = sizeof(char) / sizeof(byte); // 2
if (string.IsNullOrEmpty(token)) return false;
if (string.IsNullOrEmpty(value)) return false;
var valueLength = value.Length;
var tokenLength = token.Length;
if (tokenLength > valueLength) return false;
int tokenLongs;
bool tokenTrailingInt, tokenTrailingChar;
{
var remainingChars = tokenLength;
tokenLongs = remainingChars / charsPerLong;
tokenTrailingInt = (tokenLength & 0x02) != 0;
tokenTrailingChar = (tokenLength & 0x01) != 0;
}
var tokenByteLength = tokenLength * bytesPerChar;
unsafe
{
fixed (char* valuePtr = value, tokenPtr = token)
{
var curValuePtr = valuePtr;
var endValuePtr = valuePtr + valueLength;
while (true)
{
// 8-byte steps
long* tokenLongPtr = (long*)tokenPtr;
{
for (var i = 0; i < tokenLongs; i++)
{
var tokenLong = *tokenLongPtr;
var valueLong = *((long*)curValuePtr);
if (tokenLong == valueLong)
{
// we have a match, continue
tokenLongPtr++;
curValuePtr += charsPerLong;
continue;
}
else
{
goto advanceToNextDelimiter;
}
}
}
// can only be 1 4-byte value, 'cause if there were 2 it'd have been handled in the 8-byte stride
int* tokenIntPtr = (int*)tokenLongPtr;
if (tokenTrailingInt)
{
var tokenInt = *tokenIntPtr;
var valueInt = *((int*)curValuePtr);
if (tokenInt == valueInt)
{
// we have a match, continue
tokenIntPtr++;
curValuePtr += charsPerInt;
}
else
{
goto advanceToNextDelimiter;
}
}
// likewise, only 1 2-byte value or it'd be handled in the 4-byte check
char* tokenCharPtr = (char*)tokenIntPtr;
if (tokenTrailingChar)
{
var tokenChar = *tokenCharPtr;
var valueChar = *curValuePtr;
if (tokenChar == valueChar)
{
// we have a match, continue
tokenCharPtr++;
curValuePtr++;
}
else
{
goto advanceToNextDelimiter;
}
}
// at this point, the full text of token has been matched, so we need to check if the _next_ char
// in value is a delimiter or the end of value
if (curValuePtr == endValuePtr || *curValuePtr == delimiter)
{
return true;
}
// in this case, we found a string that starts with value, but is not value
// "Foo" in "FooBar" for example
// advance here to skip the rest of whatever's before
// the next delimiter
advanceToNextDelimiter:
// our own IndexOf()-esque functionality
// at the end of this curValuePtr points to the
// character _after_ the next delimiter in the string
//
// not using IndexOf() is to save us the trouble
// of tracking additional state, or doing extra work,
// to move between the index-into-a-string world and
// our constantly-advancing-pointers world
while (true)
{
var curVal = *curValuePtr;
if (curVal == delimiter)
{
// got one!
curValuePtr++;
if (curValuePtr == endValuePtr)
{
// but there wasn't anything after it
return false;
}
break;
}
curValuePtr++;
if (curValuePtr == endValuePtr)
{
// no more delimiters
return false;
}
}
// we only need to do this check after a delimiter is advanced
// because this check _itself_ guarantees that we won't
// exceed the end of value before we're done comparing
// against token
var remainingBytesInValue = ((byte*)endValuePtr) - ((byte*)curValuePtr); // we do this bytes to save an op
if (remainingBytesInValue < tokenByteLength)
{
// not possible for token to fit in string, fail early
return false;
}
}
}
}
}
}

Another approach, perhaps less memory:

public static bool ContainsToken(string value, string token, char delimiter = ';')
{
    if (string.IsNullOrEmpty(token)) return false;
    if (string.IsNullOrEmpty(value)) return false;
    if (value.Equals(token)) return true;

    return value.StartsWith(token + delimiter) || value.EndsWith(delimiter + token) || 
            value.Contains(delimiter + token + delimiter);
}

(not tested)

That would give incorrect results. Did you mean &&?

No I think it should be or, as a string can't match both start and end if it only starts with the element

Bar;blaat;foo
blaat;foo;Bar
foo;Bar;Blaat
foo;FooBar;Blaat

I think it will find 'Bar;' in all but the last, which is correct? It does allocate though which is a bit sad, but perhaps less than the string split

(but I haven't ran it, just thought of the idea of how to do it this way. Another way is linear search for the delimiters once but that code is likely more complex than the one you have and thus not favorable)

Owner

mattwarren commented Apr 20, 2016

@FransBouma Give me 30 mins and I'll add your code and the extra test cases to the Benchmark.

void Main()
{
    Console.WriteLine(ContainsToken("Bar;blaat;foo", "Bar"));
    Console.WriteLine(ContainsToken("blaat;foo;Bar", "Bar"));
    Console.WriteLine(ContainsToken("foo;Bar;Blaat", "Bar"));
    Console.WriteLine(ContainsToken("foo;FooBar;Blaat", "Bar"));
}

public static bool ContainsToken(string value, string token, char delimiter = ';')
{
    if (string.IsNullOrEmpty(token)) return false;
    if (string.IsNullOrEmpty(value)) return false;
    if (value.Equals(token)) return true;

    return value.StartsWith(token + delimiter) || value.EndsWith(delimiter + token) || 
            value.Contains(delimiter + token + delimiter);
}

output
True
True
True
False

xoofx commented Apr 20, 2016

This one should be 5 times faster than split from my measurement (haven't dig into all edge cases though) with no allocations

public static bool ContainsTokenXoofx(string value, string token, char delimiter = ';')
{
    if (string.IsNullOrEmpty(token)) return false;
    if (string.IsNullOrEmpty(value)) return false;

    int length = value.Length;
    int tokenLength = token.Length;

    for (int i = 0; i < length; i++)
    {
        for (int j = 0; j < tokenLength; j++, i++)
        {
            if (i >= length || value[i] != token[j])
            {
                goto next;
            }
        }

        if ((i == length || (i < length && value[i] == delimiter)))
        {
            return true;
        }

        next:
        i = value.IndexOf(delimiter, i);
        if (i < 0)
        {
            break;
        }
    }

    return false;
}

xoofx commented Apr 20, 2016

Also, the i < length can be removed from if ((i == length || (i < length && value[i] == delimiter))), so simplify it to if (i == length || value[i] == delimiter)

@xoofx Neat! though I think updating 'i' in the for loop is a little dirty, better to use a while instead. Also, i can't be >= length so all those comparisons can be removed ;) (the IndexOf at the end at most returns Length-1 or -1, for which you test. )

Owner

mattwarren commented Apr 20, 2016

Here's the updated results, I'll let you draw your own conclusions :)

image

Whoa, my approach is really slow, thanks for testing this. I did expect some memory allocations but not this massive slowness. Hats off to Xoofx, clearly the fastest by far :)

xoofx commented Apr 20, 2016

Updated with a while special for @frankbouma 😉
Note that it still requires the test for i >= length inside the for(j) if token is longer than the last string to check, but is matching at least the full last entry (case like ContainsToken("Bar", "Barito"))

public static bool ContainsTokenXoofx(string value, string token, char delimiter = ';')
{
    if (string.IsNullOrEmpty(token)) return false;
    if (string.IsNullOrEmpty(value)) return false;

    int length = value.Length;
    int tokenLength = token.Length;

    int i = 0;
    while (true)
    {
        for (int j = 0; j < tokenLength; j++, i++)
        {
            if (i >= length || value[i] != token[j])
            {
                goto next;
            }
        }

        if (i == length || value[i] == delimiter)
        {
            return true;
        }

        next:
        i = value.IndexOf(delimiter, i) + 1;
        if (i == 0)
        {
            break;
        }
    }

    return false;
}

Just have say: this is awesome to see happen. I'm loving it.

Owner

mattwarren commented Apr 20, 2016

And if you prefer, here's a graph of the same numbers, the legend is messed up, but reading from L -> R it should be

ContainsToken, ContainsTokenFransBouma, ContainsTokenXoofx, StringSplit

program-barplot

Owner

mattwarren commented Apr 20, 2016

Whoa, my approach is really slow, thanks for testing this.

@FransBouma When you say really slow, you mean that it's roughly 250 billionths of a second slower than @xoofx's version ;) So I wouldn't be too hard on yourself!!

nzall commented Apr 20, 2016

I am impressed that xoofx managed to implement it that efficiently. One thing I'm not too keen on is the goto, though. Is there really no way to avoid that? I think there is a way to get rid of that entire for(j) loop, even, so you don't need a goto.

@xoofx: Oh right! Totally overlooked that edge case where the i can indeed go outside the range! I overlooked the i++ in the inner forloop. Thanks for the 'while', I can stop twitching now ;)

@mattwarren: Heh if you bring it that way ;)

Owner

mattwarren commented Apr 20, 2016

Heh if you bring it that way ;)

@FransBouma Sometimes it's good to have perspective :)

@mattwarren which library contains GCDiagnoser?

@NickCraver @mattwarren Does StringComparison.CurrentCulture have the desired semantics here? I'm curious how passing StringComparison.Ordinal would impact things...

Owner

mattwarren commented Apr 20, 2016

@maggarwal You need the BenchmarkDotNet.Diagnostics package. It'll be available as a NuGet package soon, currently you have to build from source if you want it (https://github.com/PerfDotNet/BenchmarkDotNet)

Note in regards to my previous comment, @NickCraver's version and @FransBouma's are CurrentCulture while @xoofx compares the characters one-by-one and is therefore Ordinal, so there is currently a semantic difference between alternatives.

Owner

mattwarren commented Apr 20, 2016

Note in regards to my previous comment, @NickCraver's version and @FransBouma's are CurrentCulture while @xoofx compares the characters one-by-one and is therefore Ordinal, so there is currently a semantic difference between alternatives.

@nguerrera that's a good point, I missed that. I don't know the usage of the original code that @NickCraver posted, so I'm not sure if that is a problem or not.

I'm pretty sure that "ordinal" would be fine; usual use-case is testing "is {x} enabled" from multi-value configuration string values - we never use this approach to test anything related to user input.

@westonized That's not a supported use case, we'd opt for speed over handling that situation.

Depending on the input, this variation may be even faster. Or ~1.5 times slower... I wonder what the real data looks like ;)

public static unsafe bool ContainsTokenHellBrick( string value, string token, char delimiter = ';' )
{
    if ( string.IsNullOrEmpty( token ) ) return false;
    if ( string.IsNullOrEmpty( value ) ) return false;

    int length = value.Length;
    int tokenLength = token.Length;

    int currentTokenOffset = 0;
    int maxTokenOffset = length - tokenLength;

    while ( currentTokenOffset <= maxTokenOffset )
    {
        int nextDelimiterOffset = value.IndexOf( delimiter, currentTokenOffset );
        if ( nextDelimiterOffset < 0 )
            nextDelimiterOffset = length;

        if ( tokenLength == nextDelimiterOffset - currentTokenOffset )
        {
            for ( int i = 0; i < tokenLength; i++ )
            {
                if ( value[ currentTokenOffset + i ] != token[ i ] )
                    goto next;
            }

            return true;
        }

        next:
        currentTokenOffset = nextDelimiterOffset + 1;
    }

    return false;
}
                 Method |     Median |    StdDev |                                Value |
----------------------- |----------- |---------- |------------------------------------- |
 ContainsTokenHellBrick | 38.4351 ns | 0.5041 ns |              Bar1;Bar2;Bar3;Bar4;Bar |
     ContainsTokenXoofx | 47.9518 ns | 0.9066 ns |              Bar1;Bar2;Bar3;Bar4;Bar |
 ContainsTokenHellBrick | 37.3140 ns | 0.4199 ns |          Bar1;Bar2;Bar3;Bar4;NoMatch |
     ContainsTokenXoofx | 49.8620 ns | 0.6716 ns |          Bar1;Bar2;Bar3;Bar4;NoMatch |
 ContainsTokenHellBrick | 13.3256 ns | 0.1686 ns |                        Bar;blaat;foo |
     ContainsTokenXoofx |  8.2512 ns | 0.1072 ns |                        Bar;blaat;foo |
 ContainsTokenHellBrick | 20.1261 ns | 0.2744 ns |                              Foo;Bar |
     ContainsTokenXoofx | 14.4019 ns | 0.1735 ns |                              Foo;Bar |
 ContainsTokenHellBrick | 26.8856 ns | 0.4202 ns |                  Foo;FooBar;Whatever |
     ContainsTokenXoofx | 26.3001 ns | 0.3840 ns |                  Foo;FooBar;Whatever |
 ContainsTokenHellBrick | 42.5181 ns | 0.6889 ns | Some;Other;Really;Interesting;Tokens |
     ContainsTokenXoofx | 44.0047 ns | 0.4335 ns | Some;Other;Really;Interesting;Tokens |
 ContainsTokenHellBrick | 26.9582 ns | 0.4201 ns |                        blaat;foo;Bar |
     ContainsTokenXoofx | 21.3939 ns | 0.2482 ns |                        blaat;foo;Bar |
 ContainsTokenHellBrick | 20.4602 ns | 0.2005 ns |                        foo;Bar;Blaat |
     ContainsTokenXoofx | 15.0747 ns | 0.2727 ns |                        foo;Bar;Blaat |
 ContainsTokenHellBrick | 24.9415 ns | 0.2786 ns |                     foo;FooBar;Blaat |
     ContainsTokenXoofx | 25.4776 ns | 0.4810 ns |                     foo;FooBar;Blaat |

xoofx commented Apr 21, 2016

For those wondering about an unsafe version of my previous code, it is not much worth it (only 2-3% faster)

public unsafe static bool ContainsTokenXoofxUnsafe(string value, string token, char delimiter = ';')
{
    if (string.IsNullOrEmpty(token)) return false;
    if (string.IsNullOrEmpty(value)) return false;

    int length = value.Length;
    int tokenLength = token.Length;
    int i = 0;
    fixed (char* pValue = value)
    fixed (char* pToken = token)
    while (true)
    {
        for (int j = 0; j < tokenLength; j++, i++)
        {
            if (i >= length || pValue[i] != pToken[j])
            {
                goto next;
            }
        }

        if (i == length || pValue[i] == delimiter)
        {
            return true;
        }

        next:
        i = value.IndexOf(delimiter, i) + 1;
        if (i == 0)
        {
            break;
        }
    }

    return false;
}
Owner

mattwarren commented Apr 21, 2016

Phew, this has now become a bit of a beast of a benchmark, taking ~18 mins to run!!

Anyway, here are the results (you might need to install github.expandinizr to view them!!):

Total time: 00:18:35 (1115.85 sec)

// * Summary *

BenchmarkDotNet=v0.9.4.0
OS=Microsoft Windows NT 6.1.7601 Service Pack 1
Processor=Intel(R) Core(TM) i7-4800MQ CPU @ 2.70GHz, ProcessorCount=8
Frequency=2630751 ticks, Resolution=380.1196 ns, Timer=TSC
HostCLR=MS.NET 4.0.30319.42000, Arch=64-bit RELEASE [RyuJIT]
JitModules=clrjit-v4.6.100.0

Type=Program  Mode=Throughput  Runtime=Clr LaunchCount=1  
Method Median StdDev Scaled Value Gen 0 Gen 1 Gen 2 Bytes Allocated/Op
ContainsToken 457.2393 ns 2.1709 ns 3.10 Bar1;Bar2;Bar3;Bar4;Bar - - - 0.05
ContainsTokenHellBrick 34.7721 ns 0.1974 ns 0.24 Bar1;Bar2;Bar3;Bar4;Bar - - - 0.00
ContainsTokenMonty 23.5890 ns 0.6892 ns 0.16 Bar1;Bar2;Bar3;Bar4;Bar - - - 0.00
ContainsTokenXoofx 40.0252 ns 0.2262 ns 0.27 Bar1;Bar2;Bar3;Bar4;Bar - - - 0.00
ContainsTokenXoofxUnsafe 33.5358 ns 0.2041 ns 0.23 Bar1;Bar2;Bar3;Bar4;Bar - - - 0.00
StringSplit 147.5636 ns 6.2988 ns 1.00 Bar1;Bar2;Bar3;Bar4;Bar 1,136.79 - - 153.22
ContainsToken 459.6852 ns 1.8664 ns 3.11 Bar1;Bar2;Bar3;Bar4;NoMatch - - - 0.06
ContainsTokenHellBrick 32.7333 ns 0.1345 ns 0.22 Bar1;Bar2;Bar3;Bar4;NoMatch - - - 0.00
ContainsTokenMonty 29.8974 ns 0.1297 ns 0.20 Bar1;Bar2;Bar3;Bar4;NoMatch - - - 0.00
ContainsTokenXoofx 39.5378 ns 0.1530 ns 0.27 Bar1;Bar2;Bar3;Bar4;NoMatch - - - 0.00
ContainsTokenXoofxUnsafe 36.7873 ns 0.1598 ns 0.25 Bar1;Bar2;Bar3;Bar4;NoMatch - - - 0.00
StringSplit 147.9116 ns 1.3893 ns 1.00 Bar1;Bar2;Bar3;Bar4;NoMatch 1,235.30 - - 166.38
ContainsToken 91.6527 ns 0.2029 ns 0.98 Bar;blaat;foo - - - 0.01
ContainsTokenHellBrick 11.7838 ns 0.1394 ns 0.13 Bar;blaat;foo - - - 0.00
ContainsTokenMonty 6.8999 ns 0.0452 ns 0.07 Bar;blaat;foo - - - 0.00
ContainsTokenXoofx 6.8800 ns 0.0724 ns 0.07 Bar;blaat;foo - - - 0.00
ContainsTokenXoofxUnsafe 6.0679 ns 0.0435 ns 0.07 Bar;blaat;foo - - - 0.00
StringSplit 93.1068 ns 1.7476 ns 1.00 Bar;blaat;foo 692.00 - - 93.34
ContainsToken 93.7707 ns 0.6983 ns 1.26 Foo;Bar - - - 0.01
ContainsTokenHellBrick 18.6769 ns 0.4493 ns 0.25 Foo;Bar - - - 0.00
ContainsTokenMonty 11.3597 ns 0.0567 ns 0.15 Foo;Bar - - - 0.00
ContainsTokenXoofx 12.4333 ns 0.1281 ns 0.17 Foo;Bar - - - 0.00
ContainsTokenXoofxUnsafe 11.2567 ns 0.1116 ns 0.15 Foo;Bar - - - 0.00
StringSplit 74.3201 ns 0.8831 ns 1.00 Foo;Bar 534.73 - - 71.85
ContainsToken 183.9058 ns 1.0818 ns 1.72 Foo;FooBar;Whatever - - - 0.01
ContainsToken 183.7779 ns 3.1196 ns 1.72 Foo;FooBar;Whatever - - - 0.01
ContainsTokenHellBrick 23.7040 ns 1.3138 ns 0.22 Foo;FooBar;Whatever - - - 0.00
ContainsTokenHellBrick 23.2025 ns 0.1530 ns 0.22 Foo;FooBar;Whatever - - - 0.00
ContainsTokenMonty 26.4777 ns 0.2514 ns 0.25 Foo;FooBar;Whatever - - - 0.00
ContainsTokenMonty 26.6932 ns 1.2180 ns 0.25 Foo;FooBar;Whatever - - - 0.00
ContainsTokenXoofx 23.2981 ns 0.6097 ns 0.22 Foo;FooBar;Whatever - - - 0.00
ContainsTokenXoofx 22.4053 ns 0.5687 ns 0.21 Foo;FooBar;Whatever - - - 0.00
ContainsTokenXoofxUnsafe 22.2407 ns 0.1073 ns 0.21 Foo;FooBar;Whatever - - - 0.00
ContainsTokenXoofxUnsafe 22.3470 ns 0.1822 ns 0.21 Foo;FooBar;Whatever - - - 0.00
StringSplit 107.0065 ns 6.7753 ns 1.00 Foo;FooBar;Whatever 928.37 - - 124.99
StringSplit 106.2148 ns 9.4340 ns 0.99 Foo;FooBar;Whatever 762.42 - - 102.67
ContainsToken 106.1289 ns 0.6852 ns 0.63 Some;Other;Really;Interesting;Tokens - - - 0.01
ContainsTokenHellBrick 36.0504 ns 0.2313 ns 0.22 Some;Other;Really;Interesting;Tokens - - - 0.00
ContainsTokenMonty 45.9504 ns 0.2223 ns 0.27 Some;Other;Really;Interesting;Tokens - - - 0.01
ContainsTokenXoofx 36.6904 ns 0.2698 ns 0.22 Some;Other;Really;Interesting;Tokens - - - 0.00
ContainsTokenXoofxUnsafe 36.1607 ns 0.3778 ns 0.22 Some;Other;Really;Interesting;Tokens - - - 0.00
StringSplit 167.4801 ns 0.5075 ns 1.00 Some;Other;Really;Interesting;Tokens 1,347.44 - - 181.48
ContainsToken 97.3683 ns 1.6462 ns 0.98 blaat;foo;Bar - - - 0.01
ContainsTokenHellBrick 24.5331 ns 0.1976 ns 0.25 blaat;foo;Bar - - - 0.00
ContainsTokenMonty 19.1828 ns 1.1067 ns 0.19 blaat;foo;Bar - - - 0.00
ContainsTokenXoofx 19.4809 ns 0.1611 ns 0.20 blaat;foo;Bar - - - 0.00
ContainsTokenXoofxUnsafe 18.2038 ns 0.1031 ns 0.18 blaat;foo;Bar - - - 0.00
StringSplit 99.7045 ns 4.8616 ns 1.00 blaat;foo;Bar 720.94 - - 97.23
ContainsToken 93.1687 ns 0.7519 ns 0.94 foo;Bar;Blaat - - - 0.01
ContainsTokenHellBrick 18.7808 ns 0.0771 ns 0.19 foo;Bar;Blaat - - - 0.00
ContainsTokenMonty 11.0144 ns 0.1165 ns 0.11 foo;Bar;Blaat - - - 0.00
ContainsTokenXoofx 12.9650 ns 0.0562 ns 0.13 foo;Bar;Blaat - - - 0.00
ContainsTokenXoofxUnsafe 11.6043 ns 0.0976 ns 0.12 foo;Bar;Blaat - - - 0.00
StringSplit 99.0620 ns 1.7763 ns 1.00 foo;Bar;Blaat 692.00 - - 93.34
ContainsToken 183.5646 ns 1.7055 ns 1.82 foo;FooBar;Blaat - - - 0.01
ContainsTokenHellBrick 22.3335 ns 0.1357 ns 0.22 foo;FooBar;Blaat - - - 0.00
ContainsTokenMonty 24.0655 ns 0.4106 ns 0.24 foo;FooBar;Blaat - - - 0.00
ContainsTokenXoofx 21.9318 ns 0.0913 ns 0.22 foo;FooBar;Blaat - - - 0.00
ContainsTokenXoofxUnsafe 22.0677 ns 0.1473 ns 0.22 foo;FooBar;Blaat - - - 0.00
StringSplit 100.9402 ns 1.3348 ns 1.00 foo;FooBar;Blaat 670.45 - - 90.25
Owner

mattwarren commented Apr 21, 2016

Or if you prefer graphs (I'm looking at the spike that ContainsToken has for Value=Bar1;Bar2;Bar3;Bar4;NoMatch, seems strange!!):

program-barplot

Owner

mattwarren commented Apr 21, 2016

I'm looking at the spike that ContainsToken has forValue=Bar1;Bar2;Bar3;Bar4;NoMatch, seems strange!!

Actually, it's repeatable. ContainsToken seems to take longer for Bar1;Bar2;Bar3;Bar4;NoMatch and Bar1;Bar2;Bar3;Bar4;Bar. I guess it's because there are a lot of partial, but not full matches, of Bar in those string?

Method Median StdDev Scaled Value Gen 0 Gen 1 Gen 2 Bytes Allocated/Op
ContainsToken 468.6221 ns 4.1517 ns 3.23 Bar1;Bar2;Bar3;Bar4;Bar - - - 0.05
StringSplit 145.0278 ns 2.2557 ns 1.00 Bar1;Bar2;Bar3;Bar4;Bar 1,237.57 - - 156.35
ContainsToken 466.4851 ns 3.9305 ns 3.06 Bar1;Bar2;Bar3;Bar4;NoMatch - - - 0.06
StringSplit 152.3283 ns 3.3905 ns 1.00 Bar1;Bar2;Bar3;Bar4;NoMatch 1,305.00 - - 164.78
ContainsToken 94.0093 ns 0.9253 ns 1.01 Bar;blaat;foo - - - 0.01
StringSplit 93.4631 ns 1.3678 ns 1.00 Bar;blaat;foo 681.91 - - 86.24
ContainsToken 95.7284 ns 0.5576 ns 1.30 Foo;Bar - - - 0.01
StringSplit 73.5677 ns 0.6922 ns 1.00 Foo;Bar 543.19 - - 68.42
ContainsToken 185.2570 ns 0.4731 ns 1.76 Foo;FooBar;Whatever - - - 0.01
ContainsToken 185.3813 ns 0.5269 ns 1.77 Foo;FooBar;Whatever - - - 0.01
StringSplit 105.0227 ns 0.5036 ns 1.00 Foo;FooBar;Whatever 895.83 - - 113.09
StringSplit 105.5167 ns 0.8582 ns 1.00 Foo;FooBar;Whatever 887.18 - - 112.00
ContainsToken 106.4620 ns 0.2543 ns 0.64 Some;Other;Really;Interesting;Tokens - - - 0.01
StringSplit 166.3854 ns 1.6549 ns 1.00 Some;Other;Really;Interesting;Tokens 1,537.25 - - 194.08
ContainsToken 99.3290 ns 0.7519 ns 1.00 blaat;foo;Bar - - - 0.01
StringSplit 99.6951 ns 1.1993 ns 1.00 blaat;foo;Bar 779.20 - - 98.53
ContainsToken 97.0342 ns 0.4482 ns 1.00 foo;Bar;Blaat - - - 0.01
StringSplit 97.5164 ns 0.9454 ns 1.00 foo;Bar;Blaat 849.12 - - 107.34
ContainsToken 185.2089 ns 0.7341 ns 1.83 foo;FooBar;Blaat - - - 0.01
StringSplit 101.3099 ns 1.0011 ns 1.00 foo;FooBar;Blaat 773.74 - - 97.64

program-barplot

I wrote another one, without indexof/goto/unsafe/allocations. It's based on a single scan over the value string, so O(n) amortized. I love these little puzzles so I thought this could be done more efficiently without indexof. The main reasoning behind that is that indexof(delimiter) scans ahead and that same fragment is then scanned again for the token, which is a point which can be optimized: scan just once, and check token accordingly. Algorithm-wise it's the most efficient I think, but in practice it's still beaten by low-level asm, as we'll see below. The code contains some nested if's as my previous version with continue; revealed to be a bit slower, but it's easily rewritten.

First the code:

public static bool ContainsTokenSingleScan(string value, string token, char delimiter = ';')
{
    if(string.IsNullOrEmpty(token)) return false;
    if(string.IsNullOrEmpty(value)) return false;

    var inTokenScanMode = true; // as we see the start as the char right after a delimiter
    int indexInToken = 0;
    for(int i = 0; i < value.Length; i++)
    {
        if(inTokenScanMode)
        {
            if(indexInToken < token.Length)
            {
                if(value[i] == token[indexInToken])
                {
                    indexInToken++;
                }
                else
                {
                    inTokenScanMode = false;
                    indexInToken = 0;
                }
            }
            else
            {
                if(value[i] == delimiter)
                {
                    return true;
                }
                inTokenScanMode = false;
                indexInToken = 0;
            }
        }
        else
        {
            inTokenScanMode = (value[i] == delimiter);
        }
    }
    return inTokenScanMode && (indexInToken == token.Length);
}

I ran the benchmark code against stringsplit and xoofx's unsafe one, as that's one of the fastests:

// * Summary *

BenchmarkDotNet=v0.9.4.0
OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz, ProcessorCount=4
Frequency=3515627 ticks, Resolution=284.4443 ns, Timer=TSC
HostCLR=MS.NET 4.0.30319.42000, Arch=32-bit RELEASE
JitModules=clrjit-v4.6.1055.0

Type=Program  Mode=Throughput  Runtime=Clr
LaunchCount=1

                   Method |      Median |    StdDev | Scaled |                                Value |
------------------------- |------------ |---------- |------- |------------------------------------- |
  ContainsTokenSingleScan |  29.4875 ns | 0.1493 ns |   0.21 |              Bar1;Bar2;Bar3;Bar4;Bar |
 ContainsTokenXoofxUnsafe |  29.3382 ns | 0.0887 ns |   0.21 |              Bar1;Bar2;Bar3;Bar4;Bar |
              StringSplit | 141.2710 ns | 0.9459 ns |   1.00 |              Bar1;Bar2;Bar3;Bar4;Bar |
  ContainsTokenSingleScan |  33.2588 ns | 0.0806 ns |   0.23 |          Bar1;Bar2;Bar3;Bar4;NoMatch |
 ContainsTokenXoofxUnsafe |  33.2494 ns | 0.8623 ns |   0.23 |          Bar1;Bar2;Bar3;Bar4;NoMatch |
              StringSplit | 145.8904 ns | 0.5430 ns |   1.00 |          Bar1;Bar2;Bar3;Bar4;NoMatch |
  ContainsTokenSingleScan |   8.0564 ns | 0.0330 ns |   0.09 |                        Bar;blaat;foo |
 ContainsTokenXoofxUnsafe |   7.9998 ns | 0.0458 ns |   0.09 |                        Bar;blaat;foo |
              StringSplit |  88.9227 ns | 3.4081 ns |   1.00 |                        Bar;blaat;foo |
  ContainsTokenSingleScan |  11.2328 ns | 0.0541 ns |   0.16 |                              Foo;Bar |
 ContainsTokenXoofxUnsafe |  11.1442 ns | 0.4048 ns |   0.16 |                              Foo;Bar |
              StringSplit |  69.0412 ns | 2.2356 ns |   1.00 |                              Foo;Bar |
  ContainsTokenSingleScan |  20.2034 ns | 0.0552 ns |   0.20 |                  Foo;FooBar;Whatever |
  ContainsTokenSingleScan |  20.1668 ns | 0.0633 ns |   0.20 |                  Foo;FooBar;Whatever |
 ContainsTokenXoofxUnsafe |  20.1485 ns | 0.1018 ns |   0.20 |                  Foo;FooBar;Whatever |
 ContainsTokenXoofxUnsafe |  20.1113 ns | 0.0280 ns |   0.20 |                  Foo;FooBar;Whatever |
              StringSplit | 101.2630 ns | 0.5470 ns |   1.00 |                  Foo;FooBar;Whatever |
              StringSplit | 100.3031 ns | 0.3380 ns |   0.99 |                  Foo;FooBar;Whatever |
  ContainsTokenSingleScan |  33.8882 ns | 0.0943 ns |   0.21 | Some;Other;Really;Interesting;Tokens |
 ContainsTokenXoofxUnsafe |  33.9483 ns | 0.1286 ns |   0.21 | Some;Other;Really;Interesting;Tokens |
              StringSplit | 158.0980 ns | 1.3645 ns |   1.00 | Some;Other;Really;Interesting;Tokens |
  ContainsTokenSingleScan |  16.0097 ns | 0.0976 ns |   0.17 |                        blaat;foo;Bar |
 ContainsTokenXoofxUnsafe |  15.9247 ns | 0.0392 ns |   0.17 |                        blaat;foo;Bar |
              StringSplit |  94.6229 ns | 0.7197 ns |   1.00 |                        blaat;foo;Bar |
  ContainsTokenSingleScan |  11.2807 ns | 0.0557 ns |   0.12 |                        foo;Bar;Blaat |
 ContainsTokenXoofxUnsafe |  11.1888 ns | 0.0436 ns |   0.12 |                        foo;Bar;Blaat |
              StringSplit |  93.1348 ns | 4.5038 ns |   1.00 |                        foo;Bar;Blaat |
  ContainsTokenSingleScan |  20.0108 ns | 0.0713 ns |   0.19 |                     foo;FooBar;Blaat |
 ContainsTokenXoofxUnsafe |  20.1328 ns | 0.5801 ns |   0.19 |                     foo;FooBar;Blaat |
              StringSplit | 105.5727 ns | 1.5858 ns |   1.00 |                     foo;FooBar;Blaat |

It's close, but not faster in many situations (only in one). This surprised me a bit, till I saw that string.IndexOf() is implemented using assembler in the BCL, so its not a surprise it's faster than char comparisons in C# ;). This means that it isn't really a waste to scan a fragment multiple times if you can do that using low-level optimized BCL methods and if that scan ahead gives you a head start where to continue with token scanning.

Learned something new :) The benchmark framework is also quite nice. Haven't looked at it too deeply yet, e.g. don't know whether there's verification options in it (i.e. if the results produced are correct or not).

Cheers!

Finally in a place where I can run the actual benchmark (instead of guesstimating). Added my last attempt.

Running 64-bit makes a substantial difference - which isn't surprising, I anticipated that in the comments for my original attempt. I'm posting the more favorable run (the 64-bit one), since there seems to be a divide in the previously posted tables (@FransBouma is in 32-bit, @mattwarren is in 64-bit).

I suspect ContainsTokenMonty's performance gap will increase as value and token increase in size, since the main non-algorithmic wins are in comparing multiple chars in single ops (up to 4 chars per op when comparing token, and 2 chars per op when searching for the delimiter). I haven't tested this suspicion.

BenchmarkDotNet-Dev=v0.9.4.0+
OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Core(TM) i7-4960HQ CPU @ 2.60GHz, ProcessorCount=8
Frequency=2533203 ticks, Resolution=394.7572 ns, Timer=TSC
HostCLR=MS.NET 4.0.30319.42000, Arch=64-bit RELEASE [RyuJIT]
JitModules=clrjit-v4.6.96.0

Type=Program  Mode=Throughput  Runtime=Clr  
LaunchCount=1  
Method Median StdDev Scaled Value Gen 0 Gen 1 Gen 2 Bytes Allocated/Op
ContainsToken 569.5728 ns 4.9277 ns 3.99 Bar1;Bar2;Bar3;Bar4;Bar - - - 0.06
ContainsTokenHellBrick 34.0393 ns 0.4630 ns 0.24 Bar1;Bar2;Bar3;Bar4;Bar - - - 0.00
ContainsTokenMonty 16.5055 ns 0.0676 ns 0.12 Bar1;Bar2;Bar3;Bar4;Bar - - - 0.00
ContainsTokenSingleScan 29.3718 ns 0.1476 ns 0.21 Bar1;Bar2;Bar3;Bar4;Bar - - - 0.00
ContainsTokenXoofx 37.3689 ns 0.2765 ns 0.26 Bar1;Bar2;Bar3;Bar4;Bar - - - 0.00
ContainsTokenXoofxUnsafe 32.9515 ns 0.5662 ns 0.23 Bar1;Bar2;Bar3;Bar4;Bar - - - 0.00
StringSplit 142.7695 ns 2.1492 ns 1.00 Bar1;Bar2;Bar3;Bar4;Bar 496.94 - - 154.86
ContainsToken 558.9586 ns 5.4237 ns 3.82 Bar1;Bar2;Bar3;Bar4;NoMatch - - - 0.06
ContainsTokenHellBrick 34.5302 ns 0.3591 ns 0.24 Bar1;Bar2;Bar3;Bar4;NoMatch - - - 0.00
ContainsTokenMonty 20.2167 ns 0.2271 ns 0.14 Bar1;Bar2;Bar3;Bar4;NoMatch - - - 0.00
ContainsTokenSingleScan 33.2238 ns 0.1712 ns 0.23 Bar1;Bar2;Bar3;Bar4;NoMatch - - - 0.00
ContainsTokenXoofx 36.5345 ns 0.1784 ns 0.25 Bar1;Bar2;Bar3;Bar4;NoMatch - - - 0.00
ContainsTokenXoofxUnsafe 35.2670 ns 0.7166 ns 0.24 Bar1;Bar2;Bar3;Bar4;NoMatch - - - 0.00
StringSplit 146.3651 ns 0.9008 ns 1.00 Bar1;Bar2;Bar3;Bar4;NoMatch 594.99 - - 183.93
ContainsToken 103.0207 ns 0.6338 ns 1.10 Bar;blaat;foo - - - 0.01
ContainsTokenHellBrick 11.0177 ns 0.1332 ns 0.12 Bar;blaat;foo - - - 0.00
ContainsTokenMonty 6.4689 ns 0.0406 ns 0.07 Bar;blaat;foo - - - 0.00
ContainsTokenSingleScan 6.1127 ns 0.0724 ns 0.07 Bar;blaat;foo - - - 0.00
ContainsTokenXoofx 6.1134 ns 0.0501 ns 0.07 Bar;blaat;foo - - - 0.00
ContainsTokenXoofxUnsafe 6.1312 ns 0.1400 ns 0.07 Bar;blaat;foo - - - 0.00
StringSplit 93.7291 ns 0.5546 ns 1.00 Bar;blaat;foo 277.50 - - 92.26
ContainsToken 114.1318 ns 1.2303 ns 1.57 Foo;Bar - - - 0.01
ContainsTokenHellBrick 17.0889 ns 0.1333 ns 0.24 Foo;Bar - - - 0.00
ContainsTokenMonty 8.7917 ns 0.1046 ns 0.12 Foo;Bar - - - 0.00
ContainsTokenSingleScan 11.4580 ns 0.2974 ns 0.16 Foo;Bar - - - 0.00
ContainsTokenXoofx 11.8141 ns 0.1413 ns 0.16 Foo;Bar - - - 0.00
ContainsTokenXoofxUnsafe 11.5833 ns 0.2368 ns 0.16 Foo;Bar - - - 0.00
StringSplit 72.6835 ns 0.5026 ns 1.00 Foo;Bar 193.84 - - 61.57
ContainsToken 238.9126 ns 1.7528 ns 2.25 Foo;FooBar;Whatever - - - 0.03
ContainsToken 238.1762 ns 1.4844 ns 2.24 Foo;FooBar;Whatever - - - 0.03
ContainsTokenHellBrick 21.3572 ns 0.2224 ns 0.20 Foo;FooBar;Whatever - - - 0.00
ContainsTokenHellBrick 21.2637 ns 0.1341 ns 0.20 Foo;FooBar;Whatever - - - 0.00
ContainsTokenMonty 15.8655 ns 0.0711 ns 0.15 Foo;FooBar;Whatever - - - 0.00
ContainsTokenMonty 16.0360 ns 0.4333 ns 0.15 Foo;FooBar;Whatever - - - 0.00
ContainsTokenSingleScan 20.2006 ns 0.0741 ns 0.19 Foo;FooBar;Whatever - - - 0.00
ContainsTokenSingleScan 20.2010 ns 0.0846 ns 0.19 Foo;FooBar;Whatever - - - 0.00
ContainsTokenXoofx 21.5653 ns 0.2646 ns 0.20 Foo;FooBar;Whatever - - - 0.00
ContainsTokenXoofx 21.6318 ns 0.3899 ns 0.20 Foo;FooBar;Whatever - - - 0.00
ContainsTokenXoofxUnsafe 21.3633 ns 0.1293 ns 0.20 Foo;FooBar;Whatever - - - 0.00
ContainsTokenXoofxUnsafe 20.1502 ns 0.1498 ns 0.19 Foo;FooBar;Whatever - - - 0.00
StringSplit 106.2978 ns 1.9544 ns 1.00 Foo;FooBar;Whatever 352.25 - - 114.61
StringSplit 105.5826 ns 1.3622 ns 0.99 Foo;FooBar;Whatever 352.25 - - 114.61
ContainsToken 193.5371 ns 1.4477 ns 1.20 Some;Other;Really;Interesting;Tokens - - - 0.03
ContainsTokenHellBrick 37.2887 ns 0.5070 ns 0.23 Some;Other;Really;Interesting;Tokens - - - 0.00
ContainsTokenMonty 24.8710 ns 0.4596 ns 0.15 Some;Other;Really;Interesting;Tokens - - - 0.00
ContainsTokenSingleScan 35.2233 ns 0.5154 ns 0.22 Some;Other;Really;Interesting;Tokens - - - 0.00
ContainsTokenXoofx 36.7675 ns 0.9916 ns 0.23 Some;Other;Really;Interesting;Tokens - - - 0.00
ContainsTokenXoofxUnsafe 33.4664 ns 0.4110 ns 0.21 Some;Other;Really;Interesting;Tokens - - - 0.00
StringSplit 161.6573 ns 2.5366 ns 1.00 Some;Other;Really;Interesting;Tokens 602.25 - - 185.70
ContainsToken 129.5446 ns 0.6051 ns 1.30 blaat;foo;Bar - - - 0.01
ContainsTokenHellBrick 23.4975 ns 0.3080 ns 0.24 blaat;foo;Bar - - - 0.00
ContainsTokenMonty 12.8415 ns 0.0968 ns 0.13 blaat;foo;Bar - - - 0.00
ContainsTokenSingleScan 17.0308 ns 0.1163 ns 0.17 blaat;foo;Bar - - - 0.00
ContainsTokenXoofx 18.0250 ns 0.1594 ns 0.18 blaat;foo;Bar - - - 0.00
ContainsTokenXoofxUnsafe 17.8055 ns 0.2144 ns 0.18 blaat;foo;Bar - - - 0.00
StringSplit 99.4195 ns 1.0491 ns 1.00 blaat;foo;Bar 243.52 - - 80.96
ContainsToken 114.5598 ns 0.9837 ns 1.17 foo;Bar;Blaat - - - 0.01
ContainsTokenHellBrick 17.2913 ns 0.1087 ns 0.18 foo;Bar;Blaat - - - 0.00
ContainsTokenMonty 9.0493 ns 0.0407 ns 0.09 foo;Bar;Blaat - - - 0.00
ContainsTokenSingleScan 11.2418 ns 0.1855 ns 0.12 foo;Bar;Blaat - - - 0.00
ContainsTokenXoofx 12.3910 ns 0.1124 ns 0.13 foo;Bar;Blaat - - - 0.00
ContainsTokenXoofxUnsafe 10.9651 ns 0.1700 ns 0.11 foo;Bar;Blaat - - - 0.00
StringSplit 97.6417 ns 0.9631 ns 1.00 foo;Bar;Blaat 271.19 - - 90.16
ContainsToken 232.8388 ns 0.9065 ns 2.31 foo;FooBar;Blaat - - - 0.03
ContainsTokenHellBrick 21.1562 ns 0.3597 ns 0.21 foo;FooBar;Blaat - - - 0.00
ContainsTokenMonty 14.6257 ns 0.1069 ns 0.14 foo;FooBar;Blaat - - - 0.00
ContainsTokenSingleScan 18.4191 ns 0.2883 ns 0.18 foo;FooBar;Blaat - - - 0.00
ContainsTokenXoofx 21.7312 ns 0.4207 ns 0.22 foo;FooBar;Blaat - - - 0.00
ContainsTokenXoofxUnsafe 20.1018 ns 0.1837 ns 0.20 foo;FooBar;Blaat - - - 0.00
StringSplit 100.9364 ns 0.5686 ns 1.00 foo;FooBar;Blaat 336.83 - - 110.89

FransBouma commented Apr 26, 2016 edited

Nice! Interesting results, for sure :) Still glad I'm in second place in most tests (not all) ;).

This is epic! =)

Ok I couldn't resist so here is another variation :)
https://gist.github.com/bbowyersmyth/c308aa62e871d44024c0bab552567961

Minimize the expense looking for a token as there is most likely not a match. Monty2 would probably be quicker on longer partial matches.
Use loop unrolling when looking for the next token.

BenchmarkDotNet=v0.9.4.0
OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Core(TM) i5-6600 CPU @ 3.30GHz, ProcessorCount=4
Frequency=3234371 ticks, Resolution=309.1791 ns, Timer=TSC
HostCLR=MS.NET 4.0.30319.42000, Arch=64-bit RELEASE [RyuJIT]
JitModules=clrjit-v4.6.1078.0

Type=ContainsToken  Mode=Throughput  Platform=X64  
Jit=RyuJit  
Method Median StdDev Value
ContainsTokenUnroll 11.1478 ns 0.3191 ns Bar1;Bar2;Bar3;Bar4;Bar
ContainsTokenMonty2 15.4258 ns 0.2308 ns Bar1;Bar2;Bar3;Bar4;Bar
ContainsTokenUnroll 12.4808 ns 2.7918 ns Bar1;Bar2;Bar3;Bar4;NoMatch
ContainsTokenMonty2 17.0302 ns 0.3017 ns Bar1;Bar2;Bar3;Bar4;NoMatch
ContainsTokenUnroll 3.9933 ns 0.1028 ns Bar;blaat;foo
ContainsTokenMonty2 5.7593 ns 0.1258 ns Bar;blaat;foo
ContainsTokenUnroll 5.7880 ns 0.1428 ns Foo;Bar
ContainsTokenMonty2 8.0731 ns 0.1841 ns Foo;Bar
ContainsTokenUnroll 11.8456 ns 0.2204 ns Foo;FooBar;Whatever
ContainsTokenMonty2 15.0076 ns 0.2669 ns Foo;FooBar;Whatever
ContainsTokenUnroll 18.5287 ns 0.2764 ns Some;Other;Really;Interesting;Tokens
ContainsTokenMonty2 21.6304 ns 0.4823 ns Some;Other;Really;Interesting;Tokens
ContainsTokenUnroll 8.7534 ns 0.1295 ns blaat;foo;Bar
ContainsTokenMonty2 11.2296 ns 0.2047 ns blaat;foo;Bar
ContainsTokenUnroll 5.9761 ns 0.1274 ns foo;Bar;Blaat
ContainsTokenMonty2 8.1325 ns 0.2437 ns foo;Bar;Blaat
ContainsTokenUnroll 10.5742 ns 0.2372 ns foo;FooBar;Blaat
ContainsTokenMonty2 14.2297 ns 0.2002 ns foo;FooBar;Blaat

ioctlLR commented May 25, 2016 edited

I know I'm late to the game, but here's my take. On a Core i7-4810MQ @ 2.8GHz running 4.6.1 x64 w/ RyuJIT, it appears to consistently beat the previous winners (including Monty2). Enjoy!

public static bool ContainsTokenAfward(string value, string token, char delimiter = ';')
{
    if (token == null || value == null) return false;

    var valueLength = value.Length;
    var tokenLength = token.Length;

    // if the token has any length, we only need to make sure the value is long enough to hold it
    if (tokenLength == 0 || tokenLength > valueLength) return false;

    // algorithm::
    // check the first segment to see if it matches; return true if it does
    // look for {Delimiter}{token[0]} via int* cast
    // match the remaining characters of the token if found

    // we assume we're on little-endian and that strings are terminated by null
    // we also only do ordinal comparison

    unsafe
    {
        fixed (char* valueStartPtr = value, tokenStartPtr = token)
        {
            // keep up with where we are in the value and token strings
            var valuePtr = valueStartPtr;
            var tokenPtr = tokenStartPtr;

            // keep up with the ending pointer for the value
            var valueEndPtr = valueStartPtr + valueLength;

            // see if the first segment is the token
            if (*tokenPtr == *valuePtr)
            {
                // go through at a rate of 2 chars per check...
                while (*(uint*)++tokenPtr == *(uint*)++valuePtr)
                {
                    ++tokenPtr;
                    if (++valuePtr >= valueEndPtr)
                    {
                        // we're at the end of value and it matches
                        return true;
                    }
                }
                if (*tokenPtr == '\0')
                {
                    // we matched the whole token, so make sure the next char is a delimiter
                    if (*valuePtr == delimiter)
                    {
                        return true;
                    }
                }
                // we matched all but the final character, so check it and the delimiter
                else if (*tokenPtr == *valuePtr)
                {
                    if (*++valuePtr == delimiter)
                    {
                        return true;
                    }
                }
            }

            // set our search limit (no point going further if token hasn't been found yet)
            var valueEffEndPtr = valueEndPtr - tokenLength;

            // build a matching value that is the delimiter + the first token char
            var matchVal = (int)delimiter | ((int)*tokenStartPtr << 16);

            // save off the position of the 2nd token character for later...
            var resetPtr = tokenStartPtr + 1;

            // search through the string to find the correct location
            while (valuePtr < valueEffEndPtr)
            {
                // look for the next segment delimiter where the segment starts with the correct character
                var checkSegment = true;
                while (*(int*)valuePtr != matchVal)
                {
                    ++valuePtr;
                    if (valuePtr > valueEffEndPtr)
                    {
                        checkSegment = false;
                        break;
                    }
                }

                if (checkSegment)
                {
                    // valuePtr is pointing at the delimiter, so move to the 2nd char in the segment
                    valuePtr += 2;

                    // reset our matching pointer
                    tokenPtr = resetPtr;

                    // go through at a rate of 2 chars per check...
                    while (*(int*)tokenPtr == *(int*)valuePtr)
                    {
                        tokenPtr += 2;
                        if ((valuePtr += 2) >= valueEndPtr)
                        {
                            // we're at the end of value and it matches
                            return true;
                        }
                    }
                    if (*tokenPtr == '\0')
                    {
                        // we matched the whole token, so make sure the next char is a delimiter
                        if (*valuePtr == delimiter)
                        {
                            return true;
                        }
                    }
                    // we matched all but the final character, so check it and the delimiter
                    else if (*tokenPtr == *valuePtr)
                    {
                        if (*++valuePtr == delimiter)
                        {
                            return true;
                        }
                    }
                }
            }

            // we didn't find it
            return false;
        }
    }
}

ioctlLR commented May 25, 2016

BTW, @kevin-montrose: I found that your algorithms won't support tokens larger than 6 chars anywhere but the beginning of the list. I haven't tried to debug them, though.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment