On Mon, Nov 12, 2007 at 03:31:12PM -0500, Imran Hendley wrote:
> Sorry I did not have time to look at your code, but here a few quick hints:
Thanks!
> 1) Before any optimization make sure that your code works 100%
> correctly. This means testing extensively and writing tests that you
> can use as you start optimizing to make sure nothing breaks in the
> process. You might get into big trouble if there is a bug you find
> after doing lots of optimizations.
Yes... I underestimated this so far, and it's starting to show. ;-)
> 2) Learn how to profile your code. I don't work in C so unfortunately
> I can't give you specific directions. But this is always the first
> step in optimizing a large project. When you can see exactly where
> your bottlenecks are it is 100 times easier and more efficient to
> optimize. Without profiling you might find yourself spending a week on
> an optimization that ends up giving you only 1% speedup.
>
> The main optimization for me was squeezing every little bit out of
> random number generation. This meant using a third party random number
> generator in java (because the built in one is slow and also not
> really pseudorandom anyway) and using various other tricks...
I'm profiling a lot. I have also discovered gcc -fprofile-generate and
-fprofile-use in the process, and it can speed up the code by up to
another 20%!
> 3) Think very carefully about data structures and algorithms at a high
> level. I tried to simplify my board structure and my structure for
> representing strings as much as possible and this also generated a lot
> of speedup. As the last poster mentioned, if you are picking a random
> intersection and rejecting the ones that are occupied until you have
> filled the board this will take a lot longer than mainting a list of
> empty intersections and only sampling from these. More specifically,
> only sampling from empty intersections will take O(n) to fill the
> board, while sampling with replacement and rejecting occupied
> intersections will take O(nlogn) which is actually pretty bad since a
> lot of time is spent deciding where to play as it is.
Yes. Actually, I guess that adjusting the data structures is the main
optimization work I'm doing.
--
Petr "Pasky" Baudis
We don't know who it was that discovered water, but we're pretty sure
that it wasn't a fish. -- Marshall McLuhan
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
