[Icfp04-discuss] Scheme, Ruby ?

[Alejandro Forero Cuervo]

> > It would be interesting to profile your simulator to find the
> > code  consuming most  of  the time  in  a single  round. What
> > structure you used to represent ant world in Scheme ?
>
> [...]  I might  apply some  of these  changes and  see if  they
> actually  improve things.   I  know, I  should  use a  profiler
> first.

Ok, I  optimized my simulator  and built it with  the appropriate
compiler flags.

Before my  optimizations, I tested  it with two instances  of the
sample.ant running for 100.000 rounds in the sample0.world world.
I got the following times:

real    1m25.965s
user    1m24.392s
sys     0m0.388s

Sorry, that's 3 times my previous report of "around 30 seconds".

After my optimizations, the time went down 1/3:

real    0m30.629s
user    0m29.653s
sys     0m0.312s

Building it with the appropriate compiler flags (removing a lot of
safety checks) the time went down another 1/3:

real    0m7.956s
user    0m7.672s
sys     0m0.081s                                                                                             

These times are  measured in a 2.8 Ghz Athlon  with plenty of RAM
under Chicken 1.51 and GCC 3.3.3.

What  did  I  optimize?   I  made  the  simulator  make  as  many
computations  as  it  can  as it  reads  the  instructions  (this
accounts  for  about 3/4  of  the  new  savings).  Also,  in  the
closures associated  with instructions  (states), I  replaced the
numbers for states  with their actual closures to  avoid a vector
reference (this accounts for 1/4 of the savings).

There are still  more optimizations that can be  tried.  Here are
some ideas:

- Turn  the list  of  ants  into a  doubly  linked list.   Remove
  resting ants from  it.  Rather than record the  number of turns
  that an ant should rest, record  the number of the turn when it
  will be  allowed to move again.   Keep resting ants in  a list,
  sorted by the turn when they will be allowed to move again (and
  keep a pointer to its  tail for fast insertion).  Assuming that
  half the ants  are resting at any given time,  this could bring
  the running time to a half.

- Optimize the movement and senses, as I explained in my previous
  mail.  There are still some  computations that can be spared in
  moves and senses.

Thanks.

Alejo.
http://bachue.com/alejo

---=(  Comunidad de Usuarios de Software Libre en Colombia  )=---                                                              
---=(  http://bachue.com/colibri )=--=( colibri at bachue.com  )=---                                                              
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://lists.seas.upenn.edu/pipermail/icfp04-discuss/attachments/20040616/18bf712c/attachment.bin