-
redneb authored
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
a5a4c256