Character replacement in strings in VB.NET

Question

How fast can I replace characters in a string?

So the background on this question is this: We have a couple of applications that communicate with each other and with clients' applications through sockets. These socket messages contain non-printable characters (e.g. chr(0)) which need to get replaced with a predetermined string (e.g "{Nul}"}, because the socket messages are kept in a log file. On a side note, not every log message will need to have characters replaced.

Now I started off on this little adventure reading from this MSDN link which I found from a different post from this site.

The current method we used...at the beginning of the day...was using StringBuilder to check for all the possible replacements such as...

    Public Function ReplaceSB(ByVal p_Message As String) As String
      Dim sb As New System.Text.StringBuilder(p_Message)

      sb.Replace(Chr(0), "{NUL}")
      sb.Replace(Chr(1), "{SOH}")

      Return sb.ToString
    End Function

Now as the blog post points out leaving StringBuilder out and using string.replace does yield faster results. (Actually, using StringBuilder was the slowest method of doing this all day long.)

    p_Message = p_Message.Replace(Chr(0), "{NUL}")
    p_Message = p_Message.Replace(Chr(1), "{SOH}")

Knowing that not every message would need to go through this process I thought it would save time to not have to process those messages that could be left out. So using regular expressions I first searched the string and then determined if it needed to be processed or not. This was about the same as using the string.replace, basically a wash from saving the time of not processing all the strings, but losing time from checking them all with regular expressions.

Then it was suggested to try using some arrays that matched up their indexes with the old and the new and use that to process the messages. So it would be something like this...

Private chrArray() As Char = {Chr(0), Chr(1)}
Private strArray() As String = {"{NUL}", "{SOH}"}

Public Function TestReplace(ByVal p_Message As String) As String
    Dim i As Integer

    For i = 0 To ((chrArray.Length) - 1)
        If p_Message.Contains(chrArray(i).ToString) Then
            p_Message = p_Message.Replace(chrArray(i), strArray(i))
        End If
    Next

    Return p_Message
End Function

This so far has been the fastest way I have found to process these messages. I have tried various other ways of going about this as well like converting the incoming string into a character array and comparing along with also trying to loop through the string rather than the chrArray.

So my question to all is: Can I make this faster yet? What am I missing?

Solution

You might be able to squeeze out a little more speed by reducing some lookups. Take for example this:

    If p_Message.Contains(chrArray(i).ToString) Then

The .Contains method is O(n). In the worst case, you're going to traverse all the chars in the entire string without finding anything, so you expect to traverse at least one time for each character in your array, so its O(nm) where n is the length of your string and m is the number of chars you're replacing.

You might get a little better performance doing the following (my VB-fu is rusty, has not been tested ;) ):

Private Function WriteToCharList(s as String, dest as List(Of Char))
    for each c as Char in s
        dest.Add(c)
    Next
End Function

Public Function TestReplace(ByVal p_Message As String) As String
    Dim chars as new List(Of Char)(p_Message.Length)

    For each c as Char in p_Message
        Select Case c
            Case Chr(0): WriteToCharList("{NUL}", chars)
            Case Chr(1): WriteToCharList("{SOH}", chars)
            Case Else: chars.Add(c);
        End Select
    Next

    Return New String(chars)
End Function

This will traverse chars in p_Message at most twice (once for traversing, once when the string constructor copies the char array), making this function O(n).

Comments

[Juliet]

If you have the option to use C#, you might be able to write a wickedly fast function with unsafe code.

[Tim]

I had wondered if that would have been possible, but soon counted that option out because of the parameters I was given to work with...oh well

[Tim]

StringBuilder's replace() function was the slowest that I have tried all day long. When processing through 240 log messages StringBuilder was about 1.8 milliseconds slower than the last way of processing the messages from my OP.

[Juliet]

"It depends" is the right answer here. You can't really guarantee StringBuilder is faster without actually profiling.

[Tim]

I played around with different ways of using .IndexOf() and .Contains() without gaining any results, usually about a tenth or two of a millisecond slower. I am going to try some more testing with your number 2 and 3... I will post back results

[Juliet]

Note that I'm initializing the size of the chars list. The List<T> collection is basically a wrapper around an array, and if you add more items than the array can hold, it resizes the array to double its size -- so adding a single char is worst case O(n), average case O(1). If you can estimate the number of Chr(0) and Chr(1) characters you have, or just allocate a large enough buffer, you can improve performance a little bit by avoiding the occasional array resize when the number of chars you're adding exceeds the length of your char array.

[Joel Coehoorn]

Note that while accurate from a BigO standpoint, in practice this iss only faster when your dictionary size get's up a little larger - at least 10 elements or more.

[Tim]

I am using a list of 240 raw log messages for each test. I choose this set based on a heavier than average work load for the function in question. Everything in each test is exactly the same except for the function that does the replacing.

[Tim]

Well I tested this a bit and while the speed isn't bad, at this point this isn't the best answer. I do think this solution would be better if I were to more actively change other parts of the app to pass streams up the chain as you mention in your number 3 which I like the idea of doing but I don't know at the moment if that would be possible. Thank you for your thoughts!

[Tim]

This was definitely faster. This actually cut about 2 milliseconds off what is in place now using the same test data of 240 raw messages, but this wasn't the fastest that in all my testing which kind of surprised me...Thanks for the help

[Tim]

Interesting read, but the results that I have seen have been the opposite of that. StringBuilder, at least in my testing, has been one of the slower options.

[Tim]

Thank you Juliet. I gave every answer a test or two and this came up the as the fastest. Well the final solution wasn't exactly like this, the basic idea is still the same. I was a little surprised, for some reason I didn't think that select case would be that fast, but it is.