[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Sudoku puzzle solver for Apple II

Anton Treuenfels wrote:

"Michael J. Mahon" <mjmahon@aol.com> wrote in message
GL2dnfZbpopeQyjZnZ2dnUVZ_rKdnZ2d@comcast.com">news:GL2dnfZbpopeQyjZnZ2dnUVZ_rKdnZ2d@comcast.com...


Michael J. Mahon wrote:


Michael J. Mahon wrote:



Paul Schlyter wrote:



APproximately how much slower do you think a 6502 version would have
been?  10% slower?  Twice as slow?  10 times as slow?




Certainly less than twice as slow.  I'll find out what the current
speed impact would be...



Paul's message prompted me to re-look at where 65C02 ops are used, and
they are all quite easy to eliminate--most with no or negligible time
impact.

The only one that has a measurable impact is the LDA (p) in setbox,
and that can be eliminated by just doing an LDA bit rather than a TXA,
which frees up the X register to hold 0, so that the LDA (p) can become
LDA (p,x).  (I don't get to use that addressing mode much--even if it is
with a constant 0 index.  ;-)



Speaking of 'setbox', I'm surprised that you used a lookup table to
determine screen addresses but did not use one for the 'other' array. If I
understand the code correctly, you could replace the
'best*24+other_base_address' calculation with a pre-computed value. Also you
could get rid of three '-1' values in 80 rows of 'other', for a net savings
of 80 bytes to boot.


I think the simple answer is that the pieces of code were written by
different people at different times.  ;-)


Heck, you could get rid of that last -1 value in each row as well: add $80
to the last entry, so that the ASL instruction in the main loop of 'setbox'
sets the carry for that entry, clears it for all the others. Then after
you've set the bit of interest, break the loop if the carry flag is set.
That also saves one LDA instruction at the top of the loop (20 executions
instead of 21).


Switching to count control for the loop is a big win.


And then you might consider breaking the 'setbox' loop in two loops, one for
setting the low byte and one setting the 9th bit. That would eliminate the
redundant test executed inside the loop: just test it once to decide which
loop to execute. Of course all the loop control code would be duplicated and
the only differences would be the few instructions that actually set bits,
but you just saved a bunch of space by implementing that 'others' lookup
table.

And of course you don't need 65C02 instructions to do any of this :)


Right.  I've already eliminated the 65C02 instructions, and one of the
paths not (yet?) taken was splitting the loop.


Something like this:

    ...
    lda best
    asl
    tax
    lda otherptr,x
    sta p
    lda otherptr+1,x
    sta p+1
    ldx #20-1
    lda bit
    beq    high_bit_loop

:1  txa
    tay
    lda (p),y
    asl
    tay
    lda (bits),y
    ora bit
    sta (bits),y
    dex
    bpl :1
    rts

high_bit_loop:

     txa
    tay
    lda (p),y
    asl
    tay
    iny
    lda (bits),y
    ora #$01
    sta (bits),y
    dex
    bpl high_bit_loop
    rts

...to take advantage of the fact that there are two indirect pointers
already. Can use the X-register for counting directly,
and don't need to put any kind of special coded values in the 'other' table
at all.

And if that works, why not store the neighbor square# times two in the
'other' table and eliminate the ASL instruction in each loop?


It's all good...I'm working on the solver as we "speak".

There's no need to do an OR in the "=9" case, since the only values
that byte can take on are 0 and 1.  So LDA #1; STA (bits),y will do
fine.  This, together with other changes, gets this loop down to 18
cycles per iteration--too bad that it's much less frequent than the
other case.  ;-)


Oh, I gotta stop now...


Please don't!  ;-)

BTW, as I was thinking about the additional ops in the 65C02, I realized
how much more useful it would have been to provide more symmetry between
the X and Y registers.  For example, the register juggling in the above
loop would be unnecessary if you could post-index by X as well as Y.

Kind of makes you wonder who designed the extensions...

We can avoid this juggling by modifying the addresses of the "neighbor
index" loads, outside the loop.  This allows X to be used directly as
an index.  When combined with storing the index already doubled, it
drops the "<9" loop to 22 cycles per iteration, resulting in a net
saving of about 260 cycles per 'setbox' call.  In our benchmark
puzzle, it's called about 8300 times, for a saving of about 2.3 seconds
out of 30, or 7.6%.  Though I prefer factors of two, I'll take it! ;-)

-michael

Even faster Sudoku solver for *all* Apple II's soon!
Home page:  http://members.aol.com/MJMahon/

"The wastebasket is our most important design
tool--and it's seriously underused."