8

Basically what I would like to do is run multiple (15-25) regex replaces on a single string with the best possible memory management.

Overview: Streams a text only file (sometimes html) via ftp appending to a StringBuilder to get a very large string. The file size ranges from 300KB to 30MB.

The regular expressions are semi-complex, but require multiple lines of the file (identifying sections of a book for example), so arbitrarily breaking the string, or running the replace on every download loop is out of the answer.

A sample replace:

Regex re = new Regex("<A.*?>Table of Contents</A>", RegexOptions.IgnoreCase);
source = re.Replace(source, "");

With each run of a replace the memory sky rockets, I know this is because string are immutable in C# and it needs to make a copy - even if I call GC.Collect() it still doesn't help enough for a 30MB file.

Any advice on a better way to approach, or a way to perform multiple regex replaces using constant memory (make 2 copies (so 60MB in memory), perform search, discard copy back to 30MB)?

Update:

There does not appear to be a simple answer but for future people looking at this I ended up using a combination of all the answers below to get it to an acceptable state:

  1. If possible split the string into chunks, see manojlds's answer for a way to that as the file is being read - looking for suitable end points.

  2. If you can't split as it streams, at least split it later if possible - see ChrisWue's answer for some external tools that may help with this process to piping to files.

  3. Optimize the regex, avoid greedy operators and try to limit what the engine has to do as much as possible - see Sylverdrag's answer.

  4. Combine the regex when possible, this cuts down the number of replaces for when the regexs are not based on each other (useful in this case for cleaning bad input) - see Brian Reichle's answer for a code sample.

Thank you all!

Improve this question
4
  • I am calling each regex once on the string, will compiling help with the number of times it does a replace? Like in the sample regex, if there was 500 matches of Table of Contents to replace, would a complied version run faster? Commented Apr 16, 2011 at 3:52
  • Sorry, realized my mistake there and removed my comment, but you had replied by then. Yes, compiling may not give benefits for you. Commented Apr 16, 2011 at 3:57
  • I am not sure if the requirement allows you to parse a file line. If a line in the file can be considered independently then I suggest you to parse each file line (CPU vs memory??) instead of entire file into the memory. CPU cycles/time taken may increase but I think memory used will reduce. You can give it a try. Commented Apr 16, 2011 at 4:30
  • Is your memory consumption due to the fact that Regex.Replace constructs a new string? If it is, then don't use Regex.Replace, user Regex.Match instead, and write your own replacement engine, that would read/scan the input string and writes the output stream/stringbuilder replacing the parts that Regex.Match finds for you. Will this work? Commented Apr 16, 2011 at 6:32

4 Answers 4

Reset to default
2

Depending on the nature of the RegEx's, you might be able to combine them into a single regular expression and use the overload of Replace() that takes in a MatchEvaluator delegate to determine the replacement from the matched string.

Regex re = new Regex("First Pattern|Second Pattern|Super(Mega)*Delux", RegexOptions.IgnoreCase);

source = re.Replace(source, delegate(Match m)
{
    string value = m.Value;

    if(value.Equals("first pattern", StringComparison.OrdinalIgnoreCase)
    {
        return "1st";
    }
    else if(value.Equals("second pattern", StringComparison.OrdinalIgnoreCase)
    {
        return "2nd";
    }
    else
    {
        return "";
    }
});

Of course this falls apart if latter patterns need to be able to match on the result of earlier replacements.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Yes, sorry I forgot to add that some replacements are based off of other replacements. However, using this method I was able to combine several and got down to about 5 Replace calls - thank you!
2

Have a look at this post which talks about searching a stream using regular expressions rather than having to store in a string which consumes memory:

http://www.developer.com/design/article.php/3719741/Building-a-Regular-Expression-Stream-Search-with-the-NET-Framework.htm

Improve this answer

2 Comments

That's certainly an interesting read, but won't help if the pattern does not have a fixed upper bound on the length. The only way around this that I can think of is to keep the "state" at the end of scanning one string when starting on the next. But then you would also need hold on to past "pages" that could yet match.
Concur with Brian, it doesn't quite get all the way there, but I think I will be using this technique combined with several of the answers so that it aims for a best-break opportunities using this method and save it out to files mentioned in ChrisWue's answer. With your answer Brian it brings everything to a much more manageable state.
2

I have a fairly similar situation.

Use the compile option for the regex:

Source = Regex.Replace(source, pattern, replace, RegexOptions.Compiled);

Depending on your situation, it can make a major difference in speed.

Not a complete solution, especially for files larger than 3-4 Mb.

If you get to decide which regex should be run (not my case), you should probably optimize the regex as much as possible, avoiding the costly operations. For instance, avoid ungreedy operators, avoid look aheads and look behind.

Instead of using:

<a.*?>xxx

use

<a[^<>]*>xxx

The reason being that an ungreedy operator forces the regex engine to check each and every character compared to the rest of the expression whereas [^<>] only requires to compare the current character to < and > and stops as soon as the condition is matched. On a large file, this can make the difference between half a second and an application freeze.

It doesn't totally solve the problem, but it should help.

Improve this answer

2 Comments

That second tidbit does help a lot, and now looking back it is an extremely obvious optimization -- from rough testing changing about 8 of the ungreedy . star to the not <> cut the compute time down by about 2 minutes on a prev. 10 min job.
@WSkid: 2 minutes down is not bad at all. Did you try compiling as well? With large files, it should be paying off. It makes quite a bit of difference over here.
1

Assuming that the documents you load have some kind of structure you might be better off writing a parser to put the document into a stuctured form, breaking the large string into multiple chunks, and then operate on that structure.

One problem with large string is that objects over 85,000 bytes are considered large objects and put on the large object heap which is not compacted and it can lead to unexpected out of memory situations.

Another option would be to pipe it through an external tool like sed or awk.

Improve this answer

1 Comment

Thank you for that second part -- lead me to this bug report saying that the LOH is indeed fragmented and has potential OOM errors in .Net 2 and 3.5 but is slightly better in 4.0: connect.microsoft.com/VisualStudio/feedback/details/521147/…

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.