Array scan challenge

[Richard Russell]

Here's a little challenge to exercise your brain cells. You are given an array with one million elements, only one of which is non zero. For example:

Code: Select all

      DIM x&(999999)
      x&(654321) = 1

Your task is to find the non-zero element as quickly as possible using BB4W, BBCSDL or BBCTTY. Machine code / assembly language code is not allowed, nor is 'shelling out' to the OS or calling an external library; pure BASIC code only. But you can of course use language extensions available in these versions if they help.

If there are enough submissions I'll create a league table, running the code here to compare the speeds on a level playing field. Good luck!

[Edja]

I submit the following 4, rather simple and straightforward ways to meet the challenge and as requested coded in plain vanilla BB4W. The program works in the assumption that one element is different from 0.

Code: Select all

      DIM x&(999999)
      x&(654321) = 12

      TIME=0 I%=0
      WHILE x&(I%)=0 I%+=1 ENDWHILE
      PRINT TIME I% x&(I%)

      TIME=0 i=0
      WHILE x&(i)=0 i+=1 ENDWHILE
      PRINT TIME i x&(i)

      TIME=0
      FOR I%=0 TO 999999 IF x&(I%)<0 OR x&(I%)>0 EXIT FOR
      NEXT
      PRINT TIME I% x&(I%)

      TIME=0
      FOR i=0 TO 999999 IF x&(i)<0 OR x&(i)>0 EXIT FOR
      NEXT
      PRINT TIME i x&(i)
      END

As expected, the very first method, compared to the second (with index I% rather than index i) is faster. But still, the difference in speed is significant while the rest of the code is identical.
I'm quite sure other ways, much more efficient and faster, will be sent in over the following days. But this can serve just as a kick-off only and to set the baseline. I am curious to see how much faster more skilled programmers will improve on this

Edja

[Richard Russell]

I submit the following 4, rather simple and straightforward ways to meet the challenge

Thank you, I'll treat them as four separate submissions when comparing speeds. There are at least three other offerings at Facebook if you want to check there, but I'll include them (and any received at the Discussion Group) when I announce the results.

[JeremyNicoll]

I had a go at this, starting with Edja's code.

I expected - and it turned out to be so - that his(?) 3rd & 4th methods took twice as long as similar code with only one condition being tested in each iteration of the loop; no point in testing if an element of the array is less then 0 ... because it can't be. Bytes in byte arrays have values 0 - 255.

My method is:

Code: Select all

DIM x&(999999)
x&(654321) = 12
 
TIME=0
Sum& = SUM( x&() )  : REM sum of all elements in the array), so: 12 ... which is value of unknown element
PRINT "After finding     sum ("; Sum& ;")                 TIME="; TIME

REM I googled for: "BBC BASIC" instr to search memory ... and found:
REM   https://www.bbcbasic.net/wiki/doku.php?id=aliasing_20strings_20and_20byte_20arrays
REM   - which shows how to define a string which points to where the byte array's data starts

byte$       = "TEST"               : REM create a string named "byte$"
PTR(byte$)  = ^x&(0)               : REM alter "byte$"'s data pointer, to point to 0'th elem of x&()
!(^byte$+4) = DIM(x&(),1) + 1      : REM alter "byte$"'s value-length to number of bytes (DIM plus 1) in x&

found%      = INSTR(byte$, CHR$(Sum&) )  : REM NB: one more than array index (chr n in byte$ is x&(n-1)

PRINT "Position via INSTR on aliased byte-array    TIME="; TIME ; "  pos: " found%-1 ; "  elem="; x&(found%-1)

However, here, the position of the byte we're looking for has to be around 75,000 or further into the array before this method is quicker than a simple one.

[JeremyNicoll]

I did some more testing, putting an outer loop around each method, so eg

Code: Select all

DIM x&(999999)
REM x&(654321) = 12
x&( 25 * 1000) = 12

OUTERLOOP% = 20
PRINT "Outerloop is "; OUTERLOOP% : PRINT

TIME=0
FOR O% = 1 TO OUTERLOOP%
  I%=0
  WHILE x&(I%)=0 I%+=1 ENDWHILE
NEXT
PRINT "While with I%, skipping past 0-elements        TIME="; TIME ; "  pos: " I% ; "  elem="; x&(I%)

TIME=0
FOR O% = 1 TO OUTERLOOP%
  i=0
  WHILE x&(i)=0 i+=1 ENDWHILE
NEXT
PRINT "While with  i, skipping past 0-elements        TIME="; TIME ; "  pos: " i ;  "  elem="; x&(i)
PRINT

TIME=0
FOR O% = 1 TO OUTERLOOP%
  FOR I%=0 TO 999999 IF x&(I%)<0 OR x&(I%)>0 EXIT FOR
  NEXT
NEXT
PRINT "FOR   with I%, double test for non-0 elements  TIME="; TIME ; "  pos: " I% ; "  elem="; x&(I%)

TIME=0
FOR O% = 1 TO OUTERLOOP%
  FOR I%=0 TO 999999 IF x&(I%)>0 EXIT FOR
  NEXT
NEXT
PRINT "FOR   with I%, single test for non-0 elements  TIME="; TIME ; "  pos: " I% ; "  elem="; x&(I%)
PRINT

TIME=0
FOR O% = 1 TO OUTERLOOP%
  FOR i=0 TO 999999 IF x&(i)<0 OR x&(i)>0 EXIT FOR
  NEXT
NEXT
PRINT "FOR   with  i, double test for non-0 elements  TIME="; TIME ; "  pos: " i ;  "  elem="; x&(i)

TIME=0
FOR O% = 1 TO OUTERLOOP%
  FOR i=0 TO 999999 IF x&(i)>0 EXIT FOR
  NEXT
NEXT
PRINT "FOR   with  i, single test for non-0 elements  TIME="; TIME ; "  pos: " i ;  "  elem="; x&(i)
PRINT

TIME=0
FOR O% = 1 TO OUTERLOOP%
  Sum& = SUM( x&() )  : REM sum of all elements in the array), so: 12 ... ie value of unknown element
  byte$ = "TEST"                       : REM create a string named "byte$"
  PTR(byte$)  = ^x&(0)                       : REM alter "byte$"'s data pointer, to point to 0'th elem of x&()
  !(^byte$+4) = DIM(x&(),1) + 1              : REM alter "byte$"'s value-length to #bytes (DIM plus 1) in x&
  found%  = INSTR(byte$, CHR$(Sum&) )    : REM NB: one more than array index (chr n in byte$ is x&(n-1)
NEXT
PRINT "Position via INSTR on aliased byte-array       TIME="; TIME ; "  pos: " found%-1 ; "  elem="; x&(found%-1)

END

Bigger values of OUTERLOOP% get around the problem of TIME only having - at best - centisecond accuracy.

I also tried this with the unknown element in various positions in the array. If it's pretty close to the start, the simple methods are quicker, presumably because summing a million bytes takes time. But if the position is greater, the SUM & INSTR method is far quicker.

[Edja]

Improved speed and simplicity with this code.

Code: Select all

      DIM x&(999999)
      x&(654321) = 12

      TIME=0
      FOR I%=0 TO 999999
        IF x&(I%) EXIT FOR
      NEXT
      PRINT TIME I% x&(I%)

      TIME=0 I%=-1
      REPEAT I%+=1 UNTIL x&(I%)
      PRINT TIME I% x&(I%)
      END

at least three other offerings at Facebook if you want to check there

I don't have a Facebook account. Way too intrusive. Maybe someday... if there is no other option.

[Richard Russell]

My method is:

Code: Select all

byte$       = "TEST"               : REM create a string named "byte$"
PTR(byte$)  = ^x&(0)               : REM alter "byte$"'s data pointer, to point to 0'th elem of x&()
!(^byte$+4) = DIM(x&(),1) + 1      : REM alter "byte$"'s value-length to number of bytes (DIM plus 1) in x&

I'll allow this, especially as it gives good results, but it would have to be used with care because any change (inadvertent or otherwise) to byte$ subsequently in the program could result in the array being corrupted. For example if you put it in a procedure or function, and made byte$ LOCAL (as you might well be tempted to do) it would leave the array vulnerable to corruption because the string allocator would consider it 'free' string memory.

Indeed not only the array, but subsequent memory, would be in danger of corruption because the string allocator will assume that the amount of memory allocated to the 'string' follows the normal rules of always being 2^n-1 bytes, which it isn't in this case. A string longer than the array could therefore be written, splatting memory past its end. Nasty.

In the event of a tie I'll mark it down because of this vulnerability!

[Richard Russell]

Here is the final league table (sorry if anybody was preparing a submission but hadn't yet got around to posting it):

challenge.png

There's hardly anything to choose between the first two really. Had there been a dead heat I would still have put Jeremy in second place for using code reliant on implementation detail and with a memory corruption vulnerability (not disallowed by the challenge rules, but bad practice if avoidable).

I must give a (very) honourable mention to Dom Powys-Lybbe who didn't submit a solution but described in words exactly the algorithm I chose (binary split). Also credit to Ian Boddy for his simpler divide-and-conquer approach, which generally wins over a linear search.

Strictly speaking I should have disallowed Mijndert's submission because it assumes the non-zero value will always be 1, which isn't stated in the challenge. But I was generous.

Here's the full set of solutions in the form of the program I used to compare them:

Code: Select all

      DIM x&(999999)
      x&(654321) = 1

      FOR Run% = 1 TO 9
        VDU 30

        @% = 7
        PRINT "      Name " TAB(Run%*7 + 10,VPOS) "Run "; Run%

        PRINT '"Richard Russell";
        SYS "SDL_GetTicks64" TO t1%
        L% = 0 : H% = DIM(x&(),1)
        REPEAT M% = (L%+H%) DIV 2
          IF SUM(x&(L% TO M%)) H% = M% ELSE L% = M%+1
        UNTIL L%>=H%
        SYS "SDL_GetTicks64" TO t2%
        IF H% <> 654321 STOP
        PRINT TAB(Run%*7 + 8,VPOS) t2%-t1%;

        PRINT '"Jeremy Nicoll";
        SYS "SDL_GetTicks64" TO t1%
        Sum& = SUM( x&() )
        byte$       = "TEST"
        PTR(byte$)  = ^x&(0)
        !(^byte$+4) = DIM(x&(),1) + 1
        found%      = INSTR(byte$, CHR$(Sum&) ) - 1
        SYS "SDL_GetTicks64" TO t2%
        IF found% <> 654321 STOP
        PRINT TAB(Run%*7 + 8,VPOS) t2%-t1%;

        PRINT '"Ian Boddy";
        SYS "SDL_GetTicks64" TO t1%
        P%% = ^x&(0)
        FOR I% = 0 TO 999999 STEP 4
          IF P%%!I% THEN
            FOR J% = 0 TO 3
              IF x&(I%+J%) THEN
                K% = I%+J%
                EXIT FOR I%
              ENDIF
            NEXT
          ENDIF
        NEXT
        SYS "SDL_GetTicks64" TO t2%
        IF K% <> 654321 STOP
        PRINT TAB(Run%*7 + 8,VPOS) t2%-t1%;

        PRINT '"Paul Marshall";
        n% = 1000000
        SYS "SDL_GetTicks64" TO t1%
        FOR I% = 0 TO n%-1
          IF x&(I%) EXIT FOR
        NEXT
        SYS "SDL_GetTicks64" TO t2%
        IF I% <> 654321 STOP
        PRINT TAB(Run%*7 + 8,VPOS) t2%-t1%;

        PRINT '"Mike Jansen";
        SYS "SDL_GetTicks64" TO t1%
        x&() /= MOD(x&())
        x&() *= 13
        I% = LEN$^x&(0)
        SYS "SDL_GetTicks64" TO t2%
        IF I% <> 654321 STOP
        PRINT TAB(Run%*7 + 8,VPOS) t2%-t1%;

        PRINT '"Eddy Jacobs (1)";
        SYS "SDL_GetTicks64" TO t1%
        I%=0
        WHILE x&(I%)=0 I%+=1 ENDWHILE
        SYS "SDL_GetTicks64" TO t2%
        IF I% <> 654321 STOP
        PRINT TAB(Run%*7 + 8,VPOS) t2%-t1%;

        PRINT '"Eddy Jacobs (2)";
        SYS "SDL_GetTicks64" TO t1%
        i=0
        WHILE x&(i)=0 i+=1 ENDWHILE
        SYS "SDL_GetTicks64" TO t2%
        IF i <> 654321 STOP
        PRINT TAB(Run%*7 + 8,VPOS) t2%-t1%;

        x&(654321) = 1
        PRINT '"Mijndert Rooth";
        SYS "SDL_GetTicks64" TO t1%
        FOR I% = 0 TO 999999
          IF x&(I%) = 1 THEN A% = I%
        NEXT
        SYS "SDL_GetTicks64" TO t2%
        IF A% <> 654321 STOP
        PRINT TAB(Run%*7 + 8,VPOS) t2%-t1%;

        PRINT '"Eddy Jacobs (3)";
        SYS "SDL_GetTicks64" TO t1%
        FOR I%=0 TO 999999 IF x&(I%)<0 OR x&(I%)>0 EXIT FOR
        NEXT
        SYS "SDL_GetTicks64" TO t2%
        IF I% <> 654321 STOP
        PRINT TAB(Run%*7 + 8,VPOS) t2%-t1%;

        PRINT '"Eddy Jacobs (4)";
        SYS "SDL_GetTicks64" TO t1%
        FOR i=0 TO 999999 IF x&(i)<0 OR x&(i)>0 EXIT FOR
        NEXT
        SYS "SDL_GetTicks64" TO t2%
        IF i <> 654321 STOP
        PRINT TAB(Run%*7 + 8,VPOS) t2%-t1%;

      NEXT Run%

      PRINT '' "All times in milliseconds"

[Phil_Thatcham]

Running the solutions here, on a very ordinary AMD PC, gives broadly similar results to those posted except for the first two.

These consistently take three times longer than the times posted. I'm wondering why.

Also, Mike Jansen's solution fails (String too long) at:

I% = LEN$^x&(0)

Wondering about that, too. Is it happening to anyone else?

pt

[Richard Russell]

Running the solutions here, on a very ordinary AMD PC, gives broadly similar results to those posted except for the first two.

These consistently take three times longer than the times posted. I'm wondering why.

Also, Mike Jansen's solution fails (String too long) at:

I% = LEN$^x&(0)

Both would suggest you're using one of the versions of BBC BASIC coded in C, rather than in assembly language, for example a 64-bit version or an ARM version. Despite compilers being a lot better than they used to be, you can still get a benefit from hand-crafted machine code, which is probably why you're not seeing the same performance as I got in the first two cases.

Similarly the coded-in-C versions limit the length of 'fixed strings' (i.e. strings terminated by a carriage-return or NUL) to 65,535 bytes, being the size of the 'string accumulator', which breaks Mike Jansen's approach. I've long since forgotten the technical reason for this difference, I'm afraid; it could simply be that when I converted the code to C I couldn't understand how the assembler version worked!

Sadly I'm no longer able to modify the BBC BASIC source code safely, but as the C version is Open Source anybody so inclined could try to work out what the performance bottleneck affecting the first two results is and perhaps figure out a way of tackling it. Brandy BASIC is also written in C and is much faster than mine, showing that there should be room for improvement.