simulator (Re: [Icfp04-discuss] three liberal arts)

[Jed Davis]

"Tomas G. Rokicki" <rokicki at cs.stanford.edu> writes:

> There's really never any need to index x/y, or to do the +1/-1
> odd/even stuff.  Just store in each ant a pointer directly to 
> the appropriate square, and simply use a "shifted" board.
> For instance, for 100x100:
>
> cell board[100*(100+1)]
>
> +x is +1
> -x is -1
> +y left is +100
> +y right is +101
> -y left is -101
> -y right is -100

Yeah, but that's not nearly as fun as this:

    switch(dir) {
    case 0: ++x; break;
    case 1: x+=y++&1; break;
    case 2: x-=++y&1; break;
    case 3: --x; break;
    case 4: x-=--y&1; break;
    case 5: x+=y--&1; break;
    default: assert(false);
    }

(-:

> The guaranteed rocky borders mean you never have to worry about
> running off the edge.

And those borders are even sort of assumed by the provided pseudocode
for death-testing.

> There's no reason memory access should slow you down in the
> simulations, since the simulation pretty much should run out of
> cache.  What will probably slow you down is indirect jumps and
> branch mispredictions.  Keep these down and you should fly.

How are CPUs at arbitrary integer division these days?  A compiled
implementation, I realized this morning, could be getting some mileage
on Flip instructions out of knowing the RHS of the mod operation at
compile-time, if div*s are slow enough.  (Especially when, in a quick
survey I did of the downloaded ants I have, it's often equal to 2.)

(Of course, you can always cheat on the RNG, if you don't need exact
correctness.)
-- 
dn: cn=Jed Davis, o=panix.com  ##          see also jldavis at cs.oberlin.edu
objectclass: person
mail;personal: jdev at panix.com  ##    PGP Key FP:   A098 903E 9B9A DEF4 168F
mail;work:     jld@/           ##  [id 0xF33659F9] AA09 BF07 807E F336 59F9
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 185 bytes
Desc: not available
Url : http://lists.seas.upenn.edu/pipermail/icfp04-discuss/attachments/20040610/322b2abf/attachment-0001.bin