- Haskell-Cafe - Haskell.org

Optimization help needed
by Joel Reymont 24 Dec '05

24 Dec '05

Folks, These functions together can be taking 15-20% of my processing time. I'm trying to optimize the hell out of them. Would it be less expensive to convert each of them into a foreign function? Is there a way to optimize them further within Haskell? appU_wstr is particularly expensive and deals with reversing the words in a unicode string received little-endian. Thanks, Joel P.S appP_wstr :: Ptr Word8 -> Int -> String -> IO Int appP_wstr ptr ix [] = pickle short ptr ix 0 appP_wstr ptr ix a = do ix1 <- foldM (\ix' c -> pickle endianW16 ptr ix' $ word c) ix a pickle short ptr ix1 0 where word c = fromIntegral $ ord c appU_wstr :: Ptr Word8 -> Int -> IO (String, Int) appU_wstr ptr ix = do (a, ix1) <- unpickle endianW16 ptr ix appU_wstr' ix1 a [] where appU_wstr' ix 0 acc = return $!! (reverse acc, ix) appU_wstr' ix x acc = do (a, ix1) <- unpickle endianW16 ptr ix appU_wstr' ix1 a ((chr $ fromIntegral x):acc) {-# SPECIALIZE swap16 :: Word16 -> Word16 #-} {-# SPECIALIZE swap16 :: Int16 -> Int16 #-} swap16 :: Bits a => a -> a #ifdef BIG_ENDIAN swap16 v = (v `shiftR` 8) .|. (v `shiftL` 8) #else swap16 v = v #endif {-# SPECIALIZE swap32 :: Word32 -> Word32 #-} {-# SPECIALIZE swap32 :: Int32 -> Int32 #-} swap32 :: Bits a => a -> a #ifdef BIG_ENDIAN swap32 v = ( v `shiftR` 24) .|. ((v .&. 0x000000FF) `shiftL` 24) .|. ((v .&. 0x0000FF00) `shiftL` 8) .|. ((v .&. 0x00FF0000) `shiftR` 8) #else swap32 v = v #endif {-# SPECIALIZE swap64 :: Word64 -> Word64 #-} {-# SPECIALIZE swap64 :: Int64 -> Int64 #-} swap64 :: Bits a => a -> a #ifdef BIG_ENDIAN swap64 v = ( v `shiftR` 56) .|. ((v .&. 0x00000000000000FF) `shiftL` 56) .|. ((v .&. 0x00FF000000000000) `shiftR` 40) .|. ((v .&. 0x000000000000FF00) `shiftL` 40) .|. ((v .&. 0x0000FF0000000000) `shiftR` 24) .|. ((v .&. 0x0000000000FF0000) `shiftL` 24) .|. ((v .&. 0x000000FF00000000) `shiftR` 8) .|. ((v .&. 0x00000000FF000000) `shiftL` 8) #else swap64 v = v #endif -- http://wagerlabs.com/

2 2

exuberant-ctags, haskell, vim, tlist plugin
by Marc Weber 24 Dec '05

24 Dec '05

Hi. I'm a happy vim user and enjoyed using the Tlist plugin which shows only the methods and classes described in a file.. But it uses exuberant-ctags to "parse" the files which doesn't support haskell, yet. Has anyone already added haskell support? Is someone else interested? Other solutions perhaps another editor? Here are some screenshots of the tlist plugin for vim: http://www.geocities.com/yegappan/taglist/screenshots.html Marc

4 5

Re: [Haskell-cafe] Substring replacements
by Daniel Fischer 24 Dec '05

24 Dec '05

Hello Bulat, I'm not sure what your point is, let's try to enlighten me. Am Mittwoch, 21. Dezember 2005 16:30 schrieben Sie: > Hello Daniel, > > Wednesday, December 21, 2005, 5:20:18 PM, you wrote: > > DF> ordinarily, on my computer, your version of straightforward is 10-15% > faster DF> than KMP (search-patterns are now supplied on the command line > -- which has DF> no big impact; > > of course. the search pattern can be compiled into the search > algorithm just at the time of program execution. just for example, if > you have code > > main = do [x] <- getArgs > y <- return $ map (\n -> fac $ read x) [1..10^6] > > then `fac $ read x` will be computed just one time. in this time, if > your perform many searches with the same pattern - compiler must > initialize array just one time and use it for all searches > Errrh, what here? If I want to replace each occurence of a pattern within a String, of course I want the arrays built only once, destroying and rebuilding them would be deliberate stupidity, that can't be your point, certainly. And also if we interactively search and replace, as in an editor, we'd hold on to the arrays until we get the message 'no more of that, next pattern'. > > DF> searched string is " able sea..."; all compiled with -O2; > DF> NOINLINE makes no difference -- at least with optimisations on -- > > why? i think that is the right way to check speed of optimized program > without pre-compiling search pattern to search/replace algorithm at > runtime ? What has NOINLINE to do with precompiling the search pattern? BTW, I think, the KMP-algorithm is too large to be inlined anyway (maybe, if we explicitly asked for it), so I wouldn't expect any NOINLINE-effect in the first place. And about RunTimeCompilation, I don't quite understand the Wiki-page, what I imagined might be the point there is that, if I know the search pattern before, I might import the general algorithm, write a function searchReplacePattern = searchReplace "pattern" and the arrays might then be built at compile-time and included in the object code -- but I've no idea whether compilers are clever enough to do that (I believe it should be possible to write compilers which would do that, but is it worth the trouble -- or is that sort of optimisation easy and routinely done?) -- but why that would be called RunTimeCompilation, I cannot imagine. So then, the thing that might make a difference, would be not to give the search pattern at compile-time, which I did. Of course, since we search a long String, the time needed to build the arrays is minute in relation to the time needed to traverse the String, but in the more realistic situation of a shorter String (50 kB instead of 48 MB), it would be significant. > > DF> ; without optimisations, KMP suffers far worse than straightforward). > > this test is meaningless Well, it's not really a test for the algorithm, but for ghc's optimiser and I've forgotten the exact numbers, but KMP compiled without optimisation is much much, much slower than with -O2, so the optimiser does a really great job. > > >> KMP is O(m) while straightforward is O(m*n). > > DF> Where m is the length of the input and n is the length of the > searched-for DF> pattern, I think? > DF> But these are worst-case complexities, I believe, ordinarily, > straightforward DF> will be O(m), too. > > and have longer init time (and take more space), so on typical > searches it will be worser than trivial algorithm I believe you've misread here. I'm saying that while the worst case complexity for the straighforward (or trivial) algorithm is O(n*m) -- as witnessed by my test, which was deliberately designed to be baaaaad for that --, usually, in most real situations, that will have O(m) complexity, too. And I -- like you -- believe that for typical searches the straightforward algorithm will be faster (at least with a clever implementation, like yours). Cheers, Daniel P.S.: I'd really appreciate another attempt at explaining RunTimeCompilation to me (might well be an URL of a paper or something).

1 0

W3C discussion: Principle of Least Power
by Graham Klyne 23 Dec '05

23 Dec '05

There's a possibly-interesting thread running on the W3C TAG mailing list [2] about the "Principle of Least Power" [1], in which Haskell gets a mention. The debate gets kind-of interesting around discussion of analyzability of language expressions vs expressibility, with passing reference to Turing completeness. Intuitively, I've felt that expressions in a pure functional language are easier to analyze than expressions in (say) C or Java, despite them all being fully Turing complete (so no difference in expressive power there). Can it truly be said that it's easier to analyze a functional expression than a C program? What could that actually mean? I feel the discussion is (so far) missing a trick, but I'm not sure what it is. #g -- [1] http://lists.w3.org/Archives/Public/www-tag/2005Dec/0101.html http://lists.w3.org/Archives/Public/www-tag/2005Dec/0113.html http://lists.w3.org/Archives/Public/www-tag/2005Dec/0115.html (etc.) [2] http://web3.w3.org/2001/tag/ http://lists.w3.org/Archives/Public/www-tag/ -- Graham Klyne For email: http://www.ninebynine.org/#Contact

2 1

Substring replacements
by Branimir Maksimovic 23 Dec '05

23 Dec '05

I've finally performed test on amd64 and result is a same as on intel. KMP always wins. So KMP is best suited for non indexed strings and I guess should be used in library as prefered search/replace method. This test favors straightforward search. [bmaxa@devel64 myhaskell]$ time ./KMP Working:seasearch replace able seaseasearch baker seasearch charlie True Done real 0m10.783s user 0m10.769s sys 0m0.016s [bmaxa@devel64 myhaskell]$ time ./straightforward Working:seasearch replace able seaseasearch baker seasearch charlie True Done real 0m11.769s user 0m11.741s sys 0m0.028s [bmaxa@devel64 myhaskell]$ uname -a Linux devel64.office.kom 2.6.14-skas3-v8.2 #2 Fri Nov 11 21:19:36 CET 2005 x86_64 x86_64 x86_64 GNU/Linux Greetings, Bane. _________________________________________________________________ Express yourself instantly with MSN Messenger! Download today it's FREE! http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/

3 8

Vectors in Haskell
by Jeff.Harper＠handheld.com 23 Dec '05

23 Dec '05

Dear Haskell, Most of the time we get along well. But, I'm growing weary of the arguments, fights, and nitpicking when I try to implement new mathematical types and overload your operators. I don't know how to cooperate with your type systems. At moments like this, I think about getting back together with C++. I love you. But, I also love implementing complex numbers, vectors, matrices, and quaternions, and Galois fields. C++ is not nearly as elegant and beautiful as you. But, C++ doesn't complain when I try to do this. Isn't there some way we can work things out so I can implement these types with you? Seriously, I'm trying to implement a vector. I'm starting with vector addition: {- This code is works with Glasgow, ghci, with these options: -fglasgow-exts -fallow-undecidable-instances -fno-monomorphism-restriction -fallow-incoherent-instances -} data Vector a = Vector [a] deriving Show class Add a b c | a b -> c where (.+) :: a -> b -> c instance Add Int Int Int where (.+) x y = x + y instance Add Int Double Double where (.+) x y = (fromIntegral x) + y instance Add Double Int Double where (.+) x y = x + (fromIntegral y) instance Add Double Double Double where (.+) x y = x + y instance (Add a b c) => Add (Vector a) (Vector b) (Vector c) where (.+) (Vector x) (Vector y) = Vector (zipWith (.+) x y) vi1 = Vector [(1::Int)..3] vi2 = Vector [(10::Int),15,2] vd1 = Vector [(1::Double)..3] vd2 = Vector [(10::Double),15,2] test1 = vi1 .+ vi2 test2 = vi1 .+ vd2 test3 = vd1 .+ vi2 test4 = vd1 .+ vd2 v1 = Vector [1,2,3] v2 = Vector [10,15,2] However, it is necessary to explicitly nail down the type of the Vector. v1 and v2 are more general. *Main> :t v1 v1 :: forall a. (Num a) => Vector a *Main> :t v2 v2 :: forall a. (Num a) => Vector a *Main> test2 I'd like for .+ to work with v1 and v2. So, I can use things like Vector [1,2,3] in expressions, instead of Vector[(1::Int),2,3]. However, v1 and v2 do not work with .+ in the code I produced above. Does anyone have any ideas how to make this work? I hoped defining .+ more generally for instances of Num would make my vector addition code work with v1 and v2. My failed attempt involved making the following changes . . . -- I added this instance (Num d) => Add d d d where (.+) x y = x + y -- instance Add Int Int Int where -- (.+) x y = x + y instance Add Int Double Double where (.+) x y = (fromIntegral x) + y instance Add Double Int Double where (.+) x y = x + (fromIntegral y) -- instance Add Double Double Double where -- (.+) x y = x + y When I make these changes and compile, I get the following error messages on the declaration of test1 and test4. . . Vector2.hs:38:12: Overlapping instances for Add (Vector Int) (Vector Int) (Vector Int) arising from use of `.+' at Vector2.hs:38:12-13 Matching instances: Vector2.hs:31:0: instance (Add a b c) => Add (Vector a) (Vector b) (Vector c) Vector2.hs:15:0: instance (Num d) => Add d d d In the definition of `test1': test1 = vi1 .+ vi2 Vector2.hs:41:12: Overlapping instances for Add (Vector Double) (Vector Double) (Vector Double) arising from use of `.+' at Vector2.hs:41:12-13 Matching instances: Vector2.hs:31:0: instance (Add a b c) => Add (Vector a) (Vector b) (Vector c) Vector2.hs:15:0: instance (Num d) => Add d d d In the definition of `test4': test4 = vd1 .+ vd2 I interpret this as saying that the compiler doesn't know if the .+ in "test1 = vi1 .+ vi2" should match the Vector instance or the Num instance. I could understand this if Vector was an instance of class Num. However, this is not the case. I figure either Glasgow has a bug or I don't really understand the error message. I'd be grateful for any suggestions or pointers to information on how to implement vectors (or other mathematical types) so they seamlessly and intuitively work with types, classes and operators already built into Haskell. Or, if someone could point to a more intermediate level book on working with the Haskell type system, that would be great.

6 5

Arrows and pickler combinators
by Joel Reymont 23 Dec '05

23 Dec '05

Folks, I'm trying to monadify the pickler code. sequ below positively looks like >>= but you can't really join both pickle and unpickle into a single monad. I would like to keep the ops together, though, as this allows me a single specification for both pickling and unpickling. Cale suggested that PU is really an arrow in that it supports both input and output. I could not find an example of such an arrow, though. I thought that it could be a "dual arrow" but then could not find a description for one. I would appreciate your suggestions! The original paper is at http:// research.microsoft.com/ ~akenn/fun/picklercombinators.pdf Thanks, Joel P.S. data PU a = PU { appP :: Ptr Word8 -> Int -> a -> IO Int, appU :: Ptr Word8 -> Int -> IO (a, Int), appS :: a -> IO Int } pickle :: PU a -> Ptr Word8 -> Int -> a -> IO Int pickle p ptr ix value = appP p ptr ix value unpickle :: PU a -> Ptr Word8 -> Int -> IO (a, Int) unpickle p ptr ix = appU p ptr ix sizeup :: PU a -> a -> IO Int sizeup p value = appS p value lift :: a -> PU a lift x = PU (\_ ix _ -> return ix) (\_ ix -> return (x, ix)) (\_ -> return 0) sequ :: (b -> a) -> PU a -> (a -> PU b) -> PU b sequ f pa k = PU (\ptr ix b -> do let a = f b pb = k a ix1 <- appP pa ptr ix a appP pb ptr ix1 b) (\ptr ix -> do (a, ix1) <- appU pa ptr ix let pb = k a appU pb ptr ix1) (\b -> do let a = f b pb = k a sz1 <- appS pa a sz2 <- appS pb b return $ sz1 + sz2) pair :: PU a -> PU b -> PU (a,b) pair pa pb = sequ fst pa (\ a -> sequ snd pb (\ b -> lift $! (a, b))) -- http://wagerlabs.com/

3 4

Arrows for invertible programming: Notation question
by Joel Reymont 23 Dec '05

23 Dec '05

Folks, I have been looking at the code for the "Arrows for invertible programming" paper (http://www.cs.ru.nl/A.vanWeelden/bi-arrows/) and I have a question about syntax. ghci surely does not like it. What does this mean and how do I make it compile? mapl{|a, b|arr|} :: (mapl{|a, b|arr|}, ArrowChoice arr, BiArrow arr) => arr a b Thanks, Joel -- http://wagerlabs.com/

3 4

Battling time leaks
by Joel Reymont 23 Dec '05

23 Dec '05

Folks, It looks like I successfully squashed my time leaks and moving my serialization to Ptr Word8 got me as close to the metal as possible. I'm still getting wierd results, though, and they look like a time leak. ORANGE ALERT: 0s, 6s, SrvServerInfo ORANGE ALERT: 0s, 8s, SrvServerInfo ORANGE ALERT: 0s, 9s, SrvServerInfo ORANGE ALERT: 0s, 9s, SrvServerInfo ORANGE ALERT: 0s, 7s, SrvServerInfo unstuff :: Ptr Word8 -> Int -> IO Command unstuff ptr ix = do TOD time1 _ <- getClockTime (kind, ix1) <- unpickle puCmdType ptr ix TOD time2 _ <- getClockTime (cmd', _) <- unpickle (puCommand kind) ptr ix1 TOD time3 _ <- getClockTime when (time3 - time1 > 3) $ -- fail here with the messages above I would like to know where the time is going but how do I troubleshoot something like this? My understanding is that regular profiling will give me the total time spent by cost-center so if I add cost-center annotations it will not give me the average time per run. Come to think about it, the profiling report gives me the # of entries and the total time so I can get the average. Any other suggestions on how to figure out what is going on here? Thanks, Joel -- http://wagerlabs.com/

2 4

Encapsulation in Haskell
by Creighton Hogg 23 Dec '05

23 Dec '05

Hi guys, So one of the big things in object oriented programming is encapsulation, and I'm wondering how to do it properly in Haskell. How do you define new data types but minimize the dependence of external packages on the exact nature of the data definition?

5 4