Distinguish rook and bishop move efficiently

[R. Tomasi]

I'm not sure if compilers are smart enough to apply de Morgan's law though.

GCC does use de Morgan's law to optimize boolean expressions:
https://gcc.gnu.org/onlinedocs/gccint/I ... tions.html
I'm not sure if it does in the way one would expect in the particular case at hands. I remember reading a comparision between the canonicalizations done by different compilers, but I don't find the site again From what I remember de Morgan's law is rather commonly used by compilers, though.

[tromp]

I am also not convinced that !(x >> 8 & x) would be faster than kind[x].

I don't understand how that got into my post. I didn't write that.
In fact I would be convinced of the opposite, particularly since I expect the ! operator to be optimized away in tests like if is_rook_move(...) { }

[hgm]

I am also not convinced that !(x >> 8 & x) would be faster than kind[x].

I don't understand how that got into my post. I didn't write that.
In fact I would be convinced of the opposite, particularly since I expect the ! operator to be optimized away in tests like if is_rook_move(...) { }

Sorry, I messed up. I wanted to add that line as an afterthought to my own posting, but must have accidentally clicked the edit button on yours. And since my posting quoted the last part of your posting, the difference was not immediately obvious. I now corrected this mistake.

And indeed things are dependent on whether the context allows the ! to be optimized away. But even if it can, x >> 3 & x requires a MOVE, SHIFT and AND, while kind[x] just requires a LOAD and a TEST.

[klx]

Your example fails the condition "given that the move constituted by that is either a rook or a bishop move".

Ok sure, I don't know the rules for how bishops move, I just observed that it's not the same.

The 2nd line should have a logical, not bitwise, or:

Huh, why is that?

or equivalently, saving one operation:

Decent compilers will compile that to the same or equivalent code. That's like me saying x / 8 should be x >> 3 to avoid slow integer division.

I'm not sure if compilers are smart enough to apply de Morgan's law though.
When only distinguishing between rook and bishop moves, the expensive logical-and && can be replaced by a cheaper bitwise-and & between (x&56)>>3 and x&7, and using the fact that from and to are limited to 6 bits, we can replace these operands by x/8 and x.

Well I can't speak for all compilers, but modern C++ compilers at least will easily do it, and in fact your suggested code will be slightly slower (16% slower on my machine).

[klx]

BIG DISCOVERY

EMANUELS ROOK / BISHOP DETECTION STRATEGY

Code: Select all

bool is_rook_move_emanuel(int from, int to) {
    return 0x1010101010101fe & 1ULL << (from ^ to);
}

Over twice as fast as the previously suggested methods!!

Emanuel does it again!!

[tromp]

Over twice as fast as the previously suggested methods!!

You're not returning bool values though.
Which is easily fixed by right shifting the 64-bit constant instead of left-shifting 1ULL.

[R. Tomasi]

Over twice as fast as the previously suggested methods!!

You're not returning bool values though.
Which is easily fixed by right shifting the 64-bit constant instead of left-shifting 1ULL.

Not sure about Perl, but at least in C/C++ the above code will indeed return a bool value (any integer can be implicitly converted to bool).

[klx]

You're not returning bool values though.
Which is easily fixed by right shifting the 64-bit constant instead of left-shifting 1ULL.

Yeah, Roland is right, I'm assuming a C style language which automatically casts it. We can also add bool() or !!() if we want to be more explicit.

YMMV, but with my compiler and machine, right shifting produces considerably slower code, since "& 1 << x" will issue the "bit test" X86 instruction while right shift does not.

[hgm]

BIG DISCOVERY

EMANUELS ROOK / BISHOP DETECTION STRATEGY

Code: Select all

bool is_rook_move_emanuel(int from, int to) {
    return 0x1010101010101fe & 1ULL << (from ^ to);
}

Over twice as fast as the previously suggested methods!!

Emanuel does it again!!

That is a LOAD (of the constant 1ull), a LOAD of the 'magic number' (which would need a ULL suffix, btw, and must be loaded from memory even though it is a constant due to its size), a SHIFT plus an AND. That is twice as many instructions than kind[from^to]. So learn to count.

[klx]

Code: Select all

bool is_rook_move_emanuel(int from, int to) {
    return 0x1010101010101fe & 1ULL << (from ^ to);
}

That is a LOAD (of the constant 1ull), a LOAD of the 'magic number' (which would need a ULL suffix, btw, and must be loaded from memory even though it is a constant due to its size), a SHIFT plus an AND. That is twice as many instructions than kind[from^to]. So learn to count.

With all due respect, you are wrong on all accounts.

1. No it does not need a ULL suffix.
2. On x64, "movabs" loads a 64 bit immediate into a register. It does not go through memory.
3. As I wrote in another post, at least on x64 systems and with a decent compiler, the specific expression I wrote will compile to the BT (bit test) instruction. There's no loading 1ULL, no shifting. There's essentially only MOV, XOR and BT, and then the result is in the carry flag for whatever use case you have. And if this check is repeated many times (which is likely to be the case if it needs to be optimized), the constant would be kept in a register, in which case there's only XOR and BT.

Your version is not bad, but a memory lookup for each test, even if L1 cached, will nonetheless be slower.

Best regards / Emanuel