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 ?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; }
CPW bitscan with reset could someone explain this line?
Moderators: hgm, Rebel, chrisw
-
- Posts: 234
- Joined: Sat Jan 17, 2015 11:54 pm
CPW bitscan with reset could someone explain this line?
on the wiki:
-
- Posts: 855
- Joined: Sun May 23, 2010 1:32 pm
Re: CPW bitscan with reset could someone explain this line?
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
Having them in register should be faster
-
- Posts: 1563
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: CPW bitscan with reset could someone explain this line?
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.
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: CPW bitscan with reset could someone explain this line?
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.
-
- Posts: 1563
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: CPW bitscan with reset could someone explain this line?
Agreed, it is just that I don't see any reason why the optimizer could not inline that routine everywhere.
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: CPW bitscan with reset could someone explain this line?
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.
-
- Posts: 1563
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: CPW bitscan with reset could someone explain this line?
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.
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: CPW bitscan with reset could someone explain this line?
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.
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, ...);
}
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: CPW bitscan with reset could someone explain this line?
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.Joost Buijs wrote: ↑Fri Mar 15, 2019 5: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.
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.
-
- Posts: 1563
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: CPW bitscan with reset could someone explain this line?
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.hgm wrote: ↑Fri Mar 15, 2019 10:30 pmSure, 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.Joost Buijs wrote: ↑Fri Mar 15, 2019 5: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.
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.
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.