[computer-go] Language War!

[Chrilly]

----- Original Message ----- 
From: "Weston Markham" <weston.markham at gmail.com>
To: "computer-go" <computer-go at computer-go.org>
Sent: Monday, July 31, 2006 6:45 PM
Subject: Re: [computer-go] Language War!


> On 7/31/06, Chrilly <c.donninger at wavenet.at> wrote:
>> What is the advantage of a BitSet Representation over e.g. an Array of
>> Bytes?
>> Board[point]=WHITE_STONE;  is faster than something link
>> WhiteBitSet[point>>5]|=(0x1<<(point&0x1F));
>
> I'm not sure what you mean.  Here is what I believe the bitset version
> looks like:
>
> blackBitSet[point] = false; whiteBitSet[point] = true;
>
> Plus, this is C++, so if you also need the array-of-bytes syntax that
> you give, you can wrap the bitsets in a class/struct that provides it.
>
STL hides the details, but internally the implementation will be similar to 
what I have writen in plain C. My code packs 32 set members in one 
32-unsigned number and sets the according bit. C and also no modern 
processor can directly manipulate bits. The smallest addressable entity is 
the byte (there are some 8-Bit microcontrollers which have some bit-fiddling 
instructions to use e.g 256 Bytes of RAM very efficient).
One has also to consider the problem of retrieving the set bits. This is 
especially a problem if the bits are relative sparse and like in case of Go 
the bitset does not fit into one register. Bitmap representations have 
become popular in recent time in chess because of the new 64-Bit processor. 
Before there was the nasty find next bit problem. The Pentium has the 
BitScan-Instruction, but this instruction is relative slow. In case of 
several ints one has additionally a lot of if-instructions to test if there 
was a bit-set till the end of the DWORD (or QUADWORD on 64-Processors).
In Suzie I use Bitsets implemented like the code above. E.g. for the libs of 
a string. But additionally I have a bit-list. The bit-set is very fast for 
asking the "Is-Member" question, the List is much faster for iterating over 
all members. The Advantage of the bitset over an Index-Array is in this 
case, that clearing the Bit-Set is much faster. E.g. when a new single-stone 
is set and and a new group is created. Also the union of 2 sets is much 
faster. And it saves also some memory. The disadvantage is that one has to 
update both data-structures.

> I believe that a board representation based on bitsets, without
> additional data that must be updated, gains a performance benefit in
> many contexts, simply from being memory-efficient.  Less memory
> accessed means that it will fit more easily in your processor's cache.
> The quantitative advantage gained, however, is also a function of the
> hardware being used, and what other memory must be touched within your
> loop, so it is difficult to make any blanket claim that it will always
> offset the penalty of having to perform additional steps to identify
> surrounded groups.
>
OK. But see above.


> I am not familiar with J. Bently's results.  I would however, like to
> point out that the very principle that you cite, "a special purpose
> data-representation [or algorithm] is faster than a general purpose
> one" gives std::sort a big advantage over, e.g., qsort.  I'm not sure
> what effort is needed to achieve a 5:1 advantage over std::sort, but I
> can't help but think that it is highly tailored to a specific problem
> and/or specific hardware.  One ordinarily does not want to spend one's
> time writing that custom code.
>
No in all parts of the code. But in the critical parts 5 times speedup (even 
2 times speedup) is almost always worth the effort.

> With respect to STL and dynamic memory allocation, bitsets are good,
> because with any reasonable STL implementation, bitsets declared as
> automatic variables will not allocate any memory from the heap.
> vector::reserve allows one to explicitly control the timing of
> allocations.  Unfortunately, there is no standard way to explicitly
> control the timing of releasing dynamic memory.  However, in practice,
> this is not as critical, and vector::swap can be used to do it, by
> swapping with a temporary that is immediately destroyed.
>
> Weston
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/