Cereal, as you may know from my previous posts is a library for parsing binary data from strict ByteStrings. It is very similar to the binary package, but importantly, provides both an Alternative instance, and an Either String a return type for the decode function, which tells you where the parse failed.

I’ve been playing around with cereal lately in jlouis’ haskell-torrent project, rewriting the various binary parsing and producing parts of the program (the torrent file parser, and the wire protocol parser). I though it would be nice to share some of the code used for these, to demonstrate how easy cereal makes it to do such things.

To begin with, I’ll show you the part that decodes and encodes torrent files (if needed in the future). Torrent files are encoded using a very simple encoding, known as bencoding, which consists of four major primitives: Integral numbers, Strings of bytes, Arrays of bencoded objects, and Dictionaries of String, bencoded object pairs. This is very nicely represented using this datatype:

-- | BCode represents the structure of a bencoded file
data BCode = BInt Integer                       -- ^ An integer
           | BString B.ByteString               -- ^ A string of bytes
           | BArray [BCode]                     -- ^ An array
           | BDict (M.Map B.ByteString BCode)   -- ^ A key, value map
  deriving Show

the specification for bencoded data goes something like this:

Integers are encoded as the ASCII character for ‘i’ as a byte, followed by the digits of the integral value, terminated by the ASCII byte for ‘e’.

Eg: the number ‘42’ would be encoded as “i42e”

Strings are encoded as the digits of their length, followed by a colon (‘:’), then the bytes of the string. these strings are really just byte sequences, and probably shouldn’t be treated as having an encoding (as jlouis and I found out when I tried to test the current code on GHC 6.12.1, with the BString type using Strings, instead of ByteStrings, and finding out that the simple test contained byte sequences that could not be represented as Strings).

Eg: the string “hello” would become “5:hello”, “hello world” would become “11:hello world”

Arrays are encoded as ASCII ‘l’ (for list I believe), followed by any number of bencoded objects, terminated by an ASCII ‘e’. (This is where using binary became difficult, as you had to explicitly check whether you had reached the terminating ‘e’ using lookAhead when parsing before attempting to parse another bencoded object, du the the lack of actual failure handling)

Eg: ["Hello", 123] would become “l5:helloi123ee”. Notice how we’ve used the previous definitions for integral numbers, and strings.

Dictionaries are encoded as an ASCII ‘d’, followed by the String, object pairs, followed by an ASCII ‘e’.

Eg: fromList [("test",123),("arr",[1,2,"hello"])] would become “d4:testi123e3:arrli1ei2e5:helloee”.

It looks a bit of a mess, but it is quite efficient.

Encoding

When writing my Serialize instance (Cereal’s version of the Binary class) for the BCode type, I decided it would be much easier to write the put methods first. This turned out to be rather straight forward, once I’d written a few helper functions.

toW8 :: Char -> Word8
toW8 = fromIntegral . ord


fromW8 :: Word8 -> Char
fromW8 = chr . fromIntegral

toBS :: String -> B.ByteString
toBS = B.pack . map toW8

fromBS :: B.ByteString -> String
fromBS = map fromW8 . B.unpack

-- | Put an element, wrapped by two characters
wrap :: Char -> Char -> Put -> Put
wrap a b m = do
    putWord8 (toW8 a)
    m
    putWord8 (toW8 b)

-- | Put something as it is shown using @show@
putShow :: Show a => a -> Put
putShow x = mapM_ put (show x)

With these in hand, I set to work implementing the put function. The Integer and Array functions were straight forward:

instance Serialize BCode where
     put (BInt i)     = wrap 'i' 'e' $ putShow i
     put (BArray arr) = wrap 'l' 'e' . mapM_ put $ arr
 

The Dictionary and String implementations weren’t too bad either:

    put (BDict mp)   = wrap 'd' 'e' dict
                      where dict = mapM_ encPair . M.toList $ mp
                            encPair (k, v) = put (BString k) >> put v
     put (BString s)  = do
                          putShow (B.length s)
                          putWord8 (toW8 ':')
                          putByteString s

As you can see, the code is quite clear, and matches the specification quite well.

Decoding

Parsing the data was the next step. this proved a little more difficult, but with my recent (shallow) experience with Parsec, I knew what was needed.

I decided to start by writing some useful combinators (this is a lie, I wrote them when needed, but lying makes the post flow better >_>). These included the following:

-- | Get a Char. Only works with single byte characters
 getCharG :: Get Char
 getCharG = fromW8 <$> getWord8


-- | Parse a given character
 char :: Char -> Get ()
 char c = do
     x <- getCharG
     if x == c
         then return ()
         else fail $ "Expected char: '" ++ c:"' got: '" ++ [fromW8 x,'\'']

-- | Get something wrapped in two Chars
 getWrapped :: Char -> Char -> Get a -> Get a
 getWrapped a b p = char a > p < char b
                  -- The same as char a >> p >>= \x -> char b >> return x

-- | Parse zero or items using a given parser
 many :: Get a -> Get [a]
 many p = many1 p mplus return []

-- | Parse one or more items using a given parser
 many1 :: Get a -> Get [a]
 many1 p = (:) <$> p <*> many p

-- | Returns a character if it is a digit, fails otherwise. uses isDigit.
 digit :: Get Char
 digit = do
     x <- getCharG
     if isDigit x
         then return x
         else fail $ "Expected digit, got: " ++ show x

-- | Get one or more digit characters
 getDigits :: Get String
 getDigits = many1 digit

My favourite two definitions here are many and many1, which nicely show the use of Alternative: they are mutually recursive, with many1 being the only one of the two to actually do and parsing, while many checks to see if many1 failed to parse one object using the parser p. It’s really quite beautiful, and makes the code that follows a hell of a lot nicer to write. This is where the love mentioned in the title comes in by the way.

With these in hand, I could now go ahead and write the actual parsers for various BCode types. Parsing BInts and BArrays is dead simple now:

-- | Parses a BInt
 getBInt :: Get BCode
 getBInt = BInt . read <$> getWrapped 'i' 'e' getDigits


-- | Parses a BArray
 getBArray :: Get BCode
 getBArray = BArray <$> getWrapped 'l' 'e' (many get)

As as side note, I’ve now come to see just what the folks on #haskell were on about when they said Applicative is nice. I think I’ve fallen in love (yet again!).

BStrings were a little more difficult, but not hard, given what I’ve just written:

-- | Parses a BString
 getBString :: Get BCode
 getBString = do
     count <- getDigits
     BString <$> ( char ':' *> getByteString (read count))

Here we get as many digits as we can, followed by a colon, and then take the number of bytes the digits specified. Finally, we have the BDict definition, which also is quite nice, if slightly annoying with its use of pattern matching (don’t get me wrong, i love pattern matching, but it’s the only place it’s used in the parser )

-- | Parses a BDict
 getBDict :: Get BCode
 getBDict = BDict . M.fromList <$> getWrapped 'd' 'e' (many getPairs)
     where getPairs = do
             (BString s) <- getBString
             x <- get
             return (s,x)

Putting it all together, we finally have a definition for the get function in the Serialize class.

    get = getBInt <|> getBArray <|> getBDict <|> getBString
 

A rather clean, elegant, and hopefully correct serialiser and deserialiser for the bencoded format used in torrent files. I’m considering releasing this code as a separate package on hackage, but I’m still not sure how widely it might be used. I have a string feeling that that would not be very wide at all, but that a library of more advanced combinators for cereal would make life a lot easier for others like me who have some strange binary formats that need to be parsed in an efficient manner.

Please, I implore you, do let me know what you think of this all, I’m always interested in seeing what others think of my code, and ways to improve it.

Until next time,

— Axman

Over the last week or so, I’ve been playing around with some of the minor details of jlouis’ Haskell-Torrent code. The main pieces I’ve been playing with have been the more binary centric pieces: the torrent file en/decoding and since Wednesday, the wire protocol.

After trying to compile the code using GHC 6.12.1, I noticed that a rather strange dependency: HCodecs. Investigating further, I realised that all that was being used was its fairly nice binary builder and parser, and was being used in the parsing and construction of bencoded files. This seemed to me to be the domain of one of my favourite packages, binary. I also noticed that when trying to parse the sample torrent file jlouis had provided, there was binary data that could not be represented in a String type, because there were byte sequences that could not be parses into Char’s.

So I went off to try and implement the BCode module using Data.Binary. The encoding was really simple and straight forward, but parsing was another matter. Binary has no real error handeling, which meant that decoding things like lists where you keep adding elements to the list until you reach an ‘e’, was made quite verbose due to this fact. After implementing a (semi) working module, I went in search of a more parsec like interface to binary parsing. This is when someone on #Haskell informed me of cereal, a package based on binary, which added an Alternative instance, and an Either String a return type for better error reporting.

I fell in love. This was exactly what I was after, I could create my own combinators like many and many1, with the same ease I could with parsec. Using cereal, I was able to make a really clear, concise parser, which should also be quite efficient.

I will post some of this code at a later time, when i’m not writing on my iPhone, and show you just what I mean. I’m also considering releasing the BCode module as a package of it’s own, if anyone else feels it might me useful to them. Either that, or I might write up a module of useful combinators for use with cereal.

Until next time, happy new year and I hope this year treats you all better than the last one did.

– Al

I was taking a look at google analytics today, and decided to take a look at the browser percentages. I was a little surprised when I saw the results; 60.1% Firefox, 13.9% Safari, 7.9% Mozilla, 5.9% Opera, 5.5% Chrome, and 2.9% Internet Explorer, since the beginning of the year. The sort of crowd that read my blog I’d expect to be using Firefox, but maybe not such a high percentage. Pretty pleased that Safari is in second, and not totally sure what Mozilla is, but probably just the other mozilla based browsers like IceWeasel. Also a little surprised with the amount of Opera users, but not too much. But the biggest surprise was IE, I never expected I’d get so few IE users, and I’m very happy about this!

Even though I have taken to not hacking my site so much, I’m still pleased that I can basically ignore having to even try making my site IE compatible. I know I’m likely to get some responses to this saying that I should still do it, but you know what? Screw that! if people are stupid enough to still be using IE (even if it has improved in some very good ways in recent times), then I don’t care what sort of experience they have on my site. They’re in the vast minority, and they annoy me, so stuff ‘em.

Yep, not a terribly indepth or interesting post, I know, but I needed to post something… my hits were dropping!

‘Till next time,

– Axman

The other day, I put my AVar package on hackage. Doing so taught me more than i expected it would, mainly that i need to do more testing of cabal packages before submitting them, and also to make sure you’ve exported all the functions you need to actually use the package (I forgot to put putAVar in the module exports -_-). So i’m up to release 0.0.3, without much work being done at all (although, I can’t think of much more to do really).

With the current release, i think that all exceptions that may occur from functions passed by the user to the variable should be caught by and handled correctly by the variable. I guess in a sense, AVars are smart variables that know what is and isn’t good for them, and will refuse to hurt themselves (hopefully!).

If you’re interested in seeing what AVar can do, check out the Hackage page. I really have no idea how it might be useful, but I’d love to hear others thoughts on it. If you have any requests, please let me know, and I’ll see what I can do (proper transactional … transactions are not something I want to tackle, especially with uni starting on monday)

– Axman

So I’ve been trying to see if I could speed up the pidigits program, and, well, failed. I’m not alone though, Stephen Blackheath and others have tried too, and no one’s managed to make things much, if at all faster. The main problem seems to be that GHC is allocating a lot of RAM, which must be related to the need for Integers. The current program uses up 500+MB by the time it finishes. Not good. So, I’m putting a call out to see if anyone else can either think of a better way to get the answer than the current entry, or any tips about reducing memory usage. If you come up with anything, I’d love to hear from you. Cheers, ~ Axman

I’ve been talking to Stephen Blackheath on the #haskell-in-depth channel, and he’s just submitted another new program to the shootout. This entry is for the regex-dna problem.

For this benchmark, each language is limited by the speed of the regex library it’s using.
Right… let me see. Here’s what I did;
I am not certain, but it seems that forcing the evaluation of s1, s2 and s3 (the blobs of input data) before parallelizing the processing
gave better CPU utilisation.
I also changed the part at the end where it does large numbers of pattern substitutions, so that it updated everything in-place in a mutable buffer.
I found that splitting the pattern substitutions into chunks sped things up by a factor of three. It looks like there’s some sort of overhead incurred on large buffers when the regex ‘match’ function creates its AllMatches array.
The reason why I needed memmove instead of memcpy is that memmove can work on overlapping buffers.
These changes improved the performance from 1:00 user / 0:42.2 real to 0:40.1 user / 0:25.12 real on my dual core, compared with 23.3 sec user for the slower non-parallel one of the two C++ implementations. (The parallel one wouldn’t build for me.)

You can see the details of the submission here, and the actual code. He also adds:

I took my unsafePerformIO’s out too. I have a reputation to maintain!

It’s good to see that someone else is working on making haskell look good (and doing a much better job than me thankfully!). Maybe soon we’ll be topping the list, or at least beating Java to move up to 4th place.

So I’ve been taking full advantage of the new #haskell-in-depth channel, and with the thanks of blackh and others, I’ve made a few more changes, and I’ve shaved another whole 30 seconds of my already not too shabby 1m17s. I’m now down to 47.215s, making a saving of 30s, or a saving of 39%.

If you’re wondering what I’m on about, take a look at this post for the story of my n-bodies program so far, and this port for what my code looked like before.

So how did I do it this time? Well, I decided STRefs weren’t necessary, and could easily be replaces with accumulating parameters in basically all of my code that used them. I did this in the hope they would be kept in registers, but even if they’re not, it’s still faster. I also saved about 3 seconds by inlining all my read* and write* functions with {-# INLINE #-} pragmas that would write or fetch the various parts of the Body’s info. So here’s the code, first the original one:

advance dt ps = do
forM_ index1 $ \i -> do
-- (B p v m) <- readBody ps i
p <- readPos ps i
v <- readVel ps i
m <- readMass ps i
vvar <- newSTRef v
forM_ (index2 i) $ \j -> do
-- (B p' v' m') <- readBody ps j
p' <- readPos ps j
v' <- readVel ps j
m' <- readMass ps j
let dp = p .-. p'
dst = mag dp
magnit = dt / (dst  dst  dst)
change = magnit . dp
(sca1,sca2) = (m' . change, m *. change)
writeVel ps j (v' .+. sca2)
modifySTRef vvar (.-. sca1)
vvar'@(V nx ny nz) <- readSTRef vvar
-- unsafeIOToST (print vvar')
writeVel' ps i nx ny nz
writePos ps i $ move' dt (B p vvar' m)

And the new one, with an inner loop:

advance dt ps =
forM_ index1 $ \i -> do
-- (B p v m) <- readBody ps i
p <- readPos ps i
v <- readVel ps i
m <- readMass ps i
let loop2 !j !v@(V !x !y !z)
| j > numPs = return v
| otherwise  = do
p' <- readPos ps j
v' <- readVel ps j
m' <- readMass ps j
let dp = p .-. p'
dst = mag dp
magnit = dt / (dst  dst  dst)
change = magnit . dp
(sca1,sca2) = (m' . change, m *. change)
writeVel ps j (v' .+. sca2)
loop2 (j+1) (v .-. sca1)
v' <- loop2 (i+1) v
-- unsafeIOToST (print v')
writeVel ps i v'
writePos ps i $ move' dt (B p v' m)

So my last post got submitted to reddit by dons, and someone asked if I translated the code from C, so I thought I’d talk about my evolution of the problem, and how big the difference is runtime from start to finish is so far. First I should explain the problem. What needs to happen is I take 5 planets and the sun, each with an initial position and velocity, and a mass. Then I set about modifying each body’s position and velocity according to the gravitational pull of all the other bodies. For the purposes of this problem, in the end we’re only interested in the total energy in the system, which changes as time goes along. For the actual shootout, the bodies must be iterated 50,000,000 times, with a delta time of 0.1 (Not actually sure what that’s 0.1 of, possibly days). The reason I got interested in this problem was because I decided to take a look at the current haskell submission. I was a little horrified when I say it as all pointer nonsense and back magic. Full of stuff haskell can do fine (And possibly better and more safely that other languages), but should really be avoided where possible. I wanted to see if you could write a fast version, using more accessible techniques.

Lists

So my initial try used lists. I thought about how I could make is faster, and cool at the same time, and failed by using Control.Parallel, and I think all I have to say about this version that I am not proud of it, and when I just tried to run it with n=50000000, I decided to kill it after it reached 3.3GB of RAM usage in under a minute. Yeah, not great at all.

Parallel Arrays

So my next iteration of the problem basically continued on from the list version, but this using parallel arrays. As I’d basically followed in the same steps I’d used for the list version, its performance was on par with that of the list version; it was also killed after using 3GB of RAM in about 30 seconds, and again, I was not proud. It should also be mentioned that neither the list of parallel array versions produced the correct answers with n=1000, so they were never going to be contenders

STArrays

It was about this time I discovered the ST monad, and I fell in love (Sort of). The ST monad allows you to write imperative programs, using mutable variables and arrays, in a totally pure way. It’s a little like the State monad, but it has a generic state of ‘forall s’. I’m not going to go into the details of ST, but if you’re interested, check out SPJ’s paper on the subject of Lazy Functional State Threads (.ps.Z). This is where I finally started to get some good results. The program runs in about 1.4MB RAM (:O), which means I could actually time its runtime. So I did that, and well, at least it finished. The runtime was 14m46.957s according to time, which is still considerably faster than both Pythons, JavaScript under TraceMonkey, ruby, perl, php, and ruby again, but it’s slower than Lua, which is 24x slower than the current fastest C++. But I was getting somewhere! I could see this was the way to go, with memory usage being the most important thing so far, ST made keeping it really low easy as can be. Now for some speed…

STUArrays

I can’t remember where I found out about STUArrays, but I could see they were the obvious solution. They’re almost as close to C arrays as you’re going to get in nice haskell, while still remaining pure, and not so ugly. Basically STUArrays are unboxed arrays (U) in the ST monad (ST). This means that when out put a type into them, instead of putting a pointer to the data in the type inside the array, you put the actual data into the array, so it’s all sitting next to each other. This of course restricts the type you can out into an array somewhat to things like Doubles, Ints, Words, and the few other things with single constructors (This rules out Bools and Integers). There is quite a speed advantage to using STUArrays, but writing your own instance for say MArray (STUArray s) Body (ST s) is a little off putting. Luckily I had talked with Dons about what I was working on, and he’d already started working on something similar. So I nicked his MArray instance, modified it, and… Failed. For some reason, I kept getting segfaults when trying to get this STUArray stuff to work with my Body type with n > 22:

data Vec3 = V !Double !Double !Double
data Body = B {
pos ::  {-# UNPACK #-} !Vec3,
vel ::  {-# UNPACK #-} !Vec3,
mass :: !Double
}

I was not happy! And I still have no idea what went wrong. But I moved on.

STUArray s Int Double

I decided I’d avoid the MArray instance completely and use Double STUArrays directly. This turned out to be a good idea indeed, bringing some nice performance benefits. By doing this, I didn’t need to worry about taking out redundant data from the array by fetching a whole Body each time, I could pick out the data I needed, be it the Velocity, Mass or Position, or all three if I needed them all. With this work, I brought the runtime down to around 2m40 (I think), an approx. 80% improvement in runtime! This was massive! I was certainly onto something. I was now sitting behind Erlang at 5.9x and below Scheme PLT at 9.1x.

Performance

Ok, I’d come this far, but I was now stuck for ways to increase the speed. I’d done some algorithm rejiggering to see if I could gain any speed, and I managed to cut another 10 seconds or so off, but that wasn’t going to cut it. So, I took a look at the performance pages on the wiki. The Arrays page was most useful, suggesting that the use of unsafeRead and unsafeWrite could make huge improvments by removing redundant bounds checking. The floating point page also helped a little, with the suggestion of using the -fexcess-precision flag to speed up the floating point calculations. With these two changes, I managed to cut a whole minute 15 off the time. Yes, I just got a 50% speedup! Now I was getting happy. I was now beating Erlang HiPE, but sadly I was nowhere near C#’s 45 seconds, and definitely nowhere near C++’s 21 seconds. Still, how often do you get to produce a 50% speedup in some already relatively fast code?

Conclusion and the future

So what next? Well, I think I can save some more time be using explicit loops with accumulation parameters instead of using STRefs which I have a feeling may carry some overhead. I don’t know what kind of gains I can expect, but I doubt they’ll be that large. I might also consider making my code even more C like, by directly accessing parts of the arrays directly. I may even get rid of the whole ST thing, and working in IO and with more primitive operations, but by doing that, I’ll be moving away from the easier to understand code I have now. So, what can I conclude from all this? Well, Haskell sure can be fast, while still remaining beautiful. But making it really fast starts to get ugly (Introducing unsafe* does not help :\ ). There are obvious way to do things in haskell, and even some obvious fast ways to do them. But really fast code takes effort (Which is true of most, if not all languages). I’ve learnt a lot while writing this program, and I’ve still got a lot to learn. Wish me luck!

I’ve just read Marcus S. Zarra’s post about software licencing, piracy and stupidity (to paraphrase), and I think he’s hit the nail right on the head.

Treating potential customers like potential thieves makes them feel more inclined to follow these feeling. I’ll admit that I’ve pirated software, but I’ve also bought a lot of it too. The stuff I’ve pirated is uaually something that I feel is far overpriced for what they offer. Like Marcus says, software is something you make once, and sell thousands of times; it’s making money from nothing. The things I’ve bought are usually pretty cheap, and that makes me want to buy them, I want to help the developer and reward them for making something which is useful to me, and reasonably priced, or even a bargain.

I do not like being forced to buy your software. I do not like being forced to buy your software to use it for something that is useful, but not exactly (or at all) worth paying $30 for. Nor do I like being told that I have not bought your software. Give me the full thing to try, without restrictions, at all, give me a month and see if I feel I need it. If after that month, (and that’s a month of use, not a month from the date of download), I feel I need your software, then I will buy it. If I never hit that month, then no, I will not be buying it, it has not been useful enough for me to consider it. Doesn’t mean it’s not great, or that it’s buggy and annoying (I will tell you if it is), it just means I have no ude for it.

I’ll take an example, VMware Fusion. Now, this is made by a very large company, a big, corporate business, that makes expensive software for some rather important tasks. But what happened when Fusion v2.0 came out? they gave it to us for free! I, and I’m sure many others would have paid for this update, they did a lot of work for it, added some very nice new features. But instead of them saying “hey! they’re getting new stuff, they HAVE to pay!”, they seemed to take the stance that these new features were missing features, and that v2.0 was heading towards making the program more complete, rather than expanding it.

This is an excellent example of how I feel software licencing should work. Be nice to your customers, give them treats, and they will do more than stay quiet about your products, they will tell their friends, or anyone they know who might be interested. They feel an affinity with you and your software, and will go the point of arguing and fighting over which is better, your product, or someone else’s. Loyalty will always bring you more than fear, and being nice will bight you in the arse far less often than being a dick.

I don’t think I have summed this up as well as Marcus managed to (I’ve just written this from start to finish, and can’t be bothered to re-read it [pan's labyrinth awaits]), but I did feel like showing my support for his views, because he got how I feel so right.

Anyway, more later

~ Axman