[GHC] #9676: Data.List.isSuffixOf can be very inefficient
#9676: Data.List.isSuffixOf can be very inefficient -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: ekmett Type: bug | Status: new Priority: normal | Milestone: 7.10.1 Component: Core Libraries | Version: 7.8.3 Keywords: | Operating System: Architecture: Unknown/Multiple | Unknown/Multiple Difficulty: Easy (less than 1 | Type of failure: Runtime hour) | performance bug Blocked By: | Test Case: Related Tickets: | Blocking: | Differential Revisions: -------------------------------------+------------------------------------- `Data.List.isSuffixOf` reverses both lists it is given. Thus, for example, {{{#!hs [12] `isSuffixOf` [1::Int .. (10^9)] }}} will build the complete list `[10^9, (10^9-1)..1]` in memory. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9676> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9676: Data.List.isSuffixOf can be very inefficient -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: ekmett Type: bug | Status: patch Priority: normal | Milestone: 7.10.1 Component: Core | Version: 7.8.3 Libraries | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: Runtime | Blocked By: performance bug | Related Tickets: Test Case: | Blocking: | Differential Revisions: Phab:D330 | -------------------------------------+------------------------------------- Changes (by dfeuer): * status: new => patch * differential: => Phab:D330 -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9676#comment:1> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9676: Data.List.isSuffixOf can be very inefficient -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: ekmett Type: bug | Status: patch Priority: normal | Milestone: 7.10.1 Component: Core | Version: 7.8.3 Libraries | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: Runtime | Blocked By: performance bug | Related Tickets: Test Case: | Blocking: | Differential Revisions: Phab:D330 | -------------------------------------+------------------------------------- Comment (by Herbert Valerio Riedel <hvr@…>): In [changeset:"49b05d6935b6677443a970a45138def66c6f8cee/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="49b05d6935b6677443a970a45138def66c6f8cee" Improve performance of isSuffixOf (#9676) The new implementation avoids reversing the "haystack" list, which can be very expensive. Reviewed By: ekmett Differential Revision: https://phabricator.haskell.org/D330 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9676#comment:2> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9676: Data.List.isSuffixOf can be very inefficient -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: ekmett Type: bug | Status: closed Priority: normal | Milestone: 7.10.1 Component: Core | Version: 7.8.3 Libraries | Keywords: Resolution: fixed | Architecture: Unknown/Multiple Operating System: | Difficulty: Easy (less than 1 Unknown/Multiple | hour) Type of failure: Runtime | Blocked By: performance bug | Related Tickets: Test Case: | Blocking: | Differential Revisions: Phab:D330 | -------------------------------------+------------------------------------- Changes (by hvr): * status: patch => closed * resolution: => fixed -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9676#comment:3> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
participants (1)
-
GHC