- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] optimising for vector units
by MR K P SCHUPKE 26 Jul '04

26 Jul '04

As far as I understand it haskells lazy evaluation resembles dataflow computation - IE values are computed on demand. This problem has already been solved for hardware, you end up with what is termed a super-scalar architecture. Instructions read from memory fill a re-order buffer. As computations complete value slots in the reorder buffer are filled with the result values. When an instruction has all its values it can be executed, and will be assigned to the next available execution unit. I am not too sure of the internal architecture of GHC, but I can imagine that funtions waiting to be run will have slots for arguments, that will be filled in when values become available. The whole point is that a function with three parameters can spark three threads to calculate each parameter without worrying about the side affects of each function. No locking is necessary because you only spark one thread for each argument. I suspect I haven't fully understood the difficaulty in doing this, care to enlighten me? Keean.

1 0

Re: [Haskell-cafe] optimising for vector units
by Jon Cast 26 Jul '04

26 Jul '04

Ketil Malde <ketil%2Bhaskell(a)ii.uib.no> wrote: > MR K P SCHUPKE <k.schupke(a)imperial.ac.uk> writes: <snip> > One would expect a lazy and pure language Not lazy! See below. > to be excellent for parallelization, since the programmer is generally > removed from the actual flow of execution anyway. At some point (for > some n), being able to spawn n threads will gain you more than a > factor c constant overhead, ^^^^^^^^^^^^^^^^^^^^^^^^^^ What makes you think the overhead is constant? Without Optimistic Evaluation, Haskell programs mutate /heavily/, and even with Optimistic Evaluation I'm sure there is some mutation going on. With a truly parallel system, every mutation has to be locked in some way; reducing the number of locking operations to merely constant overhead is an interesting (as in extremely difficult) research problem. > and Haskell programs, with a run-time system that can evaluate > expressions in paralllel, will outperform single threaded C code. > > (But it probably isn't that simple, or we would have it already :-) Nope. Jon Cast

2 1

Re: [Haskell-cafe] optimising for vector units
by MR K P SCHUPKE 26 Jul '04

26 Jul '04

>Correct me if I'm wrong but I thought that there was some overhead to >making FFI (even safe/unsafe) You are not wrong... so it would only be worth it if you could execute a whole bunch of C at the same time. But it is possible... Consider: Use a monad to sequence vector operations on the Vector class. The monad instead of directly executing vector instructions compiles a syntax tree, or a list of instructions. This list of instructions is passed to the C code, which sequences the primitive vector ops into a block of code, and returns a function pointer via the FFI. You just call the whole block with the right parameters. This is probably getting to be more work than integrating stuff into GHC though. It is also doing stuff dynamically that could be done statically at compile time. If GCC is providing vector abstractions then it would seem a lot less work for GHC to incorporate 'vector' types directly... Anyone like to comment more specifically on what would be involved in plumbing a new datatype into GHC that handles vectors? Assuming we wanted an interface like: myFn :: Vector Word8 Four -> Vector Word8 Four. Also vector is not a good name, as with vectors: "a * b" would be the cross-product, but with SIMD we get 4 scalar multiplies... Keean.

1 0

optimising for vector units
by Matthew Roberts 26 Jul '04

26 Jul '04

Hi, Does anybody know if any of the Haskell compilers are able to optimise for vector units (like MMX, SSE(2), 3D_Now! and AltiVec)? My investigations have revealed that c requires special programming constructs to make the most of these processor capabilites (i.e. the compiler is not able to work it out for itself). Is there any work on getting haskell compilers to work this kind of thing out? Cheers, Matt

3 2

Trouble with types
by Kari Pahula 24 Jul '04

24 Jul '04

I'm new to Haskell, as you can probably tell... I have the following data types: data Real a => Energy a = Energy a deriving (Eq, Ord, Show) data Real a => HeatC a = HeatC a deriving (Eq, Ord, Show) data Object h c = Object {energy :: (Energy h), heatc :: (HeatC c)} deriving (Eq, Show) data Real a => Temp a = Temp a deriving (Eq, Ord, Show) I'd like to make a function to calculate the temperature of an object. Physically this is the total heat times the heat capacity. I tried this with the following: temp :: (Real a) => Object (Energy a) (HeatC a) -> Temp a temp Object (Energy e) (HeatC c) = Temp e*c But this fails in hugs with: ERROR "temp.hs":22 - Constructor "Object" must have exactly 2 arguments in pattern What's the syntax to use here? Should I do this in some other way? Should I use newtype here instead of data?

4 4

Re: generalised algebraic data types, existential types, and phantom types
by Jim Apple 23 Jul '04

23 Jul '04

I tried to post this to gmane.comp.lang.haskell.general, but it never got there - it may belong here anyway. Abraham Egnor wrote: > Is there any closer approximation [of GADTs] possible? {-# OPTIONS -fglasgow-exts #-} {-# OPTIONS -fallow-undecidable-instances #-} data Term a = forall b . (EqType a b, EqType b Int) => Lit Int | forall b . (EqType a b, EqType b Int) => Inc (Term Int) | forall b . (EqType a b, EqType b Bool) => IsZ (Term Int) | If (Term Bool) (Term a) (Term a) | forall b . Fst (Term (a,b)) | forall b . Snd (Term (b,a)) | forall b c . (EqType a (b,c))=> Pair (Term b) (Term c) class EqType a b | a->b, b->a instance EqType a a Unfortunately, I can't seem to write an eval function: eval (Lit a) = a gives Inferred type is less polymorphic than expected Quantified type variable `b' is unified with `Int' When checking an existential match that binds The pattern(s) have type(s): Term Int The body has type: Int In the definition of `eval': eval (Lit x) = x Any ideas? Jim

2 1

Data.Set subset function?
by Graham Klyne 22 Jul '04

22 Jul '04

I don't see a subset function in Data.Set. What is the preferred way to define this? I currently have: a `subset` b = isEmptySet (a `minusSet` b) (Hmmm... does library style prefer `subset`, `subsetOf`, `isSubset`, `isSubsetOf` ?) #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

2 1

RE: [Haskell-cafe] STG optimization
by Simon Marlow 21 Jul '04

21 Jul '04

On 20 July 2004 22:58, 7253146(a)informatica.alumnos.uma.es wrote: > So far so good. Nonetheless, some doubts have arisen when I have > started to try to add updating. In the paper, implementation for > "update in place" is extensively discussed, although it is said it > could greatly increase the memory space usage. ¿Has this risk been > measured? I think deforestation can minimize the risk; however, as > far as I know, deforestation is only applied to lists. Nowadays GHC doesn't do update-in-place. We removed update-in-place when we re-implemented the code generator and RTS back in version 4.00. There were two reasons: - update-in-place (and its friend, return-in-registers) turned out to be hugely complex when combined with all the other optimisations that GHC does. - we achieve much of the same benefit by adding unboxed tuples to the language and using the "Constructed Product Result" optimisation. CPR is now done by the strictness analyser. Nevertheless, for a while we still did update-in-place when the code genreator could statically determine that there was an update frame on the top of the stack when building a constructor application. But this could only be done when the constructor application contained no pointers - because otherwise the update-in-place code has to deal with the complexities of mutation in a generational garbage collector. But when combined with concurrency, even this kind of update-in-place is difficult, because it might be that another thread is waiting on the result of the thunk being evaluated, and the update code has to wake up that thread. So now, all updates go through one carefully optimised piece of code in the runtime. > But the STG paper ignores an optimization readyly available to me: > whenever a constructor is allocated (constructor's register > allocation aside, since the push/enter - eval/apply paper says GHC no > longer supports it), the STG machine (the one described by the paper) > takes heap space for it, although an update (indirection or copying) > is going to be done most of times. This leads to potentially bad heap > space usage and more garbage collections. > > I think update frames may be detected by the constructor allocation > code, so it could determine whether to allocate a new constructor or > build it over the closure to be updated. This could be achieved by > marking continuations and update frames in the stack, so constructor > allocation code could distinguish between them. This is inconvenient > because common continuations should remove the mark too, so I do not > like it. Yes you could do this. Don't forget to take into account the complications I mentioned above, though (much easier if you don't have generational collection and concurrency). Also you have to know whether the thunk is big enough to be updated with the constructor application. Cheers, Simon

1 0

Sets and Monads and comprehensions
by Graham Klyne 21 Jul '04

21 Jul '04

A few months ago, there was a discussion here about defining Set to be a Monad, starting with: [1] http://www.haskell.org/pipermail/haskell-cafe/2004-March/005988.html in response to which, SPJ pointed out that a Set cannot be a Monad: [2] http://www.haskell.org/pipermail/haskell-cafe/2004-March/005995.html I found myself treading a path which led me to asking the same question as [1]. Given the answer [2], I'd like to stand back a little and ask if there's another way to tackle my niggle: what I'm interested in is a set comprehension expression that is analogous to a list comprehension expression; e.g. in: [[ > import Data.Set > > type AtomicConcept = String -- named atomic concept > type AtomicRole = String -- named atomic role > > type AtomicConcepts a :: AtomicConcept -> (Set a) > type AtomicRoles a :: AtomicRole -> (Set (a,a)) > > type Interpretation a :: (Set a,AtomicConcepts a,AtomicRoles a) ... > iAL (idom,ic,ir) (ALAll r c) = mkSet [ a | (a,b) <- setToList (ir r) > , b `elementOf` ir c ] ]] is there a common or similar idiom to achieve the same effect without converting the set to a list and back? I did also find myself wondering if there was a role for unfold (or similar) here. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

2 1

STG optimization
by 7253146＠informatica.alumnos.uma.es 21 Jul '04

21 Jul '04

Hi. I have been reading recently the STG machine paper by Simon Peyton-Jones. It is relatively easy to follow the explanation, though the formal description of operational semantics is hard to understand. In order to fully understand it, I have started to implement a C-based mini STG machine, implementing the obvious compilation schemes according to the STG paper. Of course, I have not implemented most of optimizations: environment management is very rudimentary, it has three stacks (pointer args, primitive args and continuations) for simplicity, etc. At the moment I have a beatiful tree-reduction STG machine. So far so good. Nonetheless, some doubts have arisen when I have started to try to add updating. In the paper, implementation for "update in place" is extensively discussed, although it is said it could greatly increase the memory space usage. ¿Has this risk been measured? I think deforestation can minimize the risk; however, as far as I know, deforestation is only applied to lists. But the STG paper ignores an optimization readyly available to me: whenever a constructor is allocated (constructor's register allocation aside, since the push/enter - eval/apply paper says GHC no longer supports it), the STG machine (the one described by the paper) takes heap space for it, although an update (indirection or copying) is going to be done most of times. This leads to potentially bad heap space usage and more garbage collections. I think update frames may be detected by the constructor allocation code, so it could determine whether to allocate a new constructor or build it over the closure to be updated. This could be achieved by marking continuations and update frames in the stack, so constructor allocation code could distinguish between them. This is inconvenient because common continuations should remove the mark too, so I do not like it. Another (my favourite) similar solution should be introduce a new stack only for update frames, but still pushing code labels for updating in the continuation stack (which could still be merged with the primitive args stack): this way, constructor's code can still simply jump to the next "continuation" (the update code should be responsible of popping the update stack), and constructor allocation code can simply test if the "continuation" on top of the stack is a real continuation, so it can safely take newly allocated heap space for the constructor, or it is an update (perhaps by testing for equality with the top of the update stack), so the code should test if the constructor closure can be overwritten over the closure to be updated. To ilustrate my thoughts: \begin{code} some_func <some_args> = let b = <some_expression> in SomeConstructor { b, some_stuff } some_other_func <some_other_args> = let a = some_func { some_other_stuff } in case a of <some_alternatives> \end{code} In the above piece of core STG language, when the "a" closure is entered and finally "SomeConstructor" must be allocated, the code of "some_func" should check if the continuation leads to an update (in this case, an update of "a") or an continuation. In this case it leads to an update, so then the code should check if the update closure ("a") is large enough, and, in that case, build the constructor closure over it. Maybe this technique is irrelevant for performance, too expensive to implement, or having a separated update stack is too inconvenient, or these effects are achieved by other ways? Thanks in advance Jose David --------------------------------------------- Este mensaje lo ha enviado un Alumno de la Universidad de Malaga. http://www.alumnos.uma.es/

2 1