Skip to content

GitLab

  • Projects
  • Groups
  • Snippets
  • Help
    • Loading...
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
  • Sign in / Register
GHC
GHC
  • Project overview
    • Project overview
    • Details
    • Activity
    • Releases
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
    • Locked Files
  • Issues 4,392
    • Issues 4,392
    • List
    • Boards
    • Labels
    • Service Desk
    • Milestones
    • Iterations
  • Merge Requests 374
    • Merge Requests 374
  • Requirements
    • Requirements
    • List
  • CI / CD
    • CI / CD
    • Pipelines
    • Jobs
    • Schedules
    • Test Cases
  • Operations
    • Operations
    • Incidents
    • Environments
  • Analytics
    • Analytics
    • CI / CD
    • Code Review
    • Insights
    • Issue
    • Repository
    • Value Stream
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Members
    • Members
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • Glasgow Haskell Compiler
  • GHCGHC
  • Issues
  • #18789

Closed
Open
Opened Oct 01, 2020 by Ben Gamari@bgamari🐢Maintainer

Called-arity analysis can be quite slow

While looking into #18787, I noticed that called-arity analysis sometimes takes significantly longer than the surrounding simplifier runs: For instance, when compiling Cubix.Transformations.Hoist.Custom (in the library component) we have:

...
!!! Simplifier [Cubix.Transformations.Hoist.Custom]: finished in 5165.03 milliseconds, allocated 3856.175 megabytes                  
Simplifier [Cubix.Transformations.Hoist.Custom]: alloc=4043492976 time=5165.031
*** Simplifier [Cubix.Transformations.Hoist.Custom]:
Result size of Simplifier iteration=1
  = {terms: 125,012,
     types: 1,879,379,
     coercions: 653,833,
     joins: 11/64}
Result size of Simplifier iteration=2
  = {terms: 124,937,
     types: 1,874,464,
     coercions: 653,810,
     joins: 12/60}
Result size of Simplifier
  = {terms: 124,937,
     types: 1,874,464,
     coercions: 653,810,
     joins: 12/60}
!!! Simplifier [Cubix.Transformations.Hoist.Custom]: finished in 8663.68 milliseconds, allocated 2890.067 megabytes
Simplifier [Cubix.Transformations.Hoist.Custom]: alloc=3030454976 time=8663.675
*** Float inwards [Cubix.Transformations.Hoist.Custom]:
Result size of Float inwards
  = {terms: 124,937,
     types: 1,874,464,
     coercions: 653,810,
     joins: 12/60}
!!! Float inwards [Cubix.Transformations.Hoist.Custom]: finished in 121.60 milliseconds, allocated 94.945 megabytes
Float inwards [Cubix.Transformations.Hoist.Custom]: alloc=99557424 time=121.605
*** Called arity analysis [Cubix.Transformations.Hoist.Custom]:
Result size of Called arity analysis
  = {terms: 124,937,
     types: 1,874,464,
     coercions: 653,810,
     joins: 12/60}
!!! Called arity analysis [Cubix.Transformations.Hoist.Custom]: finished in 111594.82 milliseconds, allocated 77722.139 megabytes
Called arity analysis [Cubix.Transformations.Hoist.Custom]: alloc=81497569472 time=111594.817
*** Simplifier [Cubix.Transformations.Hoist.Custom]:
Result size of Simplifier iteration=1
  = {terms: 124,925,
     types: 1,872,004,
     coercions: 653,805,                                                                                                             
     joins: 13/60}                                                                                                                   
Result size of Simplifier                                                                                                            
  = {terms: 124,925,                                                                                                                 
     types: 1,872,004,                                                                                                               
     coercions: 653,805,                                                                                                             
     joins: 13/60}                                                                                                                   
!!! Simplifier [Cubix.Transformations.Hoist.Custom]: finished in 2271.06 milliseconds, allocated 1926.801 megabytes                  
...

That is called arity analysis takes over two minutes where the simplifier takes less than 10 seconds on what is likely a very similar Core program.

It sounds to me like there may be something quadratic lurking here.

Assignee
Assign to
None
Milestone
None
Assign milestone
Time tracking
None
Due date
None
Reference: ghc/ghc#18789