溢出运算符是否比执行不会导致溢出的操作效率低？

Question

我在做什么：我正在 Swift 中编写国际象棋引擎。编写强大的国际象棋引擎最重要的部分之一是能够在尽可能短的时间内生成尽可能多的未来棋盘位置。您的引擎可以在更短的时间内生成和评估的位置越多，引擎就越强大。

话虽如此，我已经编写了用于生成滑动棋子（象、车和皇后）移动的函数。 这些函数使用溢出运算符（&+、&-、&*），就像使用普通的按位运算符frequently cause overflow errors.

生成所述移动需要两个函数，一个用于为滑动块生成所有合法的垂直和水平移动，一个用于为滑动块生成所有合法的对角线移动。这两个函数实际上是在做同样的事情，我们只是对参数的处理略有不同。下面是生成水平和垂直移动的函数：

//occupied is a bitboard that represents every square on the chess board that is occupied
//this value is set somewhere before our move generation functions are ever called
var occupied: UInt64 = 0

//the rankMasks and fileMasks are simply arrays of bitboards that represent each individual file and rank on a chess board
//rankMasks8[0] would represent the squares a8-h8, rankMasks8[1] would represent the squares a7-h7
//fileMasks8[0] would represent the squares a1-a8, fileMasks8[1] would represent the squares b1-b8
let rankMasks8: [UInt64] = [ 255, 65280, 16711680, 4278190080, 1095216660480, 280375465082880, 71776119061217280, 18374686479671623680 ]
    let fileMasks8: [UInt64] = [ 72340172838076673, 144680345676153346, 289360691352306692, 578721382704613384, 1157442765409226768, 2314885530818453536, 4629771061636907072, 9259542123273814144 ]

...

//We pass a square (0 - 63) as s and we are returned a UInt64, the bitboard representing all the squares that the piece on the passed square can move to.
func horizontalAndVerticalMoves(s: Int) -> UInt64 {
    //convert the passed square into a bitboard that represents its location, by raising 2 to the power of s
    let binaryS: UInt64 = 1<<s

    //formula for generating possible horizontal moves
    let possibilitiesHorizontal: UInt64 = (occupied &- (2 &* binaryS)) ^ UInt64.reverse(UInt64.reverse(occupied) &- 2 &* UInt64.reverse(binaryS))
    //formula for generating vertical moves
    let possibilitiesVertical: UInt64 = ((occupied & fileMasks8[s % 8]) &- (2 &* binaryS)) ^ UInt64.reverse(UInt64.reverse(occupied & fileMasks8[s % 8]) &- (2 &* UInt64.reverse(binaryS)))

    //we return possible horizontal moves OR possible vertical moves
    return (possibilitiesHorizontal & rankMasks8[s / 8]) | (possibilitiesVertical & fileMasks8[s % 8])
}

关于上述函数，您需要认识到的唯一重要的事情是它为我们提供了预期的输出，并且它使用 溢出运算符。

现在，我之前对同一方法的迭代（在我了解如何使用溢出运算符规避溢出之前）更加冗长。它需要运行四个 while 循环，它们会在 "north"、"south"、"east" 或 "west" 方向上离开当前片段，直到它进入与阻止在相应方向上进一步移动的一块接触。 horizontalAndVerticalMoves 函数的迭代如下所示：

func horizontalAndVerticalMoves(s: Int) -> UInt64 {
    let rankMask: UInt64 = rankMasks8[s/8]
    let fileMask: UInt64 = fileMasks8[s%8]
    let pseudoPossibleMoves: UInt64 = rankMask ^ fileMask
    var unblockedRanks: UInt64 = 0
    var unblockedFiles: UInt64 = 0
    var direction: Direction! = Direction.north

    var testingSquare: Int = s - 8
    while direction == .north {
        if testingSquare < 0 || testingSquare%8 != s%8 {
            direction = .east
        } else {
            if 1<<testingSquare&occupied != 0 {
                unblockedRanks += rankMasks8[testingSquare/8]
                direction = .east
            } else {
                unblockedRanks += rankMasks8[testingSquare/8]
                testingSquare -= 8
            }
        }
    }

    testingSquare = s + 1
    while direction == .east {
        if testingSquare > 63 || testingSquare/8 != s/8 {
            direction = .south
        } else {
            if 1<<testingSquare&occupied != 0 {
                unblockedFiles += fileMasks8[testingSquare%8]
                direction = .south
            } else {
                unblockedFiles += fileMasks8[testingSquare%8]
                testingSquare += 1
            }
        }
    }

    testingSquare = s + 8
    while direction == .south {
        if testingSquare > 63 || testingSquare%8 != s%8 {
            direction = .west
        } else {
            if 1<<testingSquare&occupied != 0 {
                unblockedRanks += rankMasks8[testingSquare/8]
                direction = .west
            } else {
                unblockedRanks += rankMasks8[testingSquare/8]
                testingSquare += 8
            }
        }
    }

    testingSquare = s - 1
    while direction == .west {
        if testingSquare < 0 || testingSquare/8 != s/8 {
            direction = .north
        } else {
            if 1<<testingSquare&occupied != 0 {
                unblockedFiles += fileMasks8[testingSquare%8]
                direction = .north
            } else {
                unblockedFiles += fileMasks8[testingSquare%8]
                testingSquare -= 1
            }
        }
    }

    let mask = unblockedRanks | unblockedFiles
    let possibleMoves = pseudoPossibleMoves&mask

    return possibleMoves
}

我认为我新实现的这个函数的版本（使用溢出运算符的版本）不仅更简洁，而且高效。关于同一函数的这次迭代，您需要注意的唯一重要事项是它为我们提供了预期的输出，但看起来更加冗长并且不使用溢出运算符。

我注意到的： 如前所述，我预计使用溢出运算符的更新、更简洁的代码会比使用一堆 while 循环的迭代执行得更快.当运行测试我生成国际象棋动作的速度时，我发现使用 while 循环而不是溢出运算符的版本要快得多。计算国际象棋游戏中前三步的每一个组合需要原函数略小于6秒，而使用溢出运算符的较新函数 需要 13 秒.

我想知道的是： 因为我想尽可能地创建最强大的国际象棋引擎，所以我正在寻找可以加快执行速度的代码片段。旧功能比新功能执行得更快对我来说似乎违反直觉。所以我想知道， 是众所周知的 Swift 中的溢出运算符 slow/inefficient?

生成这些移动的 class 看起来像这样：https://github.com/ChopinDavid/Maestro/blob/master/Maestro/Moves.swift

Answer 1

So I am wondering, are overflow operator in Swift notoriously slow/inefficient?

不，如果有什么相反的话。

用于乘法等的机器级指令可能会设置一个溢出标志，但它们仅此而已。对于标准运算符 Swift 必须编译额外的指令来测试该标志并生成错误并且此代码包含分支（尽管分支预测应该有效地减轻这些）。

您的溢出运算符版本的代码比标准运算符版本的代码更短，而且它也是无分支的。

版本之间的性能差异是什么是另一回事，但是溢出版本应该不会慢。

您可能需要在别处寻找性能差异。狩猎愉快！

注意：以上比较基于 Swift 编译器在 Xcode 11.3.1 中生成的完全优化代码 ("Fastest, Smallest [-Os]")，调试版本可能会产生截然不同的结果。

溢出运算符是否比执行不会导致溢出的操作效率低？

Are overflow operators less efficient than performing operations that don't result in overflows?

64-bit

chess

uint64

bitboard

swift