Beginner Q: Why so slow?

help
#1

Hello, I'm working through AOC as a way to learn Rust, and my solution for day 2 part 1 is incredibly slow. As in > 13 seconds.

There are no loops, but is there some operation I'm doing here that is the obvious culprit?

use std::env;
use std::fs;
use regex::Regex;

fn main() {
  let args: Vec<String> = env::args().collect();
  let file = &args[1];
  let contents = fs::read_to_string(file).expect("File read error");
  let contents = contents.trim();

  let pws: Vec<Password> = contents.split("\n").map(parse_line).filter(|p| is_valid(p)).collect();

  println!("{:?}", pws.len())
}

#[derive(Debug, PartialEq)]
struct Password {
  first: usize,
  second: usize,
  character: char,
  password: String
}

fn parse_line(line: &str) -> Password {
  let re = Regex::new(r"(\d+)-(\d+) (\w): (\w+)").unwrap();
  let caps = re.captures(line).unwrap();

  let c: Vec<char> = caps[3].chars().collect();

  Password {
    first: caps[1].parse::<usize>().unwrap(),
    second: caps[2].parse::<usize>().unwrap(), 
    character: c[0], 
    password: caps[4].to_string()
  }
}

fn is_valid(pw: &Password) -> bool {
  let cs: Vec<char> = pw.password.chars().collect();
  (cs[(pw.first - 1)] == pw.character) ^ (cs[(pw.second - 1)] == pw.character)
}

#[cfg(test)]
mod tests {
    use super::is_valid;
    use super::parse_line;
    use super::Password;

    #[test]
    fn parsing() {
      assert_eq!(
        parse_line("1-3 a: abcde"),
        Password {
          first: 1, second: 3, character: 'a', password: "abcde".to_string()
        })
    }

    #[test]
    fn example_1() {
        assert_eq!(true, is_valid(&Password {
          first: 1, second: 3, character: 'a', password: "abcde".to_string()
        }))
    }
}
#2

Try it with optimizations enabled: cargo run --release

On my computer, a release build is about 15 times faster than a debug build, and takes about 1 second to process the provided input file.

#3

Compiling the regex is expensive, and your program recompiles it for every line of input. This change to re-use the compiled regex makes the release build about 50x faster on my computer. (It now finishes the input in about 20 milliseconds.)

--- a/src/main.rs
+++ b/src/main.rs
@@ -7,8 +7,9 @@ fn main() {
   let file = &args[1];
   let contents = fs::read_to_string(file).expect("File read error");
   let contents = contents.trim();
+  let re = Regex::new(r"(\d+)-(\d+) (\w): (\w+)").unwrap();
 
-  let pws: Vec<Password> = contents.split("\n").map(parse_line).filter(|p| is_valid(p)).collect();
+  let pws: Vec<Password> = contents.split("\n").map(|s| parse_line(s, &re)).filter(|p| is_valid(p)).collect();
 
   println!("{:?}", pws.len())
 }
@@ -21,8 +22,7 @@ struct Password {
   password: String
 }
 
-fn parse_line(line: &str) -> Password {
-  let re = Regex::new(r"(\d+)-(\d+) (\w): (\w+)").unwrap();
+fn parse_line(line: &str, re: &Regex) -> Password {
   let caps = re.captures(line).unwrap();
 
   let c: Vec<char> = caps[3].chars().collect();
3 Likes
#4

Apologies I should've mentioned - it is certainly much faster with a release build, but its still around 1 second. My solution in Clojure, which I'd expect to be much slower, is ~10ms.

If you're saying the input processing is around a second, that makes sense - but is that normal? It seems a very long time to process a 1000 row text file.

#5

Compiling the regex is expensive, and your program recompiles it for every line of input.

Ah, this is fantastic, thank you! I will give that a try.

#6

I should note that in production code, it's common to use the once_cell or lazy_static crates to initialize and re-use Regex patterns. I didn't do this above for simplicity, but the regex docs have an example.

There's a proposal to add this feature to the standard library, so an additional dependency would not be required.

2 Likes