Opened 4 years ago

Closed 4 years ago

#11162 closed bug (fixed)

T783 regresses severely in allocations with new pattern match checker

Reported by: bgamari Owned by:
Priority: normal Milestone: 8.0.1
Component: Compiler Version: 7.10.2
Keywords: PatternMatchWarnings Cc: gkaracha
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time performance bug Test Case: T783
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

The new pattern match checker (Phab:D1535) allocates 115% more than the previous checker on the T783 testcase,

bytes allocated value is too high:
    Expected    T783(normal) bytes allocated:  526230456 +/-10%
    Lower bound T783(normal) bytes allocated:  473607410 
    Upper bound T783(normal) bytes allocated:  578853502 
    Actual      T783(normal) bytes allocated: 1134085384 
    Deviation   T783(normal) bytes allocated:      115.5 %
*** unexpected stat test failure for T783(normal)

I suspect this isn't avoidable as this testcase consists of nothing more than 500 guarded equations, so exercises the checker quite thoroughly. That being said, perhaps it's worth a closer look.

Change History (6)

comment:1 Changed 4 years ago by bgamari

George, feel free to close this if you believe that there is no easy fix here.

comment:2 Changed 4 years ago by Ben Gamari <ben@…>

In e9220daf/ghc:

Bump allocations for T783

The new pattern match checker increased allocations by over 100%.
Tracking in #11162.

comment:3 Changed 4 years ago by simonpj

Keywords: PatternMatchWarnings added

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

In 28f951e/ghc:

Overhaul the Overhauled Pattern Match Checker

Overhaul the Overhauled Pattern Match Checker

* Changed the representation of Value Set Abstractions. Instead of
using a prefix tree, we now use a list of Value Vector Abstractions.
The set of constraints Delta for every Value Vector Abstraction is the
oracle state so that we solve everything only once.

* Instead of doing everything lazily, we prune at once (and in general
everything is much stricter). Hence, an example written with pattern
guards is checked in almost the same time as the equivalent with
pattern matching.

* Do not store the covered and the divergent sets at all. Since what we
only need is a yes/no (does this clause cover anything? Does it force
any thunk?) We just keep a boolean for each.

* Removed flags `-Wtoo-many-guards` and `-ffull-guard-reasoning`.
Replaced with `fmax-pmcheck-iterations=n`. Still debatable what should
the default `n` be.

* When a guard is for sure not going to contribute anything, we treat
it as such: The oracle is not called and cases `CGuard`, `UGuard` and
`DGuard` from the paper are not happening at all (the generation of a
fresh variable, the unfolding of the pattern list etc.). his combined
with the above seems to be enough to drop the memory increase for test
T783 down to 18.7%.

* Do not export function `dsPmWarn` (it is now called directly from
within `checkSingle` and `checkMatches`).

* Make `PmExprVar` hold a `Name` instead of an `Id`. The term oracle
does not handle type information so using `Id` was a waste of
time/space.

* Added testcases T11195, T11303b (data families) and T11374

The patch addresses at least the following:
Trac #11195, #11276, #11303, #11374, #11162

Test Plan: validate

Reviewers: goldfire, bgamari, hvr, austin

Subscribers: simonpj, thomie

Differential Revision: https://phabricator.haskell.org/D1795

comment:5 Changed 4 years ago by thomie

Milestone: 8.0.1

From testsuite/tests/perf/compiler/all.T for T783:

2015-08-28: 526230456 (amd64/Linux)
2016-02-03: 488592288 (amd64/Linux)

So bytes allocated is now 7% lower than it was before the whole pattern match checker overhaul. Nice.

The patch has been merged to 8.0 already in 6e23b68047a2c995562eba173fe9485cae18bff2.

comment:6 Changed 4 years ago by thomie

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