Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Optimizing a Math Expression Parser in Rust

rpallas.xyz

Post reply on HN
Print view View original

31–40 of 60 posts

Re: Optimizing a Math Expression Parser in Rust

#31

Post by tialaramex »

VGHN7XDuOXPAzol wrote: post #14
amelius wrote: post #7

Can somebody explain this line: n => Token::Operand(n.parse().unwrap()), How does the compiler derive the type of n?

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 experie…

That's an i32 not a u32 - the operands are allowed to be say -1234 not only positive numbers apparently.

Re: Optimizing a Math Expression Parser in Rust

#32

Post by pornel »

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.

Re: Optimizing a Math Expression Parser in Rust

#34

Post by tialaramex »

zokier wrote: post #27

> 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…

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

Re: Optimizing a Math Expression Parser in Rust

#35

Post by combinator_y »

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)

Re: Optimizing a Math Expression Parser in Rust

#36

Post by tialaramex »

VGHN7XDuOXPAzol wrote: post #18
catfacts wrote: post #6

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, i…

> 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)

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

Re: Optimizing a Math Expression Parser in Rust

#37

Post by IshKebab »

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

Re: Optimizing a Math Expression Parser in Rust

#38

Post by [deleted] »

tialaramex wrote: post #34
zokier wrote: post #27

> 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…

> 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 i…

[deleted]

Re: Optimizing a Math Expression Parser in Rust

#39

Post by taeric »

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.

Re: Optimizing a Math Expression Parser in Rust

#40

Post by erk__ »

IshKebab wrote: post #37

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 Per…

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

Post reply on HN