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

51–60 of 60 posts

Re: Optimizing a Math Expression Parser in Rust

#51

Post by ethan_smith »

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…

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.

Re: Optimizing a Math Expression Parser in Rust

#52

Post by IshKebab »

erk__ wrote: post #40
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

Ah interesting. It seems to be no better than the Perl one though, except not requiring Perl. It's still a static SVG.

Re: Optimizing a Math Expression Parser in Rust

#53

Post by porphyra »

IshKebab wrote: post #52
erk__ wrote: post #40

Earlier quoted context omitted.

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

Ah interesting. It seems to be no better than the Perl one though, except not requiring Perl. It's still a static SVG.

It's not a static SVG though. The SVG supports interactivity. You can click on each element to zoom in and it even has a search feature.

Re: Optimizing a Math Expression Parser in Rust

#54

Post by IshKebab »

porphyra wrote: post #53
IshKebab wrote: post #52

Earlier quoted context omitted.

Ah interesting. It seems to be no better than the Perl one though, except not requiring Perl. It's still a static SVG.

It's not a static SVG though. The SVG supports interactivity. You can click on each element to zoom in and it even has a search feature.

Ah really? Their example here doesn't do that: https://github.com/jonhoo/inferno/blob/main/tests/data/flame...

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.

Re: Optimizing a Math Expression Parser in Rust

#55

Post by porphyra »

IshKebab wrote: post #54
porphyra wrote: post #53

Earlier quoted context omitted.

It's not a static SVG though. The SVG supports interactivity. You can click on each element to zoom in and it even has a search feature.

Ah really? Their example here doesn't do that: https://github.com/jonhoo/inferno/blob/main/tests/data/flame... 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 al…

The one at https://github.com/flamegraph-rs/flamegraph/blob/main/exampl... supports both zooming and search.

Re: Optimizing a Math Expression Parser in Rust

#56

Post by jlarocco »

IshKebab wrote: post #50
remram wrote: post #44

Earlier quoted context omitted.

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

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

Not everybody wants to install Go just to get an application.

Re: Optimizing a Math Expression Parser in Rust

#57

Post by deathlock »

combinator_y wrote: post #35

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…

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

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.

Re: Optimizing a Math Expression Parser in Rust

#58

Post by remram »

IshKebab wrote: post #50
remram wrote: post #44

Earlier quoted context omitted.

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

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

I got very far in the README, bazel is required for the other repo (perf_data_converter).

Re: Optimizing a Math Expression Parser in Rust

#59

Post by IshKebab »

porphyra wrote: post #55
IshKebab wrote: post #54

Earlier quoted context omitted.

Ah really? Their example here doesn't do that: https://github.com/jonhoo/inferno/blob/main/tests/data/flame... 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 al…

The one at https://github.com/flamegraph-rs/flamegraph/blob/main/exampl... supports both zooming and search.

Ah I see. Yeah pprof is significantly superior.

Re: Optimizing a Math Expression Parser in Rust

#60

Post by ivanjermakov »

erk__ wrote: post #40
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

Also Jon streamed the process of porting flamegraph to Rust: https://youtu.be/jTpK-bNZiA4?si=VsvBln60BCEU7hbz
Post reply on HN