{"action":"created","issue":{"url":"https://api.github.com/repos/haskell-suite/haskell-src-exts/issues/200","labels_url":"https://api.github.com/repos/haskell-suite/haskell-src-exts/issues/200/labels{/name}","comments_url":"https://api.github.com/repos/haskell-suite/haskell-src-exts/issues/200/comments","events_url":"https://api.github.com/repos/haskell-suite/haskell-src-exts/issues/200/events","html_url":"https://github.com/haskell-suite/haskell-src-exts/pull/200","id":54819167,"number":200,"title":"Significant improvements when parsing with a long list of extensions","user":{"login":"ndmitchell","id":1651197,"avatar_url":"https://avatars.githubusercontent.com/u/1651197?v=3","gravatar_id":"","url":"https://api.github.com/users/ndmitchell","html_url":"https://github.com/ndmitchell","followers_url":"https://api.github.com/users/ndmitchell/followers","following_url":"https://api.github.com/users/ndmitchell/following{/other_user}","gists_url":"https://api.github.com/users/ndmitchell/gists{/gist_id}","starred_url":"https://api.github.com/users/ndmitchell/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ndmitchell/subscriptions","organizations_url":"https://api.github.com/users/ndmitchell/orgs","repos_url":"https://api.github.com/users/ndmitchell/repos","events_url":"https://api.github.com/users/ndmitchell/events{/privacy}","received_events_url":"https://api.github.com/users/ndmitchell/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":7,"created_at":"2015-01-19T22:16:05Z","updated_at":"2015-07-28T20:24:20Z","closed_at":"2015-07-28T19:40:56Z","pull_request":{"url":"https://api.github.com/repos/haskell-suite/haskell-src-exts/pulls/200","html_url":"https://github.com/haskell-suite/haskell-src-exts/pull/200","diff_url":"https://github.com/haskell-suite/haskell-src-exts/pull/200.diff","patch_url":"https://github.com/haskell-suite/haskell-src-exts/pull/200.patch"},"body":"Given the benchmark:\r\n\r\n    import Language.Haskell.Exts\r\n    import System.Time.Extra -- from the extra library on Hackage\r\n    import Control.Monad\r\n\r\n    main :: IO ()\r\n    main = do\r\n        (d,_) <- duration $ do\r\n            let parser = parseDeclWithMode\r\n                    defaultParseMode{extensions = EnableExtension EmptyDataDecls : [e | e@EnableExtension{} <- knownExtensions]}\r\n            forM_ ([1..10000]) $ \\i -> do\r\n                case parser $ \"data Foo\" ++ show i of\r\n                    ParseOk _ -> return ()\r\n                    _ -> error \"done\"\r\n        print d\r\n\r\nBefore these patches this took 45s. After, it takes 0.07s. This benchmark is based on exactly what I do in Hoogle when creating the database, so is _very_ relevant to the real-world usage.\r\n\r\nThe first change, which reduces it from 45s to 4.5s is to change the O(n^3) algorithm in toExtensionList to an O(n^2) one by dragging the nub out of the accumulator and removing the invariant that each extension is only mentioned once. The next change is to allow parseMode to be partially applied and to calculate the IParseMode in advance, if it has the information to do so. This means that in the tight loop above we only do the O(n^2) algorithms once.\r\n\r\nThe obvious next-step would be to eliminate the O(n^2) algorithms, using something from containers to give you O(n log n) instead. When parsing whole files, these fixes make little difference, since they are eliminating the startup overhead."},"comment":{"url":"https://api.github.com/repos/haskell-suite/haskell-src-exts/issues/comments/125744050","html_url":"https://github.com/haskell-suite/haskell-src-exts/pull/200#issuecomment-125744050","issue_url":"https://api.github.com/repos/haskell-suite/haskell-src-exts/issues/200","id":125744050,"user":{"login":"pjonsson","id":2082449,"avatar_url":"https://avatars.githubusercontent.com/u/2082449?v=3","gravatar_id":"","url":"https://api.github.com/users/pjonsson","html_url":"https://github.com/pjonsson","followers_url":"https://api.github.com/users/pjonsson/followers","following_url":"https://api.github.com/users/pjonsson/following{/other_user}","gists_url":"https://api.github.com/users/pjonsson/gists{/gist_id}","starred_url":"https://api.github.com/users/pjonsson/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pjonsson/subscriptions","organizations_url":"https://api.github.com/users/pjonsson/orgs","repos_url":"https://api.github.com/users/pjonsson/repos","events_url":"https://api.github.com/users/pjonsson/events{/privacy}","received_events_url":"https://api.github.com/users/pjonsson/received_events","type":"User","site_admin":false},"created_at":"2015-07-28T20:24:20Z","updated_at":"2015-07-28T20:24:20Z","body":"Is this complexity issue a regression compared to earlier releases or has it always been this way?\r\n\r\nYour patch clearly improves performance and the patch itself is small so it's not likely to break a lot of other things. Not destroying things is definitely the way forward right now given that people seem eager to get a release out through the door.\r\n"}}