frontpage.
newsnewestaskshowjobs

Made with ♥ by @iamnishanth

Open Source @Github

Open in hackernews

Optimizing a Math Expression Parser in Rust

https://rpallas.xyz/math-parser/
101•serial_dev•8h ago

Comments

tialaramex•7h ago
This reminds me I should actually write a "natural" arithmetic expression parser for my Rust crate realistic

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.

thrance•4h ago
I think having a polish notation parser is good enough for math-y applciations, I wouldn't worry about it too much if I were you. Nice crate by the way!
ramon156•7h ago
This would be a perfect class project. First lesson is letting them go loose, second lessen would be to find out which optimizations they used and which are available
makapuf•7h ago
I very much like those optimizations articles , what could be interesting is to look at benchmarks not only wall time but also other metrics :

- 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

catfacts•6h ago
I am not even a newbye in Rust and also this could be just nitpicking, but it seems that match is comparing strings and not characters, if this is the case then I think Common Lisp can optimize more, since there is a special comparison for characters in CL.

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.

VGHN7XDuOXPAzol•5h ago
If you wanted to match on characters (`char`s) then you could do this with single quotes (`'+'`)

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

catfacts•5h ago
Thanks for all the information you provided. I will read Rust by Example and stop posting in this thread to avoid deviating from the OP. Anyway, perhaps other readers are learning Rust and having the same questions in their minds, so your answers are also welcome for them.

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 !.

epage•2h ago
Likely, comparing on `char` ('+') would be slower as it requires decoding the `&str` as a `char` which comes with some significant overhead (I've seen 9% on a fairly optimized parser). Ideally, when you grammar is 7-bit ASCII (or any 8-bit UTF-8 values are opaque to your grammar), you instead parse on `&[u8]` and do `u8` comparisons, rather than `char` or `&[u8]`.
VGHN7XDuOXPAzol•5h ago
> what happens when there is an error reading the file?

the question mark `?` denotes the fact that the error is bubbled up (kind of like an exception, but with stronger typing and less silent)

catfacts•5h ago
Thanks for the info. I imagine that in this care, since it seems the error is not captured, it should end producing panic. So a question mark is used when the expected result is of type Result or Error. Also the web page, https://doc.rust-lang.org/rust-by-example/error/result.html, describe the result type as Ok(T) or Err(E), and indicates that is a richer version of Option.
VGHN7XDuOXPAzol•5h ago
Yeah, if `main` returns an error I think it exits with an error code and prints it out, so quite similar to a panic.

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.

tialaramex•3h ago
Specifically the ? symbol is currently implemented via the operator trait Try as Try::branch() which gets you a ControlFlow

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.

phi-go•5h ago
The ? will directly return Err if there is one during read_input_file(). This is just some syntactic sugar.
biorach•5h ago
> I should stop comparing Rust to CL, better learn Rust first

Yes

amelius•6h ago
Can somebody explain this line:

    n => Token::Operand(n.parse().unwrap()),
How does the compiler derive the type of n?
tialaramex•6h ago
We're doing a pattern match, so, this variable n has to be something that matches the entire value matched, its type will be identical to the type of the value matched, s a few lines earlier.

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

amelius•6h ago
Aha. But what type does n.parse() have then, and how does the compiler derive it?
ninkendo•5h ago
That function is returning a Vec<Token>, and so it knows the .collect() call needs to return a Vec<Token>, and so therefore the .map() function needs to return a Token. Therefore each match arm needs to return a Token too, so therefore the compiler selects the implementation of .parse() that returns Token.

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()?;
But when you see the .parse buried several levels deep and you have no idea what type it's trying to produce, it's a pain in the ass to read. This is why it's nice to use the turbo-fish syntax:

    let ip = ip_str.parse::<IpAddr>()?;
Since you can drop .parse::<IpAddr>()? anywhere to make the type explicit, especially when buried in type-inferred blocks like the code in TFA.
tialaramex•5h ago
In this case the compiler actually first wants the type for a parameter to the function Token::Operand

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
So the type you now care about, that of n.parse() has to be Result of some kind, and we're going to call Result::unwrap() on that, to get an i32

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.

phi-go•5h ago
Operand(u32) (see definition of Token), n will be parsed as a u32. See here: https://doc.rust-lang.org/std/primitive.str.html#method.pars...
VGHN7XDuOXPAzol•5h ago
maybe this isn't the question you meant to ask, but:

`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.

VGHN7XDuOXPAzol•5h ago
Might also be useful for me to link to the docs for `parse` [1] and to the trait `FromStr` [2] that it relies on:

[1]: https://doc.rust-lang.org/std/primitive.str.html#method.pars... [2]: https://doc.rust-lang.org/std/str/trait.FromStr.html

tialaramex•4h ago
That's an i32 not a u32 - the operands are allowed to be say -1234 not only positive numbers apparently.
felixnavid•5h ago
`n` is the same type as `s` from "match s" and 'n' is just `s` but renamed, if none of the previous conditions passed.

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.

sondr3•5h ago
If you've never been exposed to a Hindley-Milner type system[1] it can seem a bit magical, but it essentially works by trying to figure out the types from the inside and out by inferring usage all the way to the top. The type of `n` however is `&str`, but I take it you mean the matching. `n.parse()` can be anything that implements `FromStr`, but `Token::Operand` can only take a `u32`, so it can immediately infer that the result of `n.parse().unwrap()` must be `u32` (`n.parse()` is a `Result<u32, Err>`).

[1]: https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_sy...

conaclos•6h ago
I am a bit surprised that the author didn't try to implement a stream parser. This could avoid loading the entire file in memory or relying on OS features like memory-mapped files.
dominicrose•5h ago
A math expression is basically a tree but represented here as a string in a way that's probably impossible to stream.
zokier•5h ago
> We’re paying a cost for each split_whitespace call, which allocates intermediate slices.

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.

tialaramex•4h ago
> I don't think `split_whitespace` does any allocations.

Correct. Here's the implementation of split_whitespace

    pub fn split_whitespace(&self) -> SplitWhitespace<'_> {
        SplitWhitespace { inner: self.split(IsWhitespace).filter(IsNotEmpty) }
    }
So, we're just calling split(IsWhitespace).filter(IsNotEmpty) and keeping the resulting iterator.

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.

brians•3h ago
Can you help me understand what’s happening between the split and the filter on “a <space> <space> <space> b”? I expect that to be a series of calls to split, each yielding an empty slice. So the whole iterator yields a slice pointing at a, then a slice pointing at b—but it’s had to handle three intermediate slices to get the b. Right?
LegionMammal978•3h ago
It creates a Split<'_> iterator using the IsWhitespace function as the pattern. As the user calls .next() on the outer SplitWhitespace<'_>, it calls .next() on the inner Split<'_>, which yields slices "a", "", "", and "b", and the filtered iterator reduces them to "a" and "b".

(But as mentioned, this doesn't perform any allocations, since each slice is just a pointer + length into the original string.)

epage•2h ago
Likely the reason `split_whitespace` is so slow is

> ‘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.

ethan_smith•1h ago
You're right - split_whitespace returns an iterator that yields string slices (&str) which are just views into the original string without allocation, though the performance difference likely comes from avoiding the iterator indirection and boundary checks.
nurettin•4h ago
I have observed that "fearless concurrency" didn't really do much in this case compared to basic practices like not allocating in tight loops.
pornel•4h ago
I don't think memory mapping does anything to prevent false sharing. All threads still get the same data at the same address. You may get page alignment for the file, but the free-form data in the file still crosses page boundaries and cache lines.

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.

librasteve•4h ago
thought it would be fun to write this in raku

  grammar Arithmetic {
    rule TOP       { ^ <expr>       $ }
    rule expr      { <term>+ % ['+' | '-'] }
    rule term      { <value> }
    rule value     { <number> | <parens> }
    rule number    { \d+ }
    rule parens    { '(' <expr> ')' }
  }
combinator_y•3h ago
I am wondering if there is a different approach that 'peaks' better in terms of perf, like instead of doing : - Optimization 1: Do not allocate a Vector when tokenizing - Optimization 2: Zero allocations — parse directly from the input bytes - Optimization 3: Do not use Peekable - Optimization 4: Multithreading and SIMD - Optimization 5: Memory‑mapped I/O

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)

IshKebab•3h ago
Every time I see people use flamegraphs it's the ancient Perl version. There's a much better version!!!

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:

https://share.firefox.dev/3j3PJoK

erk__•3h ago
It should be noted that even though the post links to the perl version for some reason, it is actually not what cargo flamegraph [0] uses, it uses a reimplementation of it in Rust called inferno [1].

[0]: https://github.com/flamegraph-rs/flamegraph

[1]: https://github.com/jonhoo/inferno

IshKebab•1h ago
Ah interesting. It seems to be no better than the Perl one though, except not requiring Perl. It's still a static SVG.
the-wumpus•3h ago
pprof doesn't do an amazing job of explaining how to use it with perf (which you'd need to use for a rust project like OP), so:

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`.

IshKebab•1h ago
I typically use gperftools for profiling instead of perf. You can LD_PRELOAD it.
remram•3h ago
That repo has no builds and no releases, kind of surprising? And needs another tool to consume 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...

IshKebab•1h ago
I guess you didn't get very far in the README because near the top it tells you how to install it. It's a single command:

  go install github.com/google/pprof@latest
jdreaver•2h ago
I recently discovered that `perf` itself can spit out flamegraphs. My workflow has been:

    $ perf record -g -F 99 ./my-program
    $ perf script report flamegraph
You can also run `perf script -F +pid > out.perf` and then open `out.perf` in Firefox's built-in profile viewer (which is super neat) https://profiler.firefox.com
taeric•3h ago
I'm somewhat curious on if these optimizations would all have roughly the same impact if done in other orders? The presentation certainly makes it look like creating a big list of tokens is always the culprit here. Seems somewhat expected, so I agree with the text; but I still wonder if the other optimizations are best to look at in terms of percentage gains or absolute gains, here.

Neat write up! Kudos on that.

noelwelsh•3h ago
I feel like I'm taking crazy pills. It's not a parser, but a fused parser AND interpreter. This changes the game considerably! It doesn't have to produce an intermediate AST, and therefore can avoid the majority of the allocation that most parsers will perform.

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.

The struggle for control of the Arctic is accelerating – and riskier

https://www.bbc.co.uk/news/resources/idt-f92bc043-3893-4688-8937-fd9cad8b0d5b
1•speckx•1m ago•0 comments

Anthropic and DeepMind researchers more likely to reject Meta offers than OpenAI

https://www.theverge.com/ai-artificial-intelligence/703929/meta-openai-anthropic-superintelligence-lab-ai-poaching-money
1•bhouston•3m ago•1 comments

OpenAI's o3 tops new AI league table for answering scientific questions

https://www.nature.com/articles/d41586-025-02177-7
1•rntn•4m ago•0 comments

Runners improve performance by narrowing their visual focus

https://medicalxpress.com/news/2025-06-runners-narrowing-visual-focus.html
1•PaulHoule•5m ago•0 comments

"America, something's up" Walmart shoppers mystified by widespread outages

https://www.dailydot.com/news/walmart-july-7-outage/
1•Bluestein•6m ago•0 comments

P3665R0: Vertical Text Processing

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3665r0.html
1•thunderbong•8m ago•0 comments

Engineer's guide to the male bathroom (three urinal dilemma)

https://www.youtube.com/watch?v=Ost1XvqCuCY
3•armchairs196•8m ago•0 comments

Reading License Plates

https://blog.alexrinehart.net/posts/reading-license-plates/
1•speckx•9m ago•0 comments

Show HN: I built an AI transcription app because my gf needed one for uni

2•ebukao•13m ago•0 comments

The Dickson Report

https://oakandlimestone.substack.com/p/the-dickson-report
1•atx2bos•13m ago•0 comments

LLMs show cultural theory was right about the death of the author

https://www.programmablemutter.com/p/cultural-theory-was-right-about-the
2•dcre•13m ago•0 comments

I switched to a flip phone, and I'm never going back

https://www.sfgate.com/sf-culture/article/swapped-iphone-for-flip-phone-never-going-back-20762858.php
1•pilingual•14m ago•2 comments

I built a AI transcription app because my girlfriend needed one for uni

2•ebukao•16m ago•0 comments

Pentagon to Take Stake in Rare-Earth Company, Challenging China's Control

https://www.wsj.com/business/mp-materials-enters-multibillion-dollar-partnership-with-defense-dept-c8f9f806
2•sandwichsphinx•19m ago•0 comments

Optimization Culture Is Making Us Fragile

https://bradstulberg.substack.com/p/optimization-culture-is-making-us
2•mikestew•21m ago•0 comments

Show HN: asyncmcp – SNS/SQS based custom transport layer for MCP

https://github.com/bh-rat/asyncmcp
2•bharatgel•23m ago•0 comments

Chat with 19 Years of HN Data

https://camelai.com/hackernews/
2•oldfuture•25m ago•0 comments

Press Replay on Your Dreams with the Dream Recorder

https://design-milk.com/press-replay-on-your-dreams-with-the-dream-recorder/
1•Bluestein•26m ago•0 comments

Running a static website in AWS for $0.55

https://www.cottongeeks.com/articles/2025-07-10-running-a-static-website-in-aws-for-55-cents
1•deepakjois•26m ago•0 comments

Writing Bounds-Safe Code in C with Arrays

https://uecker.codeberg.page/2025-07-09.html
2•uecker•26m ago•0 comments

The Code Inflation

https://blog.hermesloom.org/p/the-code-inflation
1•sigalor•26m ago•0 comments

A New Era of Stack Overflow – Stack Overflow

https://stackoverflow.blog/2025/07/10/a-new-era-of-stack-overflow/
3•ulrischa•28m ago•0 comments

Kagi Discover: Find articles, research, videos, code, more that match interests

https://prism.kagi.com/
2•miles•30m ago•0 comments

Why Americans Can't Buy the World's Best Electric Car

https://www.nytimes.com/2025/07/08/opinion/byd-china-car-ev.html
6•bookofjoe•31m ago•2 comments

Infinitic Tac Toe - There’s always a winner

https://maxwellito.github.io/infinitictactoe/
2•susam•32m ago•0 comments

The Problem with Microsoft

https://www.trevornestor.com/post/the-problem-with-microsoft
2•SamuelAdams•32m ago•0 comments

Woman and three teenagers arrested over M&S, Co-op and Harrods cyber attacks

https://news.sky.com/story/woman-and-three-teenagers-arrested-over-mands-co-op-and-harrods-cyber-attacks-13385738
2•austinallegro•32m ago•0 comments

The Big Bang myth – Our origins will always elude us

https://unherd.com/2025/06/the-big-bang-myth/?us
1•voxleone•34m ago•0 comments

Specification Grounding: The Missing Link in Vibe Coding

https://unstract.com/blog/specification-grounding-vibe-coding/
3•constantinum•34m ago•0 comments

Astronomers Have Traced Our New Interstellar Comet's Origin, and It's a First

https://www.sciencealert.com/astronomers-have-traced-our-new-interstellar-comets-origin-and-its-a-first
2•speckx•34m ago•0 comments