Algorithm Challenge

[John Gleason]

Kevin, I finally thought of a way around the even-odd array size problem, but it depends on this: are there two LONG numbers which will never match any of the possible array values? eg. will your valid array data ever contain &hffffffff and &hfffffffe?

[Kevin Cramer]

Hi John,

There will be no numbers over 4 billion...or even one million for that matter that will be compared.

[Kevin Cramer]

Hi John,

did you ever get the ASM code for this to work?

Kevin

[John Gleason]

Hey Kevin,

I got the below asm to work, non-mmx byte-by-byte comparison like your original, but it is faster so I figure it is probably worthwhile to post. It uses byte arrays that are much faster than the string arrays of the original post.

You can uncomment the DO-LOOP and comment the messages to run a continuous test loop to check for accuracy. I've seen no failures.

Added: I keep forgetting the #ALIGN statements, so I added them below. BIG speed increase--now it's well over 2x as fast as the original algorithm.

#COMPILE EXE
#REGISTER NONE

%rawInpLength = 10000

FUNCTION PBMAIN () AS LONG

    LOCAL x AS LONG, y AS LONG, z AS LONG
    DIM overlap1 AS LONG
    LOCAL overlap2, t1ptr, t2ptr AS LONG, counter, counter2 AS LONG
    LOCAL zTemp AS LONG, tq AS LONG, t1, t2 AS QUAD
    RANDOMIZE
    counter = 0

'    OPEN "speedtest.log" FOR OUTPUT AS #10

    DIM temp1(%rawInpLength) AS BYTE 'STRING * 1
    DIM temp2(%rawInpLength) AS BYTE 'STRING * 1
'do
counter = 0
    FOR x = 1 TO %rawInpLength
         temp1(x) = RND(65,90)    'RND(65,90)
         temp2(x) = RND(65,90)    'RND(65,90)
'         temp1(x) = CHR$(RND(65,90))
'         temp2(x) = CHR$(RND(65,90))
    NEXT x
'-------------------------------------------------------------------------------------------------
'-------------------------------------------------------------------------------------------------
TIX t1
    overlap1 = %rawInpLength: overlap2 = 1
    z = %rawInpLength
    y = 1
    DO
         DO WHILE z >= overlap1
              DO WHILE y >= 1
                  '''''Do comparison here

                  IF temp1(z) = temp2(y) THEN INCR counter
                  z = z - 1
                  y = y - 1
              WEND
         WEND
         DECR overlap1
         INCR overlap2
         z = %rawInpLength
         y = overlap2

    LOOP WHILE overlap2 <= %rawInpLength-1

      'this section then continues the sliding forward from where the last code finished
    FOR z = 0 TO %rawInpLength-1

         FOR y = 1 TO %rawInpLength - z
             IF temp1(y) = temp2(y+z) THEN INCR counter
         NEXT y
    NEXT z
TIX END t1
   ? "Kevin original finish:" & STR$(t1) & STR$(counter)   '33770  345905
'-------------------------------------------------------------------------------------------------
'-------------------------------------------------------------------------------------------------
'here is a non-mmx asm version that clocks over 50% faster than above
counter2 = 0
TIX t1
  t1ptr = VARPTR(temp1(0))
  t2ptr = VARPTR(temp2(0))
  !push ebx
  !push esi
  !push edi
       !mov esi, t1ptr
       !mov edi, t2ptr
    FOR overlap2 = 1 TO %rawInpLength-1
     ' z = %rawInpLength
       !mov ebx, %rawInpLength
       !mov ecx, overlap2
       #ALIGN 16
      forY2top:
'      FOR y = overlap2 TO 1 STEP -1
          '''''Do comparison here
          !movzx eax, byte ptr[esi+ebx]
          !cmp [edi+ecx], al
          !jne short notEqual
          !add counter2, 1
         notEqual:
          !sub ebx, 1
          !sub ecx, 1
          !ja short forY2top
'        above asm does this: IF temp1(z) = temp2(y) THEN INCR counter
'      NEXT
    NEXT

'      'this section then continues the sliding forward from where the last code finished
     FOR z = 0 TO %rawInpLength-1
         !mov ebx, z
         !mov eax, %rawInpLength
         !sub eax, ebx           ;%rawInpLength - z
         !mov ecx, 1
         !mov y, eax
         #ALIGN 16
        forYtop:
'         FOR y = 1 TO %rawInpLength - z
          !mov edx, ecx
          !movzx eax, byte ptr[esi+edx]
          !add edx, ebx
          !add ecx, 1
          !cmp [edi+edx], al
          !jne short notEqual2
          !add counter2, 1
         notEqual2:
          !cmp ecx, y
          !jbe short forYtop
'         above asm does this: IF temp1(y) = temp2(y+z) THEN INCR counter
'         NEXT y
     NEXT z
   !pop edi
   !pop esi
   !pop ebx
TIX END t1
'-------------------------------------------------------------------------------------------------
'-------------------------------------------------------------------------------------------------

    ? "baker asm finish:" & STR$(t1) & STR$(counter2)   '33770  345905
    IF counter <> counter2 THEN ? "FOUND AN ERROR IN ALGO!"
'    loop

END FUNCTION

[John Gleason]

I did some accurate timings of post #44 and got right at 2.5x faster. That's quite good because with the mmx I got 3.7x, so I recovered a fair % of even the mmx speed.