Skip to content

Combinators CPS reorganization#182

Merged
jamesdbrock merged 1 commit intomainfrom
combinatorrm
Apr 7, 2022
Merged

Combinators CPS reorganization#182
jamesdbrock merged 1 commit intomainfrom
combinatorrm

Conversation

@jamesdbrock
Copy link
Member

@jamesdbrock jamesdbrock commented Apr 6, 2022 •
edited
Loading

Reorganize the Combinators to make sense with the CPS internals. These decisions were informed by benchmarking, see #177

  • Export many = List.manyRec
  • Delete sepBy, replace with sepByRec
  • Delete skipMany, replace with skipManyRec
  • Delete chainl, replace with chainlRec
  • Delete chainr, replace with chainrRec (add defer Combinator variations #177 (comment))
  • Delete manyTill, replace with manyTillRec.

Resolves #177

Checklist:

  • Added the change to the changelog's "Unreleased" section with a link to this PR and your username
  • Linked any existing issues or proposals that this pull request should close
  • Updated or added relevant documentation in the README and/or documentation directory
  • Added a test for the contribution (if applicable)

@jamesdbrock jamesdbrock force-pushed the combinatorrm branch 2 times, most recently from c3de0ba to dc9067c Compare April 6, 2022 11:39
@jamesdbrock jamesdbrock marked this pull request as ready for review April 6, 2022 11:40
@jamesdbrock jamesdbrock requested a review from natefaubion April 6, 2022 11:41
@jamesdbrock
Copy link
Member Author

jamesdbrock commented Apr 6, 2022

I would like to merge something like this PR before we tag the next release for purs 0.15 . We can do further improvements later. The only thing in this PR that I'm not sure of right now is the chainr and chainr1.

@jamesdbrock
Copy link
Member Author

jamesdbrock commented Apr 6, 2022 •
edited
Loading

I'd be very grateful for your advice about this @natefaubion .

This PR does not do everything which you suggested in your comments #154 (comment) and #177 (comment) and #154 (comment) but I believe it gives us the correct API, and is a strict improvement over the current situation. More optimizations can be done later.

@natefaubion
Copy link
Contributor

natefaubion commented Apr 6, 2022

I think we should at least benchmark the fixed chainrRec.

@natefaubion
Copy link
Contributor

natefaubion commented Apr 6, 2022

I think it's fine to keep using tailRecM, rather than just monadic recursion. For many of them they end up being equivalent due to the need for the ... <|> done pattern.

@jamesdbrock
Combinators CPS reorganization
7e523ca 
Reorganize the Combinators to make sense with the CPS internals. These
decisions were informed by benchmarking.

* Export `many = List.manyRec`
* Delete `sepBy`, replace with `sepByRec`
* Delete `skipMany`, replace with `skipManyRec`
* Delete `chainl`, replace with `chainlRec`
* Delete `chainr`, replace with `chainrRec` (added `defer`)
* Delete `manyTill`, replace with `manyTillRec`.
@jamesdbrock
Copy link
Member Author

jamesdbrock commented Apr 7, 2022

Adding a defer to chainr1 did the trick as you predicted @natefaubion .

digit 10000

runParser many digit 10000 
mean   = 6.33 ms
stddev = 7.22 ms
min    = 4.37 ms
max    = 53.22 ms
runParser Array.many digit 10000 
mean   = 63.18 ms
stddev = 5.76 ms
min    = 58.81 ms
max    = 77.75 ms
StringParser manyRec CodePoints.anyDigit 10000 
mean   = 6.67 ms
stddev = 4.61 ms
min    = 4.37 ms
max    = 20.67 ms
StringParser manyRec CodeUnits.anyDigit 10000 
mean   = 4.90 ms
stddev = 365.19 μs
min    = 4.46 ms
max    = 7.82 ms
Regex.match \d* 10000 
mean   = 357.52 μs
stddev = 130.13 μs
min    = 318.54 μs
max    = 1.60 ms

string 100000

runParser many string 
mean   = 13.09 ms
stddev = 2.07 ms
min    = 12.18 ms
max    = 36.18 ms
Regex.match literal* 
mean   = 419.30 μs
stddev = 147.18 μs
min    = 385.48 μs
max    = 1.99 ms

many anyChar 10000

runParser many anyChar 10000 
mean   = 6.33 ms
stddev = 731.97 μs
min    = 5.82 ms
max    = 11.11 ms
runParser Array.many anyChar 10000 
mean   = 64.30 ms
stddev = 6.44 ms
min    = 59.00 ms
max    = 82.89 ms

skipMany anyChar 10000

runParser skipMany anyChar 10000 
mean   = 3.54 ms
stddev = 1.14 ms
min    = 3.17 ms
max    = 10.97 ms

sepBy 10000

runParser sepBy 10000 
mean   = 8.78 ms
stddev = 1.09 ms
min    = 8.21 ms
max    = 16.20 ms

sepEndBy1 10000

runParser sepEndBy1 10000 
mean   = 6.01 ms
stddev = 539.04 μs
min    = 5.49 ms
max    = 9.33 ms

chainl 10000

runParser chainl 10000 
mean   = 4.63 ms
stddev = 413.64 μs
min    = 4.35 ms
max    = 6.76 ms

chainr 1000

runParser chainr 1000 
mean   = 571.81 μs
stddev = 150.10 μs
min    = 488.27 μs
max    = 1.71 ms

chainr 10000

runParser chainr 10000 
mean   = 6.19 ms
stddev = 342.39 μs
min    = 5.58 ms
max    = 6.91 ms

manyTill 1000

runParser manyTill 1000 
mean   = 543.63 μs
stddev = 129.30 μs
min    = 468.51 μs
max    = 1.45 ms
runParser manyTill_ 1000 
mean   = 554.62 μs
stddev = 90.48 μs
min    = 493.57 μs
max    = 1.18 ms

manyTill 10000

runParser manyTill 10000 
mean   = 5.52 ms
stddev = 245.12 μs
min    = 5.01 ms
max    = 5.99 ms
runParser manyTill_ 10000 
mean   = 5.94 ms
stddev = 486.62 μs
min    = 5.38 ms
max    = 7.56 ms

mediumJson

runParser json mediumJson 
mean   = 3.67 ms
stddev = 1.12 ms
min    = 3.14 ms
max    = 17.94 ms
StringParser.runParser json mediumJson 
mean   = 7.39 ms
stddev = 2.28 ms
min    = 6.62 ms
max    = 33.89 ms

largeJson

runParser json largeJson 
mean   = 12.48 ms
stddev = 460.88 μs
min    = 11.74 ms
max    = 14.18 ms
StringParser.runParser json largeJson 
mean   = 24.47 ms
stddev = 466.92 μs
min    = 23.76 ms
max    = 26.36 ms

@jamesdbrock jamesdbrock merged commit 059a959 into main Apr 7, 2022
@jamesdbrock jamesdbrock deleted the combinatorrm branch April 7, 2022 01:41
@jamesdbrock
Copy link
Member Author

jamesdbrock commented Apr 7, 2022

Thanks for all the MonadRec combinators @fsoikin . We have now deleted all of the non-MonadRec combinators and are keeping only your MonadRec combinators.

@fsoikin
Copy link
Contributor

fsoikin commented Apr 7, 2022

Oh wow, that drastic! Well, I guess any sane monad can be made MonadRec, eh?

Thank you for the update :-)

@jamesdbrock jamesdbrock mentioned this pull request Apr 7, 2022
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@natefaubion natefaubion Awaiting requested review from natefaubion

Assignees

No one assigned

Labels

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Combinator variations

3 participants

@jamesdbrock @natefaubion @fsoikin