#1246: <= operators get compiled worse than ==
-------------------------+--------------------------------------------------
Reporter: duncan | Owner:
Type: bug | Status: new
Priority: normal | Milestone:
Component: Compiler | Version: 6.6
Severity: normal | Keywords:
Difficulty: Unknown | Testcase:
Architecture: x86 | Os: Unknown
-------------------------+--------------------------------------------------
We'd like to define things like 'take' like this:
{{{
take :: Int -> [a] -> [a]
take n _ | n <= 0 = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs
}}}
Which is just the natural implementation from the H98 spec. Unfortunately
to make it run fast it has to be defined like so:
{{{
take :: Int -> [a] -> [a]
take n _ | n <= 0 = []
take n ls = take' n ls
where
take' :: Int -> [a] -> [a]
take' 0 _ = []
take' _ [] = []
take' n (x:xs) = x : take' (n-1) xs
}}}
The crucial difference is factoring out the i <= 0 test so that it is done
just once and then in the loop only matching against exactly 0.
Let's look at the STG:
First for the fast version:
{{{
==================== STG syntax: ====================
Take.$wtake' =
\r [ww_snF w_snH]
case ww_snF of ds_snM {
__DEFAULT ->
case w_snH of wild_so1 {
[] -> [] [];
: x_snL xs_snP ->
let {
sat_snR =
\u []
case -# [ds_snM 1] of sat_snO { __DEFAULT ->
Take.$wtake' sat_snO xs_snP; };
} in : [x_snL sat_snR];
};
0 -> [] [];
};
Take.take =
\r [n_snV ds_so0]
case n_snV of wild_so2 {
GHC.Base.I# x_snY ->
case <=# [x_snY 0] of wild1_so3 {
GHC.Base.False -> Take.$wtake' x_snY ds_so0;
GHC.Base.True -> [] [];
};
};
}}}
So we see this gives us {{{ case _ of _ { __DEFAULT -> ...; 0 -> ...} }}}
where as the simple version gives us:
{{{
Take.$wtake =
\r [ww_sn1 w_sn3]
case <=# [ww_sn1 0] of wild_snl {
GHC.Base.False ->
case w_sn3 of wild1_snm {
[] -> [] [];
: x_sn7 xs_sna ->
let {
sat_snc =
\u []
case -# [ww_sn1 1] of sat_sn9 { __DEFAULT ->
Take.$wtake sat_sn9 xs_sna; };
} in : [x_sn7 sat_snc];
};
GHC.Base.True -> [] [];
};
Take.take =
\r [w_sng w1_snk]
case w_sng of w2_snn { GHC.Base.I# ww_snj -> Take.$wtake ww_snj
w1_snk; };
}}}
Now we get {{{ case n <=# 0# of { True -> ...; False -> ...} }}}. We might
hope that this gives us equivalent code in the backend but sadly it
doesn't, the simple version is slower.
We should be able to do better since at the cpu level calculating
condition codes for == and <= is the same cost, just different
instructions.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/1246>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
