c# regex high cpu usage

Question

my little program is checking what type of script website use and it use over 80% cpu i7 processor. I wonder is it normal?

Code:

public static class EnginesMatcher
{

    public static readonly Regex Drupal1 =
        new Regex(
            @"/misc/drupal\.js|Drupal\.settings|href=""http://drupal\.org""|\?q=node/[0-9]+|/\?q=user/register|/\?q=user/password|/user/register\?destination|<li class=""collapsed""><a href=""/node/add"">|/dpl3/files/|/modules/node/",
            RegexOptions.Compiled);

    public static readonly Regex XE1 =
        new Regex(
        @"XpressEngine|content=""zeroboardXE|content=""xe_board""|var zbxe_session_name|/xe\.css\?2|/xeicon/favicon\.ico""|#xe-editor-container-1|xpress_xeditor",
            RegexOptions.Compiled);

    //and 60 more such regex

In another class

  public async Task<Result> Match(string url)
        {

            if (!await Open(url).ConfigureAwait(false)) return ResultKey;


            if (EnginesMatcher.Drupal1.IsMatch(html))
            {
                return new Result()
                {
                    Key = AResultKey.Success,
                    LogFile = "Drupal.txt",
                    Message = "Drupal",
                    Url = url
                };
            }
            if (EnginesMatcher.XE1.IsMatch(html))
            {
                return new Result()
                {
                    Key = AResultKey.Success,
                    LogFile = "Drupal.txt",
                    Message = "Drupal",
                    Url = url
                };
            }

The Match(url) function is in ForeachAsyncLoop, the program check about 4000 links/minute. When I disable all regexs it uses up to 20% cpu, can I increase regex performance?emphasized text

I am interested in seeing the answers for this as i have noticed this too — 06needhamt
Regex uses a lot of cpu because of it's features. If you know exactly what you are looking for it can be a lot faster to do the matching yourself without regex. Also doing pruning can make it faster (aka. removing stuff you know you don't need to check) — Automatico
Are you really surprised this type of code uses a ton of CPU? — EkoostikMartin
The regexes you have there essentially all test for verbatim strings (with very few exceptions). The .NET engine should be handling those pretty fast, probably as fast as (if not faster than) any string matching routines you may write on your own. So my guess is that you have another regex further down the line (one of the "other 60" regexes) that exhibits pathological behavior (like catastrophic backtracking). You need to profile the regexes separately and find out where exactly your CPU load is generated. — Tim Pietzcker

Jim Mischel Jim Mischel · Accepted Answer · 2013-11-13T22:17:16

You probably can't speed it up very with regular expressions. However, you can probably do a lot better by using a different algorithm.

The Aho-Corasick string matching algorithm is designed to do exactly what you're doing: looking for a fixed set of strings in a large body of text.

The standard algorithm doesn't support regular expressions, but your regexes are verbatim strings. That is, you're looking for this|that|something else|something more. Which is the same as looking for four different strings.

I published an implementation of the Aho-Corasick algorithm in C# a few years ago. With a few modifications to the way you do things, it should work well.

Start by building a dictionary of the strings you're looking for and the corresponding web sites:

Dictionary<string, string> StringsToSites = new Dictionary<string, string>();

Then, add the strings. For example, for Drupal you'd add:

StringsToSites.Add("/misc/drupal\.js", "Drupal");
StringsToSites.Add("Drupal.settings", "Drupal");
StringsToSites.Add(@"href=""http://drupal\.org"", "Drupal");
// problem with this one ...   |\?q=node/[0-9]+
StringsToSites.Add("?q=user/register", "Drupal");
// etc., etc.

Note that there's a problem with things that are not verbatim strings. There's no way for the implementation to match "?q=node/[0-9]+/". The best we could do is add the string "?q=node/".

Then, create a matcher and populate it:

AhoCorasickStringSearcher matcher = new AhoCorasickStringSearcher();
foreach (var key in StringsToSites.Keys)
{
    matcher.AddItem(key);
}
matcher.CreateFailureFunction();

Then, for every link you see, call matcher.Search:

var Matches = matcher.Search(link);

That will give you a collection of StringMatch objects. You can look up the Text in the dictionary to see which site it matches. For example:

foreach (var m in Matches)
{
    string site;
    if (StringsToSites.TryGetValue(m.Text, out site))
    {
        Console.WriteLine("Text '{0}' matches site '{1}'.", m.Text, site);
    }
}

I would expect this to be at least 10 times as fast as your regex solution, possibly 100 times as fast.

c# regex high cpu usage

2 Answers