CPW bitscan with reset could someone explain this line?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
MahmoudUthman
Posts: 231
Joined: Sat Jan 17, 2015 10:54 pm

CPW bitscan with reset could someone explain this line?

Post by MahmoudUthman » Thu Mar 14, 2019 9:16 pm

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
Posts: 795
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: CPW bitscan with reset could someone explain this line?

Post by elcabesa » Fri Mar 15, 2019 10:43 am

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
Posts: 833
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: CPW bitscan with reset could someone explain this line?

Post by Joost Buijs » Fri Mar 15, 2019 11:50 am

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.

User avatar
hgm
Posts: 23165
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: CPW bitscan with reset could someone explain this line?

Post by hgm » Fri Mar 15, 2019 1:27 pm

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
Posts: 833
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: CPW bitscan with reset could someone explain this line?

Post by Joost Buijs » Fri Mar 15, 2019 2:08 pm

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

User avatar
hgm
Posts: 23165
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: CPW bitscan with reset could someone explain this line?

Post by hgm » Fri Mar 15, 2019 2:16 pm

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
Posts: 833
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: CPW bitscan with reset could someone explain this line?

Post by Joost Buijs » Fri Mar 15, 2019 4:40 pm

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
Posts: 2113
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: CPW bitscan with reset could someone explain this line?

Post by Gerd Isenberg » Fri Mar 15, 2019 8:52 pm

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, ...);
}

User avatar
hgm
Posts: 23165
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: CPW bitscan with reset could someone explain this line?

Post by hgm » Fri Mar 15, 2019 9:30 pm

Joost Buijs wrote:
Fri Mar 15, 2019 4:40 pm
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
Posts: 833
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: CPW bitscan with reset could someone explain this line?

Post by Joost Buijs » Sat Mar 16, 2019 12:27 pm

hgm wrote:
Fri Mar 15, 2019 9:30 pm
Joost Buijs wrote:
Fri Mar 15, 2019 4:40 pm
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.

Post Reply