Re: [GHC] #1246: = operators get compiled worse than ==
#1246: = operators get compiled worse than == -+-- Reporter: duncan| Owner: Type: bug | Status: new Priority: low | Milestone: 7.8.1 Component: Compiler | Version: 6.6 Keywords:| Os: Unknown/Multiple Architecture: x86 | Failure: None/Unknown Difficulty: Unknown |Testcase: Blockedby:|Blocking: Related:| -+-- Changes (by simonmar): * blockedby: 4258 = * milestone: 7.6.2 = 7.8.1 -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/1246#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #1246: = operators get compiled worse than ==
#1246: = operators get compiled worse than == ---+ Reporter: duncan| Owner: Type: bug | Status: closed Priority: low | Milestone: 7.8.1 Component: Compiler |Version: 6.6 Resolution: fixed | Keywords: Os: Unknown/Multiple | Architecture: x86 Failure: None/Unknown | Difficulty: Unknown Testcase:| Blockedby: Blocking:|Related: ---+ Changes (by simonmar): * status: new = closed * resolution: = fixed Comment: We now get equal performance for both of these functions, the only difference in the generated code is the conditional (= vs. ==). -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/1246#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #1246: = operators get compiled worse than ==
#1246: = operators get compiled worse than == -+-- Reporter: duncan|Owner: Type: bug | Status: new Priority: normal|Milestone: 7.2.1 Component: Compiler | Version: 6.6 Keywords:| Testcase: Blockedby: 4258 | Difficulty: Unknown Os: Unknown/Multiple | Blocking: Architecture: x86 | Failure: None/Unknown -+-- Changes (by simonmar): * failure: = None/Unknown * blockedby: = 4258 * milestone: 7.0.1 = 7.2.1 -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/1246#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #1246: = operators get compiled worse than ==
#1246: = operators get compiled worse than == -+-- Reporter: duncan|Owner: Type: bug | Status: new Priority: normal|Milestone: 6.14.1 Component: Compiler | Version: 6.6 Severity: normal| Resolution: Keywords:| Difficulty: Unknown Testcase:| Os: Unknown/Multiple Architecture: x86 | -+-- Changes (by simonmar): * milestone: 6.12 branch = 6.14.1 Comment: To look at with the new codegen. -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/1246#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #1246: = operators get compiled worse than ==
#1246: = operators get compiled worse than == -+-- Reporter: duncan|Owner: Type: bug | Status: new Priority: normal|Milestone: 6.12 branch Component: Compiler | Version: 6.6 Severity: normal| Resolution: Keywords:| Difficulty: Unknown Testcase:| Os: Unknown/Multiple Architecture: x86 | -+-- Changes (by igloo): * milestone: 6.10 branch = 6.12 branch -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/1246#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #1246: = operators get compiled worse than ==
On Mon, Mar 26, 2007 at 09:51:02PM -0700, Stefan O'Rear wrote: On Mon, Mar 26, 2007 at 09:31:41PM -0700, John Meacham wrote: On Mon, Mar 26, 2007 at 09:23:13PM -0700, Stefan O'Rear wrote: On Mon, Mar 26, 2007 at 09:15:35PM -0700, John Meacham wrote: actually, this is not true for the specific case of testing against zero on x86 at least. there is a 'zero flag' that is set whenever the result of an operation is zero. whereas for compares, you actually need to load zero into a register and cmp against it. Uh, you mean normal operations don't set the sign flag? (I'm just an assembly programmer and am perfectly willing to defer to a compiler writer on such issues, but it seems like a strange assertion...) They certainly do, but in this particular case, the 'decrement' (n - 1) happens to set the zero flag if n is one so we get that comparison for free. We don't have a flag which immediately tells us whether n = 0 however so we have to perform that comparison separately. Not =, no, but we do have 0 (SF) and =0 (ZF) ; if DEC has the dignity to clear OF we could use the single JLE instruction, otherwise we would need to JS then JZ to the same address. Either way we would not need to explicitly CMP anything. I think. (Actually if DEC sets OF properly then that will work just as well as clearing it.) Ah yes, you are right, that does work. it must be something else that is going on here. John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #1246: = operators get compiled worse than ==
#1246: = operators get compiled worse than == --+- Reporter: duncan| Owner: Type: bug | Status: new Priority: normal| Milestone: Component: Compiler |Version: 6.6 Severity: normal| Resolution: Keywords:| Difficulty: Unknown Testcase:| Architecture: x86 Os: Unknown | --+- Comment (by simonpj): John Meacham says actually, this is not true for the specific case of testing against zero on x86 at least. there is a 'zero flag' that is set whenever the result of an operation is zero. whereas for compares, you actually need to load zero into a register and cmp against it. -- 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 Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #1246: = operators get compiled worse than ==
#1246: = operators get compiled worse than == --+- Reporter: duncan| Owner: Type: bug | Status: new Priority: normal| Milestone: Component: Compiler |Version: 6.6 Severity: normal| Resolution: Keywords:| Difficulty: Unknown Testcase:| Architecture: x86 Os: Unknown | --+- Comment (by duncan): I'm not suggesting any unrolling. I just think the code gen can do better with =# cases. It may well be that at the very low level there is a one or two instruction advantage to comparisons to zero, but I don't think that's the issue here. I'm convinced that the stg - cmm - asm/c translation is not doing as good a job as it could do for these cases. I tried breifly to understand the cmm code from my examples above but didn't get far. -- 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 Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
[GHC] #1246: = operators get compiled worse than ==
#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
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #1246: = operators get compiled worse than ==
On Tue, Mar 27, 2007 at 12:41:30AM -, GHC wrote:
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.
actually, this is not true for the specific case of testing against zero
on x86 at least. there is a 'zero flag' that is set whenever the result
of an operation is zero. whereas for compares, you actually need to load
zero into a register and cmp against it.
though, there could be other things going on with ghc of course.
John
--
John Meacham - ⑆repetae.net⑆john⑈
___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #1246: = operators get compiled worse than ==
On Mon, Mar 26, 2007 at 09:15:35PM -0700, John Meacham wrote: actually, this is not true for the specific case of testing against zero on x86 at least. there is a 'zero flag' that is set whenever the result of an operation is zero. whereas for compares, you actually need to load zero into a register and cmp against it. Uh, you mean normal operations don't set the sign flag? (I'm just an assembly programmer and am perfectly willing to defer to a compiler writer on such issues, but it seems like a strange assertion...) Stefan ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #1246: = operators get compiled worse than ==
On Mon, Mar 26, 2007 at 09:23:13PM -0700, Stefan O'Rear wrote: On Mon, Mar 26, 2007 at 09:15:35PM -0700, John Meacham wrote: actually, this is not true for the specific case of testing against zero on x86 at least. there is a 'zero flag' that is set whenever the result of an operation is zero. whereas for compares, you actually need to load zero into a register and cmp against it. Uh, you mean normal operations don't set the sign flag? (I'm just an assembly programmer and am perfectly willing to defer to a compiler writer on such issues, but it seems like a strange assertion...) They certainly do, but in this particular case, the 'decrement' (n - 1) happens to set the zero flag if n is one so we get that comparison for free. We don't have a flag which immediately tells us whether n = 0 however so we have to perform that comparison separately. John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #1246: = operators get compiled worse than ==
On Mon, Mar 26, 2007 at 09:31:41PM -0700, John Meacham wrote: On Mon, Mar 26, 2007 at 09:23:13PM -0700, Stefan O'Rear wrote: On Mon, Mar 26, 2007 at 09:15:35PM -0700, John Meacham wrote: actually, this is not true for the specific case of testing against zero on x86 at least. there is a 'zero flag' that is set whenever the result of an operation is zero. whereas for compares, you actually need to load zero into a register and cmp against it. Uh, you mean normal operations don't set the sign flag? (I'm just an assembly programmer and am perfectly willing to defer to a compiler writer on such issues, but it seems like a strange assertion...) They certainly do, but in this particular case, the 'decrement' (n - 1) happens to set the zero flag if n is one so we get that comparison for free. We don't have a flag which immediately tells us whether n = 0 however so we have to perform that comparison separately. Not =, no, but we do have 0 (SF) and =0 (ZF) ; if DEC has the dignity to clear OF we could use the single JLE instruction, otherwise we would need to JS then JZ to the same address. Either way we would not need to explicitly CMP anything. I think. (Actually if DEC sets OF properly then that will work just as well as clearing it.) Stefan ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
