[GHC] #12665: Make Read instances faster, and make them fail fast

[GHC]

#12665: Make Read instances faster, and make them fail fast
-------------------------------------+-------------------------------------
        Reporter:  dfeuer            |                Owner:  dfeuer
            Type:  feature request   |               Status:  new
        Priority:  high              |            Milestone:  8.2.1
       Component:  Core Libraries    |              Version:  8.0.1
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Runtime           |  Unknown/Multiple
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by int-e):

 The following is a lazier variant of `valInteger` that does a chunking
 pass on `Int`s. (Resulting from discussion on #haskell)
 {{{
 -- Digits' represents a stream of digits where the last digit carries its
 own
 -- base. For example, in base 100, we could represent 12345 as either one
 of
 --   DCons 12 (DCons 34 (DNil 5 10))  or
 --   DCons 1 (DCons 23 (DCons 45 (DNil 0 1)))
 data Digits' = DCons !Integer Digits' | DNil !Integer Integer

 valInteger :: Int -> [Int] -> Integer
 valInteger _ [] = 0
 valInteger b ds = go b1 (chunks 0 0 ds) where
     -- chunking pass: collect digits in base b^chunkSize
     chunkSize :: Int
     chunkSize = 7 -- b^chunkSize must fit into an Int
     b1 :: Integer
     b1 = fromIntegral (b^chunkSize)
     chunks :: Int -> Int -> [Int] -> Digits'
     chunks l d ds | l == chunkSize = DCons (fromIntegral d) (chunks 0 0
 ds)
     chunks l d [] = DNil (fromIntegral d) (fromIntegral (b^l))
     chunks l d (d' : ds) = chunks (l+1) (d*b + d') ds
     -- bottom-up combination pass, squaring the base in each pass
     go :: Integer -> Digits' -> Integer
     go _ (DNil d _) = d
     go _ (DCons d' (DNil d b)) = d'*b + d
     go b (DCons d' ds) = go (b*b) (combine b d' ds)
     combine :: Integer -> Integer -> Digits' -> Digits'
     combine b d (DNil d' b') = DNil (d*b' + d') (b * b')
     combine b d (DCons d' (ds at DNil{})) = DCons (d*b + d') ds
     combine b d (DCons d' (DCons d'' ds)) = DCons (d*b + d') (combine b
 d'' ds)
 }}}

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/12665#comment:7>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler