Sunday, March 3, 2013

binary 0.7

binary 0.7 has just been released and compared to the current version included in the Haskell Platform, binary 0.5.1.0, it brings a few new things. Most of this has also been available in the 0.6.* versions which already have been available on hackage for some time.

Incremental interface and improved error reporting

This is probably the most requested feature, and was introduced already in binary 0.6.
In older versions of binary, you could run the Get monad with the following function:
runGet :: Get a -> Lazy.ByteString -> a
It takes the monad you want to execute, together a with a lazy ByteString containing all the input it will need to finish. While this is straight forward and easy to use, it does not meet all needs:
  1. There is no error reporting (compare with a function returning Maybe a, or Either ErrorMessage a). If a decoder error happens, it'll just call error :: String -> a.
  2. What if you don't have all input when you start to decode, like for example if you're reading from a large file or a socket? Previously, lazy IO has been used to address this, but we will look into why this is not always suitable.
To address (1), we introduce the data type Decoder as the return type for our new run function.
-- | Incremental interface to run a decoder.
runGetIncremental :: Get a -> Decoder a
A Decoder can have successfully finished in which case it'll be the Done constructor and have the final value, or have encountered a problem, in which case it'll be the Fail constructor together with the error message. In both cases, you will also get the remaining unused input, and the number of bytes consumed when the decoder succeeded or failed. In the next section, we will see why the this new run function does not need input as a second argument.

For (2), the traditional answer has been to use lazy I/O to get a lazy stream of data, which will hide that I/O is going on, and we can pretend that we already have all the input in memory. While this is fine for some scenarios, we have given up control over error handling and file handle resources. For some applications, this is simply not good enough.

Here's where the incremental interface can help. It works in the same way in binary as seen in other libraries for parsing. Instead of taking any input, it immediately produces a Decoder.  In addition to Done and Fail mentioned above, it also has the Partial constructor, meaning that the Decoder needs more input in order to finish.
-- | A decoder produced by running a 'Get' monad.
data Decoder a
  = Done !B.ByteString !ByteOffset a
    -- ^ The decoder has successfully finished. Except for the
    -- output value you also get any unused input as well as the
    -- number of bytes consumed.
  | Fail !B.ByteString !ByteOffset String
    -- ^ The decoder ran into an error. The decoder either used
    -- 'fail' or was not provided enough input. Contains any
    -- unconsumed input and the number of bytes consumed.
  | Partial (Maybe B.ByteString -> Decoder a)
    -- ^ The decoder has consumed the available input and needs
    -- more to continue. Provide 'Just' if more input is available
    -- and 'Nothing' otherwise, and you will get a new 'Decoder'.

GHC Generics

binary has also got support for automatically generating instances of the Binary class for your data types, using GHC's generics.
{-# LANGUAGE DeriveGeneric #-}

import Data.Binary
import GHC.Generics (Generic)

data Foo = Foo
         deriving (Generic)

-- GHC will automatically fill out the instance
instance Binary Foo
The was committed to binary by Bryan O'Sullivan, though pieces copied from the cereal package where it was written by Bas van Dijk.

Control.Alternative

binary now implements the Alternative class, and you can use the <|> combinator to try a decoder and fallback to another if the first failed. Although many binary formats don't strictly require backtracking in the decoder, it can be used for convenience or if it leads to code which is easier to read. In the example below, we parse frames in some binary format, trying first one kind of frames, then the other. If it's neither kind, we fail altogether.

data Frame = FrameA {- some fields specific to A frames -}
           | FrameB {- some fields specific to B frames -}

decodeFrame :: Get Frame
decodeFrame = decodeFrameA <|> decodeFrameB <|> fail "not a frame!"

decodeFrameA :: Get Frame
decodeFrameA = do
  word <- getWord8
  unless (isFrameAMagicWord word) $ fail "not an A-frame!"
  {- continue decoding... -}
  return (FrameA {..})


decodeFrameB :: Get Frame
decodeFrameB = do
  word <- getWord8
  unless (isFrameBMagicWord word) $ fail "not an B-frame!"
  {- continue decoding... -}
  return (FrameB {..})

In this particular example, though, it's not required to have backtracking, as we could have first decoded the first Word8, and then chosen to continue with either FrameA or FrameB. This continues to be the better choice for performance and should be preferred when possible, but one can imagine a more complicated binary format where using <|> is required or simply leads to cleaner code.

Control.Applicative

For each use of a primitive decoder, such as getWord8, getWord32le, and so on, binary needs to check whether there is sufficient input left, or if it needs to demand more input from the caller (by returning a Partial, as discussed above).

decodeWordTuple :: Get (Word32, Word16)
decodeWordTuple = do
  a <- getWord32le
  b <- getWord16le
  return (a,b)


Here, binary will check twice whether there is enough input. First for the 4 bytes of the Word32, and a second time whether there is 2 bytes left for the Word16. Once could think this is wasteful, and that we should only check once at the beginning for the 6 bytes that we know will be required. Unfortunately, with a monadic API this is not possible (maybe possible with some new fancy kind of rewrite rules?).
When using the applicative class though, binary tries to be clever and join these checks.

decodeWordTuple :: Get (Word32, Word16)
decodeWordTuple = (,) <$> getWord32le <*> getWord16le

It does this by using GHC's rewrite rules to rewrite the expression into a single decoder. Note that for this to make a worthwhile difference to the performance of your application, your application needs to already be quite tuned. The rewriting also relies heavily on that all decoder functions gets inlined, and can therefore be a bit hard to trigger.

Backwards compatibility

I'm pleased to say that while the internals of binary has undergone major changes, it still largely provides the same API to the developer. A few convenience functions have been added, and a few functions that doesn't make sense any more have been removed. Read the haddocks for the full API here.

Data.Binary:
decodeFileOrFail :: Binary a => FilePath
                 -> IO (Either (ByteOffset, String) a)
decodeOrFail :: Binary a =>
  Lazy.ByteString -> Either (Lazy.ByteString, ByteOffset, String)
                            (Lazy.ByteString, ByteOffset, a)

Data.Binary.Get:
runGetIncremental :: Get a -> Decoder a
runGetOrFail :: Get a -> Lazy.ByteString
  -> Either (Lazy.ByteString, ByteOffset, String)
            (Lazy.ByteString, ByteOffset, a)
pushChunk :: Decoder a -> ByteString -> Decoder a
pushChunks :: Decoder a -> Lazy.ByteString -> Decoder a
pushEndOfInput :: Decoder a -> Decoder a
uncheckedLookAhead :: Int64 -> Get Lazy.ByteString
uncheckedSkip :: Int64 -> Get ()

The functions lookAhead and lookAheadM which disappeared in binary-0.6.* and have been brought back in this release, making it easier to transition from binary-0.5.

Code

The package is available on hackage.
The code is available on github.

Contributors since the last Haskell Platform version:

  • Lennart Kolmodin
  • Johan Tibell
  • Bryan O'Sullivan
  • Bas van Dijk
  • Paolo Capriotti
  • Eyal Lotem
  • Gabor Greif

Thursday, February 17, 2011

binary by the numbers

New home

I've taken the liberty to fork the darcs repo of binary and put it on github. It contains both the latest released version as well as the new experimental continuation based Get monad a branch called cps.

git clone git://github.com/kolmodin/binary

Performance

It's interesting to run the benchmark of binary on different architectures and with different versions of GHC. Although there recently has been work within the community with fast writing (blaze-builder comes to mind) I've mostly been working on how to read things fast.

The classic binary implementation of the Get monad is a state monad while the new experimental version is continuation based, so fundamentally different. They also perform differently. To produce the numbers below I ran the benchmark suite of binary. It reads either Word8, Word16, Word32 or Word64 in a (hopefully) tight loop and then presents how fast it could do it. For example, see this graph over performance in a 32bit environment;

The nice news is that GHC 7.0.1 always performs better than GHC 6.12.3. Also the experimental cps branch (the wide green line) is faster than the classic master branch.

Things seems to be going well in 32bit land. Let's have a look in a 64bit environment;

This gives a different picture. GHC 7.0.1 still performs better than GHC 6.12.3, but we can also see that the cps branch can't keep up with the state monad based master branch (in contrast to when compiling for 32bits). Future work will include to figure out why, and how to fix it.

Lets have a look at how binary performs at writing too;

Benchmark Environment

The tests have been performed on a Sandy Bridge CPU using GHCs native backend. I wanted to try the LLVM backend too, but unfortunately LLVM crashes when compiling the benchmark executable.

Sunday, January 9, 2011

About binary

About a year ago I started hacking on a project to change the Get monad of the binary package. I've been working off and on since... :) The change will allow us to incrementally provide the Get monad with input, as well as allow backtracking and a more graceful error handling. The code was public, but got moved with the haskell.org infrastructure changes. It's now available again;
darcs get http://code.haskell.org/~kolmodin/code/binary/
Johan Tibell writes about the API update in his recent blog post. Developers familiar with attoparsec code will largely be familiar with the new binary Get monad too, as it's been a heavy influence. The type for the parse function would essentially be something like this:
data Result r =
    Fail ByteString [ByteString] -- an error msg and a trace
  | Partial (ByteString -> Result r) -- incremental input
  | Done r -- finished!
A few forks of binary tries to address this too, all in their own way. Currently I know of cereal and binary-strict.

Performance

When benchmarking cereal and the new binary package, cereal comes out on top, at the expense of not being able to consume the input in incremental chunks. I couldn't find the benchmark suit for binary-strict. The reason for cereal being faster, I think, is due to that its simpler code when having a simpler state, essentially only a single strict ByteString (the input). In binary (and attoparsec) it's a bit more complicated, due to the incremental input (in combination with supporting MonadPlus):
data S =
  S { input      :: !B.ByteString -- the current input chunk
    , next_input :: !B.ByteString -- saved input to be used when backtracking
    , read_all   :: !Bool -- have we requested all input available to parse?
    } deriving Show

newtype Get a =
  C { runCont :: forall r.
                 S ->
                 Failure   r ->
                 Success a r ->
                 Result    r }

type Failure   r = S -> [String] -> String -> Result r
type Success a r = S -> a -> Result r

bindG :: Get a -> (a -> Get b) -> Get b
bindG (C c) f = C $ \st0 kf ks -> c st0 kf (\st1 a -> runCont (f a) st1 kf ks)
Unfortunately, this results in bad performance. I'm guessing that's it's because it's reconstructing the state value (of type S), and the remaining ByteString input for each value consumed, thus a lot of allocations. So, as an experiment, I manually unpacked S;
-- No longer using S
{-
data S = S { input      :: !B.ByteString
           , next_input :: !B.ByteString
           , read_all   :: !Bool
           } deriving Show
-}

newtype Get a =
  C { runCont :: forall r.
                 -- these three were part of S, now they are separate arguments
                 B.ByteString -> -- 1
                 B.ByteString -> -- 2
                 Bool ->         -- 3
                 Failure   r ->
                 Success a r ->
                 Result    r }

type Failure   r = B.ByteString -> B.ByteString -> Bool -> [String] ->String -> Result r
type Success a r = B.ByteString -> B.ByteString -> Bool -> a -> Result r

bindG :: Get a -> (a -> Get b) -> Get b
bindG (C c) f = C $ \inp next eof kf ks ->
                             c inp next eof kf
                               (\inp' next' eof' a -> runCont (f a) inp' next' eof' kf ks)
With ghc-7, this yields a huge speed boost and reaches about half the speed of the old binary library (and ~30% faster than cereal). Unfortunately, I find the code is less readable and harder to maintain. Maybe it's worth it though. I got a hint to see ghc ticket #1349. Duncan Coutts summarizes the issue, this time about the Put monad. There are a lot of details and examples in those mails, suggesting an extension to GHC to control strictness in the arguments of higher order components. It'd allow us to write the prettier version, yet enjoying the nicer properties of the unpacked version. It's unlikely that we'll see the proposal implemented soon, though. It seems there are four options;
  • Go with the manually unpacked code
  • Drop support for backtracking
  • Drop support for incremental input
  • Find something even better, you're all invited :)

Saturday, May 10, 2008

HCAR Deadline

If you haven't followed the mailing lists lately, you might have missed that the HCAR deadline is today (10th May).
The Haskell Communities & Activities Report is a bi-annual overview of the state of Haskell as well as Haskell-related projects over the last, and possibly the upcoming 6 months. [..] If you are working on any project that is in some way related to Haskell, please write a short entry and submit it to the us. Even if the project is very small or unfinished or you think it is not important enough -- please reconsider and submit an entry anyway!
Get the full details here. I'm much looking forward to the next edition!

Sunday, January 20, 2008

The Beginning of a New Era

I still remember the event Jobs in Functional Programming, held here in Göteborg, Sweden, the 14th December last year. It was the first event of its kind, an event to attract hackers to employers, paying for you to hack in functional programming languages! Not only were 8 companies represented in some way, 6 of them had people there explaining why you should go to their company and not someone else's :) With over 100 people registered, and about as many as came, it was a joy. Professor John Hughes, well known for his work with Haskell, was the host for the evening. John ended the event with a speech, I got reminded of it by SPJ's mail. Congratulations, btw! :) They both conclude that Haskell has become much more popular, and that it has happened very fast. Five or ten years ago we would not have dreamed of having such an event as we did. Some students found it humorous when John spoke very enthusiastically about Haskell's new won popularity. But think of it this way, twenty years ago few companies would make a fuzz about FP at all. Today C#, one of the most popular languages out there from one of the (the?) biggest computer companies out there, has lots of ideas from FP. There is also F#: Microsoft's newest addition to the .NET family, a somewhat more evolved version of OCaml, adjusted to fit into the .NET world. It's not difficult to make the prediction that Haskell will get even more attention in the near future. The times are really changing. As Hughes said in his speech, this is the beginning of a new era.

Saturday, January 19, 2008

Wireless on a Thinkpad x61s

I've just configured wireless networking on my laptop, so I'd like to share a little checklist to speed up the process for others in the same situation. As you will see, it is that hard to get it going. It's as simple as setting the kernel modules, drivers, encryption and local settings. What took me the longest was actually to remember to allow my MAC address in the router... bummer :) This guide is specific to Gentoo Linux, but it should not differ too much against other distributions. I also expect you are familiar with Gentoo and how to compile your kernel. # lspci | grep Wireless 03:00.0 Network controller: Intel Corporation PRO/Wireless 4965 AG or AGN Network Connection (rev 61) First, we need to get the network interface working. Enable the new network stack, in the kernel menuconfig, enable Networking -> Wireless -> Generic IEEE 802.11 Networking Stack (mac80211). I used the currently latest stable kernel, gentoo-sources-2.6.23-r3 Also don't forget to compile the required crypto algorithms under Cryptographic API: <M> Cryptographic algorithm manager <M> CBC support <M> ECB support <M> AES cipher algorithms <M> ARC4 cipher algorithm <M> Michael MIC keyed digest algorithm <M> PCBC support This will build modules called mac80211, blkcipher, aes, arc4, ecb, cryptomgr and crypto_algapi. Load them during boot in /etc/modules.autoload.d/kernel-2.6. Also modprobe right away, so we can continue without rebooting. Add to kernel-2.6 like above. Install the network drivers; unmask and unhardmask iwlwifi and iwl4965-ucode, add ipw4965 to your use flags, then run emerge iwlwifi This will install the iwlwifi system and the firmware needed by your hardware. Now run modprobe iwl4965. Check success/failure with ifconfig -a or dmesg, you should have a new interface available. As soon as you've got the interface up and running, check your HW address. If you've got MAC filtering, don't forget to add it to your "Allow list". Better get that out of the way so we don't forget it... I'm using wpa_supplicant to configure for my networks, emerge wpa_supplicant. /etc/conf.d/net: ---------------- #dhcp is default on all devices modules=( "wpa_supplicant" ) wpa_supplicant_wlan0="-Dwext" /etc/wpa_supplicant/wpa_supplicant.conf: ---------------------------------------- ctrl_interface=/var/run/wpa_supplicant # Let any member of the group "wheel" configure the network ctrl_interface_group=wheel ap_scan=1 # Add network block to connect to unsecure networks. # Giving it a low priority will make all other blocks preferred. network={ key_mgmt=NONE priority=-9999999 } # Add a WPA2 network network={ ssid="my ssid" proto=WPA2 key_mgmt=WPA-PSK psk="secret password" } More information about wpa_supplicant, and examples, are available in /usr/share/doc/wpa_supplicant*/.

Thursday, August 23, 2007

Crap mail client

At work we're blessed with a wonderful mail client which we are suppose to use, by policy. And most people do. I try not to. Maybe you've seen this signature in some peoples' mail:
A: Because it messes up the order in which people normally read text. Q: Why is top-posting such a bad thing? A: Top-posting. Q: What is the most annoying thing in e-mail?
and indeed they are right. This particular mail client encourages top posting by doing two things. The first one is that when you hit reply it formats the new mail in this manner: <cursor here> <your signature> ------<other persons name> wrote:------ <other persons mail body indented> ... where the irritating thing is that it places your signature above the other persons mail. The second thing is that all mails are in HTML, and the client has some limitations in that regard: The text from the mail you're replying to gets indented in a way where you can't inline your replies without having your text indented too. The interesting stuff happens when people in my organization think of how to workaround these limitations. Some use top posting, and forgets to reply to half of the message. The others use a feature that comes with HTML, coloring! That is, the common way to reply is that you pick a previously not used color in that mail, and color your inlining with that. When the mail gets replied for the seventh time there is indeed eight different colors used, and everything is indented seven steps. Yay.... Naturally there is no "standardization" of which color to pick next, so each conversation is colored in a different way. It can get quite tricky to follow. Also, after a while it gets hard to pick a color that is sufficiently different from other colors. Luckily I'm not color blind. Just to make you realize how bad this really is, imagine this with your favorite indention sensitive programming language: In your editor;
  • You can't indent.
  • When you hit the tab key you just get the color for the current indention level.
  • The mapping of "intention level" to color is different for each source file.
A very interesting thought. The first person to implement this in the editor of their choice will get a postcard from Göteborg, by yours truly.