Sunday, October 14, 2007

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.

10 comments:

  1. Wow, that VBPJ article is very interesting, especially the string searching technique. It looks like that CString class converts the whole string to a byte array, is that right? The article didn't show that portion of the code, but that's how I interpreted it.

    My StringBuffer class just holds the variable-length strings that are appended as individual elements of the internal array, so an element might be a single character or a gigantic chunk of text. I guess to do the improved searching and parsing that he's talking about in the article you would have to have a byte array instead of a variable length string array though.

    Also, the comment about fixed-length strings being faster than variable-length ones inspired me to do a few tests. More on that later (if anything interesting comes of it).

    ReplyDelete
  2. Great stuff!

    I'll see if I can get some numbers on concatenation in a Java-agent tomorrow, if someone doesn't beat me to it.. :)

    ReplyDelete
  3. Not to too diminish your efforts, Charles, but I'd think that the response to Julian's challenge would need to be cross-platform, don't you?

    I mean, I can certainly see AIX, Linux or iSeries servers needing to perform this type of operation.

    But hey... it's more than I'm doing with any of this right now! :-D

    ReplyDelete
  4. Interesting, but I'm concerned bout one thing. I believe that LotusScript strings are composed of double-byte Unicode characters, not single byte ASCII characters. That being the case, I suspect you're only copying half the characters.

    ReplyDelete
  5. @Nathan - I thought about that, but I couldn't find anything other than heading into Java territory... which I'm not familiar with. The best LotusScript approach I could come up with was Mid$ in a loop. And to be honest, in my opinion it performed quite well.

    @Richard - I thought of that, too, and while LenB does return 64000 for the length of the array, the actual values are the ASCII characters. It was a bit perplexing, but I don't know enough about the internals of LotusScript to explain the mismatch. The output matches the input, which all I can expect. It is interesting to me that LotusScript lacks specific Unicode functions for string handling. I can only assume this is being handled in the Notes API automagically. If you have any info to share I would love to hear it since this is a largely undocumented area of LotusScript as far as I know.

    ReplyDelete
  6. I've got some native, cross-platform LotusScript code that'll convert a 100,000 character string to an array of single characters (actually a set of arrays) in 0.3125 seconds on my machine. Not anywhere near the CopyMemory speed you're getting Charles, but not bad for native LotusScript. I'll clean it up tomorrow (Monday) and post in the evening. Maybe Tommy will be done with his Java test by then too.

    ReplyDelete
  7. 700 000 character string to char array in Java, 15ms.

    http://dontpanic82.blogspot.com/2007/10/string-to-char-array-in-java.html

    ReplyDelete
  8. It looks like Java wins for cross-platform speed. :-) This has been fun!

    ReplyDelete
  9. Yeah, but just try to recover the temporary storage space! The garbage collector will free it when it doggone feels like it!

    ReplyDelete
  10. I know that this post is ages old but I thought I would share anyway because loops can have a dramitic effect I moved the start timer just above the last for loop and my machine kicked out .045 - .062 coded as is.

    When I changed the loop to:

    Dim bot%, top%
    bot = LBound(strTextArray)
    top = UBound(strTextArray)
    For lngIndex = bot To top
    strOneChar = Chr$(strTextArray(lngIndex))
    Next

    The bounds don't have to be determined at every iteration I was getting a .039 to .050

    I changed to a forall loop.
    Forall v in strTextArray
    strOneChar = Chr$(v)
    End Forall

    And measured .031 to .039

    happy coding :)

    ReplyDelete