5
\$\begingroup\$

I've just refactored my Rust and C++ code which simulates the shoeshine shop model from this question. What else can be improved?

C++:

#include <iostream> #include <iomanip> #include <random> #include <numeric> #include <algorithm> #include <array> #include <queue> #include <string> #include <functional> namespace shoeshine_shop { enum event_t { ARRIVED, FIRST_FINISHED, SECOND_FINISHED }; enum state_t { EMPTY, FIRST, SECOND, WAITING, BOTH, DROP, INVALID }; using distribution_t = std::function<double()>; struct pair_t { double time; event_t event; }; struct stats_t { std::array<size_t, DROP> state_counts; std::array<size_t, DROP> state_counts_with_drop; std::array<double, DROP> time_in_state; std::array<double, 3> time_in_client; double served_time; size_t served_clients, arrived_clients, dropped_clients; }; class simulation_t { private: template <typename T> auto print_tables(std::string_view title, T const &counts) { std::cout << title << "\n"; auto events = std::accumulate(std::begin(counts), std::end(counts), 0.0); for (size_t i = 0; i < DROP; ++i) std::cout << state_names[i] << ": " << counts[i] / double(events) << std::endl; std::cout << std::endl; } void debug_view(pair_t &event, state_t &state) { std::cout << "\t" << std::setprecision(std::numeric_limits<double>::digits10 + 1) << event.time << ": [" << state_names[state] << "] " << event_names[event.event] << " ==> [" << state_names[event_to_state[event.event][state]] << "]" << std::endl; } public: simulation_t(distribution_t arrival, distribution_t first_serving, distribution_t second_serving, std::uint64_t iterations = 50) : window{queue_comparator}, iterations{1'000'000 * iterations}, distributions{arrival, first_serving, second_serving}, log_tail{0} {} auto set_tail(std::uint64_t new_tail) noexcept { log_tail = new_tail; } bool simulate() { static auto pusher = [&](double t, event_t event) { double dt = distributions[event](); window.push({t + dt, event}); }; state_t state = EMPTY; double prev = 0.0; std::queue<double> arriving_times; window.push({0.0, ARRIVED}); for (std::uint64_t i = 0; i < iterations; ++i) { auto event = window.top(); window.pop(); if (iterations - i < log_tail) debug_view(event, state); switch (event.event) { case ARRIVED: ++statistics.arrived_clients; pusher(event.time, ARRIVED); break; case SECOND_FINISHED: statistics.served_time += event.time - arriving_times.front(); arriving_times.pop(); ++statistics.served_clients; } state_t new_state = event_to_state[event.event][state]; switch (new_state) { case INVALID: return false; case DROP: ++statistics.state_counts_with_drop[state]; ++statistics.dropped_clients; continue; case FIRST: case BOTH: if (event.event == ARRIVED) { arriving_times.push(event.time); pusher(event.time, FIRST_FINISHED); } break; case SECOND: pusher(event.time, SECOND_FINISHED); break; case EMPTY: case WAITING: break; } statistics.time_in_state[state] += event.time - prev; statistics.time_in_client[state_to_clients[state]] += event.time - prev; prev = event.time; state = new_state; ++statistics.state_counts[state]; } return true; } void print_report() { std::transform(std::begin(statistics.state_counts), std::end(statistics.state_counts), std::begin(statistics.state_counts_with_drop), std::begin(statistics.state_counts_with_drop), std::plus<std::size_t>()); print_tables("time in states: ", statistics.time_in_state); print_tables("entries in states: ", statistics.state_counts); print_tables("entries in states with dropouts: ", statistics.state_counts_with_drop); std::cout << "dropout: " << statistics.dropped_clients / double(statistics.arrived_clients) << std::endl; std::cout << "average serving time: " << statistics.served_time / double(statistics.served_clients) << std::endl; std::cout << "average number of clients: " << (statistics.time_in_client[1] + 2 * statistics.time_in_client[2]) / std::accumulate(std::begin(statistics.time_in_client), std::end(statistics.time_in_client), 0.0) << std::endl; } private: static constexpr std::array<const char *, 3> event_names{ {"ARRIVED", "FIRST_FINISHED", "SECOND_FINISHED"}}; static constexpr std::array<const char *, 7> state_names{ {"EMPTY", "FIRST", "SECOND", "WAITING", "BOTH", "DROP", "INVALID"}}; // clang-format off static constexpr std::array<std::array<state_t, 5>, 3> event_to_state{ // EMPTY FIRST SECOND WAITING BOTH /* ARRIVED */ {{FIRST, DROP, BOTH, DROP, DROP}, /* FIRST_FINISHED */ {INVALID, SECOND, INVALID, INVALID, WAITING}, /* SECOND_FINISHED */ {INVALID, INVALID, EMPTY, SECOND, FIRST}}}; // clang-format on static constexpr std::array<size_t, DROP> state_to_clients{0, 1, 1, 2, 2}; inline static const auto queue_comparator = [](pair_t const &left, pair_t const &right) { return (left.time > right.time); }; stats_t statistics{}; std::priority_queue<pair_t, std::vector<pair_t>, decltype(queue_comparator)> window; std::uint64_t iterations; std::array<distribution_t, 3> distributions; std::uint64_t log_tail; }; } // namespace shoeshine_shop int main(int argc, char **argv) { if (argc < 5) { std::cerr << "not enough arguments!\nlambda, m1, m2, millions of iterations"; return EXIT_FAILURE; } std::uint32_t seed = std::random_device{}(); std::mt19937 gen(seed); std::exponential_distribution arrival(std::atof(argv[1])); std::exponential_distribution first_serving(std::atof(argv[2])); std::exponential_distribution second_serving(std::atof(argv[3])); shoeshine_shop::simulation_t simul(std::bind(arrival, std::ref(gen)), std::bind(first_serving, std::ref(gen)), std::bind(second_serving, std::ref(gen)), std::atoll(argv[4])); if (argc == 6) { seed = std::atol(argv[5]); gen.seed(seed); simul.set_tail(100); } if (!simul.simulate()) { std::cerr << "ERROR: INVALID STATE REACHED, SEED: " << seed << std::endl; return EXIT_FAILURE; } simul.print_report(); return EXIT_SUCCESS; }

Rust:

use rand::{rngs::StdRng, Rng, SeedableRng}; use rand_distr::Exp; use structopt::StructOpt; mod shoeshine_shop { use std::cmp::Reverse; use std::collections::{BinaryHeap, VecDeque}; use std::convert::TryInto; use ordered_float::*; use rand::rngs::StdRng; use rand_distr::Distribution; #[derive(Copy, Clone, Debug, PartialEq, Ord, Eq, PartialOrd, enum_utils::TryFromRepr)] #[repr(usize)] enum Event { Arrived = 0, FirstFinished, SecondFinished, } #[derive(Copy, Clone, Debug, PartialEq, Ord, Eq, PartialOrd, enum_utils::TryFromRepr)] #[repr(usize)] enum State { Empty = 0, First, Second, Waiting, Both, Dropping, Invalid, } #[derive(Copy, Clone, Debug, Ord, Eq, PartialEq, PartialOrd)] struct Pair { time: OrderedFloat<f64>, event: Event, } #[rustfmt::skip] #[derive(Debug, Default)] struct Stats { state_counts: [u32; State::Dropping as usize], state_counts_with_drop: [u32; State::Dropping as usize], time_in_state: [f64; State::Dropping as usize], time_in_client: [f64; 3], served_time: f64, served_clients: u32, arrived_clients: u32, dropped_clients: u32, } const STATE_TO_CLIENTS: [usize; State::Dropping as usize] = [0, 1, 1, 2, 2]; #[rustfmt::skip] const EVENT_TO_STATE: [[State; 5]; 3] = [ // EMPTY FIRST SECOND WAITING BOTH /* Arrived */ [First, Dropping, Both, Dropping, Dropping], /* First_Finished */ [Invalid, Second, Invalid, Invalid, Waiting], /* Second_Finished */ [Invalid, Invalid, Empty, Second, First], ]; macro_rules! report { ($title:expr, $counts:expr) => {{ println!("{}", $title); let events: f64 = $counts.iter().copied().map(Into::<f64>::into).sum(); for (i, count) in $counts.iter().enumerate() { let state: State = i.try_into().unwrap(); println!("{:?}: {}", state, Into::<f64>::into(*count) / events); } println!(); }}; } pub struct Simulation<T: Distribution<f64>> { statistics: Stats, window: BinaryHeap<Reverse<Pair>>, iterations: u64, distributions: [T; 3], log_tail: u64, } use Event::*; use State::*; impl<T> Simulation<T> where T: Distribution<f64>, { pub fn new( arrival: T, first_serving: T, second_serving: T, iterations: u64, ) -> Simulation<T> { Simulation { statistics: Stats::default(), window: BinaryHeap::new(), iterations: iterations, distributions: [arrival, first_serving, second_serving], log_tail: 0, } } pub fn set_tail(&mut self, new_tail: u64) { self.log_tail = new_tail; } pub fn print_report(&mut self) { for (i, element) in self .statistics .state_counts_with_drop .iter_mut() .enumerate() { *element += self.statistics.state_counts[i]; } report!("\ntime in states: ", self.statistics.time_in_state); report!("entries in states: ", self.statistics.state_counts); report!( "entries in states with dropouts: ", self.statistics.state_counts_with_drop ); println!( "dropout: {}\naverage serving time: {}\naverage number of clients: {}", (self.statistics.dropped_clients as f64) / (self.statistics.arrived_clients as f64), self.statistics.served_time / (self.statistics.served_clients as f64), (self.statistics.time_in_client[1] + 2.0f64 * self.statistics.time_in_client[2]) / self.statistics.time_in_client.iter().sum::<f64>() ); } pub fn simulate(&mut self, prng: &mut StdRng) -> bool { macro_rules! pusher { ($t:expr, $event:expr) => {{ let dt: f64 = self.distributions[$event as usize].sample(prng).into(); self.window.push(Reverse(Pair { time: ($t + dt).into(), event: $event, })); }}; } let mut prev = 0f64; let mut state = State::Empty; let mut arriving_times = VecDeque::<f64>::new(); self.window.push(Reverse(Pair { time: 0.0.into(), event: Arrived, })); for i in 0..self.iterations { let event = self.window.pop().unwrap().0; if self.iterations - i < self.log_tail { println!( "{}: [{:?}] {:?} ==> [{:?}]", event.time.0, state, event.event, EVENT_TO_STATE[event.event as usize][state as usize] ); } match event.event { Arrived => { self.statistics.arrived_clients += 1; pusher!(event.time.0, Arrived); } SecondFinished => { self.statistics.served_time += event.time.0 - arriving_times.front().unwrap(); arriving_times.pop_front(); self.statistics.served_clients += 1; } _ => (), } let new_state = EVENT_TO_STATE[event.event as usize][state as usize]; match new_state { Invalid => return false, Dropping => { self.statistics.state_counts_with_drop[state as usize] += 1; self.statistics.dropped_clients += 1; continue; } First | Both if event.event == Arrived => { arriving_times.push_back(event.time.0); pusher!(event.time.0, FirstFinished); } Second => pusher!(event.time.0, SecondFinished), _ => (), } self.statistics.time_in_state[state as usize] += event.time.0 - prev; self.statistics.time_in_client[STATE_TO_CLIENTS[state as usize]] += event.time.0 - prev; prev = event.time.0; state = new_state; self.statistics.state_counts[state as usize] += 1; } true } } } ///shoe shine shop simulation /// /// Shoe shine shop has two chairs, one for brushing (1) and another for polishing (2). /// Customers arrive according to PP with rate λ, and enter only if first chair is empty. /// Shoe-shiners takes exp(μ1) time for brushing and exp(μ2) time for polishing. #[derive(StructOpt, Debug)] #[structopt(name = "sim")] struct Args { ///rate of customer arrival #[structopt(long)] lambda: f64, ///rate of serving on the first chair #[structopt(long)] mu1: f64, ///rate of serving on the second chair #[structopt(long)] mu2: f64, ///millions of events to simulate #[structopt(short)] iterations: u64, ///expilictly set seed #[structopt(short)] seed: Option<u64>, ///change log tail #[structopt(short, default_value = "0")] tail: u64, } fn main() { let args = Args::from_args(); let mut simulation = shoeshine_shop::Simulation::new( Exp::new(args.lambda).unwrap(), Exp::new(args.mu1).unwrap(), Exp::new(args.mu2).unwrap(), args.iterations * 1_000_000, ); let seed = args.seed.unwrap_or(rand::thread_rng().gen()); simulation.set_tail(args.tail); let mut prng: StdRng = SeedableRng::seed_from_u64(seed); if !simulation.simulate(&mut prng) { panic!("Error: invalid state reached, seed: {}", seed); } simulation.print_report(); }
\$\endgroup\$

1 Answer 1

Reset to default
1
\$\begingroup\$

Firstly, not all of your states are states. In particular, Invalid and Dropping are not states. Instead, they are types of transitions. The model would make more sense like this:

enum State { Empty, First, Second, Both, Waiting } enum Transition { NewState(State), Invalid, Dropping }

Further, I think that transition tables aren't a very Rust-y solution. Instead, I'd recommend using a match like so:

match (state, event) { (State::Empty, Event::Arrived) => Transition::NewState(State::First), (State::Second, Event::Arrived) => Transition::NewState(State::Both), (State::_, Event::Arrived) => Transition::Dropped, (State::First, Event::FirstFinished) => Transition::NewState(State::Second), (State::Both, Event::FirstFinished) => Transition::NewState(State::Waiting), (State::Second, Event::SecondFinished) => Transition::NewState(State::Empty), (State::Both, Event::SecondFinished) => Transition::NewState(State::First), (State::Waiting, Event::SecondFinished) => Transition::NewState(State::Second), _ => Transition::Invalid }

I would replace all of your [;State::Dropping as usize] arrays with EnumMap from the enum-map crate. It acts like a HashMap but is implemented in terms of an array. If you do that, your code will become somewhat simpler and you should be able to remove all conversions between usize and your state enum.

But, it seems to me that you actually have two pieces of semi-independent state: the state of your two seats. I think your code would simpler if you split them up. Something like this:

enum SeatState { Empty, Busy, Waiting } let mut seat_state_1 = SeatState::Empty; let mut seat_state_2 = SeatState::Empty; match event { Event::Arrived => { if seat_state_1 == SeatState::Empty { seat_state_1 = SeatState::Busy; } else { // handle dropping } }, Event::FirstFinished => { if seat_state_1 == SeatState::Busy { seat_state_1 = SeatState::Waiting; } }, Event::SecondFinished => { if seat_state_2 == SeatState::Busy { seat_state_2 = SeatState::Waiting } } } // If the second seat is finished, they leave. if seat_state_2 == SeatState::Waiting { seat_state_2 = SeatState::Empty; } // If the first seat is finished and the second seat is free, move over. if seat_state_1 == SeatState::Waiting && seat_state_2 == SeatState::Empty { seat_state_1 = SeatState::Empty; seat_state_2 = SeatState::Busy; }

I think this more clearly presents the logic of how the state changes in your model then a transition table.

I would recommend against defining report as a macro as you have down. Don't use a macro when you can use a function. I think part of the reason you did this was because you ended up with a lots of traits on your generic definition. But you should be able to do it more simply:

fn report<T: Copy>(title: &str, counts: &[T]) where f64: From<T> { println!("{}", title); let events: f64 = counts.iter().copied().map(f64::from).sum(); for (i, count) in counts.iter().enumerate() { let state: State = i.try_into().unwrap(); println!("{:?}: {}", state, f64::from(*count) / events); } println!(); }

You only need the T to be Copy and convertible to f64.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ About semi-independent state: your approach is very error-prone because of not interesting/invalid states (like "second is waiting") that can be expressed. Also it would mean that I have to match this split state back to one just to calculate statistics. In previous question I was suggested to write a macro which translates transition table into a match statement. But I reckon table is simpler to understand, no? Thanks for enum-map, I'll look into that. \$\endgroup\$ Commented Nov 16, 2019 at 11:16
  • \$\begingroup\$ Invalid really isn't a kind of transition so much as the lack of a transition. Option<Transition> makes more sense to me. \$\endgroup\$ Commented Nov 16, 2019 at 14:08
  • 1
    \$\begingroup\$ @rogday, we need to be careful with what we mean by understand. It is very easy to look at a table and see that state Both with event FirstFinished transitions to Waiting. However, it is not easy to understand why that is the correct transition. One has to reverse engineer the logic of the transitions. The really compact representation in a table really doesn not help there. \$\endgroup\$ Commented Nov 16, 2019 at 14:47
  • 1
    \$\begingroup\$ To me, the match is easier because it is less dense, allows comments to be added for non-obvious transitions, allows the grouping of similar cases to be handled together, and doesn't require me to either count or align items in tet. \$\endgroup\$ Commented Nov 16, 2019 at 14:49
  • 1
    \$\begingroup\$ Now, with all of that, it is subjective and you should feel free to disagree. But I hope I've at least given you an some additional insights in ways to approach these sorts of problems. \$\endgroup\$ Commented Nov 16, 2019 at 14:52

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.