Optimizing a Math Expression Parser in Rust

Table of contents

In a previous post I explored how to optimize file parsing for max speed. This time, we’ll look at a different, self-contained problem: writing a math expression parser in Rust, and making it as fast and memory-efficient as possible.

Let’s say we want to parse simple math expressions with addition, subtraction, and parentheses. For example:

4 + 5 + 2 - 1 => 10 (4 + 5) - (2 + 1) => 6 (1 + (2 + 3)) - 4 => 2

We’ll start with a straightforward implementation and optimize it step by step.

YOU CAN FIND THE FULL CODE ON: https://github.com/RPallas92/math_parser

Baseline implementation (43.1 s)

Here’s the first version of our parser:

... continue reading