Julian's parsing challenge

It all started with Tommy Valand. He posted an idea he had for speeding up string concatenation. Julian Robichaux chimed in with a StringBuffer class he had written in LotusScript that was even faster. We're talking 75,000 iterations in 0.25 seconds! In the comments on Julian's blog he offered the challenge of finding the fastest way to parse a string a character at a time. Game on!

First up I tried a rather pedestrian approach of Mid$() in a loop. I created a string of 32000 characters, ran it a few times, and got an average time of 3.6 seconds. Not shabby, but I knew somebody out there would blow that out of the water so I had to do better. :-P

I knew if I could get the characters into an array I could rip through them lightning fast. But putting the characters into an array a character at a time so I could read them, when the whole point is to read the string a character at a time, was just silly.

I spent a lot of my early career coaxing the maximum performance possible out of Visual Basic. That often draws some laughs, but people shouldn't be so dismissive. I haven't worked a lot with VB.Net, so I know mostly about "classic" VB (versions 5 and 6), which is so similar to LotusScript you can copy and paste code from one to the other. It does have some advantages over LotusScript, such as pointers, but LS has its own bag of tricks.

With this background I hit upon the idea of using a byte array. In VB I would use them in place of streams: open a connection to an FTP server, bring the data down into the byte array, then write it out to disk all at once. It was extremely efficient and incredibly fast. But how to apply this to a string that's in memory?

When I read through Julian's StringBuffer class it rang a bell. I went digging and found a string handling library from Visual Basic Programmer's Journal back in 1999. The code is remarkably similar to Julian's. I'm in no way accusing Julian of plagiarism, it was just interesting to me that two extremely intelligent people came up with such similar solutions. It's like Fert and Grünberg coming up with giant magnetoresistance separately.

Anyway, in the interest of full disclosure here's the VBPJ article (pdf) that inspired me. You may also be interested in this other article I found while researching this. It's all about VB6, but it is still an interesting read. Or it was to me.

Shoehorning this into LotusScript, here is what I came up with.

(Declarations)
Declare Sub CopyMemory Lib "kernel32" Alias "RtlMoveMemory" (dest As Any, Source As Any, Byval Bytes As Long)

Sub Initialize
   Const strBaseText = "test"
 
   Dim sglStart As Single
   Dim sglEnd As Single
   Dim sglElapsed As Single
 
   Dim strText As String
   Dim strTextArray() As Byte
   Dim strOneChar As String * 1 'a fixed-length string performs better
 
   Dim lngSize As Long
   Dim lngIndex As Long
 
   For lngIndex = 1 To 8000 'create a string of 32000 chars
       strText = strText & strBaseText
   Next
 
   sglStart = Timer()
   lngSize = Len(strText)  
   Redim strTextArray(0 To lngSize)
   CopyMemory strTextArray(0), Byval strText, lngSize
   For lngIndex = Lbound(strTextArray) To Ubound(strTextArray)
       strOneChar = Chr$(strTextArray(lngIndex))
   Next
   sglEnd = Timer()  
 
   sglElapsed = sglEnd - sglStart
   Print "Elapsed time: " & sglElapsed
 
End Sub

This LotusScript was converted to HTML using the ls2html routine,
provided by Julian Robichaux at nsftools.com.

How does it perform? Well the first time you run it...



That's certainly respectable since it's so much better than the 3.6 seconds I was seeing with a native LotusScript solution. Running the agent a second time it's like this



A few things to keep in mind

1. This is Windows only. CopyMemory is a Win32 API call so if you run this on a server that isn't Windows you will get an error.
2. It's limited to 32K characters since that's the limit of an array in LotusScript. I picked 32000 as a round number.
   
3. This is running on my fairly high-end home PC: Windows XP SP2 32-bit, Athlon 64 FX 5600+, 4GB DDR2, Seagate 7200.10 SATA2 drives. Your performance may vary.

Julian said he was going to look for a native solution that could top this, and since I cracked open the Windows API, he's going for Notes C API. That is a black art and he knows it well, so I'm skeered. :-|

Postscript about CopyMemory

It occurred to me that some people might be wondering why CopyMemory works. Why does it take a string and put the ASCII values of the characters into an array when I only give it the first element? It has to do with the way strings are stored in memory. In memory there isn't an "a" stored. It's the ASCII code. Variables are stored in one continuous segment of memory, whether it's a string or an array. So when you pass the string to CopyMemory, you're telling Windows "put the first byte in the string into slot 0 of the array, and continue doing this for X elements". Since the string is already in memory, and so is the byte array, it's able to do this move in one operation. That's why it's so insanely fast.

What I found genuinely surprising was that looping through the resulting array and using Chr$() to do assignments to a variable was so fast. Based on my experience with VB (and as shown in the article linked above), Chr$() is usually a fairly slow operation. The Notes API developers did some kind of mojo that makes this function incredibly fast in LotusScript.