Shoe shine shop model in Rust and C++ - Follow-up

Question

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();
}

Answer 1

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.