optimization - 为什么这个 Haskell 函数很慢？

Question

我有一个单行函数，它占用了我 25% 的执行时间，这对我来说确实违反直觉。

上下文是棋盘游戏 (Blokus) 的 AI，具体而言，我们在这里所做的是尝试确定将棋子放在特定棋盘单元附近的特定方向是否合法。我们已经预先计算了一个 Word64 (placementBitmap)，它显示了在特定方向上哪些单元格被一块占据，最近我们计算了一个 Word64 (cornerBitmap)，它显示了围绕这个正方形的可用单元格。所以现在我们比较它们:

legalAt (TerritoryCorner _ _ cornerBitmap) (Placement _ _ _ placementBitmap) = (placementBitmap .&. cornerBitmap) == placementBitmap

我不明白这里的几个按位运算如何比首先计算cornerBitmap 的过程花费更多的时间。拳击问题？我对 Haskell 很陌生。

TerritoryCorner 和 Placement 的数据构造函数都被定义为最后一个参数是严格的，无论它值多少钱。

使用它的上下文是列表理解:

[getMyChild corner placement | corner <- myCorners, placement <- myPlacements, legalAt corner placement]

我设法生成了以下核心，但我不知道如何解释它:

GameState.legalAt [InlPrag=INLINE[0]]
  :: Types.TerritoryCorner -> Types.Placement -> GHC.Bool.Bool
[GblId,
 Arity=2,
 Caf=NoCafRefs,
 Str=DmdType U(AAAL)U(UUUL),
 Unf=Unf{Src=InlineStable, TopLvl=True, Arity=2, Value=True,
         ConLike=True, Cheap=True, Expandable=True,
         Guidance=ALWAYS_IF(unsat_ok=True,boring_ok=False)
         Tmpl= \ (w_soat [Occ=Once!] :: Types.TerritoryCorner)
                 (w1_soaA [Occ=Once!] :: Types.Placement) ->
                 case w_soat of _ { Types.TerritoryCorner _ _ _ ww3_soay ->
                 case w1_soaA of _ { Types.Placement _ _ _ ww7_soaF ->
                 __scc {legalAt main:GameState}
                 case {__pkg_ccall ghc-prim hs_and64 GHC.Prim.Word64#
                               -> GHC.Prim.Word64#
                               -> GHC.Prim.State# GHC.Prim.RealWorld
                               -> (# GHC.Prim.State# GHC.Prim.RealWorld, GHC.Prim.Word64# #)}_aHK
                        ww7_soaF ww3_soay GHC.Prim.realWorld#
                 of _ { (# _, ds3_aHQ [Occ=Once] #) ->
                 GHC.IntWord64.eqWord64# ds3_aHQ ww7_soaF
                 }
                 }
                 }}]
GameState.legalAt =
  \ (w_soat :: Types.TerritoryCorner) (w1_soaA :: Types.Placement) ->
    case w_soat
    of _ { Types.TerritoryCorner ww_soav ww1_soaw ww2_soax ww3_soay ->
    case w1_soaA
    of _ { Types.Placement ww4_soaC ww5_soaD ww6_soaE ww7_soaF ->
    __scc {legalAt main:GameState}
    case {__pkg_ccall ghc-prim hs_and64 GHC.Prim.Word64#
                               -> GHC.Prim.Word64#
                               -> GHC.Prim.State# GHC.Prim.RealWorld
                               -> (# GHC.Prim.State# GHC.Prim.RealWorld, GHC.Prim.Word64# #)}_aHK
           ww7_soaF ww3_soay GHC.Prim.realWorld#
    of _ { (# _, ds3_aHQ #) ->
    GHC.IntWord64.eqWord64# ds3_aHQ ww7_soaF
    }
    }
    }

Answer 1

您在 32 位平台上，因此 64 位操作是 C 调用，这使得它们比在 64 位平台上慢一些。然而，这不应该花费那么多，而核心是 legalAt正如人们所希望的那样好。我认为与您的信念相反，cornerBitmap 的计算和 placementBitmap之前没做过，被legalAt逼的并且由分析器将成本归因于此。

我们需要查看更多代码和上下文以了解更多信息。