An Overview of the Corvus.Globbing Library

TLDR; In this post we look at Corvus.Globbing, a C# library for working with globs. We show how to get started with the library, some examples demonstrating how to use it, and performance benchmarks illustrating its low allocation properties and superior performance over other similar libraries.

Introduction

The Corvus GitHub Organisation contains a series of open-source repositories that provide tools and support for common requirements such as tenancy storage, authentication and more. Corvus encapsulate endjin's recommended practices for building .NET applications. These practices are founded in the knowledge gained through over a decade of real world experience building .NET applications for our customers.

Each blog post in this series will focus on a single Corvus repository, outlining the repository's intended use and how to get started.

Overview of Corvus.Globbing

In this blog post Corvus.Globbing is under the spotlight. Corvus.Globbing is a library for working with globs, it was built to be zero allocating with performance comparable to (or better than) DotNet.Glob and raw Regular Expressions, when running under dotnet 6.0.

About Globbing

Globbing is the process of using wildcard characters for defining patterns to match file names and directories against partial names. For example, in a bash shell, if you were to run ls *.txt, it would return all files inside the current working directory with a .txt file extension. The text *.txt is the glob. The wildcard character, *, essentially says "match against anything here" – so, find every file inside this directory whose name ends with the sequence of characters: '.txt'.

As another example, If you were to run ls hello*.txt, it would match all files beginning with 'hello' and ending with '.txt', meaning this glob would match against a file named 'hello-world.txt', for example. Alternatively, ls *hello*.txt, matches all files with names that contain the word 'hello' and end with '.txt'. In all of these cases the wildcard character, *, says "match against anything here". The * is the most common, but not the only, wildcard character; Corvus.Globbing supports others, as you'll see in the repo's README.

Internally, the bash shell has to parse the glob, then do some searching and comparing to find the file names that match the pattern provided. This is what Corvus.Globbing offers – the ability to match a glob pattern against file paths and names. Specifically, it allows you to say "does this glob match this file name/path" through the Match() method, as you'll see shortly.

Use Cases

The particular use case we have optimized for is a case-sensitive glob that will be matched against a large number of paths (100+), but will not necessarily be cachable.

We want a very high-performance parse of that glob, and then a performant application of the glob to a large number of candidate paths.

Our motivation for this came when "link stripping" documents to be returned from an HTTP request, to remove links that the requesting identity is not permitted to see (perhaps for security, feature enablement, or just local context). To make this process high performance we needed to minimise allocations on the hot-path of the request handler, the library has therefore been designed to be low-allocating.

Corvus.Globbing is built for net6.0.

Performance

We offer better raw matching performance (~10-30%) against a pre-tokenized glob pattern, for the StringComparison.Ordinal (case sensitive) default, than Dotnet.Glob.

Our tokenization is also ~10x faster than Dotnet.Glob so it is significantly faster in the single use/throwaway case.

See detailed performance benchmarks at the end of this post.

How to get started

Corvus.Globbing is available on NuGet. To get started with Corvus.Globbing, add a reference to the Corvus.Globbing NuGet package in your project, by running the following command:

dotnet add package Corvus.Globbing

How to use

Within the Corvus.Globbing repository, there is a Polyglot Notebook (under the folder Corvus.Globbing.Documentation.Examples) that provides examples on how to use the library. You can pull down the repo and run the notebooks locally yourself.

Examples

Basic use

The simplest use case just requires you to pass the glob and candidate path to the Match() method to determine if the glob and path match.

bool isMatch = Glob.Match("path/*atstand", "path/fooatstand"); // Returns: True

You can provide all the standard string-comparison types to the comparisonType parameter to customise the comparison behavior. The default is StringComparison.Ordinal (i.e. case sensitive), but you could do a case insensitive match:

bool isMatch = Glob.Match("path/*atstand", "PATH/fooatstand", StringComparison.OrdinalIgnoreCase); // returns: True

Efficient matching of a glob against multiple paths

If you want to match a glob against a number of paths, you want to avoid re-tokenizing the glob for each comparison.

For low memory allocation requirements and increased performance you can also stack allocate a tokenized glob array and reuse it:

string pattern = "path/*atstand";

// There can't be more tokens than there are characters in the glob pattern, so we allocate an array at least that long.
Span<GlobToken> tokenizedGlob = stackalloc GlobToken[pattern.Length];
int tokenCount = Corvus.Globbing.GlobTokenizer.Tokenize(pattern, ref tokenizedGlob);
// And then slice off the number of tokens we actually used
ReadOnlySpan<GlobToken> glob = tokenizedGlob[..tokenCount];

bool firstMatch = Glob.Match(pattern, glob, "path/fooatstand"); // Returns: True
bool secondMatch = Glob.Match(pattern, glob, "badpath/fooatstand"); // Returns: False

Efficient matching of a large glob against multiple paths

For very long potential globs you may not want to allocate them on the stack, instead you could fall back to the ArrayPool allocation technique.

The following example is useful if you don't necessarily know how long the glob is (e.g. if it's a command line argument, or an input to a web API). The code decides to use stackalloc if the provided pattern is less than a specified length, and the ArrayPool allocation technique when it is not.

int MaxGlobTokenArrayLength = 1024;

// There can't be more tokens than there are characters in the glob.
GlobToken[]? globTokenArray = null;
Span<GlobToken> globTokens = pattern.Length > MaxGlobTokenArrayLength ? stackalloc GlobToken[0] : stackalloc GlobToken[pattern.Length];

if (pattern.Length > MaxGlobTokenArrayLength)
{
    globTokenArray = ArrayPool<GlobToken>.Shared.Rent(pattern.Length);
    globTokens = globTokenArray.AsSpan();
}

try
{
    int tokenCount = GlobTokenizer.Tokenize(pattern, ref globTokens);
    ReadOnlySpan<GlobToken> tokenizedGlob = globTokens[..tokenCount];

    // Do your matching here...
    bool firstMatch = Glob.Match(pattern, tokenizedGlob, "path/fooatstand");
    Console.WriteLine($"Result of first match:\t{firstMatch}");

    bool secondMatch = Glob.Match(pattern, tokenizedGlob, "badpath/fooatstand");
    Console.WriteLine($"Result of second match:\t{secondMatch}");
}
finally
{
    if (pattern.Length > MaxGlobTokenArrayLength)
    {
        ArrayPool<GlobToken>.Shared.Return(globTokenArray);
    }
}

Benchmarks

We have used Benchmark Dotnet to compare the performance with raw RegEx and DotNet.Glob. This represents a current example run.

The numbers in square brackets in the cells under the Pattern column in the tables below are conveying the number of characters in the glob pattern used in that test run.

Compile

Here we're comparing the time and memory performance for compiling code that tokenizes a glob pattern.

Compile and match false

Comparing the time and memory performance for compiling and running Corvus.Glob.Match against the regex and DotNet.Glob equivalents, for the case where the string and glob pattern do not match.

Compile and match true

Comparing the time and memory performance for compiling and running Corvus.Glob.Match against the regex and DotNet.Glob equivalents, for the case where the string and glob pattern do match.

Match false

Comparing the time performance for running Corvus.Glob.Match against the regex and DotNet.Glob equivalents, for the case where the string and glob pattern do not match.

Match true

Comparing the time performance for running Corvus.Glob.Match against the regex and DotNet.Glob equivalents, for the case where the string and glob pattern do match.

The ratio column in the benchmark results above show that, for all patterns and operations tested, Corvus was faster than the DotNet.Glob and regex equivalents.

There's something else worth noting from these results. In the "compile and match" examples (both true and false), Corvus.Globbing is only 3.3x faster than RegEx (and 1.3x faster than DotNetGlob) when matching against 1000 strings, but Corvus.Globbing is over 1000x faster than RegEx (and ~10x faster than DotNetGlob) if we compile and match against a single string. This implies that with RegEx (and, to a lesser extent, DotNetGlob) the costs of compilation/parsing are very high compared to the cost of doing a match against a single string. Therefore, for it to be worth paying the up-front cost of compiling/parsing, you need to be matching against many more strings when using the other libraries compared to Corvus.Globbing.

As you can see, Corvus.Globbing is a useful library, with strong performance characteristics, for working with globs in C#.

If you have any thoughts on better ways to approach particular problems, or related tools you'd like to see, then we'd like to hear them – please comment below, or in the Issues section of the project.