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

0 files changed, 0 insertions, 0 deletions