Optimizing a Math Expression Parser in Rust
rpallas.xyz
rpallas.xyz
Use the Go version of pprof: https://github.com/google/pprof
Run it like `pprof -http : your_profile.out` and it will open a browser with a really nice interactive flamegraph (way better than the Perl version), plus a call graph, source line profiling, top functions, etc. etc.
It's so much better. Don't use the Perl version. I should probably write a post showing how to do this.
Another also-much-better alternative is Samply (https://github.com/mstange/samply) which uses the Firefox Profiler as a GUI. I don't like it quite as much as pprof but it's clearly still much better than what's in this article:
But even so, pprof's is better. (You'll have to try it or take my word for it; they don't seem to have a demo anywhere unfortunately.)
When you hover a function it highlights all the other calls to that function (in different stacks), and if you click it it shows all the calls to and from that function in all stacks with two-sided flame graph.
First install perf, graphviz, perf_data_converter and ofc pprof, then generate the data with `perf record [command]`, and display it with `pprof -http=: perf.data`.
edit: And I can only build it using bazel, and I need bazel to build bazel? I think I'll stick with Perl...
go install github.com/google/pprof@latest $ perf record -g -F 99 ./my-program
$ perf script report flamegraph
This part seems bit confused, I don't think `split_whitespace` does any allocations. I wish there were few intermediary steps here, e.g. going from &str and split_whitespace to &[u8] and split.
The tokenizer at that point is bit clunky, it is not really comparable to split_whitespace. The new tokenizer doesn't actually have any whitespace handling, it just assumes that every token is followed by exactly one whitespace. That alone might explain some of the speedup.
Correct. Here's the implementation of split_whitespace
pub fn split_whitespace(&self) -> SplitWhitespace<'_> {
SplitWhitespace { inner: self.split(IsWhitespace).filter(IsNotEmpty) }
}
Rust's iterators are lazy, they only do work when asked for the next item, so their internal state is only what is necessary to keep doing that each time.
IsWhitespace and IsNotEmpty are both predicates which do exactly what you think they do, they're provided in the library because they might not get inlined and if they don't we might as well only implement them exactly once.
(But as mentioned, this doesn't perform any allocations, since each slice is just a pointer + length into the original string.)
> ‘Whitespace’ is defined according to the terms of the Unicode Derived Core Property White_Space.
If they used `split_ascii_whitespace` things would likely be faster.
Switching parsing from `&str` to `&[u8]` can offer other benefits. In their case, they do `&str` comparisons and are switching that to a `u8` comparison. A lot of other parsers are doing `char` comparisons which requires decoding a `&str` to a `char` which can be expensive and is usually not needed because most grammars can be parsed as `&[u8]` just fine.
Also you don't get contention when you don't write to the memory.
The speedup may be from just starting the work before the whole file is loaded, allowing the OS to prefetch the rest in parallel.
You probably would get the same result if you loaded the file in smaller chunks.
However, avoiding creating the AST is not very realistic for most uses. It's usually needed to perform optimizations, or even just for more complicated languages that have interesting control-flow.
Right now, realistic can parse "(* (^ 40 0.5) (^ 90 0.5))" and it will tell you that's 60, because yeah, it's sixty, that's how real arithmetic works.
But it would be nice to write "(40^0.5) * (90^0.5)" or similar and have that work instead or as well. The months of work on realistic meant I spent so long without a "natural" parser that I got used to this.
grammar Arithmetic {
rule TOP { ^ <expr> $ }
rule expr { <term>+ % ['+' | '-'] }
rule term { <value> }
rule value { <number> | <parens> }
rule number { \d+ }
rule parens { '(' <expr> ')' }
}- cpu time (better CPU usage can mean shorter wall time but higher CPU)
- memory usage
- but also and maybe more interestingly complexity of code (not an absolute metric, but a very complex/non portable code for 5% speedup may or may not be worth it)
EDIT: formatting
Neat write up! Kudos on that.
Edited: In the optimized version the author use bytes and generators and avoid using strings. I don't know if Rust generators are optimized for speed or memory, ideally you could define the length of the buffer according to the memory cache available.
Edited: I find strange using input = read_input_file()? and then using eval(&input), what happens when there is an error reading the file? Rust is supposed to be a high security language. In CL there are keyword like if-does-not-exists to decide what to do and also read accepts additional parameters for end-of-file and for expressing that this read is inside a recursive procedure inside another read.
I should stop comparing Rust to CL, better learn Rust first. I consider this kind of articles a very good way of learning Rust for those interested in parsing and optimizations. Rust seems to be a very nice language when you can afford the time to develop your program.
Or if you wanted to do it on bytes, you could also do this, with (`b'+'`).
Unsure if that would provide a meaningful boost or not
Edited: I will eliminate my catfacts username (changing passsord to a random one), I don't like being downvoted and I know I should not mention it, but things are what they are. Good bye catfacts !.
the question mark `?` denotes the fact that the error is bubbled up (kind of like an exception, but with stronger typing and less silent)
I think the blog post is not focussing on error handling too much, but in any case this is 'safe', just could likely be handled better in a real-world case.
If Try::branch gives us a ControlFlow::Break we're done here, return immediately with the value wrapped by Break [if any] inside an Err, otherwise we have ControlFlow::Continue wrapping a value we can use to continue with execution of this function.
This is type checked, so if the function says it returns Result<Goose, Dalek> then the type of the value wrapped in a ControlFlow::Break had better be Err(Dalek) or else we can't use our ? operator here.
Reifying ControlFlow here separates concerns properly - if we want to stop early successfully then control flow can represent that idea just fine whereas an Exception model ties early exit to failure.
Yes
Example : - Optimization 1: Memory‑mapped I/O - Optimization 2: Do not use Peekable - Optimization 3: Do not allocate a Vector when tokenizing - Optimization 4: Zero allocations — parse directly from the input bytes Conclusion - Optimization 5: Multithreading and SIMD
I might be guessing, but in this order probably by Optimization 3 you would reach already a high throughput that you wouldn't bother with manual simd nor Multithreading. (this is a pragmatic way, in real life you will try to minimize risk and try to reach goal as fast as possible, simd/Multithreading carry a lot of risk for your average dev team)
I agree with you though from my experience Memory Mapping is only useful if you need to jump through the file or read it multiple times (as is the case after the author added simd and a two pass step, the first to identify whitespaces and the second to parse the operation and the operants). If you just need to read the file once it's better to avoid memory mapping as it adds a little overhead.
On the other hand parsing directly from the input bytes avoiding the UTF-8 validation needed to have &str type is easy enough to do but still improves performance quite a bit. Even the rust csv crate, which does much more, is around 30% faster with this optimization. https://docs.rs/csv/latest/csv/tutorial/index.html#amortizin...
This is to say, my list for "easy optimizations, big gains", would be 1) Do not allocate a Vector — 2) Do not use peekable — 3) Avoid utf8 validation. I'm still guessing, but I think memory mapping can be skipped, and might be worth it only if you plan on also implementing simd.
n => Token::Operand(n.parse().unwrap()),
That value is an item from the iterator we got from calling split_whitespace() and split_whitespace() returns a SplitWhiteSpace, a custom iterator whose items are themselves sub-strings of the input string with (no surprise) no white space in them. In Rust's terminology these are &str, references to a string slice.
So, the type is &str
I admit when I started rust, seeing calls to .parse() was one of the more confusing things I saw in rust code, because of how much it leans on type inference to be readable. In places like these, it's a bit more readable:
let ip: IpAddr = ip_str.parse()?;
let ip = ip_str.parse::<IpAddr>()?;
That function is not shown, but it is included in the full source code which was linked. Well, technically we need to know that Rust says if there's a sum type Token::Operand which has an associated value, we can always call a function to make a Token::Operand with that value, and it just names this function Token::Operand too.
So, Token::Operand takes an i32, a 32-bit signed integer. The compiler knows we're eventually getting an i32 to call this function, if not our program isn't valid.
Which means n.parse().unwrap() has the type i32
We know n is an &str, the &str type has a generic function parse(), with the following signature:
pub fn parse<F>(&self) -> Result<F, <F as FromStr>::Err> where F: FromStr
This can only work if the type F in that generic signature above is i32
Which means the new type you care about was Result<i32, ParseIntError> and the parse function called will be the one which makes Ok(i32) when presented an in-range integer.
Edited: Word-smithing, no significant change of meaning.
`n` has the same type as the input of the `match` block. In other words, it's a fallback case. (In this case, it's `&str`; the same as `"+"`, `"-"`, etc)
If you're wondering how `n.parse().unwrap()` has its type computed, well that part is because type inference is able to look at the definition of `Token::Operand(u32)` and discover that it's `u32`.
From my experience: The compiler can do this, as long as the first usage of the unknown-typed-thing gives it a type. If the first usage of it doesn't, then it won't try any harder to infer the type and it won't compile unless you add your own annotations on.
[1]: https://doc.rust-lang.org/std/primitive.str.html#method.pars... [2]: https://doc.rust-lang.org/std/str/trait.FromStr.html
Because `match <exp>` could have contained an expression, you might need to handle a "catch all" case where you can refer to the result of that expression.
The code could have been `match s.doSomething() { ...`. The lines above what you have quoted just compare the result to a couple of a constants. If none are true, the line that you have quoted is equivalent to renaming the result of that expression to `n` and then handling that case.
[1]: https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_sy...