时间戳

首页 > 解决方案 > 为什么 HashMap 在一系列插入时不是正常形式？

haskell - 为什么 HashMap 在一系列插入时不是正常形式？

问题描述

我一直在尝试使用 ghc-heap-view 包和它提供的实用程序来确保 Haskell 程序的内存模型的严格性，当我注意到我HashMap的 s 在一系列插入时似乎不在 NF 中. 我尝试打印堆树，确实显示了一些 thunk。然后我尝试了另一种插入元素的方法（使用unionand singleton），这次它很严格。

有人可以解释为什么会这样，并建议我是否可以做任何事情来使insert行为与其他方法相同？

这是我的测试代码：

module Main where

import           Control.Exception           (evaluate)
import           Data.Foldable
import           Data.HashMap.Strict         (HashMap)
import qualified Data.HashMap.Strict         as HM
import           GHC.HeapView

test1 :: HashMap Int Int
test1 = foldl' (\m v -> HM.insert v v m) HM.empty [0..5]

test2 :: HashMap Int Int
test2 = foldl' (\m v -> HM.union (HM.singleton v v) m) HM.empty [0..5]

main :: IO ()
main = do
  putStrLn "HeapTree for test1"
  t1 <- evaluate test1
  buildHeapTree 10 (asBox t1) >>= print . ppHeapTree

  putStrLn "HeapTree for test2"
  t2 <- evaluate test2
  buildHeapTree 10 (asBox t2) >>= print . ppHeapTree

这是输出：

HeapTree for test1
"BitmapIndexed ([ (_thunk (I# 0) (I# 0) 0), (_thunk (I# 1) (I# 1) 1), (Leaf (I# 2) (I# 2) 2), (Leaf (I# 3) (I# 3) 3), (Leaf (I# 4) (I# 4) 4), (Leaf (I# 5) (I# 5) 5) ]) 63"
HeapTree for test2
"BitmapIndexed ([ (Leaf (I# 0) (I# 0) 0), (Leaf (I# 1) (I# 1) 1), (Leaf (I# 2) (I# 2) 2), (Leaf (I# 3) (I# 3) 3), (Leaf (I# 4) (I# 4) 4), (Leaf (I# 5) (I# 5) 5) ]) 63"
(0.02 secs, 1,067,672 bytes)

标签： haskellstrictnessunordered-containers

解决方案

将新的非冲突键插入Leaf节点时，insert使用调用的辅助函数two来生成二元素映射。该two函数在键值方面是惰性的，这导致 GHC 创建 thunk 以创建两个新Leaf节点。这整件事非常愚蠢，因为到那时密钥实际上肯定会在 WHNF 中。但是（大概是因为递归go函数）GHC 没有意识到这一点。这个问题应该会在下一个版本中修复unordered-containers。

推荐阅读