Opened 4 years ago

Last modified 4 years ago

#11146 new bug

Manual eta expansion leads to orders of magnitude less allocations

Reported by: niteria Owned by:
Priority: normal Milestone:
Component: Compiler Version: 7.10.2
Keywords: Cc: simonmar, simonpj, osa1
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

While working on deterministic free variable computation I run into some performance issues. I narrowed it down to code that when eta expanded performed less allocations.

I ended up writing a benchmark and for large examples the eta expanded versions performs orders of magnitude less allocations.

The results of my test:

EtaExpanded test3
      50,450,112 bytes allocated in the heap
real 0.89

EtaReduced test3
   3,661,740,240 bytes allocated in the heap
real 3.66

The whole source is here: https://github.com/niteria/deterministic-fvs, I'm also attaching the two interesting implementations.

I experimented with it a little and GHC eta-expanded when I didn't have mutually recursive bindings.

Attachments (5)

FVCommon.hs (732 bytes) - added by niteria 4 years ago.
FVCommon.hs
FV.hs (530 bytes) - added by niteria 4 years ago.
EtaExpanded/FV.hs
FV.2.hs (332 bytes) - added by niteria 4 years ago.
EtaReduced/FV.hs
Tests.hs (1.1 KB) - added by niteria 4 years ago.
Tests.hs
Types.hs (95 bytes) - added by niteria 4 years ago.
Types.hs

Download all attachments as: .zip

Change History (13)

Changed 4 years ago by niteria

Attachment: FVCommon.hs added

FVCommon.hs

Changed 4 years ago by niteria

Attachment: FV.hs added

EtaExpanded/FV.hs

Changed 4 years ago by niteria

Attachment: FV.2.hs added

EtaReduced/FV.hs

Changed 4 years ago by niteria

Attachment: Tests.hs added

Tests.hs

comment:1 Changed 4 years ago by niteria

Cc: simonmar simonpj added

comment:2 Changed 4 years ago by nomeata

Let me be cheeky: Where is the bug in the report?

It is not a secret that eta-expanded definitions tend to perform better, unless you make use of sharing somewhere. So maybe you did expect the compiler to make that transformation for you? But for that to happen, the compiler needs to be very sure that it is safe to do so (e.g. no loss of sharing), and in a modular compiler, that is often not possible.

Do you have a (hopefully small and self-contained) bit of code where you think “duh, obviously the compiler should be a allowed to eta-expand here”, but it does not?

Do things are better if all the relevant code is in one module, with an explicit export list that does not include any of the functions you’d like to see eta-expanded?

comment:3 Changed 4 years ago by niteria

Where is the bug in the report?

I'm not convinced this is a bug. I've created this in response to this comment: https://phabricator.haskell.org/D1537#inline-12820.

Do you have a (hopefully small and self-contained) bit of code where you think “duh, obviously the compiler should be a allowed to eta-expand here”, but it does not?

I can't tell if GHC should be allowed to eta-expand in my example, but the fact that it decided to eta-expand in a very similar situation where I didn't have mutually recursive functions suggests that it might be able to.

Do things are better if all the relevant code is in one module, with an explicit export list that does not include any of the functions you’d like to see eta-expanded?

Yes, it's enough to not export the functions I want eta-expanded. Unfortunately that's exactly what I want do in Phab:D1537 because I'm composing a computation from smaller pieces from several modules.

comment:4 Changed 4 years ago by osa1

Could you also add Types.hs? It's used in all of the modules you added.

Changed 4 years ago by niteria

Attachment: Types.hs added

Types.hs

comment:5 Changed 4 years ago by nomeata

Yes, it's enough to not export the functions I want eta-expanded. Unfortunately that's exactly what I want do in ​Phab:D1537 because I'm composing a computation from smaller pieces from several modules.

Then GHC (likely Call Arity \o/) seems to be smart enough to do the expansion if it is allowed to operate on the whole code at once, as desired.

But with the code spread over several modules, there isn’t really much GHC can do here. You could try to make it INLINE more aggressively, or simply do the eta-expansion as you do now.

comment:6 Changed 4 years ago by osa1

I just tried INLINEing all the functions defined in FV and FV2, it didn't make any difference. (maybe because GHC was already inlining?) (tried with -O2)

comment:7 Changed 4 years ago by osa1

Cc: osa1 added

comment:8 Changed 4 years ago by thomie

Type of failure: None/UnknownRuntime performance bug
Note: See TracTickets for help on using tickets.