Hi, Recall the example from Simon's paper appearing in ICFP 2007. myLast :: [a] -> a myLast [] = error "" myLast [x] = x myLast (x:xs) = myLast xs which returns the last element in a list. Applying the idea in the paper, we should rewrite the function as follows, myLast :: [a] -> a myLast [] = error "" myLast (x:xs) = myLast' x xs where myLast' x [] = x myLast' x (y:ys) = myLast' y ys which avoids redundant pattern tests. We tried to compile the "unspecialized" version of myLast function with GHC 6.8.1 with -O2 -ddump-simpl flags and observe the core code as follows, ==================== Tidy Core ==================== lvl_r72 :: forall a_a5P. a_a5P [GlobalId] [Str: DmdType b] lvl_r72 = \ (@ a_a5P) -> GHC.Err.error @ a_a5P (GHC.Base.[] @ GHC.Base.Char) Rec { Last.$smyLast :: forall a_a5P. a_a5P -> [a_a5P] -> a_a5P [GlobalId] [Arity 2] Last.$smyLast = \ (@ a_a5P) (ipv_s6i :: a_a5P) (ipv1_s6j :: [a_a5P]) -> case ipv1_s6j of wild_X9 { [] -> ipv_s6i; : ipv2_X6p ipv3_X6r -> Last.myLast @ a_a5P wild_X9 } Last.myLast :: forall a_a5B. [a_a5B] -> a_a5B [GlobalId] [Arity 1 Str: DmdType S] Last.myLast = \ (@ a_a5P) (ds_d68 :: [a_a5P]) -> case ds_d68 of wild_B1 { [] -> lvl_r72 @ a_a5P; : x_a5I ds1_d69 -> case ds1_d69 of wild1_X9 { [] -> x_a5I; : ipv_s6i ipv1_s6j -> Last.myLast @ a_a5P wild1_X9 } } end Rec } ==================== Tidy Core Rules ==================== "SC:Last.myLast0" [0] forall {@ a_a5P ipv_s6i :: a_a5P ipv1_s6j :: [a_a5P]} Last.myLast @ a_a5P (GHC.Base.: @ a_a5P ipv_s6i ipv1_s6j) = Last.$smyLast @ a_a5P ipv_s6i ipv1_s6j It seems that $smyLast is the specialized version of myLast And the last tidy core rule says that we should replace the application (myLast (x:xs)) by ($smyLast x xs). We are surprised by the development of the second pattern of $smyLast. In the second pattern, function myLast is applied to wild_X9 which is the reference of ipv_s6j. However, according to the running example, it seems to make more sense if this application is replaced by a recursive application ($smyLast ipv_3X6r) instead. Could you guys please enlighten me? Regards, Kenny
Urk. Well spotted! I omitted a prime (writing env instead of env') in a late fix, and as a result practically no top-level rules and specialisations are being applied. What an egregious bug. The good news is that a one-character fix should make 6.8.2 perform quite a bit better than 6.8.1! Simon | -----Original Message----- | From: glasgow-haskell-users-bounces@haskell.org [mailto:glasgow-haskell-users-bounces@haskell.org] On Behalf Of | kenny lu | Sent: 15 November 2007 06:49 | To: glasgow-haskell-users@haskell.org | Subject: GHC 6.8.1 SpecConstr | | Hi, | | Recall the example from Simon's paper appearing in ICFP 2007. | | myLast :: [a] -> a | myLast [] = error "" | myLast [x] = x | myLast (x:xs) = myLast xs | | which returns the last element in a list. | | Applying the idea in the paper, we should rewrite the function | as follows, | | myLast :: [a] -> a | myLast [] = error "" | myLast (x:xs) = myLast' x xs | where myLast' x [] = x | myLast' x (y:ys) = myLast' y ys | | which avoids redundant pattern tests. | | | We tried to compile the "unspecialized" version of myLast function | with GHC 6.8.1 | with -O2 -ddump-simpl flags and observe the core code as follows, | | ==================== Tidy Core ==================== | lvl_r72 :: forall a_a5P. a_a5P | [GlobalId] | [Str: DmdType b] | lvl_r72 = \ (@ a_a5P) -> GHC.Err.error @ a_a5P (GHC.Base.[] @ GHC.Base.Char) | | Rec { | Last.$smyLast :: forall a_a5P. a_a5P -> [a_a5P] -> a_a5P | [GlobalId] | [Arity 2] | Last.$smyLast = | \ (@ a_a5P) (ipv_s6i :: a_a5P) (ipv1_s6j :: [a_a5P]) -> | case ipv1_s6j of wild_X9 { | [] -> ipv_s6i; : ipv2_X6p ipv3_X6r -> Last.myLast @ a_a5P wild_X9 | } | Last.myLast :: forall a_a5B. [a_a5B] -> a_a5B | [GlobalId] | [Arity 1 | Str: DmdType S] | Last.myLast = | \ (@ a_a5P) (ds_d68 :: [a_a5P]) -> | case ds_d68 of wild_B1 { | [] -> lvl_r72 @ a_a5P; | : x_a5I ds1_d69 -> | case ds1_d69 of wild1_X9 { | [] -> x_a5I; : ipv_s6i ipv1_s6j -> Last.myLast @ a_a5P wild1_X9 | } | } | end Rec } | | | | | ==================== Tidy Core Rules ==================== | "SC:Last.myLast0" [0] | forall {@ a_a5P ipv_s6i :: a_a5P ipv1_s6j :: [a_a5P]} | Last.myLast @ a_a5P (GHC.Base.: @ a_a5P ipv_s6i ipv1_s6j) | = Last.$smyLast @ a_a5P ipv_s6i ipv1_s6j | | It seems that $smyLast is the specialized version of myLast | And the last tidy core rule says that we should replace the | application (myLast (x:xs)) | by ($smyLast x xs). | | We are surprised by the development of the second pattern of $smyLast. | In the second pattern, function myLast is applied to wild_X9 which is | the reference of | ipv_s6j. | | However, according to the running example, | it seems to make more sense if this application is | replaced by a recursive application ($smyLast ipv_3X6r) instead. | | Could you guys please enlighten me? | | Regards, | Kenny | _______________________________________________ | Glasgow-haskell-users mailing list | Glasgow-haskell-users@haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Am Donnerstag, 15. November 2007 09:57 schrieb Simon Peyton-Jones:
Urk. Well spotted!
I omitted a prime (writing env instead of env') in a late fix, and as a result practically no top-level rules and specialisations are being applied.
What an egregious bug. The good news is that a one-character fix should make 6.8.2 perform quite a bit better than 6.8.1!
Simon
I have not yet got round to build my 6.8.1, could you tell me where to insert the prime so I could have the improvement before 6.8.2? Cheers, Daniel
On Thu, Nov 15, 2007 at 10:24:43PM +0100, Daniel Fischer wrote:
Am Donnerstag, 15. November 2007 09:57 schrieb Simon Peyton-Jones:
Urk. Well spotted!
I omitted a prime (writing env instead of env') in a late fix, and as a result practically no top-level rules and specialisations are being applied.
What an egregious bug. The good news is that a one-character fix should make 6.8.2 perform quite a bit better than 6.8.1!
I have not yet got round to build my 6.8.1, could you tell me where to insert the prime so I could have the improvement before 6.8.2?
The darcs patch is: hunk ./compiler/simplCore/Simplify.lhs 267 - add_rules env (bndr, rhs) = (env, (bndr, bndr', rhs)) + add_rules env (bndr, rhs) = (env', (bndr, bndr', rhs)) Thanks Ian
participants (4)
-
Daniel Fischer -
Ian Lynagh -
kenny lu -
Simon Peyton-Jones