title: creating a large Set - need to reduce time spent in GC
body: <p>This program creates a very large set to find a hash function collision. Is there a way to reduce the amount of time spent in GC? +RTS -s is reporting 40+% time spent in GC.</p>
  
  <p>Example usage:</p>
  
  <pre><code>./program 0 1000000 +RTS -s
  ./program 145168473 10200000 +RTS -s
  </code></pre>
  
  <p>Is there a better algorithm or data structure I can use?</p>
  
  <pre><code>{-# LANGUAGE OverloadedStrings #-}
  
  import System.Environment
  import Control.Monad
  import Crypto.Hash.SHA256
  
  import qualified Data.ByteString.Char8 as B
  import qualified Data.ByteString.Lazy.Char8 as BL
  import Data.Char
  import Data.Int
  import Data.Bits
  import Data.Binary
  import Data.Set as Set
  import Data.List
  import Numeric
  
  str2int :: (Integral a) =&gt; B.ByteString -&gt; a
  str2int bs = B.foldl (\a w -&gt; (a * 256)+(fromIntegral $ ord w)) 0 bs
  
  t50 :: Int64 -&gt; Int64
  t50 i = let h = hash $ B.concat $ BL.toChunks $ encode i
          in
            (str2int $ B.drop 25 h) .&amp;. 0x3ffffffffffff
  
  sha256 :: Int64 -&gt; B.ByteString
  sha256 i = hash $ B.concat $ BL.toChunks $ encode i
  
  -- firstCollision :: Ord b =&gt; (a -&gt; b) -&gt; [a] -&gt; Maybe a
  firstCollision f xs = go f Set.empty xs
    where
      -- go :: Ord b =&gt; (a -&gt; b) -&gt; Set b -&gt; [a] -&gt; Maybe a
      go _ _ []     = Nothing
      go f s (x:xs) = let y = f x
                      in
                        if y `Set.member` s
                          then Just x
                          else go f (Set.insert y s) xs
  
  showHex2 i
    | i &lt; 16    = "0" ++ (showHex i "")
    | otherwise = showHex i ""
  
  prettyPrint :: B.ByteString -&gt; String
  prettyPrint = concat . (Data.List.map showHex2) . (Data.List.map ord) . B.unpack
  
  
  showhash inp =
    let  h = sha256 inp
         x = B.concat $ BL.toChunks $ encode inp
     in do putStrLn $ "  - input: " ++ (prettyPrint x) ++ " -- " ++ (show inp)
           putStrLn $ "  -  hash: " ++ (prettyPrint h)
  
  main = do
           args &lt;- getArgs
           let a = (read $ args !! 0) :: Int64
               b = (read $ args !! 1) :: Int64
               c = firstCollision t [a..(a+b)]
               t = t50
           case c of
             Nothing -&gt; putStrLn "No collision found"
             Just x  -&gt; do let h = t x
                           putStrLn $ "Found collision at " ++ (show x)
                           showhash x
                           let first = find (\x -&gt; (t x) == h) [a..(a+b)]
                            in case first of
                                 Nothing -&gt; putStrLn "oops -- failed to find hash"
                                 Just x0 -&gt; do putStrLn $ "first instance at " ++ (show x0)
                                               showhash x0
  </code></pre>