#15802 closed bug (duplicate)

Inlining of constant fails when both cross-module and recursive

Reported by: j6carey Owned by:
Priority: highest Milestone:
Component: Compiler Version: 8.6.1
Keywords: Cc:
Operating System: Linux Architecture: x86_64 (amd64)
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: 10346 Differential Rev(s):
Wiki Page:

Description

When an inline recursive function is applied to a constant, that application may reduce if it is in the same module, but will not reduce when in a different module. (Naturally, this harms the ability to split a program into modules while retaining efficiency.)

For example, consider the following files:

T1.hs:

module T1 where

data IntList = Nil | Cons Int IntList

mapIntList :: (Int -> Int) -> IntList -> IntList
mapIntList f Nil = Nil
mapIntList f (Cons x xs) = Cons (f x) (mapIntList f xs)
{-# INLINE mapIntList #-}

mappedNil :: IntList
mappedNil = mapIntList id Nil

T2.hs:

module T2 where

data IntList = Nil | Cons Int IntList

mapIntList :: (Int -> Int) -> IntList -> IntList
mapIntList f Nil = Nil
mapIntList f (Cons x xs) = Cons (f x) (mapIntList f xs)
{-# INLINE mapIntList #-}

T3.hs:

module T3 where

import T2

mappedNil :: IntList
mappedNil = mapIntList id Nil

The program built from T1.hs should be equivalent to the one built from T2.hs and T3.hs; however, the core output from GHC 8.6.1 with -O2 differs significantly.

In the single-module case we obtain:

mappedNil = T1.Nil

Whereas in the two-module case we see:

mappedNil = mapIntList (id @ Int) T2.Nil

Recursion is relevant; the problem disappears if we make this change:

data IntList = Nil | Cons Int Int

mapIntList :: (Int -> Int) -> IntList -> IntList
mapIntList f Nil = Nil
mapIntList f (Cons x xs) = Cons (f x) (f xs)
{-# INLINE mapIntList #-}

Attachments (3)

T1.hs (262 bytes) - added by j6carey 11 months ago.
T2.hs (210 bytes) - added by j6carey 11 months ago.
T3.hs (79 bytes) - added by j6carey 11 months ago.

Download all attachments as: .zip

Change History (7)

Changed 11 months ago by j6carey

Attachment: T1.hs added

Changed 11 months ago by j6carey

Attachment: T2.hs added

Changed 11 months ago by j6carey

Attachment: T3.hs added

comment:1 Changed 11 months ago by mpickering

This is because SpecConstr doesn't work across modules.

See https://phabricator.haskell.org/D3566 and #10346

However, your intuition that if you apply a function to a constantly known value then it should reduce is misguided. SpecConstr only works in a narrow set of circumstances and the inliner will never inline recursive functions.

If you want to guarantee performance then the only way that I know is to use (typed) template haskell

comment:2 Changed 11 months ago by j6carey

Sorry to be unclear; I was mentioning INLINE because it ensures that the function definition is available to other modules, and therefore ensures that a reduction would be possible, not because I expect general inlining of recursive functions.

I am pretty sure that https://ghc.haskell.org/trac/ghc/ticket/10346 would do everything that I need. It also suggests that meanwhile I might be able to find an alternative design using type classes; I'll see what I can do.

Thanks for spotting that this is a duplicate issue!

comment:3 Changed 11 months ago by j6carey

Priority: normalhighest

comment:4 Changed 11 months ago by j6carey

Resolution: duplicate
Status: newclosed
Note: See TracTickets for help on using tickets.