- Haskell-Cafe - Haskell.org

vector-simd: some code available, and some questions
by Nicolas Trangez 08 Jul '12

08 Jul '12

All, After my message of yesterday [1] I got down to it and implemented something along those lines. I created a playground repository containing the code at [2]. Initial benchmark results at [3]. More about the benchmark at the end of this email. First some questions and requests for help: - I'm stuck with a typing issue related to 'sizeOf' calculation at [4]. I tried a couple of things, but wasn't able to figure out how to fix it. - I'm using unsafePerformIO at [5], yet I'm not certain it's OK to do so. Are there better (safer/performant/...) ways to get this working? - Currently Alignment phantom types (e.g. A8 and A16) are not related to each other: a function (like Data.Vector.SIMD.Algorithms.unsafeXorSSE42) can have this signature: unsafeXorSSE42 :: Storable a => SV.Vector SV.A16 a -> SV.Vector SV.A16 a -> SV.Vector SV.A16 a Yet, imaging I'd have an "SV.Vector SV.A32 Word8" vector at hand, the function should accept it as well (a 32-byte aligned vector is also 16-byte aligned). Is there any way to encode this at the type level? That's about it :-) As of now, I only implemented a couple of the vector API functions (the ones required to execute my benchmark). Adding the others should be trivial. The benchmark works with Data.Vector.{Unboxed|Storable}.Vector (UV and SV) vectors of Word8 values, as well as my custom Data.Vector.SIMD.Vector type (MV) using 16-byte alignment (MV.Vector MV.A16 Word8). benchUV, benchSV and benchMV all take 2 pre-calculated Word8 vectors of given size (1024 and 4096) and xor them pairwise into the result using "zipWith xor". benchMVA takes 2 suitable MV vectors and xor's them into a third using a rather simple and unoptimized C implementation using SSE4.2 intrinsics [6]. This could be enhanced quite a bit (I guess using the prim calling convention, FFI overhead can be reduced as well). Currently, only vectors of a multiple of 32 bytes are supported (mostly because of laziness on my part). As you can see, the zipWith Data.Vector.SIMD implementation is slightly slower than the Data.Vector.Storable based one. I didn't perform much profiling yet, but I suspect allocation and ForeignPtr creation is to blame, this seems to be highly optimized in GHC.ForeignPtr.mallocPlainForeignPtrBytes as used by Data.Vector.Storable. Thanks for any input, Nicolas [1] http://www.haskell.org/pipermail/haskell-cafe/2012-July/102167.html [2] https://github.com/NicolasT/vector-simd/ [3] http://linode2.nicolast.be/files/vector-simd-xor1.html [4] https://github.com/NicolasT/vector-simd/blob/master/src/Data/Vector/SIMD/Al… [5] https://github.com/NicolasT/vector-simd/blob/master/src/Data/Vector/SIMD/Al… [6] https://github.com/NicolasT/vector-simd/blob/master/cbits/vector-simd.c#L47

3 10

Which mailing list for GHC hacking discussion?
by Erik de Castro Lopo 08 Jul '12

08 Jul '12

Hi all, For GHC development questions (ie hacking on GHC, not with GHC) which is the appropriate mailing list ghc-cvs or ghc-users? Cheers, Erik -- ---------------------------------------------------------------------- Erik de Castro Lopo http://www.mega-nerd.com/

1 0

sample terms and interpreting program output from Tc Monad
by rickmurphy 07 Jul '12

07 Jul '12

Hi All: I'm still working through the following paper [1] and I wondered whether you could help me confirm my understanding of some sample terms and program output from the Tc Monad. For those interested, the language is specified in Parser.lhs available in the protoype here [2]. I understand these to be Rank 0 terms: (\(x::Int) . x) (0 :: Int) :: (forall. Int) -- value (\(x::Int). x) :: (forall. Int -> Int) (\(x::a). x) :: (forall. a -> a) Although the program prints forall, the absence of a type variable indicates Rank 0, correct? I understand these to be Rank 1 terms: (\x. x) :: (forall a. a -> a) -- This is not the same as the third example above, right? This one identifies the type variable a, the one above does not. Also, there's no explicit annotation, it's inferred. (\x. \y. x) :: (forall a b. b -> a -> b) -- Still rank 1. Although there's no explicit annotation, the program infers the type variables and prints the forall and the appropriate type variables for the Rank 1 polytypes. I understand these to be Rank 2 terms: (\(x::(forall a. a)). 0) :: (forall. (forall a. a) -> Int) The explicit forall annotation on the bound and binding variable x causes the program to infer a Rank 2 polytype as indicated by the "-> Int" following the (forall a. a), while noting the absence of a type variable following the left-most forall printed by the program, correct? (\(x::(forall a. a -> a)). x) :: (forall b. (forall a. a -> a) -> b -> b) Also Rank 2, only one arrow to the right of (forall a. a -> a) counts. The universal quantifier on type variable b ranges over the type variable a, correct? I understand this to be a Rank 3 term: (\(f::(forall a. a -> a)). \(x::(forall b. b)). f (f x)) :: (forall c. (forall a. a -> a) -> (forall b. b) -> c) The arrows to the right of the universally quantified a and b expressions qualify this as Rank 3. Type variable c ranges over type variables a and b, correct? Thanks for your help in better understanding this information. I'm home schooling myself on Haskell and community support is a big help. 1. Practical Type Inference for Arbitrary-Rank Types. 2.http://research.microsoft.com/en-us/um/people/simonpj/papers/higher-rank/ -- Rick

1 0

Odd HDBC connection bug
by William Shackleton 07 Jul '12

07 Jul '12

Hi I'm having issues with HDBC when connecting to a remote MySQL server - certain queries cause the DB connection to be lost. The following program demonstrates this: import Database.HDBC import Database.HDBC.ODBC main = do conn <- connectODBC "DSN=owlro" putStrLn "Connected" quickQuery' conn "SELECT time, power FROM Power LIMIT 100;" [] putStrLn "Finished query 1" quickQuery' conn "SELECT time, power FROM Power ORDER BY time;" [] putStrLn "Finished query 2" disconnect conn The DSN points to a remote 32-bit Ubuntu 12.04 Server. The connection and queries work using mysql and isql on the command line, and the table in question contains about 1.3 million rows and only the columns id, time, power. When I compile and run this on a 64-bit Ubuntu 12.04 PC using HDBC-2.3.1.1 and HDBC-odbc-2.3.1.0 using GHC, I get the following (unwanted) output: $ ghc Test.hs $ ./Test Connected Finished query 1 Test: SqlError {seState = "[\"08S01\"]", seNativeError = -1, seErrorMsg = "execute execute: [\"2013: [MySQL][ODBC 5.1 Driver][mysqld-5.5.24-0ubuntu0.12.04.1]Lost connection to MySQL server during query\"]"} This program finishes (and fails) in less than half a second. When I run it using runhaskell however, the slow second query completes: $ runhaskell Test.hs Connected Finished query 1 Finished query 2 I get the same result from ghci; this method takes about 10 seconds as expected. Basically, simple (short) queries complete, yet long ones crash the connection. I also noticed similar results with HDBC-mysql. Any ideas on what is causing this? Thanks, Will Shackleton digitalsquid.co.uk

1 1

ANNOUNCE: lens-family-th 0.1.0.0
by Dan Burton 07 Jul '12

07 Jul '12

Following the announcement of lens-family, I'm pleased to announce lens-family-th 0.1.0.0, a Template Haskell library supplying macros to generate lens-family lenses for fields of data types declared with record syntax. Be warned that currently, type signatures are *not* generated alongside the lens definitions. Type inference should correctly determine the type of the generated lenses, but I have structured the library code so that in the future, type signatures can also be generated. Patches welcome! http://hackage.haskell.org/package/lens-family-th -- Dan Burton

3 5

Re: [Haskell-cafe] translation between two flavors of lexically-scoped type variables
by oleg＠okmij.org 07 Jul '12

07 Jul '12

Kangyuan Niu wrote: > Aren't both Haskell and SML translatable into System F, from which > type-lambda is directly taken? The fact that both Haskell and SML are translatable to System F does not imply that Haskell and SML are just as expressive as System F. Although SML (and now OCaml) does have what looks like a type-lambda, the occurrences of that type lambda are greatly restricted. It may only come at the beginning of a polymorphic definition (it cannot occur in an argument, for example). > data Ap = forall a. Ap [a] ([a] -> Int) > Why isn't it possible to write something like: > > fun 'a revap (Ap (xs : 'a list) f) = f ys > where > ys :: 'a list > ys = reverse xs > > in SML? This looks like a polymorphic function: an expression of the form /\a.<body> has the type forall a. <type>. However, the Haskell function > revap :: Ap -> Int > revap (Ap (xs :: [a]) f) = f ys > where > ys :: [a] > ys = reverse xs you meant to emulate is not polymorphic. Both Ap and Int are concrete types. Therefore, your SML code cannot correspond to the Haskell code. That does not mean we can't use SML-style type variables (which must be forall-bound) with existentials. We have to write the elimination principle for existentials explicitly {-# LANGUAGE ExistentialQuantification, RankNTypes #-} {-# LANGUAGE ScopedTypeVariables #-} data Ap = forall a. Ap [a] ([a] -> Int) -- Elimination principle deconAp :: Ap -> (forall a. [a] -> ([a] -> Int) -> w) -> w deconAp (Ap xs f) k = k xs f revap :: Ap -> Int revap ap = deconAp ap revap' revap' :: forall a. [a] -> ([a] -> Int) -> Int revap' xs f = f ys where ys :: [a] ys = reverse xs Incidentally, GHC now uses SML-like design for type variables. However, there is a special exception for existentials. Please see 7.8.7.4. Pattern type signatures of the GHC user manual. The entire section 7.8.7 is worth reading.

2 2

Parameterized constraints
by Emil Axelsson 06 Jul '12

06 Jul '12

Hi! The `constraints` package provides ways to manipulate objects of kind `Constraint`. I need the same kind of manipulation, except that I need to work with objects of kind `* -> Constraint`. I.e. I need parameterized constraints that can be applied to different types. BTW, is there a standard term for things of kind `* -> Constraint`? I have a type family type family Constr (f :: * -> *) :: * -> Constraint which returns a parameterized constraint with the property that any value of type `f a` fulfills the constraint `Constr f a`. Since the constraint can be stronger than needed, I need something similar to `:-` from `constraints`, except it should operate on parameterized constraints. I have implemented the stuff I need (see below), but my question is if it's possible to do this with the `constraints` package directly (e.g. using `Forall`). I'm afraid I can't see how. Here is what I've come up with so far: -- Instead of (c1,c2) class (c1 a, c2 a) => (c1 :/\: c2) a instance (c1 a, c2 a) => (c1 :/\: c2) a -- Instead of (:-) type sub :< sup = forall a . Dict (sup a) -> Dict (sub a) -- Instead of weaken1 weak1 :: c1 :< (c1 :/\: c2) weak1 Dict = Dict weak2 :: c2 :< (c1 :/\: c2) weak2 Dict = Dict Thanks! -- / Emil

1 0

ANNOUNCE: husk-scheme, release 3.5.6
by Justin Ethier 06 Jul '12

06 Jul '12

I would like to announce the release of husk-scheme 3.5.6, a Scheme extension language and stand-alone interpreter/compiler that I have been developing. husk implements most of the Scheme R5RS standard<http://www.schemers.org/Documents/Standards/R5RS/HTML/>including advanced features such as continuations, hygienic macros, and a full numeric tower. husk has been an ongoing project for over a year now, but this is the first announcement on the mailing list so feedback is very welcome. Hackage: http://hackage.haskell.org/package/husk-scheme Homepage: http://justinethier.github.com/husk-scheme Change Log: https://github.com/justinethier/husk-scheme/blob/master/ChangeLog.markdown Issues and Enhancement Requests: https://github.com/justinethier/husk-scheme/issues Thanks, Justin

1 0

vector, alignment and SIMD through FFI
by Nicolas Trangez 06 Jul '12

06 Jul '12

Hello Cafe, Recently I've been playing with the implementation of an algorithm, for which we already have highly-optimized implementations available (in plain C/C++ as well as OCaml with calls to C through FFI). The algorithm works on buffers/arrays/vectors/whatever you want to call it, which needs to be combined in certain ways. This can be highly optimized by using SIMD instructions (like the ones provides by several SSE versions). I'd like to get a to Haskell version which is comparable in efficiency as the existing versions, whilst remaining as 'functional' as possible. I don't mind jumping into some low-level C glue and FFI (using ccall or custom primops), but this should be limited. Currently I have something working (still highly unoptimized) using (unboxed) vectors from the vector package, using mutable versions within a well-contained ST environment in some places. One hot zone of the current version is combining several vectors, and the performance of this operation could be greatly improved by using SIMD instructions. There's one catch though: when using these, memory should be aligned on certain boundaries (16 byte in this case). First and foremost, to be able to pass my vectors to some C functions, I should change my code into using Storable vectors (which should be fine, I guess I can expect similar performance characteristics?). I couldn't find any information on alignment guarantees of these vectors though... Which is how I get to my question: are there any such guarantees? If not, are there any pointers to how to proceed with this? I guess tracking alignment at the type level should be the goal, you can find some code trying to explain my reasoning up to now at the end of this email. I have some issues with this: - I'd need to re-implement almost all vector operations, which seems stupid. - It doesn't actually work right now ;-) - It'd be nice to be able to encode 'compatible' alignment: as an example, a 16 byte aligned buffer is also 8 byte aligned... I hope the above explains somewhat my goal. Any thoughts & help on this would be very welcome! Thanks, Nicolas module Data.Vector.SIMD ( -- ... ) where import qualified Data.Vector.Storable as SV import Foreign.Storable (Storable, sizeOf) import Foreign.Ptr (Ptr, FunPtr) import Foreign.ForeignPtr (ForeignPtr, newForeignPtr) import System.IO.Unsafe (unsafePerformIO) class Alignment a where alignment :: a -> Int data A8Byte instance Alignment A8Byte where alignment _ = 8 data A16Byte instance Alignment A16Byte where alignment _ = 16 newtype Alignment a => SIMDVector a b = V (SV.Vector b) replicate :: (Alignment a, Storable b) => a -> Int -> b -> SIMDVector a b replicate a n b = V v where ptr = unsafePerformIO $ do v <- _mm_malloc n (alignment a) -- memset etc return v v = SV.unsafeFromForeignPtr0 ptr n -- These are 2 _stub versions of the procedures since xmminstr.h (or mm_malloc.h -- when using GCC) contains them as inline procedures which are not available -- as-is in a library. There should be some C module which exports -- _mm_malloc_stub and _mm_free_stub, which simply includes xmminstr.h and calls -- the underlying procedures. foreign import ccall "_mm_malloc_stub" _mm_malloc_stub :: Int -> Int -> IO (Ptr a) foreign import ccall "_mm_free_stub" _mm_free_stub :: FunPtr (Ptr a -> IO ()) _mm_malloc :: Storable a => Int -> Int -> IO (ForeignPtr a) _mm_malloc s l = do -- This fails: -- Ambiguous type variable `a0' in the constraint: -- (Storable a0) arising from a use of `sizeOf' -- v <- c_mm_malloc (s * sizeOf (undefined :: a)) l newForeignPtr _mm_free_stub undefined -- This allocates a 16 byte aligned output buffer, takes 2 existing ones and -- calls some FFI function to perform some magic. -- The implementation could run inside ST, if the FFI import (which e.g. works -- on a mutable buffer and returns IO ()) is lifted into ST using unsafeIOToST mySIMDFun :: SIMDVector A16Byte a -> SIMDVector A16Byte a -> SIMDVector A16Byte a mySIMDFun a b = undefined

3 3

cabal equivalent to "make -k"?
by Omari Norman 06 Jul '12

06 Jul '12

When using make (or, at least, GNU make) the "-k" option keeps going as far as possible after a compilation error. It's handy during developing--for instance, "I know half of my code is busted, but I just want to see if this file compiles." Is there a similar way to do this with cabal? Thanks. --Omari

1 0