performance - 为什么 replicateM (length xs) m 比 sequenceA (fmap (const m) xs) 更有效？

Question

我为一个编程问题提交的两份报告仅在一个表达式上有所不同(其中 anchors 是一个非空列表，(getIntegrals n) 是一个状态单子(monad)):
Submission 1 . replicateM (length anchors - 1) (getIntegrals n) Submission 2 . sequenceA $ const (getIntegrals n) <$> tail anchors我猜这两个表达式的等价性在编译时应该很容易看出。然而，comparatively sequenceA一个更慢，更重要的是，占用 >10 倍的内存:


代码
时间
内存


复制M一
732 毫秒
22200 KB

序列一个
1435 毫秒
262100 KB


(第二个条目出现“测试 4 超出内存限制”错误，因此情况可能更糟)。
为什么会这样？
很难预测哪些优化是自动的，哪些不是!
编辑:按照建议，粘贴 Submission 1下面的代码。在这个交互式问题中，“服务器”有一个大小为 n 的隐藏树。 .我们的代码的工作是找出那棵树，使用最少量的 ? k 形式的查询。 .粗略地说，服务器对 ? k 的响应是节点 k 对应的行在树的邻接距离矩阵中。我们的选择k是:最初 1 ，然后从 getAnchors 获得一堆节点.

{-# LANGUAGE Safe #-}
{-# OPTIONS_GHC -O2 #-}

import Data.Maybe
import qualified Data.ByteString.Lazy.Char8 as B8
import qualified Data.ByteString.Builder as Bu
import Data.Functor.Identity
import Control.Monad.Trans.State
import Control.Monad
import Control.Applicative
import Data.ByteString.Builder.Extra (flush) 
import System.IO

type St = StateT [B8.ByteString] Identity

solve :: St Bu.Builder
solve = do
  n <- getIntegral
  ds <- getIntegrals n  -- get the first row of adjacency matrix
  let
    anchors = getAnchors ds
    readFirst = if head anchors==1 then return ds else getIntegrals n
    readRest = replicateM (length anchors - 1) (getIntegrals n) -- get some other rows too
  adjss <- liftA2 (:) readFirst readRest  
  let
    adj1ss = [map snd $ filter ((1==).fst) (zip adjs [1..]) | adjs <- adjss]
    s0 = Bu.string7
    snl = Bu.string7 "\n" <> flush
    i0 = Bu.intDec
    printEdge src dst = i0 src <> s0 " " <> i0 dst <> snl
    printAdj (src,dsts) = mconcat [printEdge src dst | dst<-dsts]
    printAdjs = mconcat $ printAdj <$> zip anchors adj1ss
    ask k = s0 "? " <> i0 k <> snl
    askRest = mconcat $ ask <$> (dropWhile (==1) anchors)
  return $ ask 1 <> askRest <> s0 "!" <> snl <> printAdjs

getAnchors :: [Int]->[Int]
getAnchors xs = reverse $ go (zip xs [1..]) [] [] where
  go [] odds evens = if length odds < length evens then odds else evens
  go ((k,i):rest) odds evens
    | even k = go rest odds (i: evens)
    | odd k = go rest (i: odds) evens
 
getByteString :: St B8.ByteString
getByteString = state getNext where
  getNext [] =  (B8.take 0 (B8.pack "."),[])
  getNext (w:ws) =  (w,ws)
 
getIntegral :: Num t => St t
getIntegral  = convertToNum <$> getByteString where
  convertToNum x =  fromIntegral $ fromMaybe 0 $ liftA fst $ B8.readInteger x
 
getIntegrals :: Num t => Int -> St [t]
getIntegrals n = replicateM n getIntegral

main :: IO ()
main = do
  hSetBuffering stdout NoBuffering
  bytestrings <- B8.words <$> B8.getContents
  B8.putStr $ Bu.toLazyByteString $ evalState solve bytestrings

Answer 1

这里的问题与内联有关。我不完全理解它，但这是我理解的。
内联
首先我们发现复制粘贴definition of replicateM 进入提交 1 会产生与提交 2 (submission) 相同的糟糕性能。但是，如果我们替换 INLINABLE replicateM 的编译指示与 NOINLINE pragma 事情再次起作用( submission )。INLINABLE编译指示 replicateM不同于 INLINE pragma，后者导致比前者更多的内联。具体来说，如果我们定义 replicateM在同一个文件中，用于内联的 Haskells 启发式决定内联，但使用 replicateM在这种情况下，即使存在 INLINABLE，它也从基础决定反对内联。语用。sequenceA和 traverse另一方面，两者都有 INLINE导致内联的编译指示。从上述实验中得到提示，我们可以定义一个不可内联的 sequenceA并且这确实使解决方案 2 起作用( submission )。

{-# NOINLINE sequenceA' #-}
sequenceA' :: [St x] -> St [x]
sequenceA' = sequenceA

出了什么问题？
以下是我的一些相当严重的猜测。
但是内联是如何引起问题的呢？好吧，让我们看看以下两个核心转储之间的区别
内联:

没有内联:

在这里，我们两次都在查看对应的内容，第一个实例是内联部分，第二个实例是对 replicateM 的实际调用。

readRest = replicateM (length anchors - 1) (getIntegrals n)

现在有趣的是，在内联代码中，黄色突出显示的行在 replicateM 的每个循环中运行。 ，而在非内联部分，它们只计算一次，在传递给 replicateM 的 lambda 抽象之外。 .
但他们在做什么？有多个变量称为 ds在核心，但这个是指这个:

这又对应于

solve = do
  n <- getIntegral

所以我认为正在发生的是，而不是运行 getIntegral一次并保存结果，它的起始状态被保存，并且在循环的每一次通过时都以该状态重新运行。确实将此行更改为以下内容(需要 BangPatterns 语言扩展)修复了所有版本( submission )。

solve = do
  !n <- getIntegral

我仍然不确定，但这是我最好的猜测。
以下是两个核心转储供引用: Inline ,
Noinline
这太疯狂了
是的，但是我觉得这里的根本问题是您使用惰性 IO 和惰性状态。使用严格的状态转换器 Haskell 可能会想办法不保留旧状态(我不知道，只是猜测)，但是我们不能在这里使用严格的状态，因为您依赖惰性 IO，即获取所有输入一开始使用 getContents并懒惰地强制它，同时确保在强制太多之前提供输出。相反，明确地逐行读取输入会更安全。 IE。替换 StateT [ByteString]与 IO或者更花哨的东西，比如 Conduit或 Pipe .