Ticket #27 (new defect)

Opened 5 years ago

Space leak in to2sComplement

Reported by: dom Owned by: somebody
Priority: major Milestone:
Component: component1 Version:
Keywords: Cc:

Description

The space leak is actually in to2scomplement. The culprit is reverse - obvious once you think about it. 2(106) used to almost destroy my machine and anything bigger actually did grind it to a complete standstill.

to2sComplement :: Num a => Integer -> [a] to2sComplement n | n >= 0 = 0:(k 7 n) | otherwise = k 8 (fromInteger $ 2p + n) where p = length (k 7 (-n-1)) + 1 infixr 5 $$ ($$) = (.).(.) k :: Num a => Integer -> Integer -> [a] k = reverse $$ (map fromInteger) $$ flip (curry (unfoldr nnbIterator)) nnbIterator :: (Integer, Integer) -> Maybe (Integer, (Integer, Integer)) nnbIterator (0,0) = Nothing nnbIterator (0,p) = Just (0,(0,p-1)) nnbIterator (n,0) = Just (n rem 2,(n quot 2,7)) nnbIterator (n,p) = Just (n rem 2,(n quot 2,p-1))

OTOH this seems to run in log space (which you might expect) consuming about 200k for 2(106) (a 300k digit number) which doesn't seem unreasonable.

This puts more emphasis on changing to use the BitPut? monad. I think it should be straightforward to make the change now everything is monadic. I'll have a look at what's involved but first I want to get the inter-operability testing framework working.

h' :: Integer -> Integer -> BitPut? h' p 0 = do putNBits (fromIntegral p) (0::Word8) h' 0 n = do putNBits 1 (n mod 2) h' 7 (n div 2) h' p n = do putNBits 1 (n mod 2) h' (p-1) (n div 2) to2sComplementReverse :: Integer -> BitPut? to2sComplementReverse n | n >= 0 = do h' 7 n putNBits 1 (0::Word8) | otherwise = h' 8 (2(l n) + n) l n = genericLength ((flip (curry (unfoldr nnbIterator)) 7) (-n-1)) + 1 to2sComplementUsingReverse :: Integer -> BL.ByteString? to2sComplementUsingReverse n = BL.reverse (BL.map reverseBits (runBitPut (to2sComplementReverse n)))

reverseBits :: Word8 -> Word8 reverseBits = reverseBits3 . reverseBits2 . reverseBits1 reverseBits1 :: Word8 -> Word8 reverseBits1 x = shiftR x 4 .|. shiftL x 4 reverseBits2 :: Word8 -> Word8 reverseBits2 x = shiftR (x .&. 0xcc) 2 .|. shiftL (x .&. 0x33) 2 reverseBits3 :: Word8 -> Word8 reverseBits3 x = shiftR (x .&. 0xaa) 1 .|. shiftL (x .&. 0x55) 1

Note: See TracTickets for help on using tickets.