Replace `binary-parsers` dependency with `attoparsec`?

[RyanGlScott]

Currently, aig cannot be built with GHC 9.2 because of its dependency on binary-parsers, as binary-parsers imposes an upper bounds of bytestring < 0.11. I've submitted a PR upstream at winterland1989/binary-parsers#6, but it hasn't been merged for over a month. Moreover, it's unclear if binary-parsers is still maintained, as there have not been any new commits to the repo for about three years.

Perhaps we should just replace the binary-parsers dependency with attoparsec, which provides similar parsing functionality. I think the following should work:

Details

diff --git a/aig.cabal b/aig.cabal
diff --git a/aig.cabal b/aig.cabal
index 22e9202..3c49362 100644
--- a/aig.cabal
+++ b/aig.cabal
@@ -36,10 +36,9 @@ library
   default-Language: Haskell2010
   ghc-options:      -Wall -fno-ignore-asserts
   build-depends:
+    attoparsec,
     base >= 4.9 && < 4.17,
     bimap,
-    binary,
-    binary-parsers,
     bytestring,
     containers >= 0.5.5,
     mtl,
diff --git a/src/Data/AIG/CompactGraph.hs b/src/Data/AIG/CompactGraph.hs
index 3282f85..cb3063d 100644
--- a/src/Data/AIG/CompactGraph.hs
+++ b/src/Data/AIG/CompactGraph.hs
@@ -24,8 +24,9 @@ module Data.AIG.CompactGraph
   ) where
 
 import Control.Monad (forM_, replicateM)
-import Data.Binary.Get
-import qualified Data.Binary.Parser as BP
+import Data.Attoparsec.ByteString (Parser)
+import qualified Data.Attoparsec.ByteString.Char8 as AttoC8
+import qualified Data.Attoparsec.ByteString.Lazy as AttoL
 import Data.Bits (shiftL, shiftR, (.&.), (.|.), xor, testBit)
 import Data.IORef (IORef, newIORef, modifyIORef', readIORef, writeIORef)
 import Data.List (elemIndex, intersperse)
@@ -256,44 +257,44 @@ encodeDifference w@(fromIntegral -> b)
 ------------------------------------------------------------------
 -- AIG parsing
 
-spaces :: Get ()
-spaces = BP.skipWhile BP.isHorizontalSpace
+spaces :: Parser ()
+spaces = AttoL.skipWhile AttoC8.isHorizontalSpace
 
-getIntWords :: Get [Int]
-getIntWords = BP.decimal `BP.sepBy` spaces
+getIntWords :: Parser [Int]
+getIntWords = AttoC8.decimal `AttoL.sepBy` spaces
 
-getIntWordsLine :: Get [Int]
-getIntWordsLine = getIntWords <* BP.skipWhile BP.isEndOfLine
+getIntWordsLine :: Parser [Int]
+getIntWordsLine = getIntWords <* AttoL.skipWhile AttoC8.isEndOfLine
 
-getHeader :: Get (Int, Int, Int, Int, Int)
+getHeader :: Parser (Int, Int, Int, Int, Int)
 getHeader =
-  do BP.string (modeString Binary)
+  do _ <- AttoL.string (modeString Binary)
      spaces
      ns <- getIntWordsLine
      case ns of
        [m, i, l, o, a] -> return (m, i, l, o, a)
        _ -> fail $ "Invalid AIG header: " ++ show ns
 
-getOutput :: Get (CompactLit s)
+getOutput :: Parser (CompactLit s)
 getOutput =
   do ns <- getIntWordsLine
      case ns of
        [n] -> return (CompactLit (fromIntegral n))
        _ -> fail $ "Invalid output line: " ++ show ns
 
-getDifference :: Get Word32
+getDifference :: Parser Word32
 getDifference = go 0 0
   where
     addByte x b i = x .|. (((fromIntegral b) .&. 0x7f) `shiftL` (7*i))
     go x i =
-      do b <- getWord8
+      do b <- AttoL.anyWord8
          let x' = addByte x b i
          if b .&. 0x80 /= 0 then go x' (i + 1) else return x'
 
-getDifferences :: Get (Word32, Word32)
+getDifferences :: Parser (Word32, Word32)
 getDifferences = (,) <$> getDifference <*> getDifference
 
-getGraph :: Get (Var, [Var], [CompactLit s], Bimap Var (CompactLit s, CompactLit s))
+getGraph :: Parser (Var, [Var], [CompactLit s], Bimap Var (CompactLit s, CompactLit s))
 getGraph =
   do (maxvar, ninputs, nlatches, nouts, nands) <- getHeader
      outputs <- replicateM (nlatches + nouts) getOutput
@@ -352,7 +353,8 @@ instance IsAIG CompactLit CompactGraph where
   withNewGraph _proxy k = k =<< newCompactGraph
 
   aigerNetwork _proxy fp =
-    do (maxv, inps, outs, gates) <- runGet getGraph <$> LBS.readFile fp
+    do res <- AttoL.parseOnly getGraph <$> LBS.readFile fp
+       (maxv, inps, outs, gates) <- either fail pure res
        maxVar  <- newIORef maxv
        inputs  <- newIORef inps
        andMap  <- newIORef gates

[RyanGlScott]

#11 implements this idea. Before merging #11, however, I'd like to run the AIG parser on a large example to make sure the performance hasn't regressed. @jldodds has provided me such an example, which we might consider adding to the test suite if it's feasible (both timing-wise and copyright-wise).

[RyanGlScott]

I wrote a microbenchmark to time how long it takes to parse .aig files and write them back to disk:

module Main (main) where

import Data.AIG.CompactGraph
import Data.AIG.Interface
import Data.Foldable
import Text.Printf (printf)

main :: IO ()
main = for_ [0..32 :: Int] $ \i -> do
  let suffix = printf "%02d" i
      oldFP = "new" ++ suffix ++ ".aig"
      newFP = "copy_of_" ++ oldFP
  n <- aigerNetwork compactProxy oldFP
  writeAiger newFP n

I tested this on .aig files obtained from the output of a large-ish ABC session. Here are the results on commit c9a7dd9, which uses binary-parsers:

$ time ./Main 

real 0m7.041s
user 0m6.852s
sys 0m0.180s

And here are the results with #11, which uses attoparsec:

$ time ./Main 

real 0m7.272s
user 0m7.095s
sys 0m0.168s

attoparsec is ever-so-slightly slower, but not by much.

[RyanGlScott]

An alternative to using an ordinary Attoparsec parser is using Data.Attoparsec.Zepto, which provides an even more performant parser that is optimized for parsers without much recursion or backtracking. If I switch out binary-parsers for Zepto:

Details

diff --git a/aig.cabal b/aig.cabal
index 17d76e5..e2c76ca 100644
--- a/aig.cabal
+++ b/aig.cabal
@@ -36,10 +36,9 @@ library
   default-Language: Haskell2010
   ghc-options:      -Wall -fno-ignore-asserts
   build-depends:
+    attoparsec,
     base >= 4.9 && < 4.16,
     bimap,
-    binary,
-    binary-parsers,
     bytestring,
     containers >= 0.5.5,
     mtl,
diff --git a/src/Data/AIG/CompactGraph.hs b/src/Data/AIG/CompactGraph.hs
index 3282f85..69691f7 100644
--- a/src/Data/AIG/CompactGraph.hs
+++ b/src/Data/AIG/CompactGraph.hs
@@ -24,8 +24,9 @@ module Data.AIG.CompactGraph
   ) where
 
 import Control.Monad (forM_, replicateM)
-import Data.Binary.Get
-import qualified Data.Binary.Parser as BP
+import qualified Data.Attoparsec.ByteString.Char8 as AttoC8
+import qualified Data.Attoparsec.Combinator as Comb
+import qualified Data.Attoparsec.Zepto as Zepto
 import Data.Bits (shiftL, shiftR, (.&.), (.|.), xor, testBit)
 import Data.IORef (IORef, newIORef, modifyIORef', readIORef, writeIORef)
 import Data.List (elemIndex, intersperse)
@@ -34,9 +35,10 @@ import Data.Map (Map)
 import qualified Data.Bimap as Bimap
 import qualified Data.Map.Strict as Map
 import qualified Data.ByteString as BS
-import qualified Data.ByteString.Lazy as LBS
+import qualified Data.ByteString.Char8 as BSC8
 import qualified Data.ByteString.Builder as BS
-import Data.Word (Word32)
+import qualified Data.ByteString.Unsafe as BSU
+import Data.Word (Word8, Word32)
 import System.IO (Handle, withFile, IOMode(..))
 
 import Data.AIG.Interface hiding (xor)
@@ -256,32 +258,56 @@ encodeDifference w@(fromIntegral -> b)
 ------------------------------------------------------------------
 -- AIG parsing
 
-spaces :: Get ()
-spaces = BP.skipWhile BP.isHorizontalSpace
+type Parser = Zepto.ZeptoT IO
 
-getIntWords :: Get [Int]
-getIntWords = BP.decimal `BP.sepBy` spaces
+skipWhile :: (Word8 -> Bool) -> Parser ()
+skipWhile p = Zepto.takeWhile p *> pure ()
 
-getIntWordsLine :: Get [Int]
-getIntWordsLine = getIntWords <* BP.skipWhile BP.isEndOfLine
+getWord8 :: Parser Word8
+getWord8 = do
+  b <- Zepto.take 1
+  pure (BSU.unsafeHead b)
 
-getHeader :: Get (Int, Int, Int, Int, Int)
+spaces :: Parser ()
+spaces = skipWhile AttoC8.isHorizontalSpace
+
+getIntWords :: Parser [Int]
+getIntWords = decimal `Comb.sepBy` spaces
+
+-- Taken from the @chronos@ library, which is licensed under the 3-Clause
+-- BSD License.
+decimal :: Parser Int
+decimal = do
+  digits <- Zepto.takeWhile wordIsDigit
+  case BSC8.readInt digits of
+    Nothing -> fail "somehow this didn't work"
+    Just (i,_) -> pure i
+
+-- Taken from the @chronos@ library, which is licensed under the 3-Clause
+-- BSD License.
+wordIsDigit :: Word8 -> Bool
+wordIsDigit a = 0x30 <= a && a <= 0x39
+
+getIntWordsLine :: Parser [Int]
+getIntWordsLine = getIntWords <* skipWhile AttoC8.isEndOfLine
+
+getHeader :: Parser (Int, Int, Int, Int, Int)
 getHeader =
-  do BP.string (modeString Binary)
+  do Zepto.string (modeString Binary)
      spaces
      ns <- getIntWordsLine
      case ns of
        [m, i, l, o, a] -> return (m, i, l, o, a)
        _ -> fail $ "Invalid AIG header: " ++ show ns
 
-getOutput :: Get (CompactLit s)
+getOutput :: Parser (CompactLit s)
 getOutput =
   do ns <- getIntWordsLine
      case ns of
        [n] -> return (CompactLit (fromIntegral n))
        _ -> fail $ "Invalid output line: " ++ show ns
 
-getDifference :: Get Word32
+getDifference :: Parser Word32
 getDifference = go 0 0
   where
     addByte x b i = x .|. (((fromIntegral b) .&. 0x7f) `shiftL` (7*i))
@@ -290,10 +316,10 @@ getDifference = go 0 0
          let x' = addByte x b i
          if b .&. 0x80 /= 0 then go x' (i + 1) else return x'
 
-getDifferences :: Get (Word32, Word32)
+getDifferences :: Parser (Word32, Word32)
 getDifferences = (,) <$> getDifference <*> getDifference
 
-getGraph :: Get (Var, [Var], [CompactLit s], Bimap Var (CompactLit s, CompactLit s))
+getGraph :: Parser (Var, [Var], [CompactLit s], Bimap Var (CompactLit s, CompactLit s))
 getGraph =
   do (maxvar, ninputs, nlatches, nouts, nands) <- getHeader
      outputs <- replicateM (nlatches + nouts) getOutput
@@ -352,7 +378,9 @@ instance IsAIG CompactLit CompactGraph where
   withNewGraph _proxy k = k =<< newCompactGraph
 
   aigerNetwork _proxy fp =
-    do (maxv, inps, outs, gates) <- runGet getGraph <$> LBS.readFile fp
+    do fpContents <- BS.readFile fp
+       res <- Zepto.parseT getGraph fpContents
+       (maxv, inps, outs, gates) <- either fail pure res
        maxVar  <- newIORef maxv
        inputs  <- newIORef inps
        andMap  <- newIORef gates

Then the performance actually improves slightly!

$ time ./Main 

real    0m6.533s
user    0m6.394s
sys     0m0.133s

One thing to consider is that this design requires Data.ByteString.readFile instead of Data.ByteString.Lazy.readFile. That is, we must read the entire contents of the .aig file before parsing it, instead of lazily parsing the contents on demand. In this example, that doesn't appear to matter that much, so perhaps we should do this anyway.

[RyanGlScott]

For the sake of completeness, I also tried megaparsec:

Details

diff --git a/aig.cabal b/aig.cabal
index 17d76e5..04f1d96 100644
--- a/aig.cabal
+++ b/aig.cabal
@@ -38,11 +38,11 @@ library
   build-depends:
     base >= 4.9 && < 4.16,
     bimap,
-    binary,
-    binary-parsers,
     bytestring,
     containers >= 0.5.5,
+    megaparsec >= 9.0,
     mtl,
+    parser-combinators >= 1.2,
     vector,
     QuickCheck >= 2.7
 
diff --git a/src/Data/AIG/CompactGraph.hs b/src/Data/AIG/CompactGraph.hs
index 3282f85..cafea50 100644
--- a/src/Data/AIG/CompactGraph.hs
+++ b/src/Data/AIG/CompactGraph.hs
@@ -23,9 +23,8 @@ module Data.AIG.CompactGraph
   , newCompactGraph
   ) where
 
+import qualified Control.Applicative.Combinators as AppComb
 import Control.Monad (forM_, replicateM)
-import Data.Binary.Get
-import qualified Data.Binary.Parser as BP
 import Data.Bits (shiftL, shiftR, (.&.), (.|.), xor, testBit)
 import Data.IORef (IORef, newIORef, modifyIORef', readIORef, writeIORef)
 import Data.List (elemIndex, intersperse)
@@ -34,10 +33,14 @@ import Data.Map (Map)
 import qualified Data.Bimap as Bimap
 import qualified Data.Map.Strict as Map
 import qualified Data.ByteString as BS
-import qualified Data.ByteString.Lazy as LBS
 import qualified Data.ByteString.Builder as BS
-import Data.Word (Word32)
+import Data.Void (Void)
+import Data.Word (Word8, Word32)
 import System.IO (Handle, withFile, IOMode(..))
+import qualified Text.Megaparsec as Mega
+import qualified Text.Megaparsec.Byte as MegaByte
+import qualified Text.Megaparsec.Byte.Binary as MegaByte
+import qualified Text.Megaparsec.Byte.Lexer as MegaByte
 
 import Data.AIG.Interface hiding (xor)
 
@@ -256,44 +259,69 @@ encodeDifference w@(fromIntegral -> b)
 ------------------------------------------------------------------
 -- AIG parsing
 
-spaces :: Get ()
-spaces = BP.skipWhile BP.isHorizontalSpace
+type Parser = Mega.Parsec Void BS.ByteString
 
-getIntWords :: Get [Int]
-getIntWords = BP.decimal `BP.sepBy` spaces
+-- Taken from the attoparsec library, which is licensed under the 3-Clause BSD
+-- License.
+--
+-- | A predicate that matches either a carriage return @\'\\r\'@ or
+-- newline @\'\\n\'@ character.
+isEndOfLine :: Word8 -> Bool
+isEndOfLine w = w == 13 || w == 10
+{-# INLINE isEndOfLine #-}
 
-getIntWordsLine :: Get [Int]
-getIntWordsLine = getIntWords <* BP.skipWhile BP.isEndOfLine
+-- Taken from the attoparsec library, which is licensed under the 3-Clause BSD
+-- License.
+--
+-- | A predicate that matches either a space @\' \'@ or horizontal tab
+-- @\'\\t\'@ character.
+isHorizontalSpace :: Word8 -> Bool
+isHorizontalSpace w = w == 32 || w == 9
+{-# INLINE isHorizontalSpace #-}
 
-getHeader :: Get (Int, Int, Int, Int, Int)
+skipWhile :: (Word8 -> Bool) -> Parser ()
+skipWhile p = Mega.takeWhileP Nothing p *> pure ()
+
+spaces :: Parser ()
+spaces = skipWhile isHorizontalSpace
+
+getIntWords :: Parser [Int]
+getIntWords = MegaByte.decimal `AppComb.sepBy` spaces
+
+getIntWordsLine :: Parser [Int]
+getIntWordsLine = getIntWords <* skipWhile isEndOfLine
+
+getHeader :: Parser (Int, Int, Int, Int, Int)
 getHeader =
-  do BP.string (modeString Binary)
+  do _ <- MegaByte.string (modeString Binary)
      spaces
      ns <- getIntWordsLine
      case ns of
        [m, i, l, o, a] -> return (m, i, l, o, a)
        _ -> fail $ "Invalid AIG header: " ++ show ns
 
-getOutput :: Get (CompactLit s)
+getOutput :: Parser (CompactLit s)
 getOutput =
   do ns <- getIntWordsLine
      case ns of
        [n] -> return (CompactLit (fromIntegral n))
        _ -> fail $ "Invalid output line: " ++ show ns
 
-getDifference :: Get Word32
+getDifference :: Parser Word32
 getDifference = go 0 0
   where
     addByte x b i = x .|. (((fromIntegral b) .&. 0x7f) `shiftL` (7*i))
+
+    go :: Word32 -> Int -> Parser Word32
     go x i =
-      do b <- getWord8
+      do b <- MegaByte.word8
          let x' = addByte x b i
          if b .&. 0x80 /= 0 then go x' (i + 1) else return x'
 
-getDifferences :: Get (Word32, Word32)
+getDifferences :: Parser (Word32, Word32)
 getDifferences = (,) <$> getDifference <*> getDifference
 
-getGraph :: Get (Var, [Var], [CompactLit s], Bimap Var (CompactLit s, CompactLit s))
+getGraph :: Parser (Var, [Var], [CompactLit s], Bimap Var (CompactLit s, CompactLit s))
 getGraph =
   do (maxvar, ninputs, nlatches, nouts, nands) <- getHeader
      outputs <- replicateM (nlatches + nouts) getOutput
@@ -352,7 +380,8 @@ instance IsAIG CompactLit CompactGraph where
   withNewGraph _proxy k = k =<< newCompactGraph
 
   aigerNetwork _proxy fp =
-    do (maxv, inps, outs, gates) <- runGet getGraph <$> LBS.readFile fp
+    do res <- Mega.parse getGraph fp <$> BS.readFile fp
+       (maxv, inps, outs, gates) <- either (fail . Mega.errorBundlePretty) pure res
        maxVar  <- newIORef maxv
        inputs  <- newIORef inps
        andMap  <- newIORef gates

That was even slower that vanilla attoparsec, however:

$ time ./Main 

real    0m7.420s
user    0m7.153s
sys     0m0.208s

Based on this analysis, I think Zepto is the way to go. Any objections?

[robdockins]

My only concern is about the change to strict parsing. I doubt we'll ever be dealing with files large enough that it matters... but I've been surprised before. Since we parse the whole thing into main memory anyway, I'm guessing it isn't a big deal.

[RyanGlScott]

My only concern is about the change to strict parsing. I doubt we'll ever be dealing with files large enough that it matters... but I've been surprised before.

Yes, very true. Luckily, the implementation of Zepto is small enough to where it may be reasonable to port it over to lazy ByteStrings without too much hassle. I'll give that a try.

[robdockins]

I'm not sure forking is worth the effort. I'd say we go with zepto for now, but leave some breadcrumbs in the right places to remind us that we can switch to atto instead if lazy parsing becomes necessary.

[RyanGlScott]

Sounds good to me. I've opened #11 with the Zepto approach, leaving breadcrumbs in the form of a Note.