Почему HashMap не находится в нормальной форме после ряда вставок - PullRequest
Новая
       65

Почему HashMap не находится в нормальной форме после ряда вставок

5 голосов
/ 05 мая 2019

Я пытался убедиться в строгости модели в памяти программы на Haskell, используя пакет ghc-heap-view и утилиты, которые он предоставляет, когда заметил, что мои HashMap не отображаются вН.Ф. по серии на вставках.Я попытался распечатать дерево кучи, и действительно, он показывает некоторые гирлянды.Затем я попробовал другой способ вставки элементов (используя union и 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)

1 Ответ

3 голосов
/ 06 мая 2019

При вставке нового, не конфликтующего ключа в узел Leaf, insert использует вспомогательную функцию с именем two для создания двухэлементной карты. Функция two ленива в значениях ключей, что приводит к тому, что GHC создает блоки для создания двух новых узлов Leaf. Все это довольно глупо, потому что ключи уже наверняка будут в WHNF. Но (предположительно из-за рекурсивной функции go) GHC не осознает этого. Проблема должна быть исправлена ​​в следующей версии unordered-containers.

...