On Thu, Feb 16, 2012 at 4:42 PM, Johan Tibell wrote:

1. In theory the user could create a cut-n-paste copy of the data structure and specialize it to a particular type, but I think we all agree that would be unfortunate (not to say that it cannot be justified in extreme cases.)

I thought data families could help here, as in, you could do a SPECIALIZE on a data type and the compiler will turn it into a data family behind the scenes and specialize everything to said type. though, that wouldn't do things like turn a Data.Map into a Data.IntMap... John

Welcome back to reality Don! ;) On Thu, Feb 16, 2012 at 4:56 PM, Don Stewart wrote:

Couldn't you measure it by changing base to use data Int = I# {-# UNPACK #-} Int# and see what happens?

I'm not sure what this would mean. Int# is already unpacked. -- Johan

Of course, that makes sense. Do we already have a way to specify that a field should be lazy? I can imagine programs where we don't want this behaviour, and people would need an escape hatch (or their programs might run slower, or even not terminate). I know we've got lazy patterns with ~, do we have data Foo = Foo ~Int | Bar ~Double Alex On 17/02/2012, at 11:59, Johan Tibell wrote:

On Thu, Feb 16, 2012 at 4:52 PM, Alex Mason wrote:

...

Sounds like it's definitely worth playing with. I would hesitate to use the shootout benchmarks though, simply because anything there is already going to be unpacked to the hilt.

That was the point of number (2) above. By disabling their unpack pragmas through the compiler and measuring the performance, we can simulate a world where people don't write unpack pragmas and then see how much GHC could improve things in such a world. If the gain is large enough we can turn this optimization on and people can waste less time cluttering their code with unpack pragmas!

Note that this proposal doesn't but you any new expressive powers. The intention is two-fold: decrease the amount of clutter in Haskell programs and have code written by beginner/intermediate level Haskellers perform better out-of-the-box.

...

How difficult do you think it would be to implement this in GHC?

Quite easy I think. All the difficulty is in getting good benchmarks.

-- Johan

Hi all, On Thu, Feb 16, 2012 at 4:59 PM, Johan Tibell wrote:

On Thu, Feb 16, 2012 at 4:52 PM, Alex Mason wrote:

...

How difficult do you think it would be to implement this in GHC?

Quite easy I think. All the difficulty is in getting good benchmarks.

The computeRep function in compiler/basicTypes/DataCon.lhs seems to be the right place for this. -- Johan

You do know about -funbox-strict-fields, a flag that exists already, don't you. (Sorry if I'm behind the curve here; have not followed the thread.) S | -----Original Message----- | From: glasgow-haskell-users-bounces@haskell.org [mailto:glasgow-haskell- | users-bounces@haskell.org] On Behalf Of Johan Tibell | Sent: 17 February 2012 01:14 | To: glasgow-haskell-users | Subject: Re: Unpack primitive types by default in data | | On Thu, Feb 16, 2012 at 4:25 PM, Johan Tibell wrote: | > I've been thinking about this some more and I think we should | > definitely unpack primitive types (e.g. Int, Word, Float, Double, | > Char) by default. | | Initially we could hide this feature behind a new | -funbox-strict-primitive-fields, but I definitely think we should push | towards making it the default as some of the benefit (especially for | beginners) comes from that. | | -- Johan | | _______________________________________________ | Glasgow-haskell-users mailing list | Glasgow-haskell-users@haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

Hi, On 17.02.2012, at 09:52, Roman Leshchinskiy wrote:

Johan Tibell wrote:

...

The worry is that reboxing will cost us, but I realized today that at least one other language, Java, does this already today and even though it hurts performance in some cases, it seems to be a win on average. In Java all primitive fields get auto-boxed/unboxed when stored in polymorphic fields (e.g. in a HashMap which stores keys and fields as Object pointers.) This seems analogous to our case, except we might also unbox when calling lazy functions.

I'm not convinced that this is a good idea because it doesn't treat all types equally. The comparison with Java is problematic, IMO, because in Java 'int' is always called 'int' whereas in Haskell, it might be called many different things.

Actually, there are two types for every primitive type in Java: int / java.lang.Integer byte / java.lang.Byte char / java.lang.Char float / java.lang.Float double / java.lang.Double ... Starting with Java 5, javac automatically boxes / unboxes between a primitive type and its corresponding reference type. I.e. the programmer still specifies how a value is stored. This autoboxing simply makes them assignment compatible. As far as I understand it, auto boxing was introduced in order to better integrate primitive types with generics, not as an optimization. And I doubt that it is an optimization on average. I think, It might still be a good idea to realize Johann's proposal. I am just cautious whether Java really shows that this is a good idea. Regards, Jean

On Fri, Feb 17, 2012 at 3:13 AM, Roman Leshchinskiy wrote:

True, I didn't phrase that right at all. AFAIK, in Java, there is a one-to-one correspondence between a primitive type and its boxed version. So you can say that boxed integers will be unboxed when necessary and it's clear what that means. But in Haskell, there is no such one-to-one correspondence. This is a very good thing but it makes specifying and understanding what will be unboxed when much harder.

You're right that it's harder to specify exactly when unpacking happens but default is better, both if you know how it works and if you don't. - If you don't know how it works (e.g. you're a beginner/intermediate level Haskeller) the default is saner. - If you know how it works you don't have to write all these UNPACKs that sit on every single primitive field* in our core libraries. * I did a quick count of how many primitive fields are manually unpacked in text, bytestring, and containers. Here are the results (unpacked/total): text: 27/30 Not unpacked: Data/Text/Lazy/Builder/Int.hs:data T = T !Integer !Int Data/Text/Lazy/Read.hs:data T = T !Integer !Int Data/Text/Read.hs:data T = T !Integer !Int These three seem all to get their boxed removed anyway as they're just used as a return type and get turned into (# Integer, Int# #) anyway. An unpack here wouldn't have hurt. bytestring: 3/3 containers: 13/13 I would be interested to see if there's a case where primitive fields aren't unpacked and that's not a misstake. -- Johan

On Tue, Feb 28, 2012 at 1:11 AM, Simon Marlow wrote:

I think there are some in GHC - I've been surprised occasionally when adding an UNPACK makes things worse.

I just realized that there is a failure mode I didn't quite consider: having a mix of strict and non-strict primitive fields. While this can happen on purpose, I think it happens more often due to non-strict being the default. Having a field with such a mix might lead to more re-boxing. Cheers, Johan

On Wed, Feb 29, 2012 at 2:08 AM, Simon Marlow wrote:

(I think you meant "record", not "field" in the last sentence, right?)

I did mean record, but I wasn't being very clear. Let me try again.

It's not obvious to me why having a mixture of strict and nonstrict (maybe you meant UNPACKed and not UNPACKed?) fields would make things worse. Could you give a concrete example?

Sure. Lets say we have a value x of type Int, that we copy from constructor to constructor: f (C_i x) = C_j x -- for lots of different i:s and j:s (In practice C_i and C_j most likely have different types.) In a program with constructors, C_1 .. C_n, we can do one of three things: 1. Unpack no fields. 2. Unpack some fields. 3. Unpack all fields. Now, if we have a program that's currently in state (1) and we move to state (2) by manually adding some unpack pragmas, performance might get worse, as we introduce re-boxing where there was none before. However, if we kept unpacking fields until we got into state (3), performance might be even better than in state (1), because we are again back into a state where * there's no reboxing (lazy functions aside), but * we have better cache locality. I suspect many large Haskell programs (GHC included) are in state (1) or (2). If we introduce -funbox-primtive-fields and turn it on by default, the hope would be that many programs go from (1) to (3), but that only works if the programs have consistently made primitive fields strict (or kept them all lazy, in which case -funbox-primitive-fields does nothing.) If the programmer have been inconsistent in his/her use of strictness annotations, we might end up in (2) instead. Did this make any more sense? Cheers, Johan

On Fri, Feb 17, 2012 at 2:42 AM, Jean-Marie Gaillourdet wrote:

Actually, there are two types for every primitive type in Java: int / java.lang.Integer byte / java.lang.Byte char / java.lang.Char float / java.lang.Float double / java.lang.Double ...

We have the same split in Haskell, but our spelling is a bit funny: {-# UNPACK #-} !Int / !Int {-# UNPACK #-} !Word8 / !Word8 ...

Starting with Java 5, javac automatically boxes / unboxes between a primitive type and its corresponding reference type. I.e. the programmer still specifies how a value is stored. This autoboxing simply makes them assignment compatible. As far as I understand it, auto boxing was introduced in order to better integrate primitive types with generics, not as an optimization. And I doubt that it is an optimization on average.

Sure, introducing autoboxing isn't an optimization in Java. Java programmers were manually boxing values before putting them into data structures before the introduction of autoboxing. What I'm saying is that if we switch to a scheme were we automatically unpack fields by default, we get to a situation which operationally is very similar to the Java one: every time you stick an (automatically unpacked) field into a polymorphic data structure you get autoboxing, but otherwise you work with an unpacked field. Here's an example showing the operational similarities if this proposal was accepted: Java: class Vec3 { public Vec3(int x, int y, int z) { ... } public int x; // you'd rarely see Integer here! public int y; public int z; } Vec3 v = new Vec3(1,2,3); // No indirection overheads for many common operations: public Vec3 sum(Vec3 v1, Vec3 v2) { return new Vec3(v1.x + v2.x, v1.y + v2.y, v1.z + v2.z); } // Autoboxing when used with polymorphic data types HashMap m = new HashMap(); m.put("key", v.x); // autoboxing happens here: Int -> Integer Haskell: data Vec3 = Vec3 { x :: !Int, y :: !Int, z :: !Int } -- represented as Int# Int# Int# let v = Vec3 1 2 3 -- No indirection overheads for many common operations: sum :: Vec3 -> Vec3 -> Vec3 sum (Vec3 x1 y1 z1) (Vec3 x2 y2 z2) = Vec3 (x1+x2) (y1+y2) (z1+z2) -- Autoboxing when used with polymorphic data types let m = Map.empty let m' = Map.insert "key" (x v) -- reboxing happens here: Int# -> Int

I think, It might still be a good idea to realize Johann's proposal. I am just cautious whether Java really shows that this is a good idea.

Java doesn't show that boxing is good, but I think it does show that never using primitive fields is worse that sometimes reboxing. Cheers, Johan

On 17/02/2012, at 17:51, Johan Tibell wrote:

On Fri, Feb 17, 2012 at 12:52 AM, Roman Leshchinskiy wrote:

...

I'm not convinced that this is a good idea because it doesn't treat all types equally. The comparison with Java is problematic, IMO, because in Java 'int' is always called 'int' whereas in Haskell, it might be called many different things.

To better understand the proposal, which of the types below would you want to be unboxed automatically?

data A = A Int# newtype B = B A data C = C !B data D = D !C data E = E !() data F = F !D

All of the above. Put in other words: all fields whose final representation type could be the size of a pointer if we unpacked enough.

Ok, that makes sense. I would include Double# and Int64# in this list. For the simple reason that if the target audience are beginners they will have a hard time figuring out why their programs run 20x faster with Float/Int than with Double/Int64 instead of just 2x faster. Roman

On 17/02/2012 20:10, Johan Tibell wrote:

...

nofib probably has, to a first approximation, zero strictness annotations. Because most of the programs in there predate the addition of strictness annotations to Haskell.

That's good for us.

In what way? The nofib programs have no strictness annotations, so they won't be affected by the optimisation, so the results won't tell us anything at all. (am I missing something here?) Cheers, Simon

The downside of nofib is that it probably doesn't represent real world Haskell programs well, as they tend to use more packed types, such as ByteString, Text, and Vector. Still, it's a good start.

...

GHC itself would be a good benchmark, incidentally...

Indeed, that's what I thought as well. How do I test the build time of GHC? By building my modified GHC in one build tree and then use it to build another GHC in another (clean) build tree?

-- Johan