Announcement

Collapse
No announcement yet.

INSTR performance

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

  • INSTR performance

    I've been doing some testing with long strings and INSTR tests, and it seems that in a limiting case when the strings are of equal length and contain entirely different values (all 1s and all zeros) the INSTR test adds significant execution time, though if the strings are of the same length, and differ in the first byte, there is only one possible result from the INSTR function. Or maybe the results are an artefact of the method?

    Code:
    #COMPILE EXE
    #DIM ALL
    
    #INCLUDE "WIN32API.INC"
    %IDD_DIALOG1  =  101
    %IDC_LISTBOX1 = 1001
    %IDC_LABEL1   = 1002
    %IDC_LABEL2   = 1003
    %IDC_LISTBOX2 = 1004
    '-----------------------------------------------------
    CALLBACK FUNCTION ShowDIALOG1Proc()
        LOCAL i, j, l, u AS LONG
        LOCAL t AS DOUBLE
        STATIC s,ss AS STRING
    
        SELECT CASE AS LONG CBMSG
            CASE %WM_INITDIALOG
                FOR i = 100 TO 120
                    j = i*1000000
                    t = TIMER
                    s = STRING$(j,0)
                    ss = STRING$(j,1)
                    u = TIMER - t
                    l = INSTR(s, ss)
                    t = TIMER -t
                    LISTBOX ADD CBHNDL, %IDC_LISTBOX1, FORMAT$(j, "#,###") + " " + FORMAT$(t,"#,###") + " secs"
                    LISTBOX ADD CBHNDL, %IDC_LISTBOX2, FORMAT$(j, "#,###") + " " + FORMAT$(u,"#,###") + " secs"
                NEXT
        END SELECT
    END FUNCTION
    '------------------------------------------------------------
    FUNCTION ShowDIALOG1(BYVAL hParent AS DWORD) AS LONG
        LOCAL lRslt AS LONG
        LOCAL hDlg  AS DWORD
    
        DIALOG NEW hParent, "INSTR performance", 155, 119, 376, 121, %WS_POPUP OR %WS_BORDER OR %WS_DLGFRAME OR %WS_SYSMENU OR _
            %WS_CLIPSIBLINGS OR %WS_VISIBLE OR %DS_MODALFRAME OR %DS_3DLOOK OR %DS_NOFAILCREATE OR %DS_SETFONT, %WS_EX_CONTROLPARENT _
            OR %WS_EX_LEFT OR %WS_EX_LTRREADING OR %WS_EX_RIGHTSCROLLBAR, TO hDlg
        CONTROL ADD LISTBOX, hDlg, %IDC_LISTBOX1, , 200, 20, 175, 95, %WS_CHILD OR %WS_VISIBLE OR %WS_TABSTOP OR %WS_VSCROLL OR _
            %LBS_NOTIFY OR %LBS_HASSTRINGS OR %LBS_USETABSTOPS, %WS_EX_CLIENTEDGE OR %WS_EX_LEFT OR %WS_EX_LTRREADING OR _
            %WS_EX_RIGHTSCROLLBAR
        CONTROL ADD LABEL,   hDlg, %IDC_LABEL1, "with INSTR test", 200, 5, 175, 15
        CONTROL ADD LABEL,   hDlg, %IDC_LABEL2, "without INSTR test", 5, 5, 175, 15
        CONTROL ADD LISTBOX, hDlg, %IDC_LISTBOX2, , 5, 20, 175, 95, %WS_CHILD OR %WS_VISIBLE OR %WS_TABSTOP OR %WS_VSCROLL OR _
            %LBS_NOTIFY OR %LBS_HASSTRINGS OR %LBS_USETABSTOPS, %WS_EX_CLIENTEDGE OR %WS_EX_LEFT OR %WS_EX_LTRREADING OR _
            %WS_EX_RIGHTSCROLLBAR
        DIALOG SHOW MODAL hDlg, CALL ShowDIALOG1Proc TO lRslt
        FUNCTION = lRslt
    END FUNCTION
    
    '================================
    FUNCTION PBMAIN()
        ShowDIALOG1 %HWND_DESKTOP
    END FUNCTION

  • #2
    Perhaps when dealing with such long strings (the creation time for which is included in your elapsed times, BTW), you should test yourself.

    Code:
     LOCAL pS AS BYTE PTR, pSS AS BYTE PTR
     pS = STRPTR (s): pSS = STRPTR (SS)
     IF LEN(S) = LEN(SS) THEN
       IF   @ps <> @pSS THEN
           hit = %FALSE 
       END IF
    ELSE
          hit = INSTR (S, SS) 
     END IF
    True enough, the compiler "could" use a test like...
    Code:
     IF LEN(searchfor) > LEN (SearchIN) - Characters_already_searched THEN
        Hit = FALSe  ' because what's left to search in can't possibly match a longer string)
    ...but INSTR is a 'generic' function which must handle all possible lengths of source and target strings.

    I will guess that someone at PB tried something like the above a long time ago and decided the gain when the strings are "really long" was not worth the cost of checking the length of the remaining target when the strings were "average length"

    INSTR was the one function I could never beat using POINTER variables when I wrote an article on the use of those then-brand-new "Pointer" variables in PB/DOS; so I have a lot of respect for that existing INSTR function.

    MCM
    Michael Mattias
    Tal Systems Inc. (retired)
    Racine WI USA
    [email protected]
    http://www.talsystems.com

    Comment


    • #3
      faster than INSTR?

      Originally posted by Michael Mattias View Post
      I have a lot of respect for that existing INSTR function.
      Me too, it's fast until you get into this big string comparison. I have a sneaking suspicion that the logic does not take account of the remaining length, that is, doesn't give up when the remaining "big string" length is less than that of the "little string". If this is the case then there may be a balance point on one side of which using pointers and considering the string lengths will be faster than using INSTR. I'm on the case.

      Comment


      • #4
        Agreed, INSTR is so well written that it's almost impossible to beat.

        The only exception I saw is when the searched substring is big enought,
        then a Boyer-Moore routine can be faster.

        Steve Hutchesson and Börje Hagsten had an instructive discussion on that... Boyer-Moore algo

        Comment


        • #5
          Sure sounds like INSTR is optimized for "best performance given average-size strings," which is fine by me.

          Your results also support the premise, "all optimization is application-specific", which I think I have heard here at least two or three times.

          Then again, if the searchfor and searchin are the same length, maybe an equality test would be better than an INSTR test, but the 'first byte comparison' test I used should be plenty quick enough, as both getting LEN() or the STRPTR() are really quick.

          MCM
          Michael Mattias
          Tal Systems Inc. (retired)
          Racine WI USA
          [email protected]
          http://www.talsystems.com

          Comment


          • #6
            Originally posted by Michael Mattias View Post
            Then again, if the searchfor and searchin are the same length...
            The problem arises when both strings are large, equal lengths is a subset of this.

            It also appears that if the "searchfor" is longer than the "searchin" then the search is not inhibited, BTW.

            Comment


            • #7
              Agreed, INSTR is so well written that it's almost impossible to beat.
              That sounds like a challenge! If I had a bit of spare time I'd take it on, but for now, I'd just point out that a number of string scanning functions are built into the CPU as single CPU instructions. PB will be using the instruction that the CPU provides to do the job.

              As is often the case, the speed for large strings will be limited by memory bus bandwidth. If you want to scan a large string faster than INSTR then you need to get the data from memory more quickly.

              Paul.

              Comment


              • #8
                Paul,

                I hope you will find the time to try,
                the Boyer-Moore routine was the fastest when the substring
                was long enought but I never saw anything faster
                than INSTR for a 1, 2 or 3 characters substring.

                Having seen your assembly works in other threads
                make me think that you can come up with interesting stuff.

                So, faster or not, if you submit code,
                I think that the PB community will benefit from it,
                it's an oportunity to learn from each other.

                So ! The challenge is on... (If you have time of course)

                Comment


                • #9
                  Having skimmed a few references to the Boyer-Moore method it seems that it may not be best suited to my application, which includes comparing huge strings which will often contain all possible character values (0-255). This will lead to repeated sequences which will limit the skip distance which the BM can achieve. My guess is that just by preventing the instring search from looking for a string inside a shorter string (if this is indeed what is happening), a slightly shorter run time can be obtained.

                  That having been said, it may be that having a BM algo in the source code forum is a higher prize than fixing my application (US readers - I'm using irony here). As a starting point, there is C source code on Wikipedia, but they deprecate their own accompanying table-building source code. Maybe there is some better source code lying around somewhere?

                  Comment


                  • #10
                    It also appears that if the "searchfor" is longer than the "searchin" then the search is not inhibited, BTW.
                    I don't know how you could have deterimined that without dis-assembling; but if true that would be an optimization missed by the compiler writers.

                    Unless .. making this test costs more (cycles) than it's worth (which is subjective) when working with the aforementioned "average length" (also subjective) strings. But I have to believe the function must obtain the lengths of both strings before starting the comparison anyway; which would leave only an integer comparison to do before comparing bytes, a comparison which surely can't cost all that much.

                    Or, perhaps the writers just eschewed the test figuring nobody would try to use the INSTR function when it surely must return 'no hit.'

                    MCM
                    Michael Mattias
                    Tal Systems Inc. (retired)
                    Racine WI USA
                    [email protected]
                    http://www.talsystems.com

                    Comment


                    • #11
                      Originally posted by Michael Mattias View Post
                      I don't know how you could have deterimined that without dis-assembling;
                      In the above code, I just added one to the length of the ss string in the STRING$ statement, and observed that the elapsed times were pretty much the same.

                      Comment


                      • #12
                        In the above code, I just added one to the length of the ss string in the STRING$ statement, and observed that the elapsed times were pretty much the same
                        Well, considering the strings' creation time is included in your elapsed time, I'd say that's no surprise at all. Had your times been only for INSTR execution I might be tempted to agree with your theory.
                        Michael Mattias
                        Tal Systems Inc. (retired)
                        Racine WI USA
                        [email protected]
                        http://www.talsystems.com

                        Comment


                        • #13
                          Given this INSTR characteristic your testing discovered, Chris, perhaps the thing to do when the big string comparison need arises is something like what follows. I added a high resolution timer too.

                          Code:
                          #COMPILE EXE
                          #DIM ALL
                          DECLARE FUNCTION QueryPerformanceCounter LIB "KERNEL32.DLL" ALIAS "QueryPerformanceCounter" (lpPerformanceCount AS QUAD) AS LONG
                          DECLARE FUNCTION QueryPerformanceFrequency LIB "KERNEL32.DLL" ALIAS "QueryPerformanceFrequency" (lpFrequency AS QUAD) AS LONG
                          
                          '~~~~~~~~~~~A Variation of Dave Roberts' MACRO Timer~~~~~~~~~~~~~~~~~~~~~~~
                          MACRO onTimer
                            LOCAL qFreq, qOverhead, qStart, qStop AS QUAD
                            LOCAL f AS STRING
                            f = "#.###"
                            QueryPerformanceFrequency qFreq
                            QueryPerformanceCounter qStart ' Intel suggestion. First use may be suspect
                            QueryPerformanceCounter qStart ' So, wack it twice <smile>
                            QueryPerformanceCounter qStop
                            qOverhead = qStop - qStart     ' Relatively small
                          END MACRO
                          
                          MACRO goTimer = QueryPerformanceCounter qStart
                          MACRO stopTimer = QueryPerformanceCounter qStop
                          
                          MACRO showTimer = USING$(f,(qStop - qStart - qOverhead)*1000/qFreq) + " milliseconds"
                          '~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                          
                          #INCLUDE "WIN32API.INC"
                          %IDD_DIALOG1  =  101
                          %IDC_LISTBOX1 = 1001
                          %IDC_LABEL1   = 1002
                          %IDC_LABEL2   = 1003
                          %IDC_LISTBOX2 = 1004
                          '-----------------------------------------------------
                          CALLBACK FUNCTION ShowDIALOG1Proc()
                              LOCAL i, j, l, u AS LONG
                              LOCAL t AS DOUBLE
                              STATIC s,ss AS STRING
                              ontimer
                          
                              SELECT CASE AS LONG CBMSG
                                  CASE %WM_INITDIALOG
                                      FOR i = 100 TO 120
                                          j = i*1000000
                                          t = TIMER
                                          s = STRING$(j,0)
                                          ss = STRING$(j,1)
                                          u = TIMER - t
                                          gotimer
                                          IF CVQ(s) = CVQ(ss) AND CVQ(s, 33) = CVQ(ss, 33) THEN '1st check, say, 16 early bytes to see if there's even a chance of match
                                             l = INSTR(s, ss)
                                          END IF
                                          stoptimer
                                          t = TIMER -t -u
                                          LISTBOX ADD CBHNDL, %IDC_LISTBOX1, FORMAT$(j, "#,###") + " " + showtimer '& " 'FORMAT$(t,"#,###") + " secs"
                                          LISTBOX ADD CBHNDL, %IDC_LISTBOX2, FORMAT$(j, "#,###") + " " + FORMAT$(u,"#,###") + " secs"
                                      NEXT
                              END SELECT
                          END FUNCTION
                          '------------------------------------------------------------
                          FUNCTION ShowDIALOG1(BYVAL hParent AS DWORD) AS LONG
                              LOCAL lRslt AS LONG
                              LOCAL hDlg  AS DWORD
                          
                              DIALOG NEW hParent, "INSTR performance", 155, 119, 376, 121, %WS_POPUP OR %WS_BORDER OR %WS_DLGFRAME OR %WS_SYSMENU OR _
                                  %WS_CLIPSIBLINGS OR %WS_VISIBLE OR %DS_MODALFRAME OR %DS_3DLOOK OR %DS_NOFAILCREATE OR %DS_SETFONT, %WS_EX_CONTROLPARENT _
                                  OR %WS_EX_LEFT OR %WS_EX_LTRREADING OR %WS_EX_RIGHTSCROLLBAR, TO hDlg
                              CONTROL ADD LISTBOX, hDlg, %IDC_LISTBOX1, , 200, 20, 175, 95, %WS_CHILD OR %WS_VISIBLE OR %WS_TABSTOP OR %WS_VSCROLL OR _
                                  %LBS_NOTIFY OR %LBS_HASSTRINGS OR %LBS_USETABSTOPS, %WS_EX_CLIENTEDGE OR %WS_EX_LEFT OR %WS_EX_LTRREADING OR _
                                  %WS_EX_RIGHTSCROLLBAR
                              CONTROL ADD LABEL,   hDlg, %IDC_LABEL1, "INSTR test", 200, 5, 175, 15
                              CONTROL ADD LABEL,   hDlg, %IDC_LABEL2, "Making String", 5, 5, 175, 15
                              CONTROL ADD LISTBOX, hDlg, %IDC_LISTBOX2, , 5, 20, 175, 95, %WS_CHILD OR %WS_VISIBLE OR %WS_TABSTOP OR %WS_VSCROLL OR _
                                  %LBS_NOTIFY OR %LBS_HASSTRINGS OR %LBS_USETABSTOPS, %WS_EX_CLIENTEDGE OR %WS_EX_LEFT OR %WS_EX_LTRREADING OR _
                                  %WS_EX_RIGHTSCROLLBAR
                              DIALOG SHOW MODAL hDlg, CALL ShowDIALOG1Proc TO lRslt
                              FUNCTION = lRslt
                          END FUNCTION
                          
                          '================================
                          FUNCTION PBMAIN()
                              ShowDIALOG1 %HWND_DESKTOP
                          END FUNCTION
                          btw, if you see this Dave Roberts, note that I 86'ed the UGLY arithmetic.

                          Comment


                          • #14
                            Originally posted by Michael Mattias View Post
                            considering the strings' creation time is included in your elapsed time
                            There are two times recorded for each test, one is the time to create the string and the other is the time to create the string PLUS the time for the INSTR test. The difference between the two times should be the INSTR time alone.

                            Comment


                            • #15
                              > btw, if you see this Dave Roberts, note that I 86'ed the UGLY arithmetic.

                              Noted!

                              Comment


                              • #16
                                Why not go the whole hog and have timings exclusive.

                                Code:
                                CALLBACK FUNCTION ShowDIALOG1Proc()
                                    LOCAL i, j, l, u AS LONG
                                    LOCAL t AS DOUBLE
                                    STATIC s,ss AS STRING
                                    LOCAL strCreate, strCalculate AS STRING
                                    ontimer
                                
                                    SELECT CASE AS LONG CBMSG
                                        CASE %WM_INITDIALOG
                                            FOR i = 100 TO 120
                                                j = i*1000000
                                                gotimer
                                                't = Timer
                                                s = STRING$(j,0)
                                                ss = STRING$(j,1)
                                                'u = Timer - t
                                                stoptimer
                                                strCreate = showtimer
                                                gotimer
                                                IF CVQ(s) = CVQ(ss) AND CVQ(s, 33) = CVQ(ss, 33) THEN '1st check, say, 16 early bytes to see if there's even a chance of match
                                                   l = INSTR(s, ss)
                                                END IF
                                                stoptimer
                                                t = TIMER -t -u ' ???
                                                strCalculate = showtimer
                                                LISTBOX ADD CBHNDL, %IDC_LISTBOX1, FORMAT$(j, "#,###") + " " + strCalculate '& " 'FORMAT$(t,"#,###") + " secs"
                                                LISTBOX ADD CBHNDL, %IDC_LISTBOX2, FORMAT$(j, "#,###") + " " + strCreate ' Format$(u,"#,###") + " secs"
                                            NEXT
                                    END SELECT
                                END FUNCTION

                                Comment


                                • #17
                                  > '1st check, say, 16 early bytes to see if there's even a chance of match

                                  Yeah, but you are posing the question knowing the answer.

                                  Suppose there is a difference at the 17th byte. We are now faced with almost the same problem we started with if we strip off the first 16 bytes. The argument still holds ie check the first 16 bytes with a possibility of ad nauseam.

                                  If we pad both strings out with either all 0's or all 1's so that they are divisible by, say 4096 or 16384 or whatever, and compare random sections and ensure no repetition then if, for example, there are 2^16 total possible comparisons, if there is a difference the birthday paradox should give us a 50% chance of finding it with 2^8 comparisons.

                                  With the padding, if the strings are the same then they will still be the same and if they are different then they will still be different.

                                  Will it work and will it be faster than not doing it? Don't know. Bit pressed for time at the minute.

                                  Comment


                                  • #18
                                    It should be obvious that the search string length must always be less than or equal to the length of the string being searched. Otherwise, you should immediately return 0 (zero) and exit.

                                    The maximum number of search loops is equal to the main string length - search string length +1.

                                    INSTR() in PowerBasic does one thing that most people fail to consider, which is that it can be used to search from the beginning to the end, or from the end to the beginning of the main string.

                                    INSTR() might benefit from testing more than one byte at a time (say two or four characters at once), but unfortunately, in order to find the first possible occurance, the loop can only advance (or retrograde) one byte at a time.

                                    A special use of INSTR() might be to test for non-case specific matches. At present you have to force the search string and main string to the same case to ensure a match using something like UCASE$() or LCASE$(). These methods force PowerBasic to create a temporary copy of the string(s), but allows faster use of INSTR() whereas a caseless version of INSTR() would be much slower in execution.

                                    It might be possible to write a faster version of INSTR(), but it most likely would be limited to a specific use or range of uses. The question is, can the INSTR() instruction be improved on without sacrificing speed? I've argued that there should be another optional parameter that could be used in INSTR() to limit or cap how much of the main string to search. For instance, say I am at position "A" currently in my mainstring, and I wanted to search and see if the word "fortune" appears in this line, but not risk searching the whole file, which could add a lot of time to my efforts:

                                    b=INSTR(a,main$,"fortune",INSTR(a,main$,ANY $CRLF))

                                    The INSTR(a,main$,ANY $CRLF) represents the "cap" or last search position I want to search within. Though I might have a problem with the last line in a file with no trailing $CR or $LF symbol, I could deal with that readily enough this way:

                                    b=INSTR(a,main$,ANY $CRLF)
                                    if b=0 THEN b=LEN(main$)+1
                                    b=INSTR(a,main$,"fortune",b)

                                    Another approach is to write the new INSTR() replacement so that if the third parameter does not exist or evaluates to zero, that the process automatically uses the LEN(main$) to set the maximum number of test loops.

                                    Comment


                                    • #19
                                      Originally posted by Donald Darden View Post
                                      It should be obvious that the search string length must always be less than or equal to the length of the string being searched. Otherwise, you should immediately return 0 (zero) and exit.
                                      That seems to be the problem. I say "seems to" because I can't prove it. At any point in the search, if the remaining (unsearched) portion of the string to be searched is shorter than the string searched for, the function should exit returning zero.

                                      To do this is not the same as limiting, i.e. setting the end of the substring to be searched.

                                      If I want a better performance (and I do) I shall have to add it to my burden.

                                      Comment


                                      • #20
                                        Get the length of your target string.
                                        Add search string to end of target string.
                                        Do INSTR on augmented target string.
                                        If returned string position is > length of original target then exit.
                                        Dave.

                                        You're never too old to learn something stupid.

                                        Comment

                                        Working...
                                        X