haskell / haskell/attoparsec

decimal is quadratic

Open
#217 2 comments 0 reactions 0 assignees View on GitHub
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.