5
\$\begingroup\$

I have implemented a simple NFA that recognizes words in parallel. All the code is on GitHub, here.

  • A main recognizes method tells if a word (&str) is recognized by an NFA. Inside this method, I set up a thread pool and a channel and call a recognizes_in_parallel method.

  • The recognizes_in_parallel takes a word and a state and handles two things:

    1. It spawns a new thread each time the transition function results in more than one state, i.e., when non-determinism occurs.
    2. It tells if starting at the state argument, the automaton recognizes the word argument.
  • The recognizes_in_parallel method sends the result of trying to recognize the word through the channel.

  • The main thread then receives until a true is sent or when all the threads have hung up or sent false.

I am very new to Rust, just finished reading The Rust Book a couple of weeks ago, and I want to know if this code can be improved regarding readability, efficiency, and organization.

Are there good quality unit tests that could be written for the parallelization? Can I improve the use of locks here? Can I write less verbose initialization? I think I abused the Copy and Clone traits, is there a way to reduce their use?

Two things to keep in mind:

  • ThreadPool is not Sync, that's why we need the Mutex (or so I understood).
  • I don't understand why the following change breaks the code, i.e., it does not halt.
// Works!!
pool.lock().unwrap().execute(move || {
    root_nfa.recognize_in_parallel(&word[..], root_nfa.start, tx, pool_clone);
});
---
// Does not work :(
let pool = pool.lock().unwrap();
pool.execute(move || {
    root_nfa.recognize_in_parallel(&word[..], root_nfa.start, tx, pool_clone);
});

Finally, here's the relevant code:

// state.rs
#[cfg(test)]
#[path = "./state.test.rs"]
mod tests;

#[derive(PartialEq, Eq, Debug, Hash, Copy, Clone)]
pub struct State {
    pub id: i32,
}

impl State {
    pub fn new(id: i32) -> State {
        State { id }
    }
}
// symbol.rs
#[derive(PartialEq, Eq, Debug, Hash, Copy, Clone)]
pub enum Symbol {
    Epsilon,
    Identifier(char),
}
// nfa.rs
use crate::{state::State, symbol::Symbol};
use std::collections::{HashMap, HashSet};
use std::sync::{mpsc, Arc, Mutex};
use threadpool::ThreadPool;

#[cfg(test)]
#[path = "./nfa.test.rs"]
mod tests;

const WORKER_COUNT: usize = 1024;

#[derive(Debug, PartialEq, Eq, Clone)]
pub struct NFA {
    states: HashSet<State>,
    alphabet: HashSet<Symbol>,
    start: State,
    transition_function: HashMap<(State, Symbol), HashSet<State>>,
    accepting_states: HashSet<State>,
}

impl NFA {
    pub fn new(
        states: HashSet<State>,
        alphabet: HashSet<Symbol>,
        start: State,
        transition_function: HashMap<(State, Symbol), HashSet<State>>,
        accepting_states: HashSet<State>,
    ) -> NFA {
        NFA {
            states,
            alphabet,
            start,
            transition_function,
            accepting_states,
        }
    }

    pub fn add_transition(
        &mut self,
        source_state: State,
        symbol: Symbol,
        destination_states: HashSet<State>,
    ) {
        self.transition_function
            .insert((source_state, symbol), destination_states);
    }

    fn step(&self, ch: char, state: State) -> HashSet<State> {
        let symbol_states = self
            .transition_function
            .get(&(state, Symbol::Identifier(ch)))
            .expect(&format!("No transition found for ({:?}, {:?})", state, ch));

        match self.transition_function.get(&(state, Symbol::Epsilon)) {
            Some(set) => symbol_states.union(set).cloned().collect(),
            None => symbol_states.to_owned(),
        }
    }

    fn recognize_in_parallel<'a>(
        &self,
        word: &str,
        state: State,
        tx: mpsc::Sender<bool>,
        pool: Arc<Mutex<ThreadPool>>,
    ) {
        let mut state = state;
        for ch in word.chars() {
            let next_states = self.step(ch, state);

            if next_states.len() == 1 {
                state = *next_states.iter().next().unwrap();
            } else {
                let mut next_states = next_states.iter();
                state = *next_states.next().unwrap();

                for &state in next_states {
                    let tx = tx.clone();
                    let child_nfa = self.clone();
                    let word = word.to_owned();
                    let pool_clone = Arc::clone(&pool);

                    pool.lock().unwrap().execute(move || {
                        child_nfa.recognize_in_parallel(&word[1..], state, tx, pool_clone);
                    })
                }
            }
        }

        tx.send(self.accepting_states.contains(&state)).unwrap();
    }

    pub fn recognizes(&self, word: &str) -> bool {
        let pool = threadpool::ThreadPool::new(WORKER_COUNT);
        let pool = Arc::new(Mutex::new(pool));

        let (tx, rx) = mpsc::channel();

        let root_nfa = self.clone();
        let word = word.to_owned();
        let pool_clone = Arc::clone(&pool);
        pool.lock().unwrap().execute(move || {
            root_nfa.recognize_in_parallel(&word[..], root_nfa.start, tx, pool_clone);
        });

        let did_recognize = rx.iter().any(|did_recognize| did_recognize);

        // If we don't join here, `rx` would be droped
        // and a thread might try to send to a closed channel.
        pool.lock().unwrap().join();

        did_recognize
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ Regarding the Does not work :( part: the lifetime of a temporary value in a let binding extends to the end of the enclosing scope, whereas temporary values in an expression statement (an expression followed by ;) are discarded at the end of the statement. \$\endgroup\$
    – L. F.
    Jun 22 at 6:02
2
\$\begingroup\$

Welcome to Rust, and welcome to Code Review.

File organization

First of all, the placement of test modules is unconventional:

#[cfg(test)]
#[path = "./dfa.test.rs"]
mod tests;

The common approach is to either simply put the tests at the end of the module, or create a folder for the module:

- src/
  - lib.rs
  - dfa/
    - mod.rs      # equivalent to src/dfa.rs
    - tests.rs    # can be accessed within `mod.rs` as `mod tests;`

Using #[path = "..."] is overkill here. (It also refused to work on my computer for weird reasons, so I had to relocate the files.)

Warnings

The compiler emits a bunch of dead code warnings:

warning: associated function is never used: `new`
  --> src\dfa.rs:18:12
   |
18 |     pub fn new(
   |            ^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: associated function is never used: `add_transition`
  --> src\dfa.rs:34:12
   |
34 |     pub fn add_transition(&mut self, source_state: State, symbol: char, destination_state: State) {
   |            ^^^^^^^^^^^^^^

warning: associated function is never used: `recognizes`
  --> src\dfa.rs:39:12
   |
39 |     pub fn recognizes(&self, word: &str) -> bool {
   |            ^^^^^^^^^^

warning: constant is never used: `WORKER_COUNT`
  --> src\nfa.rs:10:1
   |
10 | const WORKER_COUNT: usize = 1024;
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: associated function is never used: `new`
  --> src\nfa.rs:22:12
   |
22 |     pub fn new(
   |            ^^^

warning: associated function is never used: `add_transition`
  --> src\nfa.rs:38:12
   |
38 |     pub fn add_transition(
   |            ^^^^^^^^^^^^^^

warning: associated function is never used: `step`
  --> src\nfa.rs:48:8
   |
48 |     fn step(&self, ch: char, state: State) -> HashSet<State> {
   |        ^^^^

warning: associated function is never used: `recognize_in_parallel`
  --> src\nfa.rs:60:8
   |
60 |     fn recognize_in_parallel(
   |        ^^^^^^^^^^^^^^^^^^^^^

warning: associated function is never used: `recognizes`
  --> src\nfa.rs:93:12
   |
93 |     pub fn recognizes(&self, word: &str) -> bool {
   |            ^^^^^^^^^^

warning: associated function is never used: `new`
  --> src\state.rs:11:12
   |
11 |     pub fn new(id: i32) -> State {
   |            ^^^

warning: variant is never constructed: `Epsilon`
 --> src\symbol.rs:3:5
  |
3 |     Epsilon,
  |     ^^^^^^^

warning: variant is never constructed: `Identifier`
 --> src\symbol.rs:4:5
  |
4 |     Identifier(char),
  |     ^^^^^^^^^^^^^^^^

warning: 12 warnings emitted

warning: associated function is never used: `add_transition`
  --> src\nfa.rs:38:12
   |
38 |     pub fn add_transition(
   |            ^^^^^^^^^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: 1 warning emitted

These warnings reveal two issues:

  1. dfa, nfa, state, and symbol are declared as private modules in lib.rs, so they can only be used within the crate rooted at lib.rs. Therefore, they produce dead code warnings even though their items are marked as pub.
  • Solution: add pub to all lines in lib.rs.
  1. Instead of using the crate rooted at lib.rs, you re-declare all modules in main.rs. In essence, you have two separately compiled crates that happen to share some of their source files, which is clearly not what we want.
  • Solution: remove the module declarations in main.rs and prefix module names with atl::. Alternatively, group all use declarations together, which I prefer: (I recommend the same for use declarations in other files)
use {
    atl::{nfa::NFA, state::State, symbol::Symbol},
    std::{
        collections::{HashMap, HashSet},
        iter::FromIterator,
    },
};

clippy

Running cargo clippy results in more warnings:

warning: name `DFA` contains a capitalized acronym
 --> src\dfa\mod.rs:8:12
  |
8 | pub struct DFA {
  |            ^^^ help: consider making the acronym lowercase, except the initial letter: `Dfa`
  |
  = note: `#[warn(clippy::upper_case_acronyms)]` on by default
  = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#upper_case_acronyms

warning: name `NFA` contains a capitalized acronym
  --> src\nfa\mod.rs:12:12
   |
12 | pub struct NFA {
   |            ^^^ help: consider making the acronym lowercase, except the initial letter: `Nfa`
   |
   = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#upper_case_acronyms

warning: use of `expect` followed by a function call
  --> src\dfa\mod.rs:43:22
   |
43 |                       .expect(&format!(
   |  ______________________^
44 | |                         "No transition found for ({:?}, {:?})",
45 | |                         *current_state, symbol
46 | |                     ))
   | |______________________^ help: try this: `unwrap_or_else(|| panic!("No transition found for ({:?}, {:?})", *current_state, symbol))`
   |
   = note: `#[warn(clippy::expect_fun_call)]` on by default
   = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#expect_fun_call

warning: use of `expect` followed by a function call
  --> src\nfa\mod.rs:51:14
   |
51 |             .expect(&format!("No transition found for ({:?}, {:?})", state, ch));
   |              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: try this: `unwrap_or_else(|| panic!("No transition found for ({:?}, {:?})", state, ch))`
   |
   = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#expect_fun_call

warning: 4 warnings emitted

warning: redundant clone
  --> src\main.rs:36:15
   |
36 |         states.clone(),
   |               ^^^^^^^^ help: remove this
   |
   = note: `#[warn(clippy::redundant_clone)]` on by default
note: this value is dropped without further use
  --> src\main.rs:36:9
   |
36 |         states.clone(),
   |         ^^^^^^
   = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#redundant_clone

warning: redundant clone
  --> src\main.rs:37:17
   |
37 |         alphabet.clone(),
   |                 ^^^^^^^^ help: remove this
   |
note: this value is dropped without further use
  --> src\main.rs:37:9
   |
37 |         alphabet.clone(),
   |         ^^^^^^^^
   = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#redundant_clone

warning: redundant clone
  --> src\main.rs:39:28
   |
39 |         transition_function.clone(),
   |                            ^^^^^^^^ help: remove this
   |
note: this value is dropped without further use
  --> src\main.rs:39:9
   |
39 |         transition_function.clone(),
   |         ^^^^^^^^^^^^^^^^^^^
   = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#redundant_clone

warning: redundant clone
  --> src\main.rs:40:25
   |
40 |         accepting_states.clone(),
   |                         ^^^^^^^^ help: remove this
   |
note: this value is dropped without further use
  --> src\main.rs:40:9
   |
40 |         accepting_states.clone(),
   |         ^^^^^^^^^^^^^^^^
   = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#redundant_clone

warning: usage of `FromIterator::from_iter`
  --> src\main.rs:20:9
   |
20 |         HashSet::from_iter([State::new(1), State::new(2)].iter().cloned()),
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: use `.collect()` instead of `::from_iter()`: `[State::new(1), State::new(2)].iter().cloned().collect::<HashSet::from_iter([State::new(1), State<_>>()`
   |
   = note: `#[warn(clippy::from_iter_instead_of_collect)]` on by default
   = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#from_iter_instead_of_collect

warning: usage of `FromIterator::from_iter`
  --> src\main.rs:24:9
   |
24 |         HashSet::from_iter([State::new(2)].iter().cloned()),
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: use `.collect()` instead of `::from_iter()`: `[State::new(2)].iter().cloned().collect::<HashSet::from_iter([State<_>>()`
   |
   = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#from_iter_instead_of_collect

warning: usage of `FromIterator::from_iter`
  --> src\main.rs:28:9
   |
28 |         HashSet::from_iter([State::new(2)].iter().cloned()),
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: use `.collect()` instead of `::from_iter()`: `[State::new(2)].iter().cloned().collect::<HashSet::from_iter([State<_>>()`
   |
   = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#from_iter_instead_of_collect

warning: usage of `FromIterator::from_iter`
  --> src\main.rs:32:9
   |
32 |         HashSet::from_iter([State::new(2)].iter().cloned()),
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: use `.collect()` instead of `::from_iter()`: `[State::new(2)].iter().cloned().collect::<HashSet::from_iter([State<_>>()`
   |
   = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#from_iter_instead_of_collect

warning: 8 warnings emitted

There are four groups of warnings here:

  1. According to the standard Rust naming conventions, acronyms are capitalized as one word in CamelCase names, so DFA and NFA are supposed to be Dfa and Nfa respectively.

  2. The argument to expect is always evaluated even if it is not used. Use unwrap_or_else(|| panic!(/* ... */)) instead.

  3. When a value is used the last time, it can be moved instead of cloned to save allocations.

  4. from_iter is not supposed to be used directly — use collect instead.

Synchronization model

You created a bool channel, sent false and true values to report the results of each step, waited to receive a true value, and then waited for all the threads to finish computing, only to get their results discarded.

This model is inefficient. Perhaps we can use a AtomicBool as the success flag and make all workers stop when a successful result is obtained.

Miscellaneous

Let's go through the code.

This is a scary number:

const WORKER_COUNT: usize = 1024;

Are you sure the system you are working with is actually capable of running 1024 threads concurrently? If not, you are probably just adding the overhead of spawning threads. A more appropriate value might be somewhere around 4 or 8, depending on the system. See Can recursion be done in parallel? Would that make sense?.

Instead of constructors like this:

pub fn new(
    states: HashSet<State>,
    alphabet: HashSet<Symbol>,
    start: State,
    transition_function: HashMap<(State, Symbol), HashSet<State>>,
    accepting_states: HashSet<State>,
) -> Nfa {
    Nfa {
        states,
        alphabet,
        start,
        transition_function,
        accepting_states,
    }
}

just mark the fields pub. We don't even need add_transition.

When you clone something righteously, use clone, not to_owned.

Instead of let mut state = state;, simply mark the argument mut.

Types like State are usually defined as tuple structs:

#[derive(/* ... */)]
pub struct State(pub i32);

(Note that I skipped the tests since you didn't post them, but there are many opportunities for improvement in them as well!)

\$\endgroup\$
2
  • \$\begingroup\$ Thank you! This is a very thorough and thoughtful answer! Would you mind commenting on these questions? "Are there good quality unit tests that could be written for the parallelization? Can I improve the use of locks here? I think I abused the Copy and Clone traits, is there a way to reduce their use?" And also, any suggestions about tests would be very much appreciated! I feel like I upgraded my Rust skills a lot just from reading your answer. \$\endgroup\$
    – alexfertel
    Jun 22 at 13:42
  • 1
    \$\begingroup\$ @alexfertel Glad to be of help! I don't think parallelism is a big concern when writing tests - just testing the results should be fine. Some benchmarking may also be helpful. I briefly discussed the locking issue in the section "Synchronization model", but there are always different options and tradeoffs for synchronization - I'm not an expert on this either :) I don't really see how you "abused the Copy and Clone traits", so don't worry about that. Cloning isn't problematic in and of itself; appropriately placed .clone()s are nothing to worry about if the semantics calls for them. \$\endgroup\$
    – L. F.
    Jun 22 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.