Can anyone explain the performance difference between scan_forward() and scan_reversed()?

[jacksonthall22]

On my machine, scan_reversed() is consistently faster than scan_forward(). Why?

$ ipython
Python 3.11.4 | packaged by conda-forge | (main, Jun 10 2023, 17:59:51) [MSC v.1935 64 bit (AMD64)]
Type 'copyright', 'credits' or 'license' for more information
IPython 8.14.0 -- An enhanced Interactive Python. Type '?' for help.

In [1]: import chess

In [2]: b = chess.Board()

In [3]: %timeit list(chess.scan_forward(b.occupied))
10.3 µs ± 466 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

In [4]: %timeit list(chess.scan_reversed(b.occupied))
6.85 µs ± 396 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

In [5]: %timeit list(chess.scan_forward(b.occupied_co[chess.BLACK]))
5.25 µs ± 337 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

In [6]: %timeit list(chess.scan_reversed(b.occupied_co[chess.BLACK]))
3.7 µs ± 301 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

In [7]: %timeit list(chess.scan_forward(b.occupied_co[chess.WHITE]))
3.76 µs ± 209 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

In [8]: %timeit list(chess.scan_reversed(b.occupied_co[chess.WHITE]))
3.18 µs ± 287 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

Looking at the implementations, it seems like they do almost exactly the same things. Can anyone explain this magic in detail?

def scan_forward(bb: Bitboard) -> Iterator[Square]:
    while bb:
        r = bb & -bb
        yield r.bit_length() - 1
        bb ^= r

def scan_reversed(bb: Bitboard) -> Iterator[Square]:
    while bb:
        r = bb.bit_length() - 1
        yield r
        bb ^= BB_SQUARES[r]

[niklasf]

It's really just the extra & and - on integers. Bitwise operations aren't as fast in Python as in other languages, and -bb is costly because it's not wrapping at 64 bits.

As an optimization, the library internals already use scan_reversed() where the iteration order is not observable.