Slowish loop

[John Gleason]

I noticed a slowish loop in my code, but after optimizing it a little, I got a much bigger speed increase than expected. On my laptop, the tix in the second loop below can exceed the first by as much as 150x or more. The loops do the same task, and it doesn't seem like there should be a big difference. I'm wondering if it might just be my computer, or maybe an error somewhere in the code. :thinking:

#COMPILE EXE
#DIM ALL

%MLEN = 5
%LOSIZE = &h04000
%HISIZE = 2 * %LOSIZE + %LOSIZE \ 2
%LOOPCNT = &h80000 \ %LOSIZE - 1

FUNCTION PBMAIN () AS LONG
     LOCAL ii, ii2, n AS LONG, t, t2 AS QUAD
     LOCAL qx2 AS STRING
 
     n = %HISIZE / %MLEN
     qx2 = STRING$(2000000, "5")
     DIM arr40(%LOOPCNT) AS STRING * %HISIZE AT STRPTR(qx2)
     DIM p(n) AS EXT, o(n) AS EXT
     
     FOR ii2 = 0 TO %LOOPCNT STEP 2
        TIX t
        FOR ii = 0 TO n - 1
            p(ii) = VAL(PEEK$(VARPTR(arr40(ii2)) +  ii    * %MLEN, %MLEN))
            o(ii) = VAL(PEEK$(VARPTR(arr40(ii2)) + (ii+1) * %MLEN, %MLEN))
        NEXT
        TIX END t
     NEXT

     FOR ii2 = 0 TO 3 STEP 2    'only do 2 loops for test
        TIX t2
        FOR ii = 0 TO n - 1
            p(ii) = VAL(MID$(arr40(ii2),   ii * %MLEN + 1, %MLEN))
            o(ii) = VAL(MID$(arr40(ii2+1), ii * %MLEN + 1, %MLEN))
        NEXT
        TIX END t2
        ? "PEEK time = " & STR$(t) & $CRLF & "MID time = " & STR$(t2) & $CRLF & "PEEK is" & STR$(t2 \ t) & "x faster"
     NEXT
     ? "Done"

END FUNCTION

[Chris Boss]

Your bottleneck is in code like this:

 VAL(PEEK$(VARPTR(arr40(ii2)) +  ii

Going from a pointer (VARPTR) to a string (PEEK$) and then back to numeric value (VAL) is going to be slower than dealing with numeric data directly.

PEEK$ is not really well suited for reading just a few bytes in large iterations. It is better suited to read large blocks of bytes quickly.

When working with just a few bytes (in your case 5) you need to reexamine your method. If the data is in ascii format, then possibly reading the data directly using the DIM AT (as a string) syntax maybe a little faster, but a really fast method would be to do conversion of the ascii values to numeric yourself and simply skip using any string functions. I don't know off hand the best way to code that, but that would be the better approach.

While PB strings are fast, string functions compared to numeric functions are very slow. Numeric only code runs very fast, especially if dealing with just longs.


When converting back and forth between numeric to string and a back again you create a bottleneck for speed.

[John Gleason]

Thanks Chris, the code can (and will soon, hopefully) benefit from those optimizations, but beyond the specifics of the optimization, my more fundamental questions really are, 1) do you see the two loops run in orders of magnitude different times, and 2) if so, what might be the reason for that difference?

I thought MID$ might be somewhat slower, maybe 2x tops, but definitely not 150+ times slower as it seems to test on my laptop.

[Paul Dixon]

John,
I get about 50:1 speed ratio.
String functions are slow. Often very slow. If you can avoid them then do.
PEEK is probably avoiding all the built in overhead associated with manipulating strings so it's a lot faster.

Paul.

[John Gleason]

Thanks Paul, well, looks like a third of my computer is still working. It's the degree of difference that is surprising. I'll note that for the future under the heading of "minor changes for big efficiency improvements." (There actually was a thread a couple week ago that listed a few others.)

[Tom Hanlin]

Well, MID$, unlike PEEK$, has to look up a target string and act differently depending on whether you've gone past the bounds of the string... among other things. Dunno, the code you show does not do the same thing for both tests, so I'm just taking a wild stab at it.

In both cases, you have extra overhead from multiplications and having to recalculate the memory location for every array index. You could do better by using pointers, which will only require a cheap increment on every loop.

[Michael Mattias]

> qx2 = STRING$(2000000, "5")

It "looks like" the goal is to "read many five-character decimal digit strings into an array of long integers." (In this case all those digits are "55555")

In which case the simplest code is

  LOCAL p5  AS STRING  PTR * 5 
  p5  =     address of ([file?] data as a string)  
  FOR Z = first record to last record
      Destarray& (Z) = VAL (@p5) 
      INCR p5
  NEXT

For only 400,000 of these things I would not worry about the speed. You can always bury this data load in the splash screen code and no one will notice.

MCM

[John Gleason]

the code you show does not do the same thing for both tests

Hi Tom, thanks for pointing that out. I used more comprehensive test data and now both loops match their output exactly. The timing difference of the two loops seems to have closed the gap somewhat with the changes, but is still in the ballpark of the above code. The difference was not what I really expected, so thought I'd ask, and perhaps now feel like a better person for the asking.

ADDENDUM: an..d now I feel a bit less better because I changed the wrong index in the code, so here it is corrected yet again. Also I time the whole loop for a better average. I get about 100x difference on my computer.

#COMPILE EXE
#DIM ALL

%MLEN = 5
%LOSIZE = &h04000
%HISIZE = 2 * %LOSIZE + %LOSIZE \ 2
%LOOPCNT = &h80000 \ %LOSIZE - 1

FUNCTION PBMAIN () AS LONG
     LOCAL ii, ii2, n AS LONG, t, t2 AS QUAD
     LOCAL qx2 AS STRING

     n = %HISIZE / %MLEN
     qx2 = REPEAT$(200000, "1234567890")
     DIM arr40(%LOOPCNT) AS STRING * %HISIZE AT STRPTR(qx2)
     DIM p(n) AS EXT, o(n) AS EXT

     TIX t
     FOR ii2 = 0 TO %LOOPCNT STEP 2
        FOR ii = 0 TO n - 1
            p(ii) = VAL(PEEK$(VARPTR(arr40(ii2))   + ii * %MLEN, %MLEN))
            o(ii) = VAL(PEEK$(VARPTR(arr40(ii2+1)) + ii * %MLEN, %MLEN))
        NEXT
     NEXT
     TIX END t

     TIX t2
     FOR ii2 = 0 TO %LOOPCNT STEP 2                                 
        FOR ii = 0 TO n - 1
            p(ii) = VAL(MID$(arr40(ii2),   ii * %MLEN + 1, %MLEN))
            o(ii) = VAL(MID$(arr40(ii2+1), ii * %MLEN + 1, %MLEN))
        NEXT
     NEXT
     TIX END t2
     ? "PEEK time = " & STR$(t) & $CRLF & "MID time = " & STR$(t2) & $CRLF & "PEEK is" & STR$(t2 \ t) & "x faster"

END FUNCTION