Make Read instances for Integral types faster, and make them fail fast

At present, the Read instances for standard types are generally written as though Read were a typical parser for a programming language. However, it most assuredly is not. Specifically, we currently follow the pattern of lexing and then parsing. The first problem with that is that while we follow that model, we don't actually get the big benefit of that model; the class methods don't mention or respect token boundaries, so lexing first doesn't prevent backtracking. More to the point, perhaps, lexing looks at the string and attempts to identify the next token, whatever it may be. But for Read, we don't need that. Thanks to the types, we have a very clear sense of what characters we expect to encounter.

I've started to sketch out an improvement, which reads Int and Word around seven times as fast (9.5 times as fast with parentheses and negation), and will fail immediately on something like read (fix ('a':)) :: Int rather than going into an infinite loop.

To begin with, modify the definition of paren thus:

expectP' :: Char -> ReadPrec ()
expectP' c = lift (expect' c)
{-# INLINE expectP' #-}

expect' :: Char -> ReadP ()
expect' c = do
  ReadP.skipSpaces
  thing <- ReadP.get
  if thing == c
    then pure ()
    else ReadP.pfail
{-# INLINE expect' #-}


paren :: ReadPrec a -> ReadPrec a
-- ^ @(paren p)@ parses \"(P0)\"
--      where @p@ parses \"P0\" in precedence context zero
paren p = do expectP' '('
             x <- reset p
             expectP' ')'
             return x

This allows fast failure when looking for parentheses, so we don't have to scan to the end of the first token (whatever it may be) before concluding that it is not '('.

Now we can parse Word and Int very efficiently. I had to specialize earlier than I wanted to convince GHC that I don't want to convert through Integer. I'm not sure why the fromIntegral rule doesn't fire reliably around here. The code below (temporarily) uses the current definition for base 16, because that's a bit fussy; I'll rewrite it soon.

charDiff :: Char -> Char -> Word
charDiff c1 c2 = fromIntegral (ord c1 - ord c2)
{-# INLINE charDiff #-}

readHexOct :: ReadP Word
readHexOct = do
  _ <- ReadP.char '0'
  baseId <- lexBaseChar
  case baseId of
    Oct -> readBaseP 8
    Hex -> L.readHexP
{-# INLINE readHexOct #-}

data BaseId = Oct | Hex

lexBaseChar :: ReadP BaseId
lexBaseChar = do { c <- ReadP.get;
                   case c of
                     'o' -> pure Oct
                     'O' -> pure Oct
                     'x' -> pure Hex
                     'X' -> pure Hex
                     _ -> ReadP.pfail }

readWord :: ReadP Word
readWord = readNumber (readHexOct ReadP.<++ readBaseP 10)

readInt :: ReadP Int
readInt = fromIntegral <$> readWord

readBaseP :: Integral a => Word -> ReadP a
readBaseP !base = do
  c <- ReadP.get
  let diff = charDiff c '0'
  if diff < base
    then readBaseP' base (fromIntegral diff)
    else ReadP.pfail
{-# INLINE readBaseP #-}

readBaseP' :: Integral a => Word -> a -> ReadP a
readBaseP' !base !acc0 = ReadP.look >>= go acc0
  where
    go !acc (c:cs) | diff < base = ReadP.get *> go (fromIntegral base * acc + fromIntegral diff) cs
      where diff = charDiff c '0'
    go !acc _ = pure acc
{-# INLINE readBaseP' #-}

readNumber :: Num a => ReadP.ReadP a -> ReadPrec a
readNumber p = parens $ do
  cs <- lift skipSpaces *> look
  case cs of
    ('-': _) -> get *> lift (skipSpaces *> (negate <$> p))
    _ -> lift $ skipSpaces *> p
{-# INLINE readNumber #-}

Other Word and Int-like types can be built on top of that foundation. I haven't yet attempted to deal with other instances, but I think there are probably a lot of opportunities for similar improvements.

WARNING: I know very little about parsing, and less about ReadPrec. It's conceivable that I've made some semantic errors here, although I don't think I have.