Announcement

Collapse
No announcement yet.

Fast string searching

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

  • #21
    I have been reading this forum with great interest.
    Given Hutch's comments on the uncertainty and variability of speed of the Boyer Moore algorithm it occurred to me that Instr could be made faster by using the power of the architecture rather than any special math. Instr does byte comparisons and so has to branch and test the second byte on average once in every 256 bytes, the third byte once in every 65536 etc, however if the string is compared as dwords then the first branch will only occur on average once in every 4294967296 bytes and if the search string is over 8 bytes then another compare will only take place every 2^64 bytes. This has to be offset by the speed loss due to continually reading missalingned dwords. my test program run on an AMD 650 gives approx 20% speed gain over instr, this gain should be fairly constant no matter the size of the search string or the string to be searched. Note the search string must be at least 4 bytes and the string to be searched at least 3 bytes longer.

    The test program sets up a 50 meg random string of bytes 0 to 254 and forces the last byte to be unique, it then searches for a 47 byte string with the last byte of it also being the unique byte.

    Code:
    #COMPILE EXE
    #REGISTER NONE
    FUNCTION BigInstr(Start AS LONG, SrchStr AS STRING, SrchText AS STRING) AS LONG
        LOCAL ssa AS DWORD
        LOCAL sta AS DWORD
        LOCAL ssl AS LONG
        LOCAL stl AS LONG
        LOCAL wrk AS LONG
    '    IF LEN(SrchStr) < LEN(SrchText) - 3 OR LEN(SrchText) < 5 OR Start < 0 OR start > LEN(SrchStr) - 7 THEN
    '        BigInstr = -1
    '        EXIT FUNCTION
    '    END IF
        ssa = STRPTR(SrchStr)
        ssa = ssa + Start
        sta = STRPTR(SrchText)
        stl = LEN(SrchText) - 4
        ssl = LEN(SrchStr) - Start - stl + 1
        ! MOV ESI, ssa
        ! MOV EDI, sta
        ! MOV ECX, ssl
        ! MOV EDX, stl
        ! MOV EAX, [EDI]
        ! CLD
        SrchLoop:
        ! CMP EAX, [ESI]
        ! JE FrstByteMtch
        FrstByteNM:
        ! CMP EAX, [ESI + 1]
        ! JE ScndByteMtch
        ScndByteNM:
        ! CMP EAX, [ESI + 2]
        ! JE ThrdByteMtch
        ThrdByteNM:
        ! CMP EAX, [ESI + 3]
        ! JE FrthByteMtch
        FrthByteNM:
        ! ADD ESI, 4
        ! SUB ECX, 4
        ! JG SrchLoop
        BigInstr = 0                'no match so set zero and exit
        EXIT FUNCTION
        FrstByteMtch:
        ! PUSHAD
        ! ADD ESI, 4
        ! ADD EDI, 4
        FBWords:
        ! SUB EDX, 4
        ! JS FBWrem
        ! CMPSW
        ! JE FBWords
        ! POPAD
        ! JMP FrstByteNM            'no match so continue search
        FBWrem:
        ! ADD EDX, 4
        ! JZ FBout
        FBBytes:
        ! SUB edx, 1
        ! JNS FBBnf
        FBout:
        ! POPAD
        ! MOV wrk, ECX
        BigInstr = ssl - wrk + 1    'match so set position and exit
        EXIT FUNCTION
        FBBnf:
        ! CMPSB
        ! JE FBBytes
        ! POPAD
        ! JMP FrstByteNM            'no match so continue search
        ScndByteMtch:
        ! PUSHAD
        ! ADD ESI, 5
        ! ADD EDI, 4
        SBWords:
        ! SUB EDX, 4
        ! JS SBWrem
        ! CMPSW
        ! JE SBWords
        ! POPAD
        ! JMP ScndByteNM            'no match so continue search
        SBWrem:
        ! ADD EDX, 4
        ! JZ SBout
        SBBytes:
        ! SUB edx, 1
        ! JNS SBBnf
        SBout:
        ! POPAD
        ! MOV wrk, ECX
        BigInstr = ssl - wrk + 2    'match so set position and exit
        EXIT FUNCTION
        SBBnf:
        ! CMPSB
        ! JE SBBytes
        ! POPAD
        ! JMP ScndByteNM            'no match so continue search
        ThrdByteMtch:
        ! PUSHAD
        ! ADD ESI, 6
        ! ADD EDI, 4
        TBWords:
        ! SUB EDX, 4
        ! JS TBWrem
        ! CMPSW
        ! JE TBWords
        ! POPAD
        ! JMP ThrdByteNM            'no match so continue search
        TBWrem:
        ! ADD EDX, 4
        ! JZ TBout
        TBBytes:
        ! SUB edx, 1
        ! JNS TBBnf
        TBout:
        ! POPAD
        ! MOV wrk, ECX
        BigInstr = ssl - wrk + 3    'match so set position and exit
        EXIT FUNCTION
        TBBnf:
        ! CMPSB
        ! JE TBBytes
        ! POPAD
        ! JMP ThrdByteNM            'no match so continue search
        FrthByteMtch:
        ! PUSHAD
        ! ADD ESI, 7
        ! ADD EDI, 4
        QBWords:
        ! SUB EDX, 4
        ! JS QBWrem
        ! CMPSW
        ! JE QBWords
        ! POPAD
        ! JMP FrthByteNM            'no match so continue search
        QBWrem:
        ! ADD EDX, 4
        ! JZ QBout
        QBBytes:
        ! SUB edx, 1
        ! JNS QBBnf
        QBout:
        ! POPAD
        ! MOV wrk, ECX
        BigInstr = ssl - wrk + 4    'match so set position and exit
        EXIT FUNCTION
        QBBnf:
        ! CMPSB
        ! JE QBBytes
        ! POPAD
        ! JMP FrthByteNM            'no match so continue search
    END FUNCTION
    FUNCTION PBMAIN
        LOCAL stp AS BYTE PTR
        LOCAL rn AS DOUBLE
        LOCAL rb AS BYTE
        LOCAL x AS LONG
        LOCAL t1 AS SINGLE
        LOCAL t2 AS SINGLE
        LOCAL t3 AS SINGLE
        a$ = SPACE$(50000000)
        stp = STRPTR(a$)
        RANDOMIZE
        FOR x = 0 TO 49999998
            rn = RND * 255
            rb = INT(rn)
            @stp[x] = rb
        NEXT
        @stp[49999999] = 255
        b$ = RIGHT$(a$, 47)
        t1 = TIMER
        FOR x& = 0 TO 9
            posb& = BigInstr(0, a$, b$)
        NEXT
        t2 = TIMER
        FOR x& = 0 TO 9
            posi& = INSTR(a$, B$)
        NEXT
        t3 = TIMER
        MSGBOX "BigInstr took" + STR$(t2 - t1) + " and returned" + STR$(posb&) + $crlf + "Instr took" + STR$(t3 - t2) + " and returned" + STR$(posi&)
        t1 = TIMER
        FOR x& = 0 TO 9
            posi& = INSTR(a$, B$)
        NEXT
        t2 = TIMER
        FOR x& = 0 TO 9
            posb& = BigInstr(0, a$, b$)
        NEXT
        t3 = TIMER
        MSGBOX "BigInstr took" + STR$(t3 - t2) + " and returned" + STR$(posb&) + $crlf + "Instr took" + STR$(t2 - t1) + " and returned" + STR$(posi&)
    END FUNCTION

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

    Comment


    • #22
      John,

      That's very interesting!

      I'll give it a go as soon as i have a free moment.

      - Nathan.

      Comment


      • #23
        John,

        Its an interesting idea, I have thought about a DWORD size read
        but the alignment and overhead problems looked like a lot of work
        so I did not pursue it.

        It tests ok reasonable on my PIII but on my AMD, INSTR is clearly
        faster so hardware comes into play a lot with a function of this
        type.

        With the actual code, I suggest there are a couple of areas that you
        could get faster, PUSHAD/POPAD are slow, if you selected which
        registers you needed to preserve, you can save some time there and
        try using indexed pointers instead of the old string instructions
        as you can usually get a speed gain there.

        Test is th WIN32API.INC file looped 100 times with a search phrase added
        near the end "' ** VERSION.DLL Declares".
        Code:
                       PIII 600        AMD 550 K6-2
            BigINSTR    710 ms           575 ms
            INSTR       790 ms           410 ms
            BMBinSearch 355 ms           310 ms
        The Boyer Moore is a lot faster because of its logic, by not having
        to scan every BYTE, it can shift reasonable amounts on mismatch.

        I have found something that solves the very occasional failure with
        the BM algo, I needed to calculate the God Suffix Shift in a different
        manner, when I have finished testing it, I will post it here, it is
        clocking up at about the same speed as the earlier one.

        Regards,

        [email protected]

        ------------------
        hutch at movsd dot com
        The MASM Forum - SLL Modules and PB Libraries

        http://www.masm32.com/board/index.php?board=69.0

        Comment


        • #24
          PIII 600 AMD 550 K6-2
          BigINSTR 710 ms 575 ms
          INSTR 790 ms 410 ms
          BMBinSearch 355 ms 310 ms
          The the BMBinSearch is what i'm using, not had a single problem now that
          it's working. It serves well for the type of strings i am searching for and in.

          Keep updating your BMBinSearch Steve!

          I really dig your work.


          - Nathan.

          Comment

          Working...
          X