[computer-go] Language War!

[Weston Markham]

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.

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.

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.

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