zesterer
my implementation is slow, how can I optimize my parser?
In my code, there is lots of chumsky parser, such as comment_parser:
pub(crate) fn comment_parser<'a>() -> impl Parser<
'a,
&'a str,
NodeOrToken<GreenNode, GreenToken>,
extra::Full<Rich<'a, char>, RollbackState<ParserState>, ()>,
> + Clone {...}
In the main(), the core code is:
let parse_result = document::document_parser().parse_with_state(
input,
&mut RollbackState(ParserState::default_with_radio_targets(radio_targets)),
);
I know the parser_with_state() function is slow, but I'm not sure which of its sub‑parsers is causing the performance bottleneck. (document_parser is composed of lots of other sub-parsers)
Any suggestions?
It's really quite difficult to give a useful answer with this little to go on.
Chumsky is broadly designed such that all of the information the compiler's optimiser needs to squash the IR down into an equivalent hand-written parser is there, but whether this actually happens is up to the optimiser.
When you say that it's slow, what do you mean? A little bit slower than you'd expect, or dramatically so?
benchmark
bench mark result:
@zesterer
Running benches/doc_parse.rs (target/release/deps/doc_parse-44ef6fb8a1ceb328) Benchmarking org-doc-parse/windancer/test: Warming up for 3.0000 s Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 17.8s. org-doc-parse/windancer/test time: [1.6879 s 1.7259 s 1.7813 s] thrpt: [8.7120 KiB/s 8.9913 KiB/s 9.1941 KiB/s] org-doc-parse/orgize/test time: [2.1100 ms 2.4407 ms 2.8186 ms] thrpt: [5.3767 MiB/s 6.2093 MiB/s 7.1823 MiB/s]
What the benchmark function does: read a org-mode file and parse it and write the results to a json file.
- input: tests/test.org
- output:
- tests/orgize_red_tree.json
- tests/windancer_red_tree.json
How to reproduce:
git clone [email protected]:cnglen/windancer.git && cd windancer && cargo bench
Flamegraph
It seems that Vector takes lots of time. I try to rewrite, but the run time is still large.
v1:
pub(crate) fn document_parser_v1<'a>() -> impl Parser<
'a,
&'a str,
NodeOrToken<GreenNode, GreenToken>,
extra::Full<Rich<'a, char>, RollbackState<ParserState>, ()>,
> {
let parser = object::blank_line_parser()
.repeated()
.collect::<Vec<_>>()
.then(element::comment::comment_parser().or_not())
.then(element::drawer::property_drawer_parser().or_not())
.then(section::section_parser(element::element_in_section_parser()).or_not())
.then(
element::heading_subtree_parser()
.repeated()
.collect::<Vec<_>>(),
)
.map(
|(
(((blank_lines, maybe_comment), maybe_property_drawer), maybe_section),
headings,
)| {
let mut children = vec![];
for blank_line in blank_lines {
children.push(NodeOrToken::Token(blank_line));
}
let mut children_in_section = vec![];
if let Some(comment) = maybe_comment {
children_in_section.push(comment);
}
if let Some(property_drawer) = maybe_property_drawer {
children_in_section.push(property_drawer);
}
if let Some(section) = maybe_section {
for e in section.as_node().unwrap().children() {
children_in_section.push(e.to_owned());
}
}
if children_in_section.len() > 0 {
let zeroth_section = NodeOrToken::Node(GreenNode::new(
OrgSyntaxKind::Section.into(),
children_in_section,
));
children.push(zeroth_section);
}
for c in headings {
children.push(c);
}
let node = GreenNode::new(OrgSyntaxKind::Document.into(), children);
NodeOrToken::Node(node)
},
);
Parser::boxed(parser)
}
v2:
pub(crate) fn document_parser_v2<'a>() -> impl Parser<
'a,
&'a str,
NodeOrToken<GreenNode, GreenToken>,
extra::Full<Rich<'a, char>, RollbackState<ParserState>, ()>,
> {
#[derive(Default, Clone)]
struct DocumentBuilder {
children: Vec<NodeOrToken<GreenNode, GreenToken>>,
zeroth_section_children: Vec<NodeOrToken<GreenNode, GreenToken>>,
}
let parser = empty()
.to(DocumentBuilder::default())
.foldl(
object::blank_line_parser()
.map(NodeOrToken::Token)
.repeated(),
|mut builder, blank_line| {
builder.children.push(blank_line);
builder
}
)
.foldl(
element::comment::comment_parser().or_not()
.then(element::drawer::property_drawer_parser().or_not())
.then(section::section_parser(element::element_in_section_parser()).or_not())
.map(|((maybe_comment, maybe_drawer), maybe_section)| (maybe_comment, maybe_drawer, maybe_section))
.repeated()
.at_most(1),
|mut builder, (maybe_comment, maybe_drawer, maybe_section)| {
if let Some(comment) = maybe_comment {
builder.zeroth_section_children.push(comment);
}
if let Some(drawer) = maybe_drawer {
builder.zeroth_section_children.push(drawer);
}
if let Some(section) = maybe_section {
if let NodeOrToken::Node(section_node) = section {
builder.zeroth_section_children.extend(
section_node.children().map(|c| c.to_owned())
);
}
}
builder
}
)
.map(|builder| {
let mut children = builder.children;
if !builder.zeroth_section_children.is_empty() {
let zeroth_section = NodeOrToken::Node(GreenNode::new(
OrgSyntaxKind::Section.into(),
builder.zeroth_section_children,
));
children.push(zeroth_section);
}
children
})
.foldl(
element::heading_subtree_parser().repeated(),
|mut children, heading| {
children.push(heading);
children
},
)
.map(|children|{
NodeOrToken::Node(GreenNode::new(OrgSyntaxKind::Document.into(), children))
});
Parser::boxed(parser)
}
cargo flamegraph --example main -- show-output
Such a large difference sometimes implies that the parser is structured in such a way that it needs to perform a lot of backtracking, and likely has exponential complexity.
Parser::parse_with_state is not, by itself, expensive (in fact, Parser::parse calls it, just with a state of type ()). However, RollbackState could be the culprit: because all it can do is clone the state, it has to perform a clone every time a branch of the parser could fail. If ParserState is expensive to clone, this can be quite costly. Maybe it's worth considering whether you can implement Inspector for ParserState manually if there's a cheaper way to checkpoint & restore the state.
Thanks. The most of time spent is in the state.rewind() and state.save(). After remove unnecessary states, the time is not too much slow.