Runtime: API Proposal: String.IsLike

[Symbai]

Similar to https://github.com/dotnet/corefx/blob/0e65e923689962f9634b5948d15f995140cc7c93/src/Common/src/System/Text/SimpleRegex.cs#L21 but public and high performance as the linked method is up to 10x slower against own implementations when I tested.

API:

IsLike(this string input, string pattern, StringComparison mode = StringCoomparison.OrdinalIgnoreCase)

Usage:

static string FullName = "Pablo Alexander Jeff";
static string Version = "1.0.5.0";
static string LongString = "And where would you see yourself in five years’ time Mr. Jeffries?";
static string Path = "C:\\Windows\\System32\\drivers\\";
static string IP = "127.0.0.1";

void Matches() {
    if (FullName.IsLike("Pablo * Jeff"))
        //do stuff
    if (Version.IsLike("1.0.*.0"))
        //do stuff
    if (LongString.IsLike("*you*Jeffries"))
        //do stuff
    if (Path.IsLike(TextBox1.Text))
        //do stuff
    if (IP.IsLike("127.*.*.1"))
        //do stuff
}

There is a wide range for common scenarios given that Corefx also uses something like this itself. There might be a few things to discuss however:

• Should it also support ? for single match too? This is supported on a lot other wild card searches and therefore maybe expected. Or should it only support * for match any like in the linked method above?
• Naming of the method

[scalablecory]

What benefit do you see versus regex?

[Symbai]

Lots of performance. Wildcard match is more common and Regex is for more advanced scenarios than such a simple check. Even in the Corefx example above the team hasn't used regex but a custom implementation, for likely exactly the same reason.

[stephentoub]

for likely exactly the same reason

No. It was changed to remove a dependency on the Regex library that was there for an obscure use case, in order to reduce the size of a published single-file executable that otherwise wasn't using regular expressions.

[danmosemsft]

the linked method is up to 10x slower against own implementations when I tested.

What implementation? I'm curious how that could be much faster.

Regex is for more advanced scenarios than such a simple check

It's easy to make it perform such a check, eg
c# public static class MyStringExtensions { public static bool IsMatch(this string str, string pattern) { pattern = Regex.Escape(pattern); pattern = pattern.Replace(@"\?", ".?").Replace(@"\*", ".*"); return Regex.IsMatch(str, pattern); } }

[Symbai]

It's easy to make it perform such a check, eg

I never said its difficult. I said that Regex costs a lot of performance, even when compiled and regex is usually used for more complex scenarios or when performance doesn't matter but for a simple wildcard match you rather write your own because it's written in less than 50 lines and its a lot faster.

I think the benefit is great (even against Regex) and the implementation is easy and there a lot of scenarios where this can or will be used.

the linked method is up to 10x slower against own implementations when I tested.

What implementation? I'm curious how that could be much faster.

Don't know about others but this is mine and depending on input and pattern it is 1.5-10x faster while producing the same results, at least in my tests. I have changed it a bit as my original method supported a lot more wildcard symbols. There might be better implementations:

public static bool IsMatch(this string str, string pattern, StringComparison stringComparison = StringComparison.Ordinal)
{
    if (string.IsNullOrEmpty(pattern) || string.IsNullOrEmpty(str))
    {
        return false;
    }
    if (pattern == "*")
    {
        return true;
    }

    var strSpan = str.AsSpan();
    var patternSpan = pattern.AsSpan();


    var strIndex = 0;

    for (var patternIndex = 0; patternIndex < pattern.Length; patternIndex++)
    {
        var patternCh = pattern[patternIndex];

        var patternChSpan = patternSpan.Slice(patternIndex, 1);

        if (strIndex >= str.Length)
        {
            if (patternCh == '*')
            {
                return true;
            }

            return false;
        }

        var strAtIndex = strSpan.Slice(strIndex, 1);
        if (patternChSpan.Equals(strAtIndex, stringComparison))

        {
            strIndex++;
            continue;
        }

        if (patternCh != '*')
        {
            return false;
        }

        if (patternIndex == pattern.Length - 1)
        {
            return true;
        }

        int nextWildcardIndex = pattern.IndexOf('*', patternIndex + 1);
        int skipStringEndIndex;
        if (nextWildcardIndex == -1)
        {
            skipStringEndIndex = pattern.Length - 1;
        }
        else
        {
            skipStringEndIndex = nextWildcardIndex - 1;
        }

        int skipToStringStartIndex = patternIndex + 1;
        int skipToStringLength = skipStringEndIndex - patternIndex;

        ReadOnlySpan<char> skipToString = patternSpan.Slice(skipToStringStartIndex, skipToStringLength);
        int skipToStringIndex = strSpan.Slice(strIndex).IndexOf(skipToString, stringComparison) + strIndex;
        if (skipToStringIndex == -1)
        {
            return false;
        }

        strIndex = skipToStringIndex;
    }

    if (strIndex < str.Length)
    {
        return false;
    }

    return true;
}

[danmosemsft]

I haven't tested your code but it does not appear to do backtracking. So "foo*bar" will not match "foobarbar"

[stephentoub]

while producing the same results

FWIW, I just tried it with the tests at
https://github.com/dotnet/corefx/blob/e99ec129cfd594d53f4390bf97d1d736cff6f860/src/Common/tests/Tests/System/Text/SimpleRegexTests.cs#L12-L42
and it didn't pass a bunch of them.

For example, your implementation returns true for:
```C#
IsMatch("ab", "abb*")

even though it shouldn't match (the pattern requires an extra 'b' that the input doesn't have).  Conversely your implementation returns false for:
```C#
IsMatch("aaaa", "*a")

even though it should match (the '*' in the pattern should match the first three 'a's). If you're using this for production purposes, you might want to try it and see if any of the failures are meaningful to you.

I haven't looked at the perf claims since it's not meaningful to talk about performance when things don't functionally match.

There might be a few things to discuss however

This is where a proposal like this become challenging. Is just * sufficient? Do we also need ?? Some fairly basic scenarios entail character sets... what about those? And so on. It's easy to come up with simple examples that depend on this or that feature, at which point you find yourself either building a bunch of specialized implementations, or just using a general regex engine.

I think we'd need to really understand the target scenarios, what was required for them, and why regex was insufficient to add a specialized method for it.

That said, such a method already exists in .NET Core, as part of Microsoft.VisualBasic.Core.dll, and you can use it from C# if you like:
```C#
using Microsoft.VisualBasic;
using Microsoft.VisualBasic.CompilerServices;
using System;

class Program
{
static void Main()
{
Console.WriteLine(LikeOperator.LikeString("aaaa", "*a", CompareMethod.Binary));
}
}
```

[Symbai]

@stephentoub: One scenario would be filtering a collection in WPF by user input. If a collection has a lot of entries which isn't unusual it would perform the check for each entry. So 200,000 calls to regex for 200,000 entries. More calls for more entries.

Filtering file system against multiple inputs would be another performance critical situation. Either you call GetFiles(".") and then do regex against each file two times for two inputs or you call GetFiles(input1) + GetFiles(input2) which I dont know if its faster but definitely slower than a custom string wildcard match.

I am aware of such a method exist in VB.NET but (edit: it's slower even than regex, see below) I dont understand why its VB.NET exclusive. Why it was added there? Why does C# have not such a method? Do it make sense for C# to have such a method as well? If not, does it make sense to keep such a method on VB.NET then?

This is where a proposal like this become challenging. Is just * sufficient? Do we also need ?? Some fairly basic scenarios entail character sets... what about those? And so on. It's easy to come up with simple examples that depend on this or that feature, at which point you find yourself either building a bunch of specialized implementations, or just using a general regex engine.

I wouldn't call this a challenge rather than a design choice. Star character is a must have. The others are nice to have but not certainly necessary. Like I said the idea was to not use regex for performance reasons and in this case the wild card match should be as fast as possible. The more character we support the less faster it will be and the reason to not use regex will also be less then. But this is just my opinion, when people want complex features to perform complex searches regex is better for them. For just a star wild card match regex is too slow however. You can easily get half if not less the duration by a custom implementation and maybe even better memory usages.

I've seen the .NET team fighting for 20ms improvements. Now this would be a larger improvement for literally low cost of implementation for common scenarios (i.e. filtering by end user input IS an often used feature). But if I cannot convince you then feel free to drop until someone else comes up with it.

//edit: For the records I've ran a benchmark of the IsMatchWithStarWildcard method against a regex version:

public static bool IsMatchRegex(this string str, string pattern)
{
    pattern = Regex.Escape(pattern);
    pattern = pattern.Replace(@"\*", ".*");
    return Regex.IsMatch(str, pattern);
}

Benchmark:

[CoreJob]
[MemoryDiagnoser]
[RPlotExporter]
public class ObjectTest
{
    const string PersonName = "Per Torn Klas Monika";
    const string PersonNamePattern = "Per*Monika";

    [Benchmark]
    public bool Regex_1x()
    {
        bool result = false;
        result = PersonName.IsMatchRegex(PersonNamePattern);
        return result;
    }
    [Benchmark]
    public bool VBNET_1x()
    {
        bool result = false;
        result = LikeOperator.LikeString(PersonName, PersonNamePattern, Microsoft.VisualBasic.CompareMethod.Text);
        return result;
    }
    [Benchmark]
    public bool Custom_1x()
    {
        bool result = false;
        result = Sch.IsMatchWithStarWildcard(PersonName, PersonNamePattern);
        return result;
    }
    [Benchmark]
    public bool Regex_200k()
    {
        bool result = false;
        for (int i = 0; i < 200000; i++)
        {
            result = PersonName.IsMatchRegex(PersonNamePattern);
        }
        return result;
    }
    [Benchmark]
    public bool VBNET_200k()
    {
        bool result = false;
        for (int i = 0; i < 200000; i++)
        {
            result = LikeOperator.LikeString(PersonName, PersonNamePattern, Microsoft.VisualBasic.CompareMethod.Text);
        }
        return result;
    }
    [Benchmark]
    public bool Custom_200k()
    {
        bool result = false;
        for (int i = 0; i < 200000; i++)
        {
            result = Sch.IsMatchWithStarWildcard(PersonName, PersonNamePattern);
        }
        return result;
    }
    [Benchmark]
    public bool Regex_2m()
    {
        bool result = false;
        for (int i = 0; i < 2000000; i++)
        {
            result = PersonName.IsMatchRegex(PersonNamePattern);
        }
        return result;
    }
    [Benchmark]
    public bool VBNET_2m()
    {
        bool result = false;
        for (int i = 0; i < 2000000; i++)
        {
            result = LikeOperator.LikeString(PersonName, PersonNamePattern, Microsoft.VisualBasic.CompareMethod.Text);
        }
        return result;
    }
    [Benchmark]
    public bool Custom_2m()
    {
        bool result = false;
        for (int i = 0; i < 2000000; i++)
        {
            result = Sch.IsMatchWithStarWildcard(PersonName, PersonNamePattern);
        }
        return result;
    }
}

Results:

| Method | Mean | Error | StdDev | Gen 0 | Gen 1 | Gen 2 | Allocated |
|------------ |-------------------:|-------------------:|-------------------:|------------:|------:|------:|-------------:|
| Regex_1x | 565.4 ns | 1.2191 ns | 1.0807 ns | 0.0248 | - | - | 200 B |
| VBNET_1x | 1,161.3 ns | 2.0277 ns | 1.5831 ns | 0.1583 | - | - | 1248 B |
| Custom_1x | 172.6 ns | 0.2701 ns | 0.2527 ns | - | - | - | - |
| Regex_200k | 111,916,900.0 ns | 158,710.3188 ns | 140,692.5637 ns | 5000.0000 | - | - | 40000000 B |
| VBNET_200k | 236,496,002.0 ns | 5,790,122.5054 ns | 5,946,029.5174 ns | 31666.6667 | - | - | 249600000 B |
| Custom_200k | 34,759,701.9 ns | 83,225.8380 ns | 73,777.5376 ns | - | - | - | - |
| Regex_2m | 1,106,216,178.6 ns | 1,865,558.2249 ns | 1,653,768.7743 ns | 51000.0000 | - | - | 400000000 B |
| VBNET_2m | 2,354,742,947.1 ns | 51,823,545.3405 ns | 53,218,965.5747 ns | 318000.0000 | - | - | 2496000000 B |
| Custom_2m | 327,363,346.4 ns | 1,579,074.7548 ns | 1,399,808.6400 ns | - | - | - | - |

Pretty much speaks for itself.

[MarkPflug]

Your regex benchmark is "preparing" the regex each iteration. Try moving that out of the loop? That is probably the source of the bulk of the memory allocation. The regex should also probably be anchored with "^" + pattern + "$". Your benchmark is only testing a string that matches? Shouldn't you also benchmark non-matches, since that would be the more common case in practice? You might also try using the RegexOptions.Compiled, which can provide a significant performance improvement when the regex is reused a lot. Probably also need RegexOptions.SingleLine for it to behave like your custom method?

But, before any of that matters you need to make sure your custom code is correct, and it sounds like it has some bugs. Making it correct might also impact it's performance. So, are you sure that regex isn't fast enough? It seems like you are currently comparing apples and oranges.

[Symbai]

@MarkPflug I was testing the bug-free IsMatchWithStarWildcard, not my custom code so that's irrelevant for the benchmark. Also moving this out of the loop will improve the benchmark but not cover real world scenarios. Same for compiled.

One real world scenario would be WPF collection filter:

string _filterString;
public string FilterString
{
   get => _filterString;
  set 
  { 
      _filterString = value; 
      NotifyPropertyChanged("FilterString");
      _customerView.Refresh();
  }
}
bool CustomerFilter(object item)
{
    Customer customer = item as Customer;
    return customer.IsMatchWithStarWildcard( _filterString );
}

CustomerFilter would be called by .NET for every item in the collection and the FilterString is changed by the end user. Nothing to compile and move out of loop here. For this real world scenario you will get the results of the benchmark.

[svick]

@Symbai

CustomerFilter would be called by .NET for every item in the collection and the FilterString is changed by the end user. Nothing to compile and move out of loop here. For this real world scenario you will get the results of the benchmark.

You can compile the regex whenever FilterString is set and then use that from CustomerFilter. That way, you won't pay the cost of parsing the regex on every call to CustomerFilter.

[danmosemsft]

Yes, to be fair you should move preparing and compiling the regex out of the loop -- if the concern is performance, that is what you would do.