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

41–50 of 60 posts

Re: Optimizing a Math Expression Parser in Rust

#41

Post by brians »

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…

Can you help me understand what’s happening between the split and the filter on “a 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?

Re: Optimizing a Math Expression Parser in Rust

#42

Post by noelwelsh »

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.

Re: Optimizing a Math Expression Parser in Rust

#43

Post by the-wumpus »

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…

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

Re: Optimizing a Math Expression Parser in Rust

#44

Post by remram »

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…

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

Re: Optimizing a Math Expression Parser in Rust

#45

Post by LegionMammal978 »

brians wrote: post #41
tialaramex wrote: post #34

Earlier quoted context omitted.

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

Can you help me understand what’s happening between the split and the filter on “a 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?

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

Re: Optimizing a Math Expression Parser in Rust

#46

Post by jdreaver »

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…

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

Re: Optimizing a Math Expression Parser in Rust

#47

Post by epage »

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…

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.

Re: Optimizing a Math Expression Parser in Rust

#48

Post by epage »

VGHN7XDuOXPAzol wrote: post #17
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…

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

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

Re: Optimizing a Math Expression Parser in Rust

#49

Post by IshKebab »

the-wumpus wrote: post #43
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…

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

I typically use gperftools for profiling instead of perf. You can LD_PRELOAD it.

Re: Optimizing a Math Expression Parser in Rust

#50

Post by IshKebab »

remram wrote: post #44
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…

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
Post reply on HN