#9251: ghc does not expose branchless max/min operations as primops -------------------------------------+------------------------------------ Reporter: carter | Owner: carter Type: task | Status: new Priority: normal | Milestone: 7.10.1 Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: None/Unknown | Difficulty: Unknown Test Case: | Blocked By: Blocking: | Related Tickets: #9246 -------------------------------------+------------------------------------ Comment (by arotenberg): Question: What "should" the behaviors of min and max be for the special cases of negative zero and NaN? Currently GHC does this: {{{ Prelude> min 0.0 (-0.0) :: Double 0.0 Prelude> min (-0.0) 0.0 :: Double -0.0 Prelude> min 0.0 (0.0/0.0) :: Double NaN Prelude> min (0.0/0.0) 0.0 :: Double 0.0 }}} The SSE instructions, at least, [http://x86.renejeschke.de/html/file_module_x86_id_173.html work similarly if you get the order right]: If the values being compared are both 0.0s (of either sign), the value in the second operand (source operand) is returned. If a value in the second operand is an SNaN, that SNaN is returned unchanged to the destination (that is, a QNaN version of the SNaN is not returned). If only one value is a NaN (SNaN or QNaN) for this instruction, the second operand (source operand), either a NaN or a valid floating-point value, is written to the result. If instead of this behavior, it is required that the NaN source operand (from either the first or second operand) be returned, the action of MINSD can be emulated using a sequence of instructions, such as, a comparison followed by AND, ANDN and OR. However, [http://en.wikipedia.org/wiki/IEEE_754_revision#min_and_max according to Wikipedia], IEEE 754-2008 specifies The min and max operations are defined but leave some leeway for the case where the inputs are equal in value but differ in representation. In particular: min(+0,−0) or min(−0,+0) must produce something with a value of zero but may always return the first argument. In order to support operations such as windowing in which a NaN input should be quietly replaced with one of the end points, min and max are defined to select a number, x, in preference to a quiet NaN: min(x,NaN) = min(NaN,x) = x max(x,NaN) = max(NaN,x) = x In the current draft, these functions are called minNum and maxNum to indicate their preference for a number over a quiet NaN. Some further comparisons: Java's `Math.min` [http://docs.oracle.com/javase/8/docs/api/java/lang/Math.html#min-double- double- specifies] Returns the smaller of two double values. That is, the result is the value closer to negative infinity. If the arguments have the same value, the result is that same value. If either value is NaN, then the result is NaN. Unlike the numerical comparison operators, this method considers negative zero to be strictly smaller than positive zero. If one argument is positive zero and the other is negative zero, the result is negative zero. The .NET Framework's `Math.Min` [http://msdn.microsoft.com/en- us/library/xcd487wd%28v=vs.110%29.aspx specifies] Parameter val1 or val2, whichever is smaller. If val1, val2, or both val1 and val2 are equal to NaN, NaN is returned. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9251#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9251: ghc does not expose branchless max/min operations as primops -------------------------------------+------------------------------------ Reporter: carter | Owner: carter Type: task | Status: new Priority: normal | Milestone: 7.10.1 Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: None/Unknown | Difficulty: Unknown Test Case: | Blocked By: Blocking: | Related Tickets: #9246 -------------------------------------+------------------------------------ Comment (by carter): actually, importantly, in section 5.11 of the 2008 standard they say Four mutually exclusive relations are possible: **less than** , **equal**, **greater than**, and **unordered**. The last case arises when at least one operand is NaN. Every NaN shall compare unordered with everything, including itself. Comparisons shall ignore the sign of zero (so +0 = −0). Infinite operands of the same sign shall compare equal. thus the Ord compare based instance should actually perhaps throw an exception or otherwise fail when either argument is Nan? I'll need read a bit more. ANYWAY, theres several *distinct* semantics that can be chosen, and adding suitable support to ghc for the different semantics that aren't interexpressible is something I'll spend some time thinking about. don't worry, you'll have the version you want, but there will be an IEEE compliant one that also satisfies the corresponding haskell standard (BOTH, if they disagree theres a serious problem i'll have to have some discussion about) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9251#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9251: ghc does not expose branchless max/min operations as primops -------------------------------------+------------------------------------ Reporter: carter | Owner: carter Type: task | Status: new Priority: normal | Milestone: 7.10.1 Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: None/Unknown | Difficulty: Unknown Test Case: | Blocked By: Blocking: | Related Tickets: #9246 -------------------------------------+------------------------------------ Comment (by arotenberg): Yeah, I've seen those slides before. The problem with the arguments presented is that I know there is a class of users who demands "linguistically-legislated exact reproducibility" for floating-point computations, because I'm part of it! For my day job, I use Java to write a tool for modeling safety-critical software systems on desktop hardware. For our purposes, it is ''far'' more important that the results of the simulation be exactly identical across different platforms than it is they be numerically accurate or efficiently computable. We use Java's `strictfp` keyword and `StrictMath` class ubiquitously in our simulation engine, because it is essential that the output of our program be identical, no matter where or when it is run. When it is necessary to compute different or more numerically-accurate floating-point outputs, we emulate it in software. This is slow but allows us 100% confidence that you will always get the same results. That said, our application is a rare case. In most situations, faster and more accurate computations that can give slightly different results on different machines are preferable to calculations that are wrong in exactly-reproducible ways. Which section (if any) of the Haskell 2010 Report specifies the behavior of floating-point operations? I've glanced through it quickly but all I've been able to find is [https://www.haskell.org/onlinereport/haskell2010/haskellch9.html#x16-1710009 the Prelude definitions of the instances for Float and Double], which just list them as primitives. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9251#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9251: ghc does not expose branchless max/min operations as primops -------------------------------------+------------------------------------- Reporter: carter | Owner: carter Type: task | Status: new Priority: normal | Milestone: 7.10.1 Component: Compiler | Version: 7.8.2 Resolution: | Keywords: newcomer Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: Runtime | Blocked By: performance bug | Related Tickets: #9246 Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by thomie): * keywords: => newcomer * failure: None/Unknown => Runtime performance bug Comment: Adding 'newcomer' keyword by carter's suggestion in the description. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9251#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9251: ghc does not expose branchless max/min operations as primops -------------------------------------+------------------------------------- Reporter: carter | Owner: Type: task | Status: new Priority: normal | Milestone: 7.10.1 Component: Compiler | Version: 7.8.2 Resolution: | Keywords: newcomer Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: Runtime | Blocked By: performance bug | Related Tickets: #9246 Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by carter): sure thing. I think the only newcomer friendly bit would be writing the branchless min/max for Word and Int and friends. its a bit more subtle for the floating point versions -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9251#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9251: ghc does not expose branchless max/min operations as primops -------------------------------------+------------------------------------- Reporter: carter | Owner: Type: task | Status: new Priority: normal | Milestone: 7.12.1 Component: Compiler | Version: 7.8.2 Resolution: | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9246 | Differential Revisions: -------------------------------------+------------------------------------- Comment (by carter): the idea is not to use it for the normal comparison code, but to make it available for those who need suitable supporting primops. *THOUGH* if we can provide suitable instruction level versions of the Ord based min and max, thats a thing we can think about too. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9251#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9251: ghc does not expose branchless max/min operations as primops -------------------------------------+------------------------------------- Reporter: carter | Owner: osa1 Type: task | Status: new Priority: normal | Milestone: 8.0.1 Component: Compiler | Version: 7.8.2 Resolution: | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9246 | Differential Revisions: -------------------------------------+------------------------------------- Changes (by WrenThornton): * cc: wren@… (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9251#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9251: ghc does not expose branchless max/min operations as primops -------------------------------------+------------------------------------- Reporter: carter | Owner: osa1 Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9246 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by rockbmb): Hello; What is the status on this issue? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9251#comment:19 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9251: ghc does not expose branchless max/min operations as primops -------------------------------------+------------------------------------- Reporter: carter | Owner: osa1 Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9246 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by ulysses4ever): Ben, I'm interested in this. For osa1's work: I don't see a patch. [https://lpaste.net/134455 His link above] has a tiny example program using something called `min##` which is not defined there. Is there a clear strategy on how to attack this ticket? Let's say, starting with the most conservative step: provide primop version of integer `min` / `max` which, for x86, is implemented in assembly (`CMOV` or SSE4's `PMINSD` / `PMAXSD`). -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9251#comment:21 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9251: ghc does not expose branchless max/min operations as primops -------------------------------------+------------------------------------- Reporter: carter | Owner: osa1 Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9246 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by ulysses4ever): I agree with measure-first reasoning. How would one compare the performance of the current code with the one using primop which we haven't defined yet, though? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9251#comment:23 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9251: ghc does not expose branchless max/min operations as primops -------------------------------------+------------------------------------- Reporter: carter | Owner: osa1 Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #9246 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): Well, implementing then measuring (and accept the fact that the implementation may be thrown away as a consequence) is one option. However, another option would be to work incrementally: measuring a best- case speed-up in a C (or similar) program. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9251#comment:25 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler