Opened 3 years ago

Closed 3 years ago

Last modified 3 years ago

#11688 closed bug (fixed)

Bytestring break failing rewrite to breakByte and failing to eliminate boxing/unboxing

Reported by: alexbiehl Owned by:
Priority: normal Milestone: 8.0.1
Component: Compiler Version: 7.10.3
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s): Phab:D1980
Wiki Page:

Description (last modified by alexbiehl)

Tyson Whitehead gives a detailed description of the problem 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.

Attachments (2)

tywhitehead_rewrite.hs (923 bytes) - added by alexbiehl 3 years ago.
Test program from Tywhitedheads bug report
11688_smaller_testcase.hs (280 bytes) - added by alexbiehl 3 years ago.
Smaller testcase which failes to rewrite break and failes to unbox result of findIndexOrEnd

Download all attachments as: .zip

Change History (20)

Changed 3 years ago by alexbiehl

Attachment: tywhitehead_rewrite.hs added

Test program from Tywhitedheads bug report

comment:1 Changed 3 years ago by alexbiehl

Description: modified (diff)

Changed 3 years ago by alexbiehl

Attachment: 11688_smaller_testcase.hs added

Smaller testcase which failes to rewrite break and failes to unbox result of findIndexOrEnd

comment:2 Changed 3 years ago by alexbiehl

(Compile both example with -ddump-simpl -O2 -ddump-simpl -dsuppress-all -dno-suppress-idinfo )

comment:3 Changed 3 years ago 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.

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.

comment:4 Changed 3 years ago by bgamari

Differential Rev(s): Phab:D1980
Status: newpatch
Type of failure: None/UnknownRuntime performance bug

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.

comment:5 Changed 3 years ago 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 (which is the very first rule that fires). 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.

Last edited 3 years ago by bgamari (previous) (diff)

comment:6 Changed 3 years ago by bgamari

Status: patchnew

comment:7 Changed 3 years ago 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.

comment:8 Changed 3 years ago 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).

comment:9 Changed 3 years ago 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!

comment:10 Changed 3 years ago by bgamari

Status: newpatch

Here's a new patch (Phab:D1980 again) which makes the base changes (although only for Eq; perhaps we should give the same treatment to Ord as well?) and adds some documentation.

Last edited 3 years ago by bgamari (previous) (diff)

comment:11 Changed 3 years ago by simonpj

See also #10528, especially ticket:10528#comment:13, which explains why rewriting the LHS of a rule is not so cool.

Last edited 3 years ago by bgamari (previous) (diff)

comment:12 Changed 3 years ago by Ben Gamari <ben@…>

In 0bd0c31e/ghc:

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

comment:13 Changed 3 years ago by bgamari

Milestone: 8.0.1
Status: patchupstream

Merged to ghc-8.0 as ed3398d176fc777dff8f5ae5315425e40c705c2d.

I have a bytestring branch updating the rewrite rules which I now need to upstream.

comment:14 Changed 3 years ago by bgamari

I've opened bytestring #71 for the rewrite rule fixes.

comment:15 Changed 3 years ago by Ben Gamari <ben@…>

In 26f86f3/ghc:

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.

comment:16 Changed 3 years ago by Herbert Valerio Riedel <hvr@…>

In eb25381d/ghc:

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

comment:17 Changed 3 years ago by bgamari

Resolution: fixed
Status: upstreamclosed

Merged to ghc-8.0 as well.

comment:18 Changed 3 years ago by bgamari

I've given the same treatment to the Ord instances in c0e3e63eca6b0f7a21ae51d992c88821195ad94d.

Note: See TracTickets for help on using tickets.