Re: [computer-go] Chains and liberties

["Jim O'Flaherty, Jr." <jim_oflaherty_jr@xxxxxxxxx>]

Mark,

For performance tuning Java, I recommend this site:
http://www.javaperformancetuning.com/

These two guys work for IBM and are very in tune with all the 
performance tuning techniques in the field so to speak.


Jim


Mark Boon wrote:

> > -----Original Message-----
> > From: computer-go-bounces@xxxxxxxxxxxxxxxxx
> > [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx]On Behalf Of Gunnar
> > Farnebdck
> > Sent: Saturday, November 13, 2004 19:05
> > To: computer-go
> > Subject: Re: [computer-go] Chains and liberties
> >
> >
> > Mark wrote:
> >    
> > > Yes, I can see how that is possible, I'll think about that. But you will
> > > still need to process all the stones of the newly merged group
> > >      
> > to set the
> >    
> > > pointer to the Chain datastructure in the chain array for all
> > >      
> > the points,
> >    
> > > no?
> > >      
> > Yes. (To be perfectly honest I had forgot about this little detail
> > when I wrote the previous message, but the cyclic lists are still a
> > nice idea and a space-effective way to store some of the information.)
> >
> >    
> > > Well, keeping the chains and liberty-lists for reversal is kind
> > >      
> > of the same
> >    
> > > as keeping a change-stack I suppose.
> > >      
> > Not from my point of view. I would rather say that it's a way to
> > reduce the size of the change-stack.
> >    
> I've done a quick implementation along the lines I described. I found that
> along with the marking of the merged chain in the chain array, all I need to
> do is adding those same points to an array of integers. Although it has to
> do this for all stones in the chain, I don't see how keeping cyclic lists is
> going to beat that. I may be wrong of course. (And I have somehow gotten to
> hate making linked-lists, so I suppose I'm a bit biased here.)
>
> Taking back a move takes just moving around a few pointers. Except when
> splitting chains, in which case it needs to mark all the stones involved in
> the chain-array again.
>
> I'm not too enthousiastic about the speed. A quick test seemed to point to a
> little over 0.5 million moves per second, including taking back those same
> moves. 2 uSec per move doesn't compare too well with my ladder-module, which
> is more than twice the speed and does a whole lot more. So using it for
> ladders is not an option. But maybe for the other tactial readers and
> life-and-death it is, provided I can optimize the current implementation
> still.
>
> My implementation also feels rather OO. That means lots of function-calls.
> I'm not sure to what extent they are inlined and optimized by the compiler.
> The profiler I have is lousy and shows considerable time spent on
> function-calls, even though I know most of them should have been compiled
> out. I've been out of this kind of programming too long, it will take me a
> little time to automatically know what's fast and what's not.
>
> The other thing with OO in Java is the collections. Since Java 1.4 it
> doesn't have type-safe collections, I need to do a cast in a few places. But
> casts are very expensive. In Java 1.5, which I don't use yet, there are
> type-safe collections, but I understand from the documentation it just does
> the cast under the hood. (Swept under the carpet I call that.)
>
> Thirdly, my object pools are standard Stack objects. Since Stack is
> synchronized, this involves a considerable performance-hit as well. But it
> seemed to me for the future it's wise to keep these thread-safe. Again, I
> wish I had a better profiler.
>
> Some more work and investigation maybe necessary. Hopefully this can be used
> as a point of reference for faster methods or some clever optimization. At
> least I think the implementation *looks* pleasant and clean, something that
> may disappear with optimizations.
>
> David Weiss said he probably won't be able to finish his flat-file
> implementation for the pattern matcher before next week. I also didn't get
> aproved by SourceForge yet, so it may take a little more before I'm going to
> publish this all. In the meantime I hope I'll have some more spare time to
> tinker with the chain administration.
>
>
>
> _______________________________________________
> computer-go mailing list
> computer-go@xxxxxxxxxxxxxxxxx
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
>  
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/