CPW bitscan with reset could someone explain this line?

[MahmoudUthman]

on the wiki:

While traversing sets, one may combine bitscanning with reset found bit. That implies passing the bitboard per reference or pointer, and tends to confuse compilers to keep all inside registers inside a typical serialization loop [22] .

Code: Select all

int bitScanForwardWithReset(U64 &bb) { // also called dropForward
    int idx = bitScanForward(bb);
    bb &= bb - 1; // reset bit outside
    return idx;
}

what is meant by "tends to confuse compilers to keep all inside registers inside a typical serialization loop"?, is it that it keeps the compiler from vectorizing the serialization loop or something else ?

[elcabesa]

I understand that it confuse the compiler about keeping the data in cpu register instead that in ram.
Having them in register should be faster

[Joost Buijs]

That note is based on 15 year old data, my guess is that the optimizers of modern compilers don't have a problem with it.

[hgm]

I think that would only hold if you compile in such a way that the optimizer can in-line the routine everywhere. There is no way to pass a pointer to a register. So if this routine and the caller are compiled separately, the only way for the caller to make the bitboard available for change is to put it in memory.

[Joost Buijs]

Agreed, it is just that I don't see any reason why the optimizer could not inline that routine everywhere.

[hgm]

That would happen, for instance, when it was in a separate source file, and you don't specify this fancy global link-time optimization. So I think a small caveat is still justified; the programmer should be careful not to have any adverse effects from this.

[Joost Buijs]

When you define this function inline in a header file interprocedural or linktime optimization is not necessary, at least that is my experience with the compilers I use. It might be different for g++, I don't know.

[Gerd Isenberg]

see also ...
https://www.chessprogramming.org/Bitboa ... with_Reset

A win of abstraction is to use a combined bitscan with reset found bit routine. This is fine. But probably harder for compilers to generate optimal code in the if-do-while-sense, where reset last bit already sets the zero-flag. If you don't care on such micro-optimizations, this is the preferred control structure.

Code: Select all

while ( x ) {
   int idx = bitScanAndReset(&x); // square index from 0..63
   *list++ = foo(idx, ...);
}

[hgm]

When you define this function inline in a header file interprocedural or linktime optimization is not necessary, at least that is my experience with the compilers I use. It might be different for g++, I don't know.

Sure, files that are #included are basically the same file. Usually it is considered bad practice to have executable code in headers, but for inlined functions it seems a good solution.

I never saw much benefit in such two-statement subroutines anyway. Might as well write the two statements in the code directly. For me,

idx = bitScanAndReset(&b);

reads just as easily as

idx = bitScan(b); b &= b-1;

It is just like 'Reset' is spelled a bit differently. And if I did anything at all, out of habit I would probably #define a macro for it (naturally in a header) rather than an inlined function.

[Joost Buijs]

When you define this function inline in a header file interprocedural or linktime optimization is not necessary, at least that is my experience with the compilers I use. It might be different for g++, I don't know.

Sure, files that are #included are basically the same file. Usually it is considered bad practice to have executable code in headers, but for inlined functions it seems a good solution.

I never saw much benefit in such two-statement subroutines anyway. Might as well write the two statements in the code directly. For me,

idx = bitScanAndReset(&b);

reads just as easily as

idx = bitScan(b); b &= b-1;

It is just like 'Reset' is spelled a bit differently. And if I did anything at all, out of habit I would probably #define a macro for it (naturally in a header) rather than an inlined function.

It is just a matter of coding style, I always like to have these primitives in inline functions. If you want to change something in such a function you only have to change a few lines instead of changing your program at all places where you use this function.

For instance when I want to replace b &= b - 1; with b = _blsr_u64(b); I only have to change 1 line, otherwise I have to change hundreds.

I refrain from using macros because they have no type checking, as an alternative I use inline functions, const, constexpr or variable templates.