- Haskell - Haskell.org

Performance, Optimization and Code Generation
by George Beshers 26 Sep '06

26 Sep '06

This starts out with my being interested in darcs <-> git related issues. Since git uses sha1 I wanted to have the ability to calculate sha1 in an application where I was intending to use darcs as a back-end. The performance gap is > * 30 between Haskell and sha1sum. That seemed rather steep and so I started looking... Using ghc 6.4.2 The following code is from SHA1: -- {-# INLINE step #-} step :: ABCDE -> BS.ByteString -> ABCDE step abcde0@(ABCDE a b c d e) words = abcde5 where s16 = get_word_32s words s80 = s16 ++ (zipWith4 f0) (drop 13 s80) (drop 8 s80) (drop 2 s80) s80 f0 a b c d = rotL (a `xor` b `xor` c `xor` d) 1 (s20_0, s60) = splitAt 20 s80 (s20_1, s40) = splitAt 20 s60 (s20_2, s20) = splitAt 20 s40 (s20_3, _) = splitAt 20 s20 abcde1 = foldl (doit f1 0x5a827999) abcde0 s20_0 abcde2 = foldl (doit f2 0x6ed9eba1) abcde1 s20_1 abcde3 = foldl (doit f3 0x8f1bbcdc) abcde2 s20_2 ABCDE a' b' c' d' e' = foldl (doit f2 0xca62c1d6) abcde3 s20_3 f1 (XYZ x y z) = (x .&. y) .|. ((complement x) .&. z) f2 (XYZ x y z) = x `xor` y `xor` z f3 (XYZ x y z) = (x .&. y) .|. (x .&. z) .|. (y .&. z) abcde5 = ABCDE (a + a') (b + b') (c + c') (d + d') (e + e') -- {-# INLINE get_word_32s #-} get_word_32s :: BS.ByteString -> [Word32] get_word_32s s = map f [0..15] where f i = foldl (+) 0 $ map (\n -> toEnum (fromEnum (BS.index s (i*4+n))) `shiftL` (8 * (3-n))) [0..3] -- {-# INLINE doit #-} doit :: (XYZ -> Word32) -> Word32 -> ABCDE -> Word32 -> ABCDE doit f k (ABCDE a b c d e) w = ABCDE a' a (rotL b 30) c d where a' = rotL a 5 + f (XYZ b c d) + e + w + k -- {-# INLINE rotL #-} rotL :: Word32 -> Rotation -> Word32 rotL a s = shiftL a s .|. shiftL a (s-32) -- rotL a s = a `seq` rotate a s I want to focus on the *rotL* function --- get_word_32s might be faster with a rewrite. Using -prof -auto-all and -P at runtime produced the following summary... COST CENTRE MODULE %time %alloc ticks bytes get_word_32s MySHA1 39.3 35.0 10597 6952614960 rotL MySHA1 22.6 18.5 6089 3682275072 step MySHA1 21.2 24.1 5701 4783669848 doit MySHA1 16.2 21.8 4362 4332088320 As part of a larger program, but the sha1 portion was where 98% of the time went. So * I tried using the built-in "rotate", * I tried inlining, * I tried using -fasm directly * I tried generating C with -O2, * I tried using 'seq' in a number of places. None of this made much difference. Comment, the C code for just rotL would be unsigned int rotate(unsigned int a, int b) { return (a << b) | (a >> (b - 32)); } and the assembler at gcc -O2 is concise and straightforward: .file "rotate.c" .text .p2align 4,,15 .globl rotate .type rotate, @function rotate: pushl %ebp movl %esp, %ebp movl 8(%ebp), %edx movl 12(%ebp), %ecx popl %ebp movl %edx, %eax sall %cl, %eax subl $32, %ecx shrl %cl, %edx orl %edx, %eax ret .size rotate, .-rotate .section .note.GNU-stack,"",@progbits .ident "GCC: (GNU) 3.3.5 (Debian 1:3.3.5-3)" GHC's code on this part is nothing like competitive because of the need for closures --- I think. 1) What approaches to getting the compiler to optimize have I overlooked? Or, how would you change the code to get the compiler to generate better code for rotL? 2) Am I missing an easy way to get strictness on the rotL function? 3) Is there something I am missing that keeps ghc's code from becoming about as concise as gcc -O2? 4) Is the code generator simply not able to handle this? Thanks in advance, George

4 3

Repeated evaluation of a constant value.
by Paul Johnson 26 Sep '06

26 Sep '06

I recently wanted to pass a lookup table around a program. Rather than having something explicitly typed as Map.Map I wrote a function that assembled a Map and then used Map.lookup to return a function, like this: > module Main where > > import qualified Data.Map as Map > import Debug.Trace > > alist :: [(String, Integer)] > alist = map (\i -> (show i, i)) [1..100] > > table :: [(String, Integer)] -> String -> Maybe Integer > table ls str = Map.lookup str fm > where fm = trace "Trace: making the map" $ Map.fromList ls "table" can be seen as a function from an association list to a look-up function. > demo :: [(String, Integer)] -> IO () > demo ls = do > showLookup "5" > showLookup "70" > showLookup "164" > showLookup "wibble" > where > func = table ls > showLookup str = > putStrLn $ "Look up " ++ show str ++ " gives " ++ > show (func str) ++ "." > > main :: IO () > main = demo alist I reasoned that closure returned by "table ls" would contain a thunk for "fm", which in turn would be evaluted the first time it was called. But it isn't: instead "fm" gets evaluated for every call to "table", as shown by the repeated trace messages. Store this message as "Thunk.lhs". Compile with ghc -O2 and run "main". What you get is: Trace: making the map Look up "5" gives Just 5. Trace: making the map Look up "70" gives Just 70. Trace: making the map Look up "164" gives Nothing. Trace: making the map Look up "wibble" gives Nothing. So my question is: how do I write "table" to return a function which does not build the lookup table for every call? Or is this a bug in GHC? (I should add that my real "table" function is rather more complicated, and only invokes Map.lookup on a subset of its arguments.) Paul.

3 3

Integrated Formal Methods 2007: First call for technical papers
by Jeremy.Gibbons＠comlab.ox.ac.uk 26 Sep '06

26 Sep '06

IFM 2007 Sixth International Conference on Integrated Formal Methods 2nd - 6th July 2007, Oxford, UK http://www.ifm2007.org First Call for Technical Papers The design and analysis of computing systems presents a significant challenge: systems need to be understood at many different levels of abstraction, and examined from many different perspectives. Formal methods---languages, tools, and techniques with a sound, mathematical basis---can be used to develop a thorough understanding, and to support rigorous examination. However, further research into effective integration is required if these methods are to have a significant impact outside academia. The IFM series of conferences seeks to promote that research, to bring together the researchers carrying it out, and to disseminate the results of that research among the wider academic and industrial community. Original, technical contributions are invited in all aspects of formal methods integration, including: * the application of one or more formal methods as an integral part of a process of analysis or design * the development or extension of one method, based upon the inclusion of ideas or concepts from others * the addition of formality to informal or semi-formal modelling languages, tools, or techniques * the combination of different formal methods, in terms of semantic integration or practical application The programme of accepted contributions will be supported by a series of workshops and tutorials, including a doctoral symposium. Important dates: The deadline for full paper submission is January 29th, 2007. Authors will be notified on or before March 19th, 2007. Details of the electronic submission process will be made available at the conference website. Conference location: IFM 2007 will be held at St Anne's College, Oxford: one of the larger colleges of the University, with excellent facilities for conferences and workshops. Additional facilities will be available in the new Computing Laboratory building, less than 5 minutes' walk from the College grounds. Oxford is easily reached from most UK cities, and is 70 minutes from the country's largest airport. Programme committee: Didier Bert, Institute IMAG, Grenoble, France Eerke Boiten, University of Kent, UK Jonathan Bowen, Museophile Ltd, UK Michael Butler, University of Southampton, UK Paul Curzon, Queen Mary, University of London, UK Jim Davies, University of Oxford, UK John Derrick, University of Sheffield, UK Steve Dunne, University of Teesside, UK Andy Galloway, University of York, UK Chris George, United Nations University, Macau Jeremy Gibbons, University of Oxford, UK Wolfgang Grieskamp, Microsoft Research, Redmond, US Henri Habrias, University of Nantes, France Maritta Heisel, University of Magdeburg, Germany Soon-Kyeong Kim, University of Queensland, Australia Michel Lemoine, ONERA, Toulouse, France Shaoying Liu, Hosei University, Tokyo, Japan Dominique Mery, LORIA, France Stephan Merz, LORIA, France Richard Paige, University of York, UK Luigia Petre, Turku Centre for Computer Science, Finland Jaco van de Pol, Centre for Mathematics and Computer Science, The Netherlands Judi Romijn, Eindhoven University of Technology, The Netherlands Thomas Santen, Technical University of Berlin, Germany Steve Schneider, University of Surrey, UK Wolfram Schulte, Microsoft Research, Redmond, US Kaisa Sere, Abo Akademi University, Turku, Finland Jane Sinclair, University of Warwick, UK Graeme Smith, University of Queensland, Australia Jin Song Dong, National University of Singapore Bill Stoddart, University of Teesside, UK Kenji Taguchi, National Institute of Informatics, Japan Helen Treharne, University of Surrey, UK Heike Wehrheim, University of Paderborn, Germany Kirsten Winter, University of Queensland, Australia Jim Woodcock, University of York, UK

1 0

ANN: HAppS version 0.8.2
by Einar Karttunen 25 Sep '06

25 Sep '06

We are pleased to announce HAppS -- Haskell Application Server version 0.8.2. HAppS is a Haskell web application server for building industrial strength Internet applications safely, quickly, and easily. With HAppS you focus entirely on application functionality implemented in your favorite language and you don't have to worry about making sure all sorts of server subsystems are functioning properly. This release has the following highlights: * Switch to BSD3 license. * Support for new ByteString. * Support GHC 6.6 (using the HAppS.cabal.ghc66) * Good support for cookies. * Revise HAppS.DNS and make it easier to access from the outside. * Much faster URI parsing. * Many internal changes to HTTP and Saver implementations. * Add new examples: cookie, dns, http. HAppS can be obtained from http://happs.org/ or directly from: * http://happs.org/auto/HAppS-0.8.2.tar.gz * darcs get --partial --tag=HAppS-0.8.2 http://happs.org/HAppS Einar Karttunen, Alex Jacobson, David Himmelstrup

1 0

BitSyntax for Haskell
by Adam Langley 23 Sep '06

23 Sep '06

Erlang's bit syntax[1] is a great for building and breaking up binary structures. I've knocked up something similar (although a little clumsy) for Haskell: http://www.imperialviolet.org/binary/bitsyntax/ http://www.imperialviolet.org/binary/bitsyntax/BitSyntax.hs I'm sure that this isn't the best possible way to do this, but it suffices at this stage for many problems. [1] http://www.erlang.org/doc/doc-5.4.12/doc/programming_examples/bit_syntax.ht… -- Adam Langley agl(a)imperialviolet.org

1 0

ANNOUNCE: Dr Haskell 0.1
by Neil Mitchell 23 Sep '06

23 Sep '06

Hi Haskell, This is the first release of Dr Haskell, a tool to help suggest improvements to your code. GETTING DR HASKELL See http://www-users.cs.york.ac.uk/~ndm/projects/drhaskell.php for details on how to download and install the program. There are prebuilt Windows binaries. This project requires Yhc to be installed and working, of which there are also prebuilt binaries (see the above web page for pointers). This program should work fine on Linux/Mac etc, provided you first have Yhc installed. AN EXAMPLE SESSION Imagine you have a program, and somewhere deep inside the program it has the expression: take 5 (repeat '!') An experienced Haskell user might realise that this is in fact replicate, but a beginner has no way of discovering this function for themselves, besides reading the standard libraries! Put that definition in a Haskell source file, say Test.hs, then run: > drhaskell Test.hs I can apply use_replicate in check_elem (5:10-6:80) Dr Haskell gives a suggestion (use_replicate) to a specific function (check_elem) and a given source location (line 5, column 10) Of course, they might have written take 5 $ repeat '!', or take n . repeat, or quite a few other variations. Dr Haskell can see through these things nicely. Of course, Dr Haskell can make more powerful suggestions, for example: if f x then 4 else if g x then 4 else primes !! 10 And Dr Haskell will suggest you use f x || g x instead The hints are isolated from the program, and can be easily changed by the user. More hint patches are most welcome. See http://www.cs.york.ac.uk/fp/darcs/drhaskell/Hints.hs for a list of the hints currently available in the code. LIMITATIONS Requires a working copy of Yhc. You must first have your program/file successfully compiling with Yhc. Once you have got over the admin side (compiling etc, invoking correctly), the actual hint algorithm is pretty robust. Bug reports/suggestions/patches most welcome. YHC INFORMATION Home page: http://haskell.org/haskellwiki/Yhc Build details: http://haskell.org/haskellwiki/Yhc/Building Windows snapshot: http://haskell.org/haskellwiki/Yhc/Snapshots If Yhc won't build for you, or you have other difficulties, please bug the Yhc Team on their mailing list, yhc -at- haskell -dot- org. Thanks Neil

1 0

ANNOUNCE: new release of Hugs
by Ross Paterson 23 Sep '06

23 Sep '06

We are pleased to announce a new minor release of Hugs, fixing a few bugs with the May 2006 release, and with libraries roughly matching the forthcoming GHC 6.6 release. It is available from the Hugs page: http://www.haskell.org/hugs/ As with the May 2006 release, two sizes of the Windows distribution and two sizes of source distribution are available for download. Distributions for other platforms will be linked to when they are provided by third parties. Packagers can choose between an omnibus package and a more modular arrangement.

3 2

Implicit type of numeric constants
by Robert Stroud 22 Sep '06

22 Sep '06

Hello, I'm a newcomer to Haskell and I've been typing some simple expressions into Hugs in an attempt to understand how the built-in numeric types work . However, I'm puzzled by the following example: k = 2 f :: Int -> Int -> Int f x y = x * y After loading a file containing this code into Hugs, if I type "f 2 2" I get the value 4 as expected, but if I type "f k k" I get a type error because the type of k is inferred to be Integer. This seems like a violation of referential transparency to me - I would expect the inferred type of k to be the same as the type of 2. However, if I type an apparently equivalent let expression into Hugs directly, then I get the value 4 as expected let k = 2 ; f :: Int -> Int -> Int ; f x y = x * y in f k k Why is there a difference in behaviour? For that matter, if the type of 2 is "Num a => a", which I understand to mean "an arbitrary numeric type", why is it OK to pass 2 to a function that expects an Int? Thank you. Robert Stroud

4 12

excel crashes when using dll
by nikunj 22 Sep '06

22 Sep '06

I have created a dll that works perfectly in the debug mode. But when i try to build it for release or for that matter even use the debug version of the library on any other computer without the debug excel crashes and gives me the "excel has encountered a problem window". do any of you guys have any ideas what might be the reason? regards nikunj -- View this message in context: http://www.nabble.com/excel-crashes-when-using-dll-tf2319001.html#a6451273 Sent from the Haskell - Haskell mailing list archive at Nabble.com.

1 0

Re[2]: [Haskell-cafe] Re: Haskell web forum
by Bulat Ziganshin 21 Sep '06

21 Sep '06

This message (from haskell-cafe) by Kurt Hutchinson exactly explains that i want and why i propose do to it. sorry for inconvenience, i don't propose to stop mail lists and plan to present in both medias (while others will continue to use irc, blogs, LJs, rss feeds and all other ways to let Haskell rule the world :) > I was just about to ask the same thing. Clearly, some prefer email > and some prefer web forums. This is undoubtably true of new Haskell > users with questions, as well. Let those interested in a web forum > set one up and run it. Those interested in email can ignore the web > forum. The Perl community has a similar setup with the popular > Perlmonks web forum, and their hundreds of mailing lists. There are > many users who read and post on both, and many who do not. > I believe Bulat was just trying to find out if anyone else would like > to help set one up, not suggesting that it replace the mailing lists. Thank you, Kurt, for detailed explanation -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

1 0