为什么 replicateM (length xs) m 比 sequenceA (fmap (const m) xs) 更有效？
Why is replicateM (length xs) m way more efficient than sequenceA (fmap (const m) xs)?
我对一个编程问题的两次提交仅在一个表达式上有所不同（其中 anchors 是一个非空列表，(getIntegrals n) 是一个状态 monad）：
Submission 1。 replicateM (length anchors - 1) (getIntegrals n)
Submission 2。 sequenceA $ const (getIntegrals n) <$> tail anchors
我想这两个表达式的等价性在编译时本身应该很容易看出。然而，comparatively sequenceA 速度较慢，更重要的是，占用 >10 倍的内存：
Code
Time
Memory
replicateM one
732 ms
22200 KB
sequenceA one
1435 ms
262100 KB
（第二个条目出现“测试 4 超出内存限制”错误，因此情况可能更糟）。
为什么会这样？
很难预测哪些优化是自动的，哪些不是！
编辑：按照建议，粘贴下面的 Submission 1 代码。在这个交互式问题中，'server' 有一棵大小为 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
这里的问题与内联有关。没完全看懂，但是我的理解是这样的。
内联
首先我们发现复制粘贴definition of replicateM into the Submission 1 yields the same bad performance as Submission 2 (submission). However if we replace the INLINABLE pragma of replicateM with a NOINLINE pragma things work again (submission).
replicateM 上的 INLINABLE 编译指示不同于 INLINE 编译指示，后者导致比前者更多的内联。特别是在这里，如果我们在同一个文件中定义 replicateM，Haskell 的内联启发式决定内联，但是从基础 replicateM 开始，它决定在这种情况下不内联，即使存在 INLINABLE pragma.
另一方面，sequenceA 和 traverse 都具有导致内联的 INLINE 编译指示。从上面的实验中得到提示，我们可以定义一个不可内联的 sequenceA，这确实使解决方案 2 起作用 (submission)。
{-# NOINLINE sequenceA' #-}
sequenceA' :: [St x] -> St [x]
sequenceA' = sequenceA
出了什么问题？
以下是我的一些相当严重的推测。
但是内联是如何导致问题的呢？好吧，让我们看看以下两个核心转储之间的区别
有内联：
没有内联:
这里我们两次查看对应的内容，第一个实例是内联部分，第二个实例是对 replicateM 的实际调用。
readRest = replicateM (length anchors - 1) (getIntegrals n)
现在有趣的一点是，在内联代码中，黄色突出显示的行在 replicateM 的每个循环中都是 运行，而在非内联部分中，它们在 lambda 之外计算一次传递给 replicateM.
的抽象
但是他们在做什么？核心里面有多个变量叫ds，但是这个是指这个：
又对应
solve = do
n <- getIntegral
所以我认为正在发生的事情是，不是 运行ning getIntegral 一次并保存结果，而是保存它的起始状态并且它是 re运行 这个状态循环的每一次通过。事实上，将此行更改为以下内容（需要 BangPatterns 语言扩展）可以修复所有版本 (submission)。
solve = do
!n <- getIntegral
我还是不太确定，但这是我最好的猜测。
这太疯狂了
嗯，是的，但我觉得这里的根本问题是你使用了惰性 IO 和惰性状态。使用严格的状态转换器 Haskell 可能会发现不保留旧状态（我不知道，只是猜测），但是我们不能在这里使用严格的状态，因为你依赖惰性 IO，即在开始时使用 getContents 获取所有输入并懒惰地强制输入，同时确保在强制过多之前提供输出。相反，逐行显式读取输入会安全得多。 IE。将 StateT [ByteString] 替换为 IO 或更花哨的东西，例如 Conduit 或 Pipe.
我对一个编程问题的两次提交仅在一个表达式上有所不同（其中 anchors 是一个非空列表，(getIntegrals n) 是一个状态 monad）：
Submission 1。 replicateM (length anchors - 1) (getIntegrals n)
Submission 2。 sequenceA $ const (getIntegrals n) <$> tail anchors
我想这两个表达式的等价性在编译时本身应该很容易看出。然而，comparatively sequenceA 速度较慢，更重要的是，占用 >10 倍的内存：
| Code | Time | Memory |
|---|---|---|
| replicateM one | 732 ms | 22200 KB |
| sequenceA one | 1435 ms | 262100 KB |
（第二个条目出现“测试 4 超出内存限制”错误，因此情况可能更糟）。
为什么会这样？
很难预测哪些优化是自动的，哪些不是！
编辑：按照建议，粘贴下面的 Submission 1 代码。在这个交互式问题中，'server' 有一棵大小为 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
这里的问题与内联有关。没完全看懂，但是我的理解是这样的。
内联
首先我们发现复制粘贴definition of replicateM into the Submission 1 yields the same bad performance as Submission 2 (submission). However if we replace the INLINABLE pragma of replicateM with a NOINLINE pragma things work again (submission).
replicateM 上的 INLINABLE 编译指示不同于 INLINE 编译指示，后者导致比前者更多的内联。特别是在这里，如果我们在同一个文件中定义 replicateM，Haskell 的内联启发式决定内联，但是从基础 replicateM 开始，它决定在这种情况下不内联，即使存在 INLINABLE pragma.
sequenceA 和 traverse 都具有导致内联的 INLINE 编译指示。从上面的实验中得到提示，我们可以定义一个不可内联的 sequenceA，这确实使解决方案 2 起作用 (submission)。
{-# NOINLINE sequenceA' #-}
sequenceA' :: [St x] -> St [x]
sequenceA' = sequenceA
出了什么问题？
以下是我的一些相当严重的推测。
但是内联是如何导致问题的呢？好吧，让我们看看以下两个核心转储之间的区别
有内联：
没有内联:
这里我们两次查看对应的内容，第一个实例是内联部分，第二个实例是对 replicateM 的实际调用。
readRest = replicateM (length anchors - 1) (getIntegrals n)
现在有趣的一点是，在内联代码中，黄色突出显示的行在 replicateM 的每个循环中都是 运行，而在非内联部分中，它们在 lambda 之外计算一次传递给 replicateM.
但是他们在做什么？核心里面有多个变量叫ds，但是这个是指这个：
又对应
solve = do
n <- getIntegral
所以我认为正在发生的事情是，不是 运行ning getIntegral 一次并保存结果，而是保存它的起始状态并且它是 re运行 这个状态循环的每一次通过。事实上，将此行更改为以下内容（需要 BangPatterns 语言扩展）可以修复所有版本 (submission)。
solve = do
!n <- getIntegral
我还是不太确定，但这是我最好的猜测。
这太疯狂了
嗯，是的，但我觉得这里的根本问题是你使用了惰性 IO 和惰性状态。使用严格的状态转换器 Haskell 可能会发现不保留旧状态（我不知道，只是猜测），但是我们不能在这里使用严格的状态，因为你依赖惰性 IO，即在开始时使用 getContents 获取所有输入并懒惰地强制输入，同时确保在强制过多之前提供输出。相反，逐行显式读取输入会安全得多。 IE。将 StateT [ByteString] 替换为 IO 或更花哨的东西，例如 Conduit 或 Pipe.