3
이 프로그램은 해시 함수 충돌을 찾기 위해 매우 큰 세트를 만듭니다. GC에서 소비되는 시간을 줄이는 방법이 있습니까? + RTS -s는 GC에서 소비 된 40 % + 시간을보고합니다.큰 세트 만들기 - GC에서 소비하는 시간을 줄여야합니다.
사용 예제 :
./program 0 1000000 +RTS -s
./program 145168473 10200000 +RTS -s
내가 사용할 수있는 더 나은 알고리즘 또는 데이터 구조가 있습니까?
{-# 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) => B.ByteString -> a
str2int bs = B.foldl (\a w -> (a * 256)+(fromIntegral $ ord w)) 0 bs
t50 :: Int64 -> Int64
t50 i = let h = hash $ B.concat $ BL.toChunks $ encode i
in
(str2int $ B.drop 25 h) .&. 0x3ffffffffffff
sha256 :: Int64 -> B.ByteString
sha256 i = hash $ B.concat $ BL.toChunks $ encode i
-- firstCollision :: Ord b => (a -> b) -> [a] -> Maybe a
firstCollision f xs = go f Set.empty xs
where
-- go :: Ord b => (a -> b) -> Set b -> [a] -> 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 < 16 = "0" ++ (showHex i "")
| otherwise = showHex i ""
prettyPrint :: B.ByteString -> 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 <- getArgs
let a = (read $ args !! 0) :: Int64
b = (read $ args !! 1) :: Int64
c = firstCollision t [a..(a+b)]
t = t50
case c of
Nothing -> putStrLn "No collision found"
Just x -> do let h = t x
putStrLn $ "Found collision at " ++ (show x)
showhash x
let first = find (\x -> (t x) == h) [a..(a+b)]
in case first of
Nothing -> putStrLn "oops -- failed to find hash"
Just x0 -> do putStrLn $ "first instance at " ++ (show x0)
showhash x0
힙 프로파일 링을 사용하여 진행 상황을 파악합니다. – augustss
예를 들어 할당 영역을 늘리려고 했습니까? 100MB의'-RTS -A100M'은? 이는 GC 실행 빈도를 줄이면 도움이되는 경우가 있습니다. 이런 식으로, 대부분의 생성 된 데이터가 잠시 보관되는 곳에서는 큰 차이를 만들 수 있습니다. –
's'는'firstCollision'의 작업자에서 엄격해야합니다. – luqui