0
import qualified Data.ByteString as B
import qualified Data.ByteString.Lazy as BL

compress2 ::
  UArray (Word8,Word8) Word8 ->
  UArray Int Word8 ->
  UArray Int Word8 ->
  Int ->
  UArray Int Word8
compress2 sbox buf0 buf1 sboxalt = compress sbox buf sboxalt where
  (beg0,end0) = bounds buf0
  (beg1,end1) = bounds buf1
  len = end0 + end1 + 2 - beg0 - beg1
  buf = listArray (0,len-1) (elems buf0 ++ elems buf1)

compress3 ::
  UArray (Word8,Word8) Word8 ->
  UArray Int Word8 ->
  UArray Int Word8 ->
  UArray Int Word8 ->
  Int ->
  UArray Int Word8
compress3 sbox buf0 buf1 buf2 sboxalt = compress sbox buf sboxalt where
  (beg0,end0) = bounds buf0
  (beg1,end1) = bounds buf1
  (beg2,end2) = bounds buf2
  len = end0 + end1 + end2 + 3 - beg0 - beg1 - beg2
  buf = listArray (0,len-1) (elems buf0 ++ elems buf1 ++ elems buf2)

data Twistree = Twistree
  { sbox    :: UArray (Word8,Word8) Word8
  } deriving Show

compressPairs :: UArray (Word8,Word8) Word8 -> [UArray Int Word8] -> [UArray Int Word8]
compressPairs _ [] = []
compressPairs _ [x] = [x]
compressPairs sbox (x:y:xs) = ((compress2 sbox x y 0) : compressPairs sbox xs)

hashPairs :: UArray (Word8,Word8) Word8 -> [UArray Int Word8] -> UArray Int Word8
hashPairs _ [] = undefined -- can't happen, there's always at least exp(4)
hashPairs _ [x] = x
hashPairs sbox x = hashPairs sbox (compressPairs sbox x)

compressTriples :: UArray (Word8,Word8) Word8 -> [UArray Int Word8] -> [UArray Int Word8]
compressTriples _ [] = []
compressTriples _ [x] = [x]
compressTriples sbox [x,y] = [compress2 sbox x y 1]
compressTriples sbox (x:y:z:xs) = ((compress3 sbox x y z 1) : compressTriples sbox xs)

hashTriples :: UArray (Word8,Word8) Word8 -> [UArray Int Word8] -> UArray Int Word8
hashTriples _ [] = undefined -- can't happen, there's always at least exp(4)
hashTriples _ [x] = x
hashTriples sbox x = hashTriples sbox (compressTriples sbox x)

linearTwistree = Twistree linearSbox

-- | Creates a Twistree with the given key.
-- To convert a String to a ByteString, put "- utf8-string" in your
-- package.yaml dependencies, import Data.ByteString.UTF8, and use
-- fromString.
keyedTwistree :: B.ByteString -> Twistree
keyedTwistree key = Twistree sbox where
  sbox = sboxes key

hash :: Twistree -> BL.ByteString -> UArray Int Word8
hash twistree stream = par h2 $ par h3 $ compress2 (sbox twistree) h2 h3 2 where
  blocks = blockize stream
  h2 = hashPairs (sbox twistree) (exp4_2adic : blocks)
  h3 = hashTriples (sbox twistree) (exp4_base2 : blocks)

This code takes a lazy ByteString, which in this program is read from a file but could come from elsewhere, and hashes it. The hash function computes h2 and h3 in parallel, because they both consume the ByteString, then calls compress2 once they're both finished.

I'd like to make this more parallel. The compress2 and compress3 operations take 289 and 763 µs, respectively, on my box, and the program spends 42.5% and 56.0% of the time in them and only 1.4% blockizing the input. Can you suggest ways to do this?

The code repo is at https://github.com/phma/wring-twistree .

2
  • 2
    This question sounds more suitable to codereview.stackexchange.com because it is so open ended.
    – Noughtmare
    Sep 18 at 8:02
  • Or you could alternatively make the question more specific by thinking of a specific approach and trying to apply it yourself first and then asking a question at the point you get stuck.
    – Noughtmare
    Sep 18 at 8:10

1 Answer 1

0

I don't know the data structure so it is hard to guess what to parallelize just looking at the code. In any case, it looks like you can simplify your implementation like this:

hashHelper _ _ _ [x] = x
hashHelper n c sbox xs = hashHelper n c sbox (compress' <$> chunksOf c xs)
  where
    compress' [x] = x
    compress' [x, y] = compress2 sbox x y n
    compress' [x, y, z] = compress3 sbox x y z n

hashTriples' = hashHelper 1 3

hashPairs' = hashHelper 0 2

You can then try

parMap rpar compress' $ chunksOf c xs

If the parallelization is too fine grained you can use parListChunk function. Hope it helps.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.