Speed drop in iterative string concatenation

[JOSE MARIA N. RAMOS]

I came across this as I was trying to generate a string of 1,000,000 random ASCII characters (in the ASCII 65 TO 90 range). My idea was to generate one random character at a time, and then keep concatenating the results into one, long string.

For this test, I eliminated the RND segment and used the following code that simply adds the character "A" in varying iterations...

----------------------------------

 
#COMPILE EXE
#DIM ALL

GLOBAL PanString$
GLOBAL Start#
GLOBAL Finish#
GLOBAL Counter&

FUNCTION PBMAIN () AS LONG

    Start# = TIMER
    
        FOR Counter& = 1 TO 100000
           
             Panstring$ = Panstring$ + "A"
        
        NEXT Counter&

        BEEP
    
    Finish# = TIMER
    PRINT "ELAPSED TIME=";Finish#-Start#
    WAITKEY$
    

END FUNCTION

---------------------------------------------
Using my old 2.6GHz PC, and my PBCC Version 4.04.042, I got these results:

ITERATIONS                 SECONDS
-------------         ----------------
100,000                         1.828 
150,000                         4.186 
200,000                         7.188 
250,000                        15.360
300,000                        39.297
400,000                       141.530

Take note of the striking drop in processing speed after the 300,000th
iteration.

My workaround was to split the processing into fewer iterations (say, 10,000 iterations x 100) and then concatenate the 100 separate strings into the final long string.

Is this relative increase in processing time caused by the increasing length of the contents of PanString$ ? Or could this be attributable to something else? I'd appreciate any feedback.

[Bob Zale]

Jose--

String concatenation can be a bottleneck when you perform the operation on a string that's 400,000 bytes long, and then repeat the operation 400,000 times.

A better plan would be to first create a string which is 400,000 bytes long:

x$ = space$(400000)

then insert the characters using the ASC() statement or the MID$() statement...

FOR i& = 1 to 400000
ASC(x$, i&) = RND(65,90)
NEXT


Best regards,

Bob Zale
PowerBASIC Inc.

[Paul Dixon]

Jose,

Is this relative increase in processing time caused by the increasing length of the contents of PanString$ ? Or could this be attributable to something else? I'd appreciate any feedback.

The sudden drop will be caused by your system (CPU) running out of cache.
Cache memory is a lot faster than main memory but it's limited to around half to one megabyte in most systems. When you run out of cache the CPU is required to start using much slower main memory.

Paul.

[Mel Bishop]

Oops! Mis-read Bob's reply. Appologies.

But actually, going the full 1 meg string buffer wouldn't take that big a speed hit.

The following took less than a second to finish:

FUNCTION PBMAIN () AS LONG
    RANDOMIZE TIMER
    x$ = SPACE$(100000)
    LOCATE 5,1 : PRINT;LEFT$(x$,80)

    FOR i& = 1 TO 1000000
    ASC(x$, i&) = RND(65,90)
    NEXT

    LOCATE 7,1 : PRINT;LEFT$(x$,80);
    LOCATE 9,1 : PRINT;LEN(x$)
    WAITKEY$

    END FUNCTION

[Bob Zale]

Check those numbers, Mel... {smile} You're filling 1,000,000 bytes in a 100,000 byte string.

Best regards,

Bob Zale
PowerBASIC Inc.

[Michael Mattias]

>You're filling 1,000,000 bytes in a 100,000 byte string

Hell of a compresssion technique.

[Mel Bishop]

Point taken. Changed it to 1,000,000 and it still took < 1 second.

[John Gleason]

Here is the absolute array technique which is even faster still--ten million in just a couple seconds. Behold:

#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN () AS LONG

    LOCAL ii AS LONG
    LOCAL rndStr, printStr AS STRING
    rndStr = SPACE$(10000000)                    'use an absolute array now to overlap string memory:
    DIM rsArr(9999999) AS BYTE AT STRPTR(rndStr) 'size is 1 less than length of string because of rsArr(0) element
    RANDOMIZE
                                                 'now quickly fill array:
    FOR ii = 0 TO 9999999                        '10,000,000 total loop iterations
       rsArr(ii) = RND(65, 90)                   'changed to characters Jose wanted
    NEXT
    
    printStr = RIGHT$(rndStr, 4000)              'for printing purposes
    ? "Done. Here are the last 4000 characters:" & $CRLF & printStr
END FUNCTION

[Michael Mattias]

 LOCAL rndStr AS STRING
 LOCAL pB As BYTE PTR 
 REGISTER II AS LONG

 rndStr       = SPACE$(10000000)
 pb            = STRPTR(rndStr)
 RANDOMIZE
 FOR ii = 1 TO 10000000      '10,000,000 total loop iterations
       @pb = RND(0, 255)
       INCR pb
  NEXT

[David Roberts]

I'm drifting off topic here but thanks John - you have just given me the fastest binary array to hex string to date - by a factor of 10.

Function PBMain () As Long
  
  Dim hashByte() As Byte
  Dim hashByteHex () As String * 2
  Local hashText As String
  Local hashSize, i As Long
  
  hashSize = 32 ' bytes for example
  
  ReDim hashByte(hashSize -1) As Byte
  
  For i = 0 To hashSize- 1
    hashByte(i) = Rnd(0,255) ' Output from a hashing algorithm, for example
  Next
  
  hashText = Space$(2*hashSize)
  ReDim hashByteHex( hashSize - 1) As String * 2 At StrPtr(hashText)
  
  For i = 0 To hashSize-1
    hashByteHex(i) = Hex$( hashByte( i ),2 )
  Next
  
  MsgBox hashText

End Function

[John Gleason]

Dave, tho it won't help with short strings (unless there are a tons of them) here are two mods to your code to further speed it:
http://www.powerbasic.com/support/pb...398#post280398

[JOSE MARIA N. RAMOS]

Inputs regarding string concatenation slowdown

Bob, Paul, Mel, John, Michael and David: Thanks for you fast replies/inputs.

Sorry, I haven't been able to go online in the last two days.

I tried out Bob's suggestion, and his code snippet took only .0469 seconds to execute 400,000 iterations in my 2.6Ghz Pentium. I'll now try out the other suggestions.

Bob mentioned the "bottleneck" that happens somewhere around the 400,000 iteration. Is this related to what Paul said about my running out of memory cache?

[Bob Zale]

Hi Jose!

I think you may have misunderstood me slightly. There is nothing special about the number 400,000, or any other number, except for the fact that it's a very big number.

It's concatenation itself which can be a "problem" when you do it too many times on strings that are too long. Every time you add one byte to the end of a string, PowerBASIC must copy both strings (the original and the one new byte) into a new string. In your example, that means you're doing:

400,000 copy operations * 200,001 average number of bytes per copy

That's 80,000,400,000 bytes copied plus 400,000 string allocations and deletions. That's a lot of stuff to do! It takes time. Contrast it with my method which has one allocation and 400,000 byte insertions?

The cache issue Paul mentioned can have its effect as well, but I think concatenation is the real problem.

Best regards,

Bob Zale
PowerBASIC Inc.

[JOSE MARIA N. RAMOS]

Yes, I see your point....

Bob, thanks for the clarification. I should have realized this when I made the table of run times (see my original post) The repeated concatenations do take much longer as you pointed out, as they have a cumulative effect on the number of bytes processed/added per iteration.

Again, thanks for the help! I do appreciate it.