July 2007 - Haskell-Cafe

Re: [Haskell-cafe] sha1 implementation thats "only" 12 times slower then C
by Anatoly Yakovenko 14 Jul '07

14 Jul '07

---------- Forwarded message ---------- From: Anatoly Yakovenko <aeyakovenko(a)gmail.com> Date: Jul 14, 2007 11:09 AM Subject: Re: Your SHA1 To: Dominic Steinitz <dominic.steinitz(a)blueyonder.co.uk> > > 1. Very good. Thanks, it was a fun experiment. > > 2. It has type hash::BS.ByteString -> IO [Word] but hash is a pure function. > > Can this be changed? you can call it safely with unsafePerformIO, I do a lot of hacks to get the performance, like casting a C ptr from a bytestring to a word array, but each call to hash should have no side effects. > > 3. I haven't tried but I assume it only runs with ghc and not hugs? I guess if > > point 1 could be addressed then we could put it in the crypto library (assuming > > you are happy with this) with some sort of conditional flag to use your code if > > the library is being built for ghc but to use the slow version for other > > compilers / interpreters. i would be surprised if this ran on hugs, i havent tried. Also, i haven't verified that my implementation is correct, as far as the sha1 algorithm is concerned. the complexity is the same, so if there any bugs in the math they can be easily fixed without making it slower. > > On a more discursive note, I still don't think we have found the holy grail > > here: idiomatic functional programming (probably not using StorableArray and > > unsafeRead and unsafeWrite) and lightning fast speed. yea, i agree, i am doing a lot of ugly hacks to get things going faster. Actually i think the "cleaner" approach would be to use Harpy extension and do the math with x86 assembly :). This way its at least straight forward, cause right now, i was just randomly changing strictness and unboxing things so ghc generates the fastest code, but a different haskell compiler would have completely different results. > > Dominic. > > > > PS I noticed you have: > > > > splitByN::Int -> BS.ByteString -> [BS.ByteString] > > splitByN nn ll = st : (if (BS.null en) then [] else (splitByN nn en)) > > where > > (st,en) = BS.splitAt nn ll > > > > It's a function I often use: > > > > splitByN n = > > unfoldr k > > where > > k [] = Nothing > > k p = Just (splitAt n p) > > > > Maybe it should be a standard part of List and ByteString? yea i agree, i've seen a couple other implementations as well. seems like its something that should be in Prelude and ByteString. Anatoly

2 1

Frisby (PEG parser) unbiased-choice thoughts
by Isaac Dupree 14 Jul '07

14 Jul '07

since I don't like unexpected behavior happening when something not intended to happen, happens, and it's better documentation (a free assertion) -- I find myself making Haskell comments to specify whether the left-biasedness of each (//) is important, various places in my own code that uses frisby. We examine how could such an operator could behave, having similar effect to (//) but symmetric (call it (=|=); (p1 =|= p2) should be equivalent to (p2 =|= p1) )... I will use original frisby syntax (see <http://repetae.net/john/computer/frisby/>), not the Applicative/Alternative instances I added, to be clearer. "Thought 1" could make a different but valid Alternative instance, after all. Prototype implementations are given... so it's clearly still O(1). thought 1: (=|=) :: P s a -> P s a -> P s a a =|= b = ((peek a <> peek b) `onlyIf` (error "BUG in (=|=) user")) // (a // b) thought 2: (=|=) :: Eq a => P s a -> P s a -> P s a a =|= b = ((peek a <> peek b) `onlyIf` (check)) // (a // b) where check (ra,rb) = if ra /= rb then error "BUG in (=|=) user" else False --This one "unnecessarily" requires Eq just to check a programmer's --assertion of equivalence, but allows overlaps that give the same --result. On second thought... 'a' and 'b' could consume different --amounts of input and produce the same result, so this is buggy. thought 3: symmetricDifference :: P s a -> P s a -> P s a a `symmetricDifference` b = (doesNotMatch a ->> b) // (doesNotMatch b ->> a) feeding arbitrary inputs using quickcheck should hopefully catch incorrect usages of the (=|=)s that can be used in error, since it is well known that one cannot systematically determine for all PEG parsers whether the assertion will hold true (it must be at least as difficult as determining whether any two are exactly equivalent). HOWEVER it would also be interesting to see a similar system that could be restricted enough that one could show the correctness of such a non-intersection claim (I wonder how frequently such claims are fairly trivial to prove correct, anyway) Isaac

1 0

Strange results when trying to create large Bool arrays.
by Richard Kelsall 14 Jul '07

14 Jul '07

My first ever Haskell program just creates an array in memory. I wanted to try creating really big arrays. import Data.Array.IO import System import Text.Printf main = do n <- getArgs >>= readIO . head :: IO Int a <- newArray (1,n) True :: IO (IOUArray Int Bool) printf "Created array 1 .. %8d \n" (n::Int) :: IO () It appears to work up to quite large numbers, but then gets strange. When I give it an array size of 1,000,000,000,000 it returns this Created array 1 .. -727379968 Presumably the Int has overflowed without warning when read from the argument. I guess there must be a switch to make it produce a nice error message rather than overflowing without warning. If I replace all the 'Int's in the program with 'Integer's it works better, but sometimes it freezes when I give it a silly large number rather than returning an 'unable to allocate that much memory' error. And what really puzzles me is this behaviour in the 'Integer' version. 1000 created array 1000000 created array 1000000000 created array 10000000000 created array (approximately my bits of real memory) 100000000000 created array 1000000000000 freezes 10000000000000 created array 100000000000000 created array 1000000000000000 freezes 10000000000000000 created array It seems to randomly claim to have successfully created huge sizes of array. So now I am not sure which of these arrays it is really creating. I would expect it to consistently freeze above my real memory size. Or preferably return a 'not enough memory' error message. I have 1Gb of real memory in my machine. GHC 6.6.1 for Windows, running on W2K. Assuming these errors are in Haskell rather than my code (beginner's fallacy?) could I vote for having the memory, bounds, overflow etc checking switched on by default. I like my errors to be made as visible as possible as soon as possible. Or did I do something wrong? Richard.

17 29

HDBC-ODBC build/install problem.
by Edward Ing 14 Jul '07

14 Jul '07

Hi, I am trying to make HaskellDB work with HDBC-ODBC. I did builds of HDBC/HDBC-ODBC. But when I am building HaskellDB-HDBC-ODBC, I get the following message. -------------- "[1 of 1] Compiling Database.HaskellDB.HDBC.ODBC ( Database/HaskellDB/HDBC/ODBC.hs, dist\build/Database/HaskellDB/HDBC/ODBC.o ) C:\Program Files\Haskell\HDBC-odbc-1.1.2.0\ghc-6.6.1/Database/HDBC/ODBC/Connection.hi Declaration for connectODBC: Failed to load interface for `Database.HDBC.ODBC.ConnectionImpl': Use -v to see a list of the files searched for. Cannot continue after interface file error" -------------- >From this, I know the problem is the linkage between Database.HDBC.ODBC.Connection and Database.HDBC.ODBC.ConnectionImple. (Also I looked at the code to see the reference.) I did a little further investigation. I looked at the package registry area (C:\Program Files\Haskell\HDBC-odbc-1.1.2.0\ghc-6.6.1\Database\HDBC\ODBC) and notice that ConnectionImpl.hi is not there. I went back to the build directory and did find ConnectoinImpl.hi and ConnectionImpl.o. It seems like runghc Setup.hs install, did not install ConnectionImpl.hi. I looked into the file named ".installed-pkg-config" and I saw this: ------------ exposed-modules: Database.HDBC.ODBC hidden-modules: Database.HDBC.ODBC.Connection Database.HDBC.ODBC.Statement Database.HDBC.ODBC.Types Database.HDBC.ODBC.Utils Database.HDBC.ODBC.TypeConv import-dirs: "C:\\Program Files\\Haskell\\HDBC-odbc-1.1.2.0\\ghc-6.6.1" library-dirs: "C:\\Program Files\\Haskell\\HDBC-odbc-1.1.2.0\\ghc-6.6.1" hs-libraries: HSHDBC-odbc-1.1.2.0 extra-libraries: odbc32 -------------- No mention of ConnectionImple.hi. It looks like the setup up script did not install ConnectionImpl.hi. Did ConnectionImpl.o get bound into "libHSHDBC-odbc-1.1.2.0.a" even though ConnectionImpl.hi did not get successfully installed? Does anyone know why the install target does not install ConnectionImpl.hi and how I can get around this problem? (Where is the odbc32 to be found anyways?) Here are a few things I did try which did NOT work: 1. Copy ConnectionImpl.hi over manually. HaskellDB-HDBC-ODBC builds, but at runtime there is a link error. 2. Manually alter ".installed-pkg-config" to add ConnectionImpl.hi as hidden module. Please comment on why these would not work ( I will learn from this.) Help would be appreciated. Edward Ing

2 3

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

impossible to write type signature
by jeff p 14 Jul '07

14 Jul '07

Hello, I managed to write a function, which ghc accepts, for which ghc rejects it's own type signature. I remember seeing a thread about this sometime in the last year or so, but I can't seem to find it. Does anyone remember this thread? thanks, Jeff

1 1

[Math] Category theory research programs?
by Creighton Hogg 13 Jul '07

13 Jul '07

Hi Haskell, Sorry to contribute to the noise but given that we've been talking about categories lately, I was wondering if anyone had any opinions on good universities for studying category theory. I'm trying to figure out where to apply for my phd. I want to either be at a place with a strong category theory program or a strong differential geometry program. Thanks, Creighton

4 3

money type ?
by Simon Michael 13 Jul '07

13 Jul '07

Good day all, my budding ledger program could not balance transactions exactly because of rounding error with Double. I *think* I got it working better with Rational (it was late). Another suggestion from #haskell was to multiply all money by 100. I'm tracking multiple currencies/commodities with varying precision so this gets a bit more complicated. Is there a type or library out there that's good for representing money and other quantities while avoiding rounding errors ? Best - Simon

9 12

Simple newbie question - Int and Integer
by Gregory Propf 13 Jul '07

13 Jul '07

So what the hell is the difference between them? Int and Integer. They aren't synonyms clearly. What's going on? ____________________________________________________________________________________ Take the Internet to Go: Yahoo!Go puts the Internet in your pocket: mail, news, photos & more. http://mobile.yahoo.com/go?refer=1GNXIC

6 7

better error expression in IO function
by brad clawsie 13 Jul '07

13 Jul '07

i am working on improving a module for getting Yahoo Finance quote data, hopefully getting it to a point that i can put it on hackage in the quote retrieval function, there are a few places i would like to call out errors. in a trivial case i could return IO (Maybe String) with Nothing signifying any error state, or Just expressing the data but i would like to be able to express some of these error cases in a more structured manner i know the Either type can be used in such a case(?), but i've had some problem locating a satisfactory example (if this is indeed appropriate) could one of the vets here provide a simplistic example expressing error cases, preferrably in the IO Monad (in case there are any gotchas there)? thanks so much! brad

8 10