Quadratic run-time behaviour in size of input #34

New Issue

2017-07-04T22:55:01+02:00

lspitzner commented

2017-07-04 22:55:01 +02:00

(Migrated from github.com)

Symptoms are run-times in the order of seconds for largish modules. Noticable starting at ~500 loc; a simple testcase consists of a sequence of foo$i :: Int; foo$i = $i for $i in 1..1000. The runtime for this testcase seems to grow in quadratic fashion.

Profiling shows that filterAnns is likely the cuplrit.

	total time  =       21.29 secs   (21288 ticks @ 1000 us, 1 processor)
	total alloc = 3,394,268,880 bytes  (excludes profiling overheads)

COST CENTRE                       MODULE                                                 SRC                                                                            %time %alloc

filterAnns                        Language.Haskell.Brittany.Internal.LayouterBasics      src/Language/Haskell/Brittany/Internal/LayouterBasics.hs:(240,1)-(241,67)       76.2    0.1
runMemoStateT                     Control.Monad.Trans.Memo.State                         Control/Monad/Trans/Memo/State.hs:(56,1)-(58,23)                                 5.9   26.1
everything                        Data.Generics.Schemes                                  src/Data/Generics/Schemes.hs:104:1-59                                            3.0   10.2
censor                            Control.Monad.Writer.Class                             Control/Monad/Writer/Class.hs:(99,1)-(101,17)                                    2.6   11.7
transformAlts                     Language.Haskell.Brittany.Internal.Transformations.Alt src/Language/Haskell/Brittany/Internal/Transformations/Alt.hs:(75,1)-(364,59)    1.7   13.3
...

I have not looked into what exactly makes it quadratic; the use of everything from uniplate in foldedAnnKeys looks suspicious though. Solution is either to stop filtering (filtering serves a "sandboxing" purpose mostly, at least for the per-declaration use of the function) or to make the function more efficient.

Symptoms are run-times in the order of seconds for largish modules. Noticable starting at ~500 loc; a simple testcase consists of a sequence of `foo$i :: Int; foo$i = $i` for `$i` in `1..1000`. The runtime for this testcase seems to grow in quadratic fashion. Profiling shows that `filterAnns` is likely the cuplrit. ~~~~ total time = 21.29 secs (21288 ticks @ 1000 us, 1 processor) total alloc = 3,394,268,880 bytes (excludes profiling overheads) COST CENTRE MODULE SRC %time %alloc filterAnns Language.Haskell.Brittany.Internal.LayouterBasics src/Language/Haskell/Brittany/Internal/LayouterBasics.hs:(240,1)-(241,67) 76.2 0.1 runMemoStateT Control.Monad.Trans.Memo.State Control/Monad/Trans/Memo/State.hs:(56,1)-(58,23) 5.9 26.1 everything Data.Generics.Schemes src/Data/Generics/Schemes.hs:104:1-59 3.0 10.2 censor Control.Monad.Writer.Class Control/Monad/Writer/Class.hs:(99,1)-(101,17) 2.6 11.7 transformAlts Language.Haskell.Brittany.Internal.Transformations.Alt src/Language/Haskell/Brittany/Internal/Transformations/Alt.hs:(75,1)-(364,59) 1.7 13.3 ... ~~~~ I have not looked into what exactly makes it quadratic; the use of `everything` from uniplate in `foldedAnnKeys` looks suspicious though. Solution is either to stop filtering (filtering serves a "sandboxing" purpose mostly, at least for the per-declaration use of the function) or to make the function more efficient.

Sign in to join this conversation.

No Milestone

No project

No Assignees

1 Participants

Notifications

Due Date

The due date is invalid or out of range. Please use the format 'yyyy-mm-dd'.

No due date set.

Dependencies

No dependencies set.

Reference: hexagoxel/brittany#34