[GHC] #10067: The Read Integer instance is too slow

[GHC]

#10067: The Read Integer instance is too slow
-------------------------------------+-------------------------------------
        Reporter:  redneb            |                   Owner:
            Type:  feature request   |                  Status:  patch
        Priority:  high              |               Milestone:  7.10.1
       Component:  Core Libraries    |                 Version:  7.11
      Resolution:                    |                Keywords:
Operating System:  Unknown/Multiple  |            Architecture:
 Type of failure:  Runtime           |  Unknown/Multiple
  performance bug                    |               Test Case:
      Blocked By:                    |                Blocking:
 Related Tickets:                    |  Differential Revisions:  Phab:D645
-------------------------------------+-------------------------------------

Comment (by Austin Seipp <austin@…>):

 In [changeset:"a5a4c25626e11e8b4be6687a9af8cfc85a77e9ba/ghc"]:
 {{{
 #!CommitTicketReference repository="ghc"
 revision="a5a4c25626e11e8b4be6687a9af8cfc85a77e9ba"
 Provide a faster implementation for the Read Integer instance

 Summary:
 The current implementation of the Read Integer instance has quadratic
 complexity and thus performs badly on large inputs. This patch provides a
 rather simple sub-quadratic algorithm. For small inputs, we use the old
 algorithm (there is a small penalty for that). The gains for large
 inputs can be dramatic: on my system, the time to perform
     read (take 1000000 $ cycle "1234567890") :: Integer
 drops from 65 seconds to less than a second.

 Note that we already provide an ad-hoc instance for Show Integer, so this
 patch essentially does the same thing for Read Integer.

 Test Plan: Check that read :: String -> Integer returns correct results
 for inputs of various sizes.

 Reviewers: austin, hvr

 Reviewed By: austin, hvr

 Subscribers: ekmett, thomie

 Differential Revision: https://phabricator.haskell.org/D645

 GHC Trac Issues: #10067
 }}}

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/10067#comment:11>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler