17
\$\begingroup\$

I'm learning Rust and a few questions did arise during translation of my C++ code to Rust. There are comments in Rust code I'd like to be answered. Is there an idiomatic way to solve this task? The task was in simulating a random process - there are two chairs, which have different processing capacity and there is a flow of customers, who visit the chairs sequentially.

Summary: Shoe shine shop has two chairs, one for brushing (1) and another for polishing (2). Customers arrive according to PP with rate \$\lambda\$, and enter only if first chair is empty. Shoe-shiners takes \$\exp(\mu_1)\$ time for brushing and \$\exp(\mu_2)\$ time for polishing.

Code in C++:

#include <map>
#include <string>
#include <random>
#include <iostream>
#include <numeric>
#include <algorithm>
#include <queue>

int main(int argc, char *argv[]) {
  if (argc < 5) {
    std::cerr << "not enough arguments!\nlambda, m1, m2, max_time";
    return -1;
  }

  using distribution_t = std::exponential_distribution<double>;

  std::string event_names[3] = {"ARRIVED", "FIRST_FINISHED", "SECOND_FINISHED"};
  std::string state_names[7] = {"EMPTY", "FIRST", "SECOND", "WAITING",
                                "BOTH",  "DROP",  "INVALID"};

  enum event_t { ARRIVED = 0, FIRST_FINISHED, SECOND_FINISHED };
  enum state_t { EMPTY = 0, FIRST, SECOND, WAITING, BOTH, DROP, INVALID };

  std::size_t state_to_clients[DROP] = {0, 1, 1, 2, 2};

  // clang-format off
  //                         EMPTY    FIRST    SECOND   WAITING  BOTH
  state_t event_to_state[3][5] = {
      /* ARRIVED */         {FIRST,   DROP,    BOTH,    DROP,    DROP},
      /* FIRST_FINISHED */  {INVALID, SECOND,  INVALID, INVALID, WAITING},
      /* SECOND_FINISHED */ {INVALID, INVALID, EMPTY,   SECOND,  FIRST},
  };
  // clang-format on

  double lambda = atof(argv[1]);
  double m1 = atof(argv[2]);
  double m2 = atof(argv[3]);
  double time_max = atof(argv[4]);

  std::mt19937_64 generator(std::random_device{}());

  struct stats_t {
    std::size_t state_counts[DROP]{}; // max feasible event - BOTH
    std::size_t state_counts_with_drop[DROP]{};

    double time_in_state[DROP]{};
    double time_in_client[3]{}; // roflanEbalo

    double served_time = 0.0;
    std::size_t served_clients = 0;

    std::size_t arrived_clients = 0;
    std::size_t dropped_clients = 0;
  } stats;

  double times[3]{};
  distribution_t dists[3] = {distribution_t(lambda), distribution_t(m1),
                             distribution_t(m2)}; // mean = 1/param

  std::map<double, event_t> timeline;

  auto inserter = [&timeline, &generator](event_t event, double &t,
                                          distribution_t &dist) {
    double dt;
    do {
      dt = dist(generator);
    } while (!timeline.try_emplace(t + dt, event).second);
    t += dt;
  };

  for (std::size_t i = 0; i < 3; ++i)
    while (times[event_t(i)] < time_max)
      inserter(event_t(i), times[i], dists[i]);

  double prev = 0;
  state_t state = EMPTY;
  std::queue<double> arriving_times;

  for (auto [time, event] : timeline) {
    if (argc > 5) {
      std::cout << "[PROCESSING]: " << time << " " << event_names[event]
                << std::endl;
      std::cout << "[INFO]: " << state_names[state] << std::endl;
    }

    if (event == ARRIVED)
      ++stats.arrived_clients;

    state_t new_state = event_to_state[event][state];

    switch (new_state) {
    case INVALID:
      break;

    case DROP:
      ++stats.state_counts_with_drop[state];
      ++stats.dropped_clients;
      break;

    default:
      if (event == ARRIVED)
        arriving_times.push(time);
      else if (event == SECOND_FINISHED) {
        stats.served_time += time - arriving_times.front();
        arriving_times.pop();
        ++stats.served_clients;
      }

      stats.time_in_state[state] += time - prev;
      stats.time_in_client[state_to_clients[state]] += time - prev;
      prev = time;

      state = new_state;
      ++stats.state_counts[state];

      break;
    }
  }

  std::transform(std::begin(stats.state_counts), std::end(stats.state_counts),
                 std::begin(stats.state_counts_with_drop),
                 std::begin(stats.state_counts_with_drop),
                 std::plus<std::size_t>());

  auto report = [&state_names](std::string_view title, auto counts) {
    std::cout << title << std::endl;

    auto events = std::accumulate(counts, counts + DROP, 0.0);

    for (std::size_t i = 0; i < DROP; ++i)
      std::cout << state_names[i] << ": " << counts[i] / double(events)
                << std::endl;
    std::cout << std::endl;
  };

  report("time in states: ", stats.time_in_state);
  report("entries in states: ", stats.state_counts);
  report("entries in states with dropouts: ", stats.state_counts_with_drop);

  std::cout << "dropout: "
            << stats.dropped_clients / double(stats.arrived_clients)
            << std::endl;

  std::cout << "average serving time: "
            << stats.served_time / double(stats.served_clients) << std::endl;

  std::cout << "average number of clients: "
            << (stats.time_in_client[1] + 2 * stats.time_in_client[2]) /
                   std::accumulate(std::begin(stats.time_in_client),
                                   std::end(stats.time_in_client), 0.0)
            << std::endl;

  // arr=(10 10 10); for i in {0..2}; do for param in {1..100}; do
  // darr=("${arr[@]}"); darr[i]=${param}; echo "${darr[@]}" >> ../out.txt &&
  // ./lab2.exe ${darr[@]} 1000000 >> ../out.txt; done; done
}

Code in Rust:

use std::collections::BTreeMap;
use std::collections::VecDeque;
use std::env;

extern crate rand;
use rand::distributions::*;

extern crate ordered_float;
pub use ordered_float::*;

// variant is never constructed: `FirstFinished`, why do I get this message? I can see this variant printed when running the program
#[derive(Copy, Clone, Debug, PartialEq)]
enum Events {
    Arrived = 0,
    FirstFinished,
    SecondFinished,
}

#[derive(Copy, Clone, Debug, PartialEq)]
enum States {
    Empty = 0,
    First,
    Second,
    Waiting,
    Both,
    Dropping,
    Invalid,
}

#[rustfmt::skip]
#[derive(Debug, Default)]
struct Stats {
    state_counts:           [u32; States::Dropping as usize],
    state_counts_with_drop: [u32; States::Dropping as usize],

    time_in_state:          [f64; States::Dropping as usize],
    time_in_client:         [f64;  3],

    served_time:            f64,
    served_clients:         u32,

    arrived_clients:        u32,
    dropped_clients:        u32,
}

// 1 template function for this? Or any other way to cast integer to enum? Or I should use libraries for this?
impl From<usize> for States {
    fn from(s: usize) -> States {
        let tmp: u8 = s as u8;
        unsafe { std::mem::transmute(tmp) }
    }
}

impl From<usize> for Events {
    fn from(s: usize) -> Events {
        let tmp: u8 = s as u8;
        unsafe { std::mem::transmute(tmp) }
    }
}

//what do I need lifetime 'a for? Is there supertrait that specifies multiple traits? ("Number", "container", idk)
//Or can I just say that allowed types are f64 and i32?
fn report<'a, T>(title: &str, counts: &'a [T; States::Dropping as usize])
where
    T: std::iter::Sum<&'a T> + std::ops::Div + Copy + Into<f64> + std::fmt::Display,
{
    println!("{}", title);
    let events: T = counts.iter().sum();

    for i in 0..(States::Dropping as usize) {
        println!(
            "{:?}: {}",
            Into::<States>::into(i),
            Into::<f64>::into(counts[i]) / Into::<f64>::into(events) // How to call Into properly? this looks bad
        );
    }
    println!();
}

fn main() {
    let state_to_clients: [usize; States::Dropping as usize] = [0, 1, 1, 2, 2];

    #[rustfmt::skip]
    let event_to_state: [[States; 5]; 3] = [
        //                     EMPTY            FIRST             SECOND           WAITING           BOTH
        /* Arrived */         [States::First,   States::Dropping, States::Both,    States::Dropping, States::Dropping],
        /* First_Finished */  [States::Invalid, States::Second,   States::Invalid, States::Invalid,  States::Waiting],
        /* Second_Finished */ [States::Invalid, States::Invalid,  States::Empty,   States::Second,   States::First],
    ];

    let args: Vec<String> = env::args().collect();

    if args.len() < 5 {
        panic!("Not enough arguments!");
    }

    let (lambda, m1, m2, time_max) = (
        args[1].parse::<f64>().unwrap(),
        args[2].parse::<f64>().unwrap(),
        args[3].parse::<f64>().unwrap(),
        args[4].parse::<f64>().unwrap(),
    );

    let mut rng = rand::thread_rng();
    let mut stats = Stats::default();
    let mut times: [f64; 3] = Default::default();

    let mut dists: [Exp; 3] = [Exp::new(lambda), Exp::new(m1), Exp::new(m2)];

    // I don't like OrderedFloat because it's a wrapper. Is there a way to implement Ord for floats and keep nice syntax?
    // Maybe it's the problem of algorithm. Any proposals?
    let mut timeline: BTreeMap<OrderedFloat<f64>, Events> = BTreeMap::new();
    let mut inserter = |event: &Events, t: &mut f64, distribution: &mut Exp| {
        let mut dt;

        //Is it ok to emulate do while loops like this?
        while {
            dt = OrderedFloat(distribution.sample(&mut rng));
            let key = OrderedFloat(*t + Into::<f64>::into(dt));

            match timeline.get(&key) {
                Some(_) => true,
                None => {
                    timeline.insert(key, *event);
                    false
                }
            }
        } {}
        *t += Into::<f64>::into(dt);
    };

    for i in 0..3 {
        while times[i] < time_max {
            inserter(&i.into(), &mut times[i], &mut dists[i]);
        }
    }

    let mut prev = 0f64;
    let mut state = States::Empty;
    let mut arriving_times = VecDeque::<f64>::new();

    for (time, event) in timeline {
        if args.len() > 5 {
            println!("[PROCESSING]: {} {:?}", time, event);
            println!("[INFO]: {:?}", state);
        }

        if event == Events::Arrived {
            stats.arrived_clients += 1;
        }

        let new_state = event_to_state[event as usize][state as usize];

        match new_state {
            States::Dropping => {
                stats.state_counts_with_drop[state as usize] += 1;
                stats.dropped_clients += 1;
            }
            States::Invalid => (),
            _ => {
                if event == Events::Arrived {
                    arriving_times.push_back(Into::<f64>::into(time));
                } else if event == Events::SecondFinished {
                    stats.served_time += Into::<f64>::into(time) - arriving_times.front().unwrap();
                    arriving_times.pop_front();
                    stats.served_clients += 1;
                }

                stats.time_in_state[state as usize] += Into::<f64>::into(time) - prev;
                stats.time_in_client[state_to_clients[state as usize] as usize] +=
                    Into::<f64>::into(time) - prev;
                prev = Into::<f64>::into(time);

                state = new_state;
                stats.state_counts[state as usize] += 1;
            }
        };
    }

    for (i, element) in stats.state_counts_with_drop.iter_mut().enumerate() {
        *element += stats.state_counts[i];
    }

    report("time in states: ", &stats.time_in_state);
    report("entries in states: ", &stats.state_counts);
    report(
        "entries in states with dropouts: ",
        &stats.state_counts_with_drop,
    );

    println!(
        "dropout: {}\naverage serving time: {}\naverage number of clients: {}",
        (stats.dropped_clients as f64) / (stats.arrived_clients as f64),
        stats.served_time / (stats.served_clients as f64),
        (stats.time_in_client[1] + 2.0f64 * stats.time_in_client[2])
            / stats.time_in_client.iter().sum::<f64>()
    );
}
\$\endgroup\$
  • \$\begingroup\$ It seems to me that your use of a state transition table is very C++ and not really in keeping with Rust style. I'd like to offer more concrete advice, but I'm having trouble understanding the logic of your table. I'd have thought it would Invalid to Arrive when not in the empty state. But you either transition to Dropping or Both. I'm guessing that Dropping means that the client left before the shoe shine was finished, and you are interpreting "Arrive" in a non-empty state as "Depart." But then I can't figure out what the Both state is doing. \$\endgroup\$ – Winston Ewert Nov 10 at 6:04
  • \$\begingroup\$ You seem to transition to the Both state if the client leaves while the left-shoe is being shined? But it would seem that the second shoe wouldn't be shined in that case, so its odd to call it Both. And I can't figure out any logic to the transition to the First or Waiting states from that state. \$\endgroup\$ – Winston Ewert Nov 10 at 6:06
  • \$\begingroup\$ I took another look this morning and I now think both versions are solving the wrong problem. I edited my answer with details. Hope this helps! \$\endgroup\$ – trentcl Nov 10 at 14:44
  • \$\begingroup\$ @winston-ewert It's allowed to receive a client on the first chair while the second is occupied. "BOTH" state means both clients are getting served. "WAITING" means client on the first chair awaits for the other one to finish. \$\endgroup\$ – rogday Nov 10 at 23:21
  • 2
    \$\begingroup\$ Please don't edit the question after it has been answered, the point is to allow every reviewer to see the same code. For more information see this help page codereview.stackexchange.com/help/someone-answers \$\endgroup\$ – pacmaninbw Nov 14 at 12:26
16
\$\begingroup\$

Correctness of the solution

On reflection, I'm not sure either the C++ or the Rust code solves the problem as stated. I'm not completely sure I understand the shoe shine shop model so I may be wrong. Here's what it looks like the code does: you generate a bunch of random events of all kinds, and order them in time. Then you process the events one by one starting with the earliest. But that doesn't make sense!

Customers arrive according to PP with rate \$\lambda\$, and enter only if first chair is empty. Shoe-shiners takes \$\exp(\mu_1)\$ time for brushing and \$\exp(\mu_2)\$ time for polishing.

The way I'm reading it, your random variables should be ordered not with respect to other events of the same kind, but with respect to the order of events in the shop. A shop can't finish shining a shoe before it has been brushed, and it can't finish brushing a shoe before any customers have arrived. Therefore, you need to schedule a FirstFinished event with respect to the Arrived event that initiated it, not with respect to the previous FirstFinished event.

A BTreeMap isn't the right solution to this problem. One way to solve it might be a priority queue with both the event kind and the time of the event (possibly a BinaryHeap<(OrderedFloat<f64>, Events)>). Your event queue starts out filled with only Arrivals, randomly distributed according to \$PP(\lambda)\$. As you process the queue, you pull off an arrival, and schedule the FirstFinished event at some time in the future relative to the arrival time. Then you pull off the next event, which could either be another Arrival (which you would have to drop) or the FirstFinished event you just pushed on (which would enable you to transition to the next state, and schedule the SecondFinished event), and continue processing.

I thought so too, but my group mate guessed that it doesn't make a difference. When the results produced by this program matched theoretical ones, I was convinced. Out of interest I just programmed your version of the solution and the results are the same.

Okay, I'm not an expert but I do think this is technically true, because the expected time remaining until the next event does not depend on the time since the last event. So from a pure results perspective your colleague may be correct. However, there are still two good reasons to write the solution the way it is formulated:

  1. You are relying, perhaps unaware, on a feature unique to exponential distributions. Suppose you were asked to model the same problem, but use a normal distribution for the time it takes to brush or shine shoes (which is probably more reasonable, anyway). Your current code can't be easily changed to account for that; you'll have to rewrite it. Also, if somebody else came along after you, they might not realize this code depends on an exponential distribution; they are likely to be confused (as I was).
  2. Generating a lot of random numbers has performance implications. Consider the difference between cargo run 1 50 50 10 and cargo run 1 1000000000 1000000000 10. These simulations should serve roughly the same number of customers, but the second one calculates nearly two billion random numbers that never get used!

That said, a lot of the advice I have to give here is applicable generally, so let's proceed as if the program's behavior is correct as written. I will restrict myself to comments on the Rust code, as that's what I am more familiar with.

Versions

You may be using an older version of Rust. extern crate declarations are not needed anymore in the 2018 edition. If you're still on 2015, that's fine; I just thought you might like to know.

Most distributions in the rand::distributions module have been moved to a separate crate, rand_distr. The old versions are deprecated; I got warnings about it during compilation. I don't know how long ago this change was made; you might want to update your dependencies. Again, not necessarily a problem, just FYI.

Style

Thank you for using rustfmt.

States and Events should be named State and Event, because each enum represents a single state or event, not several.

Star imports (like use rand::distributions::*;) are usually inadvisable, like using namespace in C++, because they pollute the module namespace. If you have a lot of them you can easily lose track of which names come from where. You're only using a couple of specific names here, so just write them explicitly:

use rand::distributions::{Distribution, Exp};
pub use ordered_float::OrderedFloat;

(Seeing as nothing else is marked pub, that can presumably go too.)

Don't loop over integers and then index into a slice. Instead, loop over the slice, and possibly throw an .iter().enumerate() in if you need access to the index, so

for i in 0..s.len() { /* do something with s[i] */ }

becomes

for element in s { /* do something with element */ }
// or
for (i, element) in s.iter().enumerate() { /* if you need i too */ }

Questions

Variant is never constructed

// variant is never constructed: `FirstFinished`, why do I get this message? I can see this variant printed when running the program

This looks like a compiler bug in that it doesn't realize that converting from an integer, with or without unsafe, can create variants without naming them.

Integer to enum conversions

// 1 template function for this? Or any other way to cast integer to enum? Or I should use libraries for this?
impl From<usize> for States {
    fn from(s: usize) -> States {
        let tmp: u8 = s as u8;
        unsafe { std::mem::transmute(tmp) }
    }
}

There is no reason to use unsafe here. In fact, as written it is incorrect, because passing a usize that doesn't correspond to a valid States could cause undefined behavior. As long as you're using safe Rust, the compiler protects you from unsafety; when you use unsafe, you assume responsibility for writing a safe abstraction that can't be used unsafely.

C-like enums implement the TryInto trait, which you should use instead. You can replace the bodies of both functions with s.try_into().unwrap(). Oops, this was a blunder on my part. TryFrom/TryInto are not automatically implemented for C-like enums; that was a requested feature that I thought had been implemented, and compiled when I tried it but actually is incorrect. Instead you should probably just write TryFrom yourself; here's one example. However, converting enums to integers isn't particularly idiomatic in Rust; if you rewrite the code to use a match as under "Design concerns" below, it's not necessary.

report

//what do I need lifetime 'a for? Is there supertrait that specifies multiple traits? ("Number", "container", idk)
//Or can I just say that allowed types are f64 and i32?
fn report<'a, T>(title: &str, counts: &'a [T; States::Dropping as usize])
where
    T: std::iter::Sum<&'a T> + std::ops::Div + Copy + Into<f64> + std::fmt::Display,
{

What do I need 'a for?

Not much, in this example. Named lifetimes are all about specifying relationships, in this case, the relationship between counts, which is a reference, and Sum<&T> which is a trait satisfied by T. You have T: Sum<&'a T>, which means that you can add a bunch of &'a Ts and get the sum as a T. You have a bunch of &'a Ts (the slice) and you need a T, so that's the right constraint. There's not much more to it than that.

Is there a supertrait that specifies multiple [number-like] traits?

There are traits like that, defined in the num_traits crate. You usually want num_traits::Num to do general math on a generic type. But it's not really needed here; if you change the events line to

    let events: f64 = counts.iter().copied().map(Into<f64>::into).sum();

you only need T: Copy + Into<f64> to implement the whole function. (This line looks pretty ugly; probably there's something nice and elegant I'm overlooking.)

Calling into

            Into::<States>::into(i),
            Into::<f64>::into(counts[i]) / Into::<f64>::into(events) // How to call Into properly? this looks bad

If you really need to specify the type argument to Into, that's how you would do it, but that's unusual. Most of the time you can just write .into(). When the types implement From, that is also often somewhat cleaner.

            States::from(i),
            counts[i].into() / events.into()

You have several other intos scattered in this loop:

    for (time, event) in timeline { ... }

But they're all turning time, which is an OrderedFloat<f64>, into a regular f64. You don't need to do that; because OrderedFloat is just a newtype struct, you can just access the inner value with .0. Or in this case, since you don't actually need the OrderedFloat inside the loop, you may use a destructuring pattern to pull it out as you iterate.

    for (OrderedFloat(time), event) in timeline { ... }

OrderedFloat

    // I don't like OrderedFloat because it's a wrapper. Is there a way to implement Ord for floats and keep nice syntax?
    // Maybe it's the problem of algorithm. Any proposals?
    let mut timeline: BTreeMap<OrderedFloat<f64>, Events> = BTreeMap::new();

Not really, you need to decide somehow how to handle NaNs. If NaNs aren't a possibility, maybe floating-point numbers aren't an appropriate type. An alternative might be to pick a unit, like 1 nanosecond, and just keep all your times and durations as integers, only converting them for display purposes.

Emulating do loops

        //Is it ok to emulate do while loops like this?
        while {
            /* loop body that returns true or false */
        } {}

I mean, I guess it works, but ew. Just use loop and have if condition { break; } in there somewhere.

Design concerns

main is too long. pacmaninbw's advice applies as well to Rust as to C++. I'd try to move some of that logic out to methods of State.

I like the way you use derive(Default) to avoid doing unnecessary work; that feels nice and idiomatic.

The Invalid state of your machine makes me slightly uncomfortable. There are uses for such things but it looks like you could get rid of it entirely and just panic immediately when you encounter an invalid state/event combination, rather than making your state temporarily invalid until the next loop iteration.

There's another thing that also seems awkward to me, and that's the repeated use of States::Dropping as usize for an array size. This use of enums is normal in C but in Rust it just feels out of place; enum is not just a renamed integer but a full-featured sum type. Ideally, you would make use of this to write a next_state function that is statically guaranteed to cover all the bases:

fn next_state(sr: State, event: Event) -> Option<State> {
    match sr {
        State::Empty => match event {
            Event::Arrived => Some(State::First),
            _ => None,
        }
        State::First => match event {
            Event::Arrived => Some(State::Dropping),
            Event::FirstFinished => Some(State::Second),
            _ => None,
        }
        /* ... */
    }
}

Turning this into a macro so you can keep the nice table format in the source code seems pretty doable.

Miscellaneous tips

    let event_to_state: [[States; 5]; 3] = [
        //                     EMPTY            FIRST             SECOND           WAITING           BOTH
        /* Arrived */         [States::First,   States::Dropping, States::Both,    States::Dropping, States::Dropping],
        /* First_Finished */  [States::Invalid, States::Second,   States::Invalid, States::Invalid,  States::Waiting],
        /* Second_Finished */ [States::Invalid, States::Invalid,  States::Empty,   States::Second,   States::First],
    ];

This is a bit long and noisy compared to the C++ version; you can trim it down by adding a use States::*;. Also it should be a const (not quite like C's const; more analogous to constexpr in C++).

    use States::*;
    #[rustfmt::skip]
    const EVENT_TO_STATE: [[States; 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],
    ];

I might consider using a declarative macro instead of a generic function for report. It's internal, the abstraction is mostly syntax and the trait bounds are not terribly interesting.

I don't really like macros since I come from c++. Are they widely used by Rust community?

Yes. Declarative macros (those defined with macro_rules!) are quite different from preprocessor macros (fancy text substitution) like in C.

  • They resemble C++ templates in that they must be syntactically valid at definition, but don't type check until instantiated.
  • Macros are hygienic (names defined in the macro don't leak to the outer scope, or vice versa).
  • They are also scoped, so they don't leak out of the function or module in which they are defined.

As with any form of metaprogramming, it's possible to go overboard, but you shouldn't be afraid of using a macro now and again to reduce repetitive code that can't easily be made into a function or generic. Procedural macros are a different story, but they're even more infrequently needed.

\$\endgroup\$
  • \$\begingroup\$ Thank you for such an extensive and detailed reply! Correctness: I thought so too, but my group mate guessed that it doesn't make a difference. When the results produced by this program matched theoretical ones, I was convinced. Out of interest I just programmed your version of the solution and the results are the same. Integer to enum conversions: I can't seem to find any information about enums implementing TryInto trait - it doesn't work, should I derive them from something? Report: I don't really like macros since I come from c++. Are they widely used by Rust community? \$\endgroup\$ – rogday Nov 10 at 23:15
  • 1
    \$\begingroup\$ @rogday I can always use some practice with C++, so I tried to write this simulator in C++ as if in Rust. Here's what I came up with. It is a bit longer than yours, but does some extras, and some of the verbosity is just writing long C++ versions of something that is short in Rust (like #[derive(Debug)]). More importantly, it doesn't have a Dropping or an Invalid state, and it uses enum class, no integer conversions. I make no claim about it being good (fast, idiomatic) C++ -- I don't specialize in that language. \$\endgroup\$ – trentcl Nov 16 at 2:11
  • 1
    \$\begingroup\$ I need Dropping state to calculate statistics. Also, there is a priority_queue, which doesn't require pop_heap functions. Why don't you like transition table? Isn't it much simpler than nested if statements? Anyway, I was asked not to edit my question, so if you'd like to take a look at my implementation of your treeless way, codereview.stackexchange.com/questions/232390/… \$\endgroup\$ – rogday Nov 16 at 11:06
  • 1
    \$\begingroup\$ Thanks, I didn't know about priority_queue. I actually don't have anything against the transition table, but I do dislike turning enums into integers in order to index it, because it depends on the order of variants in the enum and isn't type safe. If you add another state to the machine or decide to reorder them (as I did), the match will either fail to compile or continue working exactly as before, whereas the transition table will silently change its behavior, possibly invoking UB, while the compiler at most issues a warning. \$\endgroup\$ – trentcl Nov 16 at 13:08
  • 1
    \$\begingroup\$ switch doesn't work with non-integers and enum classes are not integers. I'd have to go back to regular non-type-safe enums for that to work. (Unless there's a way to make static_cast predictable for an enum class?) I'd still be stuck with a nested switch instead of a nicely formatted state table like in Rust, which partially defeats the purpose. And all the default:s and break;s that are logically necessary but syntactically optional make switch fragile at the best of times. Just doesn't seem worth it to me. \$\endgroup\$ – trentcl Nov 16 at 13:32
10
\$\begingroup\$

Forgive me, I am unable to review the rust code because I do not know rust, I am only reviewing the c++ code..

Use System Defined Exit Codes

Returning -1 as an exit code from a c++ program is rather uncommon, the generally accepted values to return from a c++ program are zero for success and one for failure. What is even better is that if the cstdlib header is included then the symbolic constants EXIT_SUCCESS and EXIT_FAILURE are available for use which makes the program more readable and very portable.

int main(int argc, char *argv[]) {
    if (argc < 5) {
        std::cerr << "not enough arguments!\nlambda, m1, m2, max_time";
        return EXIT_FAILURE;
    }

In the error message above, unless the user is familiar with what lambda, m1, m2 and max_time are the message may be unclear to the user.

Complexity

The function main() is too complex (does too much). As programs grow in size the use of main() should be limited to calling functions that parse the command line, calling functions that set up for processing, calling functions that execute the desired function of the program, and calling functions to clean up after the main portion of the program.

There is also a programming principle called the Single Responsibility Principle that applies here. The Single Responsibility Principle states:

that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.

There are many possible functions in main():
- Process the command line arguments
- Process the states
- An inserter function rather than a lambda declaration
- A report function rather than a lambda declaration
- Print the output

The declarations for the stats_t struct, and the enums event_t and state_t should be moved out of main().

\$\endgroup\$
7
\$\begingroup\$

You’ll often hear Haskel programmers talk about making invalid states impossible to express. The Rust community has taken this to heart and developed a state machine pattern that uses structs and traits rather than enums.

This pattern has many benefits, but to quote some of the main ones from the article:

  • Transition errors are caught at compile time! For example you can't even create a Filling state accidentally without first starting with a Waiting state. (You could on purpose, but this is beside the matter.)
  • Transition enforcement happens everywhere.
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for the link on statemachines! it's something I'd be comfortable doing in other languages but this way of handling it in rust is very nice. \$\endgroup\$ – QuantumChris Nov 11 at 12:29

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.