Eli Dowling (Dec 03 2024 at 13:55): Eli Dowling (Dec 03 2024 at 13:55):Hey, I was just thinking about streaming decoding again and was doing some parsing for advent of code and realised I'd like a streaming parser.
I'd also like my parser to also be effect polymorphic so I can write one parser that can either operator on an in memory stream/iterator or an iterator to some external data, like a file or a tcp stream.
Currently as I understand it, I'd have to write my parser and stream type as effectful even if they aren't
Richard Feldman (Dec 03 2024 at 16:05):I think as long as the parsing operations themselves are all pure, you can write it in terms of all pure functions
Richard Feldman (Dec 03 2024 at 16:05):in other words, defining the Parser value is done using all pure functions
Richard Feldman (Dec 03 2024 at 16:06):and then you offer 2 ways of actually executing it on a data source, one pure and one effectful
Eli Dowling (Dec 03 2024 at 16:08):Okay, but if I have a streaming parser, and it's parsing JSON, say it's at the point of parsing a string, then it runs out of data. My parser then needs to fetch extra data at that point, emitting an effect from somewhere in the bowels of the parser.
That requires that the entire parser be effectful
Richard Feldman (Dec 03 2024 at 16:09):I don't think the Parser should do that
Richard Feldman (Dec 03 2024 at 16:09):as in, the Parser's job is to say "I ran out of data and I need some more, or else this is an error"
Richard Feldman (Dec 03 2024 at 16:10):and then in that example, it's the job of the effectful function that's reading data to receive that information from the Parser, go (effectfully) get more data, and then call into the parser again to continue
Richard Feldman (Dec 03 2024 at 16:10):to put it another way, a "streaming Parser" should be implemented using 100% pure functions and should have no clue whatsoever that I/O even exists in the universe
Richard Feldman (Dec 03 2024 at 16:11):however, it should be set up in such a way that it can be paused, resumed, say "I need more data" etc
Richard Feldman (Dec 03 2024 at 16:11):so that a caller can pause it, resume it, pick up where it left off, etc. while supplying data incrementally from whatever source the caller likes (including I/O)
Eli Dowling (Dec 03 2024 at 16:11):But that's how streaming parsers work... they try to fetch more data and continue or they stop.
Otherwise you have to now unwind the entire parse state and return some half parsed json stuff and then get some more bytes and then re dig in partially re-parsing all the stuff you just did to get back to where you were before.
Eli Dowling (Dec 03 2024 at 16:12):Richard Feldman said:
so that a caller can pause it, resume it, pick up where it left off, etc. while supplying data incrementally from whatever source the caller likes (including I/O)
I'm not sure such a design exists...
I'd be curious to see one if it does
Richard Feldman (Dec 03 2024 at 16:12):Eli Dowling said:
But that's how streaming parsers work... they try to fetch more data and continue or they stop.
Otherwise you have to now unwind the entire parse state and return some half parsed json stuff and then get some more bytes and then re dig in partially re-parsing all the stuff you just did to get back to where you were before.
oh are you assuming using function recursion for the parser state?
Richard Feldman (Dec 03 2024 at 16:13):like if all the parser state is in an ordinary value, there's nothing to unwind haha
Richard Feldman (Dec 03 2024 at 16:13):you just have your state in a value, and you return that wrapped in an Err and that's it
Richard Feldman (Dec 03 2024 at 16:18):(and in general, any design that uses function recursion for state can be refactored to use an explicit stack value instead of the call stack, which is beneficial in general because it avoids stack overflows)
Eli Dowling (Dec 03 2024 at 16:25):Hmm.... that does seem true, as in the fact that recursive algorithms can be replaced with non recursive ones.
I feel like I've been down this path and hit a road block before, but I'll take a crack at it and see if I get stuck :sweat_smile:
I'll get back to you :)
Richard Feldman (Dec 03 2024 at 16:28):awesome, very exciting! :smiley:
Jasper Woudenberg (Dec 03 2024 at 17:03):If you're looking for examples, one parser that has the resumable feature Richard mentioned from the Haskell ecosystem is attoparsec:
https://hackage.haskell.org/package/attoparsec-0.14.4/docs/Data-Attoparsec-ByteString.html
It defines a custom result type on that page I linked, which shows essentially three states: failed, done, and "need more data". It describes itself as an incremental parser.
Haskell has a couple of different libraries for streaming IO. Typically they provide helpers for including attoparsec parsers into such pipelines, effectively creating a streaming parser. For example, here's those helpers for a streaming IO library called conduit:
https://www.stackage.org/haddock/lts-22.43/conduit-extra-1.3.6/Data-Conduit-Attoparsec.html
In typical Haskell fashion it's quite a learning curve to figure out how to use all these bits together, so sharing this more as a point of inspiration than something I think we should emulate in Roc 1:1. I've worked a bit with attoparsec and conduit, happy to answer any questions about them I can if that's useful.
Eli Dowling (Dec 03 2024 at 19:03):Okay, I tried using the token stream approach. obviously I couldn't ever actually decode properly because the type system can't handle that and the decoder api only supports bytes so it's not easy to work with a token stream. But I think I got all the code working. Except when I tried to run the final thing... I got a compiler bug :sweat_smile:
thread 'main' panicked at crates/compiler/mono/src/inc_dec.rs:93:13:
assertion failed: !self.not_reference_counted.contains(symbol)
stack backtrace:
0: rust_begin_unwind
at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/std/src/panicking.rs:647:5
1: core::panicking::panic_fmt
at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/core/src/panicking.rs:72:14
2: core::panicking::panic
at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/core/src/panicking.rs:144:5
3: roc_mono::inc_dec::SymbolRcTypes::get
at ./roc/crates/compiler/mono/src/inc_dec.rs:93:13
4: roc_mono::inc_dec::RefcountEnvironment::get_symbol_rc_type
at ./roc/crates/compiler/mono/src/inc_dec.rs:268:9
5: roc_mono::inc_dec::RefcountEnvironment::add_symbol_with
at ./roc/crates/compiler/mono/src/inc_dec.rs:315:15
6: roc_mono::inc_dec::RefcountEnvironment::add_symbol
at ./roc/crates/compiler/mono/src/inc_dec.rs:311:9
Here is a gist: https://gist.github.com/faldor20/b645f5b2837b96767048e9663323b8b6
Eli Dowling (Dec 03 2024 at 19:06):it should work. but I'd like to benchmark it against some other approaches to see how much overhead it has
Brendan Hansknecht (Dec 03 2024 at 22:16):Haven't seen an error like that in a long while
Luke Boswell (Dec 03 2024 at 22:31):Does it help to change the numbers to nvm this is refereounce counting relatedU64 instead of Dec?
Notification Bot (Dec 04 2024 at 04:57):25 messages were moved here from #ideas > opt-in effect polymorphism by Eli Dowling.
Eli Dowling (Dec 04 2024 at 06:42):Well @Richard Feldman I was able to build a parser that works that way. It's not actually effectful right now, but it is entirely pure except for a single outer function which you could pass a byte read effect into and then poll for bytes.
It wasn't particularly natural or easy, but we did eventually get there. I'm sure I could clean it up to be neater and require less code, but it works and in the interest of performance optimisations I want to keep everything pretty much in one big simple function.
The next step is to try to implement the same thing in ocaml, and then an effectful version in ocaml and see what the perf difference is.
https://github.com/faldor20/roc-experiments/blob/master/flat-test.roc
I definitely hit a lot of compiler edge cases here. And the language server is pretty much broken in this file. All the nested recursive types crash the compiler if anything doesn't perfectly line up
Eli Dowling (Dec 04 2024 at 07:02):@Jasper Woudenberg I appreciate the reference, I admit looking at the parser, because it's built with parser combinators it's pretty hard to understand what in the world it's doing under the hood. But I will spend some time trying to grok it at some point :sweat_smile:
Eli Dowling (Dec 04 2024 at 07:24):I like that I seem to have settled on a very similar interface, though:
image.png
I also return a continuation to allow resumption, which gives me hope that I've got something that will work pretty well :)
Richard Feldman (Dec 04 2024 at 12:09):yooooo very cool @Eli Dowling! :heart_eyes::heart_eyes::heart_eyes:
Eli Dowling (Dec 04 2024 at 12:13):I got the translation into Ocaml done too. So I've just gotta hook the roc one up to an actual effectful file reader then make an ocaml effectful version (I think that will be significantly simpler.
Eli Dowling (Dec 06 2024 at 04:15):The results are in!
https://github.com/faldor20/roc-experiments/tree/master
Benchmark 1 (26 runs): ./effectful.exe
measurement mean ± σ min … max outliers delta
wall_time 196ms ± 9.11ms 184ms … 220ms 5 (19%) 0%
peak_rss 9.44MB ± 0 9.44MB … 9.44MB 0 ( 0%) 0%
cpu_cycles 302M ± 17.5M 289M … 352M 0 ( 0%) 0%
instructions 1.07G ± 22.5 1.07G … 1.07G 3 (12%) 0%
cache_references 11.8M ± 93.2K 11.6M … 11.9M 3 (12%) 0%
cache_misses 76.4K ± 10.8K 58.2K … 100K 0 ( 0%) 0%
branch_misses 977K ± 3.91K 973K … 989K 3 (12%) 0%
Benchmark 2 (14 runs): ./flat.exe
measurement mean ± σ min … max outliers delta
wall_time 371ms ± 95.9ms 297ms … 552ms 0 ( 0%) 💩+ 89.3% ± 19.5%
peak_rss 9.54MB ± 55.8KB 9.44MB … 9.57MB 3 (21%) + 1.1% ± 0.2%
cpu_cycles 572M ± 152M 459M … 860M 0 ( 0%) 💩+ 89.1% ± 20.2%
instructions 1.77G ± 95.1 1.77G … 1.77G 0 ( 0%) 💩+ 65.1% ± 0.0%
cache_references 24.1M ± 271K 23.5M … 24.4M 2 (14%) 💩+104.0% ± 1.0%
cache_misses 114K ± 17.9K 78.9K … 140K 0 ( 0%) 💩+ 48.7% ± 12.1%
branch_misses 568K ± 13.5K 543K … 601K 1 ( 7%) ⚡- 41.9% ± 0.6%
Benchmark 3 (9 runs): ./roc.exe
measurement mean ± σ min … max outliers delta
wall_time 578ms ± 15.9ms 558ms … 601ms 0 ( 0%) 💩+194.5% ± 4.5%
peak_rss 2.85MB ± 57.8KB 2.75MB … 2.88MB 2 (22%) ⚡- 69.8% ± 0.2%
cpu_cycles 942M ± 18.9M 920M … 975M 0 ( 0%) 💩+211.5% ± 4.7%
instructions 4.21G ± 18.5 4.21G … 4.21G 0 ( 0%) 💩+291.9% ± 0.0%
cache_references 23.9K ± 4.47K 17.1K … 29.5K 0 ( 0%) ⚡- 99.8% ± 0.5%
cache_misses 10.1K ± 1.45K 8.15K … 12.4K 0 ( 0%) ⚡- 86.8% ± 9.7%
branch_misses 714K ± 5.08K 707K … 722K 0 ( 0%) ⚡- 26.9% ± 0.3%
Using effects for streaming parsing... big win
Brendan Hansknecht (Dec 06 2024 at 04:39):Effectful is calling effects in the middle of parsing while flat is returning and then calling an effect and then resuming?
Also, what buffer size?
Eli Dowling (Dec 06 2024 at 04:41):Yep that's right
effectful and flat are in ocaml because ocaml has good support for all sorts of effects. I could write an effectful version in roc as well I guess if I just make every function effectful.
10k for all of them.
The flat parsers have a tokenizer step. I'll try to remove that and see if it's significantly better.
Eli Dowling (Dec 06 2024 at 04:45):I could probably improve my parsing method, but I just wanted to get something done. They are all pretty much the same though so it should hurt them all. except the tokenizer step.
Eli Dowling (Dec 06 2024 at 07:09):I'm trying to get an effectful roc version to work, but I'm fighting a pernicious non-inplace mutation ruining any hope I have of good perf. I just cannot for the life of me figure out where it's happening. :sweat_smile:
Brendan Hansknecht (Dec 06 2024 at 07:35):Profiling and looking for memcpy helps generally
Jasper Woudenberg (Dec 06 2024 at 07:37):Do you see any effect on performance difference of the buffer size used? Intuitively I'd say that as the buffer size used increases performance differences should go to zero, given the pure parser needs to get new data less often and so overhead related to that goes to zero.
Last updated: Jun 16 2026 at 16:19 UTC