Announcement

Collapse
No announcement yet.

Slowish loop

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Slowish loop

    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:
    Code:
    #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

  • #2
    Your bottleneck is in code like this:

    Code:
     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.
    Chris Boss
    Computer Workshop
    Developer of "EZGUI"
    http://cwsof.com
    http://twitter.com/EZGUIProGuy

    Comment


    • #3
      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.

      Comment


      • #4
        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.

        Comment


        • #5
          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.)

          Last edited by John Gleason; 24 Sep 2009, 07:02 PM. Reason: add pic

          Comment


          • #6
            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.

            Comment


            • #7
              > 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
              Code:
                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
              Michael Mattias
              Tal Systems (retired)
              Port Washington WI USA
              [email protected]
              http://www.talsystems.com

              Comment


              • #8
                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.
                Code:
                #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
                Last edited by John Gleason; 25 Sep 2009, 09:57 AM. Reason: addendum

                Comment

                Working...
                X