Code review requested / how the heck do they get this faster?


#1

I’ve been plugging away at the piglatin problem on Kattis, https://open.kattis.com/problems/piglatin. Note their particular flavour of rules, so “y” counts as a vowel, for example. I’m pretty new to Rust, and I’m using Kattis to give me specific things to work on, and help improve. My approach so far is to write in Python (my usual language) to make sure I have the logic right, then attempt to produce something equivalent in rust. Sometimes that requires re-thinking the logic to suit the new language.

I got some working Rust code with relative ease for this one, but it was horribly slow. You know you’re doing something wrong when Rust is taking longer than Python!

I’ve completely overhauled it and now have something that runs their test cases in 0.07s according to the kattis servers. What is baffling me, and now has me really curious is that there are some solutions on there that do it in 0.03s. Note that, as I understand it, on kattis you can’t use external crates.

I can’t see obvious ways to make this code faster, and I think I’m pretty happy with it, as is, but I’d love any feedback, and would be curious to see if there are ways this might be made faster?

use std::io::{self, BufRead};


fn is_vowel(letter: char) -> bool {
    return letter == 'a' || letter == 'e' || letter == 'i' || letter == 'o' || letter =='u' || letter=='y'
}


fn pig_word(word: &str) -> String{
    for (index, letter) in word.chars().enumerate() {
        if is_vowel(letter){
            if index == 0 {
                return format!("{}{}", word, "yay");
            } else {
                let (tailit, headit) = word.split_at(index);
                return format!("{}{}ay", headit, tailit);
            }
        }
    }

    return word.to_string();
}

fn folder(mut current: String, next: String) -> String {
    if !current.is_empty() {
        current.push(' ');
    }
    current.push_str(&next);
    current
}

fn main() {
    // set things up
    let stdin = io::stdin();
    for raw_line in stdin.lock().lines() {
        let line = raw_line.unwrap();    
        println!("{}", line.split_whitespace().map(pig_word).fold(String::new(), folder));
     }
}

p.s. a few things I was doing wrong originally:

  • lots of casting between str, &str, char, String and vectors. I’ve no background with statically compiled languages, I knew lots of casting probably meant I was probably doing things wrong!
  • Defined a static HashSet containing the vowels, because I used a set in python knowing it would be fast. Switching away from a hashset to that is_vowel function reduced runtime by about 20% or so. Haven’t experimented with python to see if going away from set would speed things up there too.
  • Didn’t leverage map, stumbled across it after finding when I’d already got this whole thing written. https://codereview.stackexchange.com/questions/175906/convert-string-to-pig-latin-in-rust. Different logic there for piglatin makes most of that unusable, but I did do some experiments with bits of the code there, ultimately deciding not to use it. Runtime didn’t change after I switched to map, but I wouldn’t necessarily expect it to. Syntax is definitely cleaner.

#2

Rust uses utf8 String and converts to char which is 32 bit Unicode scalar value. Switching type would likely give boost.


#3

One potential speed boost - you’re avoiding repeatedly locking/unlocking stdin, which is good, but you could also do the same for stdout! Replace your main with something like this:

fn main() {
    // set things up
    let stdin = io::stdin();
    let stdout = io::stdout();
    let mut out_lock = stdout.lock();

    for raw_line in stdin.lock().lines() {
        let line = raw_line.unwrap();
        writeln!(
            out_lock,
            "{}",
            line.split_whitespace()
                .map(pig_word)
                .fold(String::new(), folder)
        )
        .unwrap();
    }
}

Note that you’ll need std::io::Write in scope, or to import std::io::prelude::*.

I learned this tip from a blog post called ‘Rust Performance Pitfalls’, by @llogiq - definitely worth a read if you’re trying to squeeze a little more performance out of your program :slight_smile:


#4

Thanks for the suggestions @jonh and @17cupsofcoffee. I modified things to avoid the char type (I really love that “as u8” thing), and the stdout lock, but it didn’t really make that much of a difference in the case of kattis.
It definitely did when run against a copy of Bram Stoker’s Dracula, that I used as an example of larger data, where it cut the runtime by about half!

For kattis, I think it means that probably there is some kind of logical trick I could use somewhere :smiley:

I could probably use a hashmap for memoisation or something, but I would imagine for this kind of challenge (especially at these runtime lengths) the amount of repeated strings is likely to be small enough that the overhead wouldn’t be worth it.

use std::io::{self, BufRead, Write};

fn is_vowel(letter: u8) -> bool {
    // Strings are utf8.
    return letter == 'a' as u8 || letter == 'e' as u8 || letter == 'i' as u8 || letter == 'o' as u8 || letter == 'u' as u8 || letter == 'y' as u8 
}

fn pig_word(word: &str) -> String {
    let mut index = 0;
    for &letter in word.as_bytes() {
        if is_vowel(letter){
            if index == 0 {
                return format!("{}{}", word, "yay");
            } else {
                let (tailit, headit) = word.split_at(index);
                return format!("{}{}ay", headit, tailit);
            }
        }
        index += 1;
    }
    return word.to_string()
}

fn folder(mut current: String, next: String) -> String {
    if !current.is_empty() {
        current.push(' ');
    }
    current.push_str(&next);
    current
}

fn main() {
    // set things up
    let stdin = io::stdin();
    let stdout = io::stdout();
    let mut out_lock = stdout.lock();

    for raw_line in stdin.lock().lines() {
        let line = raw_line.unwrap();
        writeln!(
            out_lock,
            "{}",
            line.split_whitespace()
                .map(pig_word)
                .fold(String::new(), folder)
        )
        .unwrap();
    }
}

Anyway, as I say, thanks for the help and suggestions. I might revisit this code at a later stage if something else occurs to me, but it’s nice and fast.


#5

Oh wow. Just managed to find the code from one of the 0.03s solutions. Don’t think it’s a logic thing, so much as highly micro-optimising.


#6

I would instead use `b"aeiouy".contains(&letter). It’s easier to read and is possibly faster.


#7

Another note is that the original code that iterated over chars was buggy, because split_at wants a byte index and you were giving it a char index.


#8

Huh. Interesting. It was producing correct output.


#9

If you want to be horrified, I dug up my first attempt:

use std::collections::HashSet;
use std::io::{self, BufRead};

fn main() {
    // set things up
    let stdin = io::stdin();

    // is there a better way to do this?  Would be nice to do it in one line.
    let mut vowels = HashSet::new();
    vowels.insert("a".to_string());
    vowels.insert("e".to_string());
    vowels.insert("i".to_string());
    vowels.insert("o".to_string());
    vowels.insert("u".to_string());
    vowels.insert("y".to_string());

    // here comes the actual work
    for entry in stdin.lock().lines() {
        let mut output: String = "".to_owned();
        let line = entry.unwrap();
        let split = line.split(" ");
        for word in split {
            let ch_vec:Vec<char> = word.chars().collect();
            // If the first character is a vowel, just add yay.
            let ch = ch_vec[0];
            if vowels.contains(&ch.to_string()){
                output.push_str(word);
                output.push_str("yay ");
            } else {
                // Word doesn't start with a vowel.  We need to iterate over it.
                // When we get to a vowel, we need to add all letters so far to it, then add ay
                let mut postfix: String = "".to_owned();
                let mut new_word: String = "".to_owned();
                let mut vowel_not_reached = true;
                for i in 0..ch_vec.len(){
                    if vowel_not_reached {
                        if vowels.contains(&ch_vec[i].to_string()){
                            vowel_not_reached = false;
                            postfix.push_str("ay");
                            new_word.push_str(&ch_vec[i].to_string());
                        } else {
                            postfix.push_str(&ch_vec[i].to_string());
                        }
                    } else {
                        new_word.push_str(&ch_vec[i].to_string());
                    }
                }
                new_word.push_str(&postfix);
                output.push_str(&new_word);
                output.push_str(" ");
            }
        }
        println!("{}", output.trim_end_matches(" "));
    }
}

#10

It would give correct output until you came across a multibyte character before the first vowel in a word.


#11

Here’s my attempt (runs in 3s on the website). The biggest speedups that I found were putting all of stdin into a vec and building all of stdout into a vec before printing. Interestingly enough I tried a version that uses memchr2 and it wasn’t really faster.

use std::io::{Read, Write};

struct Word<'a> {
    word: &'a [u8],
    pivot: Option<usize>,
    start_vowel: bool,
}

impl<'a> Word<'a> {
    #[inline]
    fn new(word: &[u8]) -> Word {
        let pivot = word.iter().position(|&c| match c {
            b'a' | b'e' | b'i' | b'o' | b'u' | b'y' => true,
            _ => false,
        });

        let (pivot, start_vowel) = match pivot {
            Some(i) if i == 0 => (None, true),
            other => (other, other.is_none()),
        };

        Word {
            word,
            pivot,
            start_vowel,
        }
    }

    #[inline]
    fn first(&self) -> &[u8] {
        match self.pivot {
            None => self.word,
            Some(0) => self.word,
            Some(i) => &self.word[i..],
        }
    }

    #[inline]
    fn second(&self) -> Option<&[u8]> {
        self.pivot.map(|i| &self.word[0..i])
    }

    #[inline]
    fn end_bytes(&self, is_last: bool) -> &[u8] {
        if is_last {
            if self.start_vowel {
                b"yay\n"
            } else {
                b"ay\n"
            }
        } else if self.start_vowel {
            b"yay "
        } else {
            b"ay "
        }
    }

    #[inline]
    fn append(&self, is_last: bool, buf: &mut Vec<u8>) {
        buf.extend(self.first());

        if let Some(b) = self.second() {
            buf.extend(b);
        }

        buf.extend(self.end_bytes(is_last));
    }
}

#[inline]
fn run() -> Result<(), std::io::Error> {
    let buf = {
        let mut buf = Vec::with_capacity(1024 * 1024);
        let sin = std::io::stdin();
        let mut sin = sin.lock();
        sin.read_to_end(&mut buf)?;
        buf
    };

    let sout = std::io::stdout();
    let mut sout = sout.lock();

    let mut out_buf: Vec<u8> = Vec::with_capacity(buf.len() * 2);
    let mut start = 0;

    for (i, &c) in buf.iter().enumerate() {
        if let Some(is_last) = match c {
            b'\n' => Some(true),
            b' ' => Some(false),
            _ => None,
        } {
            Word::new(&buf[start..i]).append(is_last, &mut out_buf);
            start = i + 1;
        }
    }

    sout.write_all(&mut out_buf)
}

fn main() -> Result<(), std::io::Error> {
    go()
}

#[cfg(feature = "time")]
#[inline]
fn go() -> Result<(), std::io::Error> {
    use std::time;

    let start = time::Instant::now();
    run()?;

    eprintln!("Ran in {:?}", time::Instant::now() - start);
    Ok(())
}

#[cfg(not(feature = "time"))]
#[inline]
fn go() -> Result<(), std::io::Error> {
    run()
}