[GHC] #11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing
#11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing -------------------------------------+------------------------------------- Reporter: alexbiehl | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- Tyson Whitehead gives a detailed description of the problem [https://github.com/haskell/bytestring/issues/70 here]. Key points: - Program fails to rewrite {{{ ByteString.break (== x) chunk }}} to {{{ ByteString.breakByte x chunk }}} - Missed unboxing opportunity (which led to 34gb additional allocations, which is why he noticed it) I could reproduce the problem on OSX and Windows with GHC 7.10.3. Haven't tested Linux. I repost it here to make sure it doesn't go unnoticed. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11688> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing -------------------------------------+------------------------------------- Reporter: alexbiehl | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by alexbiehl): * Attachment "tywhitehead_rewrite.hs" added. Test program from Tywhitedheads bug report -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11688> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing -------------------------------------+------------------------------------- Reporter: alexbiehl | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Description changed by alexbiehl: @@ -10,1 +10,1 @@ - I could reproduce the problem on OSX and Windows with GHC 7.10.3. Haven't + I can reproduce the problem on OSX and Windows with GHC 7.10.3. Haven't New description: Tyson Whitehead gives a detailed description of the problem [https://github.com/haskell/bytestring/issues/70 here]. Key points: - Program fails to rewrite {{{ ByteString.break (== x) chunk }}} to {{{ ByteString.breakByte x chunk }}} - Missed unboxing opportunity (which led to 34gb additional allocations, which is why he noticed it) I can reproduce the problem on OSX and Windows with GHC 7.10.3. Haven't tested Linux. I repost it here to make sure it doesn't go unnoticed. -- -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11688#comment:1> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing -------------------------------------+------------------------------------- Reporter: alexbiehl | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by alexbiehl): * Attachment "11688_smaller_testcase.hs" added. Smaller testcase which failes to rewrite break and failes to unbox result of findIndexOrEnd -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11688> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing -------------------------------------+------------------------------------- Reporter: alexbiehl | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by alexbiehl): (Compile both example with {{{ -ddump-simpl -O2 -ddump-simpl -dsuppress- all -dno-suppress-idinfo }}}) -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11688#comment:2> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing -------------------------------------+------------------------------------- Reporter: alexbiehl | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): I briefly looked at this; I left a comment on the `bytestring` ticket which I'll reproduce here,
I suspect the issue here is that `(==)` is being inlined too early, hiding the rule fire opportunity. By contrast, if you give `(==)` another name with a later inline pragma the `break -> breakByte` rule fires as expected.
{{{#!hs main = do chunk <- DB.hGetSome stdin 32768 let newline = c2w '\n' let (prefix,suffix) = DB.break (eq newline) chunk DB.hPut stdout prefix DB.hPut stdout suffix
eq :: Eq a => a -> a -> Bool eq = (==) {-# INLINE [1] eq #-}
{-# RULES "ByteString specialise break (eq x)" forall x. DB.break (eq x) = DB.breakByte x #-} }}}
Actually, even if one doesn't specify an explicit phase on `eq` the rule still fires! This is likely accidental, since GHC just happens to look at the `breakByte` rule before the `eq` inlining.
-- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11688#comment:3> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing -------------------------------------+------------------------------------- Reporter: alexbiehl | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1980 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: new => patch * failure: None/Unknown => Runtime performance bug * differential: => Phab:D1980 Comment: Phab:D1980 is a proposed fix. I believe it should be safe to defer inlining `Eq` and `Ord`, but this needs confirmation. I'm really not sure whether we want to risk pushing this to 8.0, even if we do conclude that it's the right way forward. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11688#comment:4> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing -------------------------------------+------------------------------------- Reporter: alexbiehl | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1980 Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): Oh dear, Phab:D1980 actually won't work at all; the problem isn't the inlining of the class methods themselves, it is the class op rule generated by GHC. Namely, {{{ Rule fired Rule: Class op == Before: GHC.Classes.== TyArg GHC.Word.Word8 ValArg GHC.Word.$fEqWord8 ValArg ds_d2p3 ValArg ds_d2p4 After: GHC.Word.$fEqWord8_$c== Cont: Stop[BoringCtxt] GHC.Types.Bool }}} This will require further pondering. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11688#comment:5> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing -------------------------------------+------------------------------------- Reporter: alexbiehl | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1980 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: patch => new -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11688#comment:6> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing -------------------------------------+------------------------------------- Reporter: alexbiehl | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1980 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): This comes up regularly; e.g. #10595, #7141 (maybe), #5973 (maybe), #4397 (I bet the fix is delicate), #2271, #1434. And #10418 is similar but for constructors not class ops. In general, I it's dangerous to match on an overloaded class op. After all, did you really mean to match on `(==)` at every type? I doubt it? In this case we mean `==` at type `Char`. So the advice in comment:4 of #10595, is to write {{{ instance Eq Char where (==) = eqChar eqChar :: Char -> Char -> Bool {-# INLINE [0] eqChar #-} -- Delay inlining }}} and then make the rule be {{{ {-# RULES "bsbreak" forall x chunk. ByteString.break (eqChar x) chunk = ... #-} }}} This is simple and robust. But it does mean chaging the base library to use named functions for instance methods. Probably good practice anyway. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11688#comment:7> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing -------------------------------------+------------------------------------- Reporter: alexbiehl | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1980 Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): Alright, we should make sure this wisdom ends up in the users guide somewhere (and maybe even the Haddocks of `GHC.Classes`; I was wondering what purpose `eqInt` served). -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11688#comment:8> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing -------------------------------------+------------------------------------- Reporter: alexbiehl | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1980 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Yes, we should! Also can you make the base-lib changes; and check that with the right RULE the original bug in `bytestring` is fixed? And then tell the `bytestring` devs. Incidentally, doesn't the rule elicit a warning? It should! -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11688#comment:9> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing -------------------------------------+------------------------------------- Reporter: alexbiehl | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1980 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: new => patch Comment: Here's a new patch which makes the `base` changes (although only for `Eq`; perhaps we should give the same treatment to `Ord` as well?) and adds some documentation. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11688#comment:10> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing -------------------------------------+------------------------------------- Reporter: alexbiehl | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1980 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): See also #10528, esp comment:13, which explains why rewriting the LHS of a rule is not so cool. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11688#comment:11> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing -------------------------------------+------------------------------------- Reporter: alexbiehl | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1980 Wiki Page: | -------------------------------------+------------------------------------- Comment (by Ben Gamari <ben@…>): In [changeset:"0bd0c31e833055eb3e86177f70c4b4d93d5a1c11/ghc" 0bd0c31e/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="0bd0c31e833055eb3e86177f70c4b4d93d5a1c11" Defer inlining of Eq for primitive types Summary: This is one solution to #11688, wherein (==) was inlined to soon defeating a rewrite rule provided by bytestring. Since the RHSs of Eq's methods are simple, there is little to be gained and much to be lost by inlining them early. For instance, the bytestring library provides, ```lang=haskell break :: (Word8 -> Bool) -> ByteString -> (ByteString, ByteString) breakByte :: Word8 -> ByteString -> (ByteString, ByteString) ``` and a rule ``` forall x. break ((==) x) = breakByte x ``` since `breakByte` implments an optimized version of `break (== x)` for known `x :: Word8`. If we allow `(==)` to be inlined too early, we will prevent this rule from firing. This was the cause of #11688. This patch just defers the `Eq` methods, although it's likely worthwhile giving `Ord` this same treatment. This regresses compiler allocations for T9661 by about 8% due to the additional inlining that we now require the simplifier to perform. Updates the `bytestring` submodule to include updated rewrite rules which match on `eqWord8` instead of `(==)`. Test Plan: * Validate, examine performance impact Reviewers: simonpj, hvr, austin Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D1980 GHC Trac Issues: #11688 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11688#comment:12> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing -------------------------------------+------------------------------------- Reporter: alexbiehl | Owner: Type: bug | Status: upstream Priority: normal | Milestone: 8.0.1 Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1980 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: patch => upstream * milestone: => 8.0.1 Comment: Merged to `ghc-8.0` as ed3398d176fc777dff8f5ae5315425e40c705c2d. I have a `bytestring` branch updating the rewrite rules which I now need to upstream. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11688#comment:13> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing -------------------------------------+------------------------------------- Reporter: alexbiehl | Owner: Type: bug | Status: upstream Priority: normal | Milestone: 8.0.1 Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1980 Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): I've opened [[https://github.com/haskell/bytestring/pull/71/files|bytestring #71]] for the rewrite rule fixes. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11688#comment:14> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing -------------------------------------+------------------------------------- Reporter: alexbiehl | Owner: Type: bug | Status: upstream Priority: normal | Milestone: 8.0.1 Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1980 Wiki Page: | -------------------------------------+------------------------------------- Comment (by Ben Gamari <ben@…>): In [changeset:"26f86f3d397159f9c0db0b59766138f553ba5a86/ghc" 26f86f3/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="26f86f3d397159f9c0db0b59766138f553ba5a86" base: Fix GHC.Word and GHC.Int on 32-bit platforms Due to a cut-and-paste error D1980 (#11688) broke 32-bit platforms. This should fix it. See #11750. }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11688#comment:15> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing -------------------------------------+------------------------------------- Reporter: alexbiehl | Owner: Type: bug | Status: upstream Priority: normal | Milestone: 8.0.1 Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1980 Wiki Page: | -------------------------------------+------------------------------------- Comment (by Herbert Valerio Riedel <hvr@…>): In [changeset:"eb25381da2e4a95337ad9c2fabff60d699b41bc7/ghc" eb25381d/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="eb25381da2e4a95337ad9c2fabff60d699b41bc7" Update bytestring submodule to latest snapshot Most notably, this pulls in the following changes
Fix breakByte and spanByte rewrite rules Implement `stripPrefix`/`stripSuffix`
The first patch is related to #11688 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11688#comment:16> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing -------------------------------------+------------------------------------- Reporter: alexbiehl | Owner: Type: bug | Status: closed Priority: normal | Milestone: 8.0.1 Component: Compiler | Version: 7.10.3 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1980 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: upstream => closed * resolution: => fixed Comment: Merged to `ghc-8.0` as well. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11688#comment:17> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#11688: Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing -------------------------------------+------------------------------------- Reporter: alexbiehl | Owner: Type: bug | Status: closed Priority: normal | Milestone: 8.0.1 Component: Compiler | Version: 7.10.3 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D1980 Wiki Page: | -------------------------------------+------------------------------------- Comment (by bgamari): I've given the same treatment to the `Ord` instances in c0e3e63eca6b0f7a21ae51d992c88821195ad94d. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/11688#comment:18> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
participants (1)
-
GHC