June 2007 - Haskell-Cafe

sha1 implementation thats "only" 12 times slower then C
by Anatoly Yakovenko 14 Jul '07

14 Jul '07

So I tried implementing a more efficient sha1 in haskell, and i got to about 12 times slower as C. The darcs implementation is also around 10 to 12 times slower, and the crypto one is about 450 times slower. I haven't yet unrolled the loop like the darcs implementation does, so I can still get some improvement from that, but I want that to be the last thing i do. I think I've been getting speed improvements when minimizing unnecessary allocations. I went from 40 times slower to 12 times slower by converting a foldM to a mapM that modifies a mutable array. Anyone have any pointers on how to get hashElem and updateElem to run faster, or any insight on what exactly they are allocating. To me it seems that those functions should be able to do everything they need to without a malloc. This is the profiling statistics generated from my implementation COST CENTRE MODULE %time %alloc hashElem SHA1 42.9 66.2 updateElem SHA1 12.7 16.7 unboxW SHA1 10.6 0.0 hashA80 SHA1 5.2 0.3 temp SHA1 4.6 0.0 sRotateL SHA1 4.6 0.0 ffkk SHA1 3.3 2.6 hashA16IntoA80 SHA1 3.1 0.1 sXor SHA1 2.9 0.0 do60 SHA1 2.9 2.6 sAdd SHA1 2.3 0.0 do20 SHA1 1.3 2.6 splitByN SHA1 1.2 2.3 do80 SHA1 0.8 2.6 do40 SHA1 0.4 2.6 Thanks, Anatoly

7 10

Need for speed: the Burrows-Wheeler Transform
by Andrew Coppin 10 Jul '07

10 Jul '07

OK, so I *started* writing a request for help, but... well I answered my own question! See the bottom... I was reading Wikipedia, and I found this: http://en.wikipedia.org/wiki/Burrows-Wheeler_transform I decided to sit down and see what that looks like in Haskell. I came up with this: module BWT where import Data.List rotate1 :: [x] -> [x] rotate1 [] = [] rotate1 xs = last xs : init xs rotate :: [x] -> [[x]] rotate xs = take (length xs) (iterate rotate1 xs) bwt :: (Ord x) => [x] -> [x] bwt = map last . sort . rotate step :: (Ord x) => [x] -> [[x]] -> [[x]] step xs = zipWith (:) xs . sort inv_bwt :: (Ord x) => x -> [x] -> [x] inv_bwt mark xs = head . filter (\xs -> head xs == mark) . head . drop ((length xs) - 1) . iterate (step xs) . map (\x -> [x]) $ xs My my, isn't that SO much shorter? I love Haskell! :-D Unfortunately, the resident C++ expert fails to grasp the concept of "example code", and insists on comparing the efficiency of this program to the C one on the website. Fact is, he's translated the presented C into C++, and it can apparently transform a 145 KB file in 8 seconds using only 3 MB of RAM. The code above, however, took about 11 seconds to transform 4 KB of text, and that required about 60 MB of RAM. (I tried larger, but the OS killed the process for comsuming too much RAM.) Well anyway, the code was written for simplicity, not efficiency. I've tried to explain this, but apparently that is beyond his comprehension. So anyway, it looks like we have a race on. >:-D The first thing I did was the optimisation mentioned on Wikipedia: you don't *need* to build a list of lists. You can just throw pointers around. So I arrived at this: module BWT2 (bwt) where import Data.List rotate :: Int -> [x] -> Int -> [x] rotate l xs n = (drop (l-n) xs) ++ (take (l-n) xs) bwt xs = let l = length xs ys = rotate l xs in map (last . rotate l xs) $ sortBy (\n m -> compare (ys n) (ys m)) [0..(l-1)] This is indeed *much* faster. With this, I can transform 52 KB of text in 9 minutes + 60 MB RAM. The previous version seemed to have quadratic memory usage, whereas this one seems to be linear. 52 KB would have taken many months with the first version! Still, 9 minutes (for a file 3 times smaller) is nowhere near 8 seconds. So we must try harder... For my next trick, ByteStrings! (Never used them before BTW... this is my first try!) module BWT3 (bwt) where import Data.List import qualified Data.ByteString as Raw rotate :: Int -> Raw.ByteString -> Int -> Raw.ByteString rotate l xs n = (Raw.drop (l-n) xs) `Raw.append` (Raw.take (l-n) xs) bwt xs = let l = Raw.length xs ys = rotate l xs in Raw.pack $ map (Raw.last . rotate l xs) $ sortBy (\n m -> compare (ys n) (ys m)) [0..(l-1)] Now I can transform 52 KB in 54 seconds + 30 MB RAM. Still nowhere near C++, but a big improvement none the less. Woah... What the hell? I just switched to Data.ByteString.Lazy and WHAM! Vast speed increases... Jeepers, I can transform 52 KB so fast I can't even get to Task Manager fast enough to *check* the RAM usage! Blimey... OK, just tried the 145 KB test file that Mr C++ used. That took 2 seconds + 43 MB RAM. Ouch.

12 21

Re: practicality of typeful programming
by oleg＠pobox.com 08 Jul '07

08 Jul '07

Daniil Elovkov wrote: > I've recently asked some questions here about some little type hackery > implementing an embedded dsl. But now I wonder if it's worth the > effort at all... Yes it is. Typed embedded DSL are quite useful and widely used. For example, Lava (high-level hardware description language) uses phantom types to prevent the designer from building meaningless circuits (e.g., connecting a Bool and an Int wires). http://citeseer.ist.psu.edu/69503.html There are other such hardware design languages which profitably use types (which ought to be popularized more). Using types can decrease the amount of error checking in the implementation. I highly recommend the following _very_ good thesis on this topic: Morten Rhiger Higher-Order Program Generation http://www.brics.dk/DS/01/4/index.html

3 7

Language semantics
by Andrew Coppin 08 Jul '07

08 Jul '07

I have a tricky little question... Suppose I write a function like this: foo pattern1 | gard1 = ... | gard2 = ... foo pattern2 | gard3 = ... | gard4 = ... According to one tutorial I read, if pattern1 matches, pattern2 will never be tried, even if both guard1 and guard2 fail. And according to another tutorial I read, if pattern1 matches but all guards fail, pattern2 *will* be tried. Can somebody comfirm which one is actually correct?

10 25

Abstraction leak
by Andrew Coppin 06 Jul '07

06 Jul '07

...and again today I found myself trying to do something that would be very easy in an imperative language, but I cannot think of a single good way of doing it in Haskell. Hopfully somebody can give me some hints. I'm writing a whole bunch of data compression programs. In particular, one of them was a Huffman encoder. The encoder scans the input file, computes symbol frequencies, and builds a canonical Huffman table, which it then dumps to file. The actual compressed data goes after that. The encoder consists of two functions. One takes the Huffman table and serializes it. The other does the actual encoding. The (++) operator joins the two together before going to file. Getting the data back is mildly more tricky. There's a decoder function that takes the complete data stream, parses out the Huffman table, and returns a pair containing the Huffman table and the remaining data. Then a second decoder function actually does the Huffman decoding on this data. So far, it's all pretty easy. The size of the Huffman table determins how many bytes the decoder needs to read, so it's easy to figure out where the table ends. And then I had a brainwave. I altered the encoder so that the output from the Huffman table serialize function codes through a simple RLE encoder before going to file. Then a went and altered the decoder to... uh... oops. Now I have a problem. It's easy enough to pass the entire data stream through an RLE decoder and feed that to the Huffman table deserialize function, and it will give be back the table. But I now have *no clue* where the table ends in the original stream! If this was Java, you would write all these compression and decompression stages as stream wrappers. So you wrap the raw input stream with an RLE decoder, have the function read the Huffman table, and then take off the RLE decoder and process the rest of the stream. However, in Haskell, the reading and deserializing of the Huffman table doesn't so anything detectable to the original data stream, so you can't tell how much of it the RLE decoder actually processed. Um... help! (What I did in the end was to write the size of the RLE encoded Huffman table to the file and read it back in the decoder. But this shouldn't actually be necessary...)

21 62

update on SoC projects?
by brad clawsie 06 Jul '07

06 Jul '07

does anyone have any interesting update info on the haskell SoC (summer of code) projects? in particular i am intersted in the haskell bindings to libcurl

4 3

Parsers are monadic?
by Gregory Propf 05 Jul '07

05 Jul '07

First post. I'm a newbie, been using Haskell for about a week and love it. Anyway, this is something I don't understand. Parsers are monadic. I can see this if the parser is reading from an input stream but if there's just a block of text can't you just have the parser call itself recursively feeding the unparsed text down the recursion and tacking nodes onto the tree as the recursions return, finally returning the whole tree to the top level caller. Seems this meets the criteria for pure functionality, same result every time with same args. myParser :: [Char] -> ParseTree ____________________________________________________________________________________ Get the free Yahoo! toolbar and rest assured with the added security of spyware protection. http://new.toolbar.yahoo.com/toolbar/features/norton/index.php

13 21

XmlSerializer.deserialize?
by Hugh Perkins 02 Jul '07

02 Jul '07

5 14

Tree Guidance
by Hans van Thiel 02 Jul '07

02 Jul '07

Hello All, Both CFP and SOE have chapters on trees and there is a standard library Data.Tree. I expected to find all kinds of functions there, as in Data.List, but instead the functions are defined as instances of more general structures. It uses: import Control.Applicative (Applicative(..), (<$>)) import Control.Monad import Data.Monoid (Monoid(..)) import Data.Sequence (Seq, empty, singleton, (<|), (|>), fromList, ViewL(..), ViewR(..), viewl, viewr) import Data.Foldable (Foldable(foldMap), toList) import Data.Traversable (Traversable(traverse)) import Data.Typeable When looking at those it is not clear (to me) what those all mean and I have not been able to find much on the WiKi either. Could someone with more experience provide some guidance on how to learn to use these libraries (and ultimately on the tree type in Data.Tree, which is what I want). There is a Zipper Monad with defined functions, which look promising, but I have not heard of this before, and it appears not to be standard. http://www.haskell.org/haskellwiki/Zipper_monad/TravelBTree http://www.haskell.org/haskellwiki/Zipper_monad Does anybody have any experience with these libraries they could share? Ideally I would want a N-ary tree, where the branches are what's actually the represented data, and so I would like to access it both from the root and the leaves. In an imperative language I would just add an up-pointer in each node, but I have no idea how expensive this would be in Haskell, or if it's necessary at all. Many thanks for your help, Hans van Thiel

4 7

Re: [Haskell-cafe] Re: Parsers are monadic?
by Gregory Propf 02 Jul '07

02 Jul '07

Thanks, that was helpful. I didn't realize that there were pure functional monads. ---------------------------------------------------------- "Monadic" just means a calculation using a mathematical structure called a monad. All impure calculations in Haskell are monadic, but not all monadic calculations are impure. Does this answer your question? --Eric _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ____________________________________________________________________________________ Be a better Globetrotter. Get better travel answers from someone who knows. Yahoo! Answers - Check it out. http://answers.yahoo.com/dir/?link=list&sid=396545469

3 2