Opened 5 years ago

Closed 5 years ago

#9676 closed bug (fixed)

Data.List.isSuffixOf can be very inefficient

Reported by: dfeuer Owned by: ekmett
Priority: normal Milestone: 7.10.1
Component: Core Libraries Version: 7.8.3
Keywords: Cc: core-libraries-committee@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s): Phab:D330
Wiki Page:

Description

Data.List.isSuffixOf reverses both lists it is given. Thus, for example,

[12] `isSuffixOf` [1::Int .. (10^9)]

will build the complete list [10^9, (10^9-1)..1] in memory.

Change History (3)

comment:1 Changed 5 years ago by dfeuer

Differential Rev(s): Phab:D330
Status: newpatch

comment:2 Changed 5 years ago by Herbert Valerio Riedel <hvr@…>

In 49b05d6935b6677443a970a45138def66c6f8cee/ghc:

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

comment:3 Changed 5 years ago by hvr

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