June 2007 - Haskell-Cafe

String Hashing
by Thomas Conway 19 Jun '07

19 Jun '07

Hi All, I'm trying to figure out how to maximum performance out of one of my inner loops which involves string hashing. Consider the following hash function, which is a transliteration of a good one written in C: --8x--8x--8x--8x--8x--8x--8x--8x--8x module HashStr where import Data.Bits import Data.ByteString as BLOB import Data.Word data Triple = Triple !Word64 !Word64 !Word64 hashStr :: ByteString -> Word64 hashStr str = hashBlock (Triple gold gold gold) str where gold = 0x9e3779b97f4a7c13 hashBlock (Triple a b c) str | BLOB.length str > 0 = hashBlock (mix (Triple a' b' c')) rest | otherwise = c where a' = a + BLOB.foldl' make 0 (slice 0) b' = b + BLOB.foldl' make 0 (slice 1) c' = c + BLOB.foldl' make 0 (slice 2) make x w = (x `shiftL` 8) + fromIntegral w slice n = BLOB.take 8 $ BLOB.drop (8 * n) str rest = BLOB.drop 24 str mix :: Triple -> Triple mix = (\(Triple a b c) -> Triple (a - c) b c) . (\(Triple a b c) -> Triple (a `xor` (c `shiftR` 43)) b c) . (\(Triple a b c) -> Triple a (b - c) c) . (\(Triple a b c) -> Triple a (b - a) c) . (\(Triple a b c) -> Triple a (b `xor` (a `shiftL` 9)) c) . (\(Triple a b c) -> Triple a b (c - a)) . (\(Triple a b c) -> Triple a b (c - b)) . (\(Triple a b c) -> Triple a b (c `xor` (b `shiftR` 8))) . (\(Triple a b c) -> Triple (a - b) b c) . (\(Triple a b c) -> Triple (a - c) b c) . (\(Triple a b c) -> Triple (a `xor` (c `shiftR` 38)) b c) . (\(Triple a b c) -> Triple a (b - c) c) . (\(Triple a b c) -> Triple a (b - a) c) . (\(Triple a b c) -> Triple a (b `xor` (a `shiftL` 23)) c) . (\(Triple a b c) -> Triple a b (c - a)) . (\(Triple a b c) -> Triple a b (c - b)) . (\(Triple a b c) -> Triple a b (c `xor` (b `shiftR` 5))) . (\(Triple a b c) -> Triple (a - b) b c) . (\(Triple a b c) -> Triple (a - c) b c) . (\(Triple a b c) -> Triple (a `xor` (c `shiftR` 35)) b c) . (\(Triple a b c) -> Triple a (b - c) c) . (\(Triple a b c) -> Triple a (b - a) c) . (\(Triple a b c) -> Triple a (b `xor` (a `shiftL` 49)) c) . (\(Triple a b c) -> Triple a b (c - a)) . (\(Triple a b c) -> Triple a b (c - b)) . (\(Triple a b c) -> Triple a b (c `xor` (b `shiftR` 11))) . (\(Triple a b c) -> Triple (a - b) b c) . (\(Triple a b c) -> Triple (a - c) b c) . (\(Triple a b c) -> Triple (a `xor` (c `shiftR` 12)) b c) . (\(Triple a b c) -> Triple a (b - c) c) . (\(Triple a b c) -> Triple a (b - a) c) . (\(Triple a b c) -> Triple a (b `xor` (a `shiftL` 18)) c) . (\(Triple a b c) -> Triple a b (c - a)) . (\(Triple a b c) -> Triple a b (c - b)) . (\(Triple a b c) -> Triple a b (c `xor` (b `shiftR` 22))) --8x--8x--8x--8x--8x--8x--8x--8x--8x Obviously, we'd like all those lambdas and composes to be inlined, along with all the intermediate Triple structures. So, how do you convince ghc to do this? Alternatively, how would you *translate* rather than transliterate, the mix function? -- Dr Thomas Conway drtomc(a)gmail.com Silence is the perfectest herald of joy: I were but little happy, if I could say how much.

6 12

Re: [Haskell-cafe] embedded build language?
by Tomasz Zielonka 19 Jun '07

19 Jun '07

[I hope you don't mind that I send this letter to haskell-cafe too. I thought someone else might be interested.] On Mon, Jun 18, 2007 at 10:52:40AM -0700, Greg Fitzgerald wrote: > >first let's see if anybody likes the general idea > Would you mind describing the role of Depends.hs in your architecture? After parsing the target file name, you have to list the files this target depends on. This list is used by the engine to check if a rebuild is neccesary, or if some required files are missing. To add a file to the dependency list, you call "require" in Depends monad. "require" returns the file name it was given, so you can do things like: matchExact "prog" $ do o_files <- sequence [ require "a.o" , require "b.o" , require "c.o" ] return $ do system ("gcc -o prog " ++ unwords o_files) The Writer part of the Depends is used to gather the list. In the example above, you could also use listen: listen :: (MonadWriter w m) => m a -> m (a, w) but I'm not sure if it's good to expose the MonadWriter interface. I think I will provide my version of listen in Depends anyway. The Reader part is currently used for a very simple thing - it supplies the target name as a hidden parameter. This allows for an easy way to get the target name regardless of the matching mechanism used. > How did you decide on using the Reader and Writer monads? This was the most natural, and the easiest, choice. > If you have multiple matching rules, should one take precedence? Right now in such situation an error will be raised. This of course may be insufficient in some cases. Depending on the circumstances, you may want to: - raise an error (like now) - choose one of the rules, perhaps based on some priorities or policies, like "most specific first" - merge the rules, somehow I haven't thought about those issues too much, but I would prefer to allow the rule author to decide. Best regards Tomek

1 0

IDE?
by bf3＠telenet.be 19 Jun '07

19 Jun '07

I've searched the internet for an Haskell IDE that supports the following: - syntax highlighting - cross module refactoring - quick navigation (goto symbol, goto instance, find usages, etc) - code completion - "debugging" (not imperative debugging, so no breakpoints, but just plugging in a visualizer/pretty printer for a function in a separate dedicated window, like what http://www.apple.com/shake does on each "node") So a bit what Jetbrains Resharper does for Visual Studio, but for Haskell. IntelliJ and Eclipse also do this for Java. This does not seem to exist? If this is correct, this is a real shame, because although I read that the productivity increases a lot when correctly using Haskell, it would increase even more when such an IDE is available. Any help to find an IDE that comes closest to these features would be much appreciated. Thanks, Peter

22 50

Efficient signal processing
by Henning Thielemann 19 Jun '07

19 Jun '07

I always thought that signal processing must be a good benchmark for compiler optimizations and optimizer rules of libraries like 'binary' and 'fps'. Many signal processing functions process a signal from the beginning to the end with a little of state, thus in many cases I expect that they can be translated to simple loops. However, I still cannot get the necessary speed for real-time processing out of 'binary' and 'fps'. In my setup a signal is of type [Double]. After a series of sound transformations a signal is finally converted to [Int16] and then to ByteString. Can I expect that interim signals represented as lists are optimized away? I have simple example which writes zeros to disk. The content of the first file is created by ByteString.replicate for the purpose of comparison with the second file. With the second file I want to check the speed of the conversion from [Int16] to ByteString. module Main (main) where import System.Time (getClockTime, diffClockTimes, tdSec, tdPicosec) import qualified Data.ByteString.Lazy as B import qualified Data.Binary.Put as Bin import Foreign (Int16) signalToBinaryPut :: [Int16] -> B.ByteString signalToBinaryPut = Bin.runPut . mapM_ (Bin.putWord16host . fromIntegral) writeSignalBinaryPut :: FilePath -> [Int16] -> IO () writeSignalBinaryPut fileName = B.writeFile fileName . signalToBinaryPut measureTime :: String -> IO () -> IO () measureTime name act = do putStr (name++": ") timeA <- getClockTime act timeB <- getClockTime let td = diffClockTimes timeB timeA print (fromIntegral (tdSec td) + fromInteger (tdPicosec td) * 1e-12 :: Double) numSamples :: Int numSamples = 1000000 zeroSignal16 :: [Int16] zeroSignal16 = replicate numSamples 0 zeroByteString :: B.ByteString zeroByteString = B.replicate (fromIntegral (2 * numSamples)) 0 main :: IO () main = do measureTime "write zero bytestring" (B.writeFile "zero-bytestring.sw" zeroByteString) measureTime "put zero int16" (writeSignalBinaryPut "zero-int16string.sw" zeroSignal16) The program is compiled with GHC-6.4 and option -O2, CPU clock 1.7 GHz. This yields: $ speedtest write zero bytestring: 2.5674e-2 put zero int16: 1.080541 That is, not using ByteString.replicate and converting from [Int16] to ByteString slows down computation by a factor of 40. What am I doing wrong?

3 4

Re: [Haskell-cafe] IDE?
by Andrew Coppin 19 Jun '07

19 Jun '07

Mark T.B. Carroll wrote: > Are KWrite and Kate something to do with KDE or something? One of the > first things I do with a new Linux install is to dump all the KDE and > Gnome stuff on the basis that it's an enormous amount of bloatware for > little gain. Others may think differently! (-: > Yeah, that'll be it then. ;-) Gnome and KDE are both rather bloated... Unfortunately, nothing better exists. :-( But then, the entire Linux world is too messy for me... hence my request for a petter OS.

4 4

Announce: New York Functional Programmers Meetup
by Brian Hurt 18 Jun '07

18 Jun '07

I'd like to announe the New York Functional Programmers Meetup, which is Wednesday, June 27th, 7PM, at the offices of Jane Street Capital. The NYFP meetup is for people using or interested in strongly typed functional languages, such as Haskell, Ocaml, SML, etc. Meeting details are here: http://lisp.meetup.com/59/ (sorry about the Lisp category- it's the closest thing Meetup has to "Functional Programmers"). Brian

1 0

Re: [Haskell-cafe] IDE?
by Michael T. Richter 18 Jun '07

18 Jun '07

On Sun, 2007-17-06 at 20:27 -0300, Alex Queiroz wrote: > Albeit buttons are mostly a waste of time because the keyboard is > so much more powerful, For a very small percentage of users, yes. For the vast majority, not even close. > nice and beautiful fonts are really a must. > Fortunately Emacs have them, as the attached screenshot demonstrates. Screenshots are worthless if they don't match my screen, aren't they? I guess I can open up exactly the same file that's in your screenshot and then use your screenshot as a background to my screen so I have the illusion of decent fonts, but that's not exactly a productive environment now, is it? -- Michael T. Richter <ttmrichter(a)gmail.com> (GoogleTalk: ttmrichter(a)gmail.com) Experts in advanced countries underestimate by a factor of two to four the ability of people in underdeveloped countries to do anything technical. (Charles P Issawi)

6 6

Re: [Haskell-cafe] IDE?
by Andrew Coppin 18 Jun '07

18 Jun '07

Mark T.B. Carroll wrote: > Andrew Coppin <andrewcoppin(a)btinternet.com> writes: > (snip) > >> KWrite and/or Kate are almost always installed when you play with >> somebody's Linux box. Emacs virtually never is. >> > (snip) > > Hmmmm. Exactly the opposite seems to be true on mine. (-: > Really? Mmm... perhaps it's distro-specific or something. *shrugs*

1 0

drscheme as haskell IDE?
by Vikrant 18 Jun '07

18 Jun '07

Hi, I see that drscheme has support for various dialects of lisps. It also supports algol! is it possible to add support for haskell in drscheme? or is there any IDE like drscheme for haskell? == Vikrant

1 0

Re: [Haskell-cafe] IDE?
by Donnchadh Ó Donnabháin 17 Jun '07

17 Jun '07

Hi Peter, I'm also just starting to learn Haskell and tried the eclipsefp eclipse plugin [1] (since my day job is java development). It seems a little basic at the moment, but judging from this blog [2] it seems to have a lot of potential. In fact part of the project seems to be to allow the development of eclipse plugins written in haskell, which could allow the possibility of integrating some of the tools listed on the haskell wiki with it. I also tried eclipsedarcs [3] for darcs repository access but it only really seems to work with local repositories. Donnchadh [1] http://eclipsefp.sourceforge.net/haskell/index.html [2] http://cohatoe.blogspot.com/ [3] http://eclipsedarcs.org/doku.php

2 2