New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Quadratic run-time behaviour in size of input #34

Closed
lspitzner opened this Issue Jul 4, 2017 · 0 comments

Comments

Projects
None yet
1 participant
@lspitzner
Copy link
Owner

lspitzner commented Jul 4, 2017

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.

@lspitzner lspitzner closed this in 867016c Sep 26, 2017

eborden added a commit to eborden/brittany that referenced this issue Nov 19, 2017

Fix quadratic behaviour (fixes lspitzner#34)
Split up annotations by top-level elements in one
go, instead of doing the filtering per top-level
element (which necessarily makes things quadratic,
or rather O(n*m) with n top-level elements and m
size of annotation map). The fixed version should
be O(log n * m), and log n is negligible.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment