Announcement

**Michael Mattias** · 25 Apr 2008, 10:54 AM

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

**Chris Holbrook** · 25 Apr 2008, 01:55 PM

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.

**Pierre Bellisle** · 25 Apr 2008, 03:38 PM

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

**Michael Mattias** · 25 Apr 2008, 05:58 PM

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

**Chris Holbrook** · 25 Apr 2008, 06:33 PM

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.

**Paul Dixon** · 25 Apr 2008, 07:24 PM

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.

**Pierre Bellisle** · 25 Apr 2008, 08:09 PM

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)

**Chris Holbrook** · 26 Apr 2008, 03:37 AM

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?

**Michael Mattias** · 26 Apr 2008, 09:00 AM

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

**Chris Holbrook** · 26 Apr 2008, 02:33 PM

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.

**Michael Mattias** · 26 Apr 2008, 04:50 PM

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.

**John Gleason** · 26 Apr 2008, 07:33 PM

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.

**Chris Holbrook** · 27 Apr 2008, 01:21 AM

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.

**David Roberts** · 27 Apr 2008, 03:02 AM

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

Noted!

**David Roberts** · 27 Apr 2008, 03:59 AM

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

**David Roberts** · 27 Apr 2008, 07:29 AM

> '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.

**Donald Darden** · 27 Apr 2008, 08:30 PM

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.

**Chris Holbrook** · 28 Apr 2008, 03:36 PM

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.

**Dave Stanton** · 28 Apr 2008, 05:00 PM

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.

Announcement

INSTR performance

INSTR performance

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment