Skip to content

Instantly share code, notes, and snippets.

@frasertweedale
Last active October 15, 2021 00:37
Show Gist options
  • Save frasertweedale/7e6c6f70fb255c5f56ac5318c08d6a52 to your computer and use it in GitHub Desktop.
Save frasertweedale/7e6c6f70fb255c5f56ac5318c08d6a52 to your computer and use it in GitHub Desktop.
Why does this program consume 8.6G memory?
module Main where
import Control.Monad (replicateM)
import Data.Char (ord)
import Data.Foldable (for_)
import Data.List (foldl')
import Data.Word (Word)
import System.Environment (getArgs)
hash :: [Char] -> Word
hash = foldl' step 0
where
step acc c = acc * 31 + fromIntegral (ord c)
compress :: Word -> Word -> Word
compress modulus = (`mod` modulus) . (* 11)
chars :: [Char]
chars = ['a'..'z'] <> ['0'..'9']
strings :: [[Char]]
strings = replicateM 6 chars
main :: IO ()
main = do
(modulusArg : _) <- getArgs
let
modulus = read modulusArg
cond = (== 42)
collisions = filter (cond . compress modulus . hash) strings
for_ collisions putStrLn
@frasertweedale
Copy link
Author

replicateM 6 chars is the culprit. The cause is something like: builds the (very large) sublists and holds on to them due to sharing while it performsliftA2 (:) c sublists

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment