How to outperform this regex replacement?

Question

After considerable measurement, I have identified a hotspot in one of our windows services that I'd like to optimize. We are processing strings that may have multiple consecutive spaces in it, and we'd like to reduce to only single spaces. We use a static compiled regex for this task:

private static readonly Regex 
    regex_select_all_multiple_whitespace_chars = 
        new Regex(@"\s+",RegexOptions.Compiled);

and then use it as follows:

var cleanString=
    regex_select_all_multiple_whitespace_chars.Replace(dirtyString.Trim(), " ");

This line is being invoked several million times, and is proving to be fairly intensive. I've tried to write something better, but I'm stumped. Given the fairly modest processing requirements of the regex, surely there's something faster. Could unsafe processing with pointers speed things further?

Edit:

Thanks for the amazing set of responses to this question... most unexpected!

Answer 1

Just one suggestion, if your data don't have unicode whitespaces, instead of \s+ use [ \r\n]+ or [ \n]+ or just  + (if there is space only), basically limit it to minimum character set.

Answer 2

Currently, you are replacing a single space with another single space. Try to match \s{2,} (or something similar, if you want to replace single newlines and other characters).

Answer 3

You could not use regular expressions. For example:

private static string NormalizeWhitespace(string test)
{
    string trimmed = test.Trim();

    var sb = new StringBuilder(trimmed.Length);

    int i = 0;
    while (i < trimmed.Length)
    {
        if (trimmed[i] == ' ')
        {
            sb.Append(trimmed[i]);

            do { i++; } while (i < trimmed.Length && trimmed[i] == ' ');
        }

        sb.Append(trimmed[i]);

        i++;
    }

    return sb.ToString();
}

With this method and the following test bed:

private static readonly Regex MultipleWhitespaceRegex = new Regex(
    @"\s+", 
    RegexOptions.Compiled);

static void Main(string[] args)
{
    string test = "regex  select    all multiple     whitespace   chars";

    const int Iterations = 15000;

    var sw = new Stopwatch();

    sw.Start();
    for (int i = 0; i < Iterations; i++)
    {
        NormalizeWhitespace(test);
    }
    sw.Stop();
    Console.WriteLine("{0}ms", sw.ElapsedMilliseconds);

    sw.Reset();

    sw.Start();
    for (int i = 0; i < Iterations; i++)
    {
        MultipleWhitespaceRegex.Replace(test, " ");
    }
    sw.Stop();
    Console.WriteLine("{0}ms", sw.ElapsedMilliseconds);
}

I got the following results:

// NormalizeWhitespace - 27ms
// Regex - 132ms

Note that this was only tested with a very simple example, could be further optimized by removing the call to String.Trim and is only provided to make a point of regular expressions sometimes not being the best answer.

Answer 4

This is about three times faster:

private static string RemoveDuplicateSpaces(string text) {
  StringBuilder b = new StringBuilder(text.Length);
  bool space = false;
  foreach (char c in text) {
    if (c == ' ') {
      if (!space) b.Append(c);
      space = true;
    } else {
      b.Append(c);
      space = false;
    }
  }
  return b.ToString();
}

Answer 5

I'm curious how a straight forward implementation might perform:

    static string RemoveConsecutiveSpaces(string input)
    {
        bool whiteSpaceWritten = false;
        StringBuilder sbOutput = new StringBuilder(input.Length);

        foreach (Char c in input)
        {
            if (c == ' ')
            {
                if (!whiteSpaceWritten)
                {
                    whiteSpaceWritten = true;
                    sbOutput.Append(c);
                }
            }
            else
            {
                whiteSpaceWritten = false;
                sbOutput.Append(c);
            }
        }

        return sbOutput.ToString();
    }

Answer 6

As it is such a simple expression, replacing two or more spaces with a single space, get rid of the Regex object and hard code the replacement yourself (in C++/CLI):

String ^text = "Some   text  to process";
bool spaces = false;
// make the following static and just clear it rather than reallocating it every time
System::Text::StringBuilder ^output = gcnew System::Text::StringBuilder;
for (int i = 0, l = text->Length ; i < l ; ++i)
{
  if (spaces)
  {
    if (text [i] != ' ')
    {
      output->Append (text [i]);
      spaces = false;
    }
  }
  else
  {
    output->Append (text [i]);
    if (text [i] == ' ')
    {
      spaces = true;
    }
  }
}
text = output->ToString ();

Answer 7

How about this...

public string RemoveMultiSpace(string test)
{
var words = test.Split(new char[] { ' ' }, 
    StringSplitOptions.RemoveEmptyEntries);
return string.Join(" ", words);
}

Test case run with NUnit:
Test time is in milliseconds.

Regex Test time: 338,8885
RemoveMultiSpace Test time: 78,9335

private static readonly Regex regex_select_all_multiple_whitespace_chars =
   new Regex(@"\s+", RegexOptions.Compiled);

[Test]
public void Test()
{
    string startString = "A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      ";
    string cleanString;
    Trace.WriteLine("Regex Test start");
    int count = 10000;
    Stopwatch timer = new Stopwatch();
    timer.Start();
    for (int i = 0; i < count; i++)
    {
        cleanString = regex_select_all_multiple_whitespace_chars.Replace(startString, " ");
    }
    var elapsed = timer.Elapsed;
    Trace.WriteLine("Regex Test end");
    Trace.WriteLine("Regex Test time: " + elapsed.TotalMilliseconds);

    Trace.WriteLine("RemoveMultiSpace Test start");
    timer = new Stopwatch();
    timer.Start();
    for (int i = 0; i < count; i++)
    {
        cleanString = RemoveMultiSpace(startString);
    }
    elapsed = timer.Elapsed;
    Trace.WriteLine("RemoveMultiSpace Test end");
    Trace.WriteLine("RemoveMultiSpace Test time: " + elapsed.TotalMilliseconds);
}

public string RemoveMultiSpace(string test)
{
    var words = test.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
    return string.Join(" ", words);
}

Edit:
Made some more tests and added Guffa´s method "RemoveDuplicateSpaces" based on StringBuilder.
So my conclusion is that the StringBuilder method is faster when there is a lot of spaces, but with less spaces the string split method is slightly faster.

Cleaning file with about 30000 lines, 10 iterations
RegEx time elapsed: 608,0623
RemoveMultiSpace time elapsed: 239,2049
RemoveDuplicateSpaces time elapsed: 307,2044

Cleaning string, 10000 iterations:
A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      A B  C   D    E     F      
RegEx time elapsed: 590,3626
RemoveMultiSpace time elapsed: 159,4547
RemoveDuplicateSpaces time elapsed: 137,6816

Cleaning string, 10000 iterations:
A      B      C      D      E      F      A      B      C      D      E      F      A      B      C      D      E      F      A      B      C      D      E      F      A      B      C      D      E      F      A      B      C      D      E      F      A      B      C      D      E      F      A      B      C      D      E      F      
RegEx time elapsed: 290,5666
RemoveMultiSpace time elapsed: 64,6776
RemoveDuplicateSpaces time elapsed: 52,4732

Answer 8

Arrays always will be faster

        public static string RemoveMultiSpace(string input)
    {
        var value = input;

        if (!string.IsNullOrEmpty(input))
        {
            var isSpace = false;
            var index = 0;
            var length = input.Length;
            var tempArray = new char[length];
            for (int i = 0; i < length; i++)
            {
                var symbol = input[i];
                if (symbol == ' ')
                {
                    if (!isSpace)
                    {
                        tempArray[index++] = symbol;
                    }
                    isSpace = true;
                }
                else
                {
                    tempArray[index++] = symbol;
                    isSpace = false;
                }
            }
            value = new string(tempArray, 0, index);
        }

        return value;
    }