decimal is quadratic
- Dominant language
- Haskell
- Stars
- 531
- Forks
- 98
- PR merge metrics
- No merged PRs in 30d
Description
```haskell
Prelude Data.Attoparsec.Text Data.Text> fmap signum (parseOnly decimal (Data.Text.replicate 100000 "9") :: Either String Integer)
Right 1
(0.32 secs, 4,286,165,576 bytes)
Prelude Data.Attoparsec.Text Data.Text> fmap signum (parseOnly decimal (Data.Text.replicate 200000 "9") :: Either String Integer)
Right 1
(1.19 secs, 17,092,657,496 bytes)
Prelude Data.Attoparsec.Text Data.Text> fmap signum (parseOnly decimal (Data.Text.replicate 400000 "9") :: Either String Integer)
Right 1
(4.83 secs, 68,266,651,512 bytes)
Prelude Data.Attoparsec.Text Data.Text> fmap signum (parseOnly decimal (Data.Text.replicate 800000 "9") :: Either String Integer)
Right 1
(18.86 secs, 272,858,846,272 bytes)
```
when doubling the size of input the time quadruples.
Tested using `cabal build --write-ghc-environment-files=always`, and then loading the library into `repl`. So the important parts are not interpreted.
In comparison, `read` is almost instant
```haskell
Prelude Data.Attoparsec.Text Data.Text> signum (read (Prelude.replicate 800000 '9') :: Integer)
1
(0.21 secs, 333,060,168 bytes)
```
Contributor guide
No contributing guide indexed for this repository
Research direction
Reproduce the scaling measurements in the issue using the `decimal` parser through `parseOnly` in the REPL, then locate the implementation and existing tests for `decimal`. Compare behavior and resource use as the input doubles; done means large integer inputs no longer show quadratic scaling while still returning the same parsed result.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- haskell
- Domain
- performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100