rustdes

Rust で discrete-event simulation (DES) のフレームワークを実装します。フレームワークの名前は、とりあえず安直ですが rustdes にしました。このスクラップには実装を進めるにあたって考えたことや学んだことを記録します。

私は単純に Rust に興味を持ち言語学習のためにこのライブラリを実装します。初めて Rust を使用するので、このライブラリのコードを使用される際は、その点にご留意ください。

なお Python には SimPy という使い勝手のよい DES フレームワークが存在しますし、Rust には、その SimPy にインスパイアされた desim が存在します。

rustdes is a simple framework for modeling discrete-event simulation with Rust, representing the following processes:

• Wait for an event to occur
• Schedule an event to occur
• Interrupt a process (should be carefully considered for necessity and expression)

Framework Components

rustdes consists of following elements:

• Environment, 時刻とイベントを管理する
• Event, 他のイベントと区別できるだけの情報を保持する
  • TimeOut, 時刻を保持するイベント
  • Condition, 複数のイベントを表すイベント
  • Process, 処理とその起点となるイベントを保持するイベント
• State, プロセスが変化させる値

Environment

Event

TimeOut

Condition

Process

State

Learn from SimPy

SimPy の docs を読んで、rustdes の設計に生かそうと思います。

Basic Concept

SimPy is a discrete-event simulation library. The behavior of active components (like vehicles, customers or messages) is modeled with processes. All processes live in an environment. They interact with the environment and with each other via events.

SimPy の process-oriented な DES のモデリングは成功していると思います。process が event を介して environment や 他の process と作用します。

SimPy の良さを説明しているエントリを紹介します。私もこのエントリと同じ意見です。

https://qiita.com/j54854/items/687f8842be1d3e212384

プロセスに処理の流れを書いていく際に，ある事象の生起を待つ，あるいは生起する事象やその結果に応じて処理を分岐させる，といったことを直感的に記述することができる．これによって，処理を事象とは別の切り口でモジュール化しやすくなる

DES をモデリングするときに、イベントにプロセスを結びつけるよりも、プロセスにイベントを記述する方が直感的だと思います。

process-oriented な表現ができるようにします。

Processes are described by simple Python generators. You can call them process function or process method, depending on whether it is a normal function or method of a class. During their lifetime, they create events and yield them in order to wait for them to be triggered.

SimPy の表現力は Python の generators によるところが大きいです。Rust の generators は unstable なので、generators を使用している desim は nightly でないとコンパイルできません。

rustdes は stable にしたいので generators を使用せず明示的に callback を記述します。

Learn from SimPy

Event basics

Events can be in one of the following states. An event

• might happen (not triggered),
• is going to happen (triggered) or
• has happened (processed).

They traverse these states exactly once in that order. Events are also tightly bound to time and time causes events to advance their state.

イベントの状態遷移はそのまま使えそうです。

As long as the event is not processed, you can add callbacks to an event. Callbacks are callables that accept an event as parameter and are stored in the Event.callbacks list.

Environment は自身の priority queue に Event を所有します。Rust の ownership rule は厳格なので、Environment 以外は Event の &mut を使えません。したがって、他のコンポーネントが Event.callbacks に callbacks を追加できません。

そこで rustdes は イベントの検索条件と操作を指定して、条件を満たすすべてのイベントの状態を変更するアプローチを採ろうと思っています。イベントの検索条件は Event の値とは別の値なので ownership rule に抵触しません。SimPy のように Event の状態を変更するためにそのインスタンスを見つけてくるよりも柔軟な表現ができるのではないかと思います。

Events also have a value. The value can be set before or when the event is triggered and can be retrieved via Event.value or, within a process, by yielding the event (value = yield event).

便利な仕様なので実現したい。

Let time pass by: the Timeout

To actually let time pass in a simulation, there is the timeout event. A timeout has two parameters: a delay and an optional value: Timeout(delay, value=None). It triggers itself during its creation and schedules itself at now + delay. Thus, the succeed() and fail() methods cannot be called again and you have to pass the event value to it when you create the timeout.

ここは踏襲する。

Waiting for multiple events at once

SimPy therefore offers the AnyOf and AllOf events which both are a Condition event.
Both take a list of events as an argument and are triggered when any (at least one) or all of them are triggered.

SimPy では Condition という Event を使って複数のイベントを待つ処理を表現します。rustdes でもイベントの検索条件を使って複数のイベントを待つ処理を表現できます。

Learn from SimPy

Process Interaction

Waiting for a Process

a SimPy Process can be used like an event (technically, a process actually is an event)

SimPy の "Process is an Event" であることが、さらに SimPy の表現力を豊かにしています。

Rust では is-a relationship を表現できないですが、プロセスをイベントのように扱えるようにします。JavaScript の Promise のような表現を想定しています。

Interrupting Another Process

Interrupts are thrown into process functions as Interrupt exceptions that can (should) be handled by the interrupted process.

SimPy では Process 内で Interrupt exception を発生させることで、そのプロセスを interrupt できます。例外を使うことで Process 内では except block に interrupt された場合の処理を記述できます。

State

State は DES 実行中に変化する値です。イベント発生時にのみ State が変化するので、State は 時間 t に対する Step Function になります。State の変化はプロセスとして記述します。

プロセスは State を変化させるので、プロセスはその State の &mut を借用する必要があります。さらに、どの State の &mut を渡せばよいかはプロセスによって異なるため自明ではありません。幸い DES は常に一つのプロセスだけを execute するので、その都度すべての State の &mut を渡せばよいと考えています。

Ownership rules を守りやすいアーキテクチャにする

Rust のコードを書いていると、Ownership rules について真剣に考えておかないと、全くコンパイルが通らないことに気づきました。すべての値の Owner を一意に決められるアーキテクチャがあればいいのですが、ないかもしれないし思いつかないかもしれません。かといって闇雲に実装するわけにはいかないようです。

長寿な値

Lifetime が大きい値から考えてみることにしました。
まず、Environment が最も長生きする（ほとんど 'static である）ことは自明だと思います。したがって、Ownership Tree の Root は Environment が適任です。

State の Owner は Component になるでしょう。使わなくなった Component があれば、付随する State を観測する必要はないでしょう。使わない Component は drop できないといけないです。

Component と Event の関係はよく考える必要がありそうです。
コンポーネントは少なくとも自分に関係するイベントを知っているはずです。多くの他のコンポーネントに関係するイベントは知らないかもしれませんが、他のコンポーネントが schedule するイベントに起因する状態変化があるでしょうし、あるいは他のコンポーネントに関係するイベントを schedule することもあるでしょう。

プロセスをどうやって記述できるとよいか

一般的にイベントには生起する時刻とプロセスが定義されています。DES は繰り返し priority queue からイベントを取り出してプロセスを実行します。このときプロセスはコンポーネントの状態を変化させます。あるプロセスが実行されている間は、他のプロセスが実行されることはありません。そう考えると、Rust の Ownership rule と相性がよさそうです。プロセスがすべての Component の &mut を借用しても大丈夫です。あるいは、一時的にすべての Component を預かっても大丈夫そうです。

プロセスを実行中に新しいイベントをスケジュールできます。このとき、誰がイベントのプロセスを定義するとよいか考えたいです。シミュレーションを実装する人は、Object-Oriented に考えたいと思うので、プロセスの定義はコンポーネントに書き分けられるとよいです。

1. プロセスに Fn trait boundary を課す
2. Component に Process trait boundary を課す

プロセスに Fn trait boundary を課す

素直な実装だと思います。ただ、Component の生存期間がプロセスよりも長いことを明示する方法が分からないです。プロセスは Environment の priority queue が所有していて、その生存期間はほとんど Environment と同じくらい長いです。一方で、Component はいつ drop されてもおかしくありません。

プロセスに Component を渡せてしまえばいいのですが、他のプロセスと干渉しないと想定するのは非現実的です。この場合は、何らかの方法で動的に Component を渡すことになると思います。

Component に Process trait boundary を課す

少し考え方を変えて Component そのものがプロセスを持っているようにします。Environment は起したイベントをプロセスに渡します。つまり Component は Process trait を実装している必要があります。一度生起したイベントは破棄されるだけなので、このタイミングでプロセスにイベントの所有権を渡してしまって大丈夫です。
この場合、Environment が Event の Owner になると思いますが、Environment は priority queue なので自然だと思います。

Event の伝搬

Component に Process trait boundary を課す場合は、Environment は生起した Event を process 関数に渡します。このとき、どの Component の process 関数に Event を渡すようにするか決めたいです。

1. イベントにコンポーネントの参照を含める
2. すべてのコンポーネントに イベントを渡す
3. イベントを pub/sub する

ライブラリの仕様にも影響があると思います。

• 誰がイベントを使うコンポーネントを決めるか
• 生起したイベントを使うことができるコンポーネントの数はいくつか

イベントにコンポーネントの参照を含める

イベントをスケジュールするときに、そのイベントを使うコンポーネントを決めます。そのコンポーネントは生起したイベントを使う唯一のコンポーネントになります。

Event は Component を一意に特定できる値を持つように実装すると思います。なぜなら Event が &Component を持つと、他の Component が &mut Component を持てなくなるためです。あるいは Rc<Component> でもいいのかもしれません。

すべてのコンポーネントにイベントを渡す

任意のコンポーネントが任意のイベントを使うことができます。したがって、DES を柔軟に記述できると思います。しかしながら、実際にはほとんどのイベントは無視されるだけなので、コンポーネントが多くなると無駄な処理が目立ちそうです。

Event を pub/sub する

すべてのコンポーネントにイベントを渡すとスケールしない可能性があるので、あらかじめコンポーネントは興味のある Event を購読するようにします。こうすることで、任意のコンポーネントが任意のイベントを使うことができます。

channel

Environment を実装してみる

ぼんやりと仕様が決まってきたので、とりあえず実装してみようと思います。コンパイルできなくなってきたら、また考え直そうと思います。

ScheduledEvent<E>

ScheduledEvent<E> は Environment の priority queue に格納される値の型です。イベントが生起される時刻とイベントの実体から構成されます。

use std::time::Duration;
struct ScheduledEvent<E> {
    time: Duration,
    event: E,
}

イベントの実体は表現したい DES によって異なるので、ジェネリクスにしました。将来的には E にいくつかの trait boundary を課すかもしれません。

priority queue

priority queue を BinaryHeap で実装しました。BinaryHeap は max-heap なので、std::cmp::Reverse で ScheduledEvent<E> を wrap しました。

use std::collections::BinaryHeap;
use std::cmp::Reverse;
pub struct Environment<E> {
    event_queue: BinaryHeap<Reverse<ScheduledEvent<E>>>,
}

impl<E> Environment<E> {
    pub fn new() -> Self {
        Environment { event_queue: BinaryHeap::new() }
    }

    pub fn schedule(&mut self, event: E, time: Duration) {
        self.event_queue.push(Reverse(ScheduledEvent{ time, event }))
    }

    pub fn step(&mut self) -> Option<Duration> {
        self.event_queue.pop().map(|Reverse(triggered)| triggered.time )
    }
}

Option<Reserve<Duration>> から .map(|Reverse(triggered)| triggered.time ) で Option<Duration> を返す表現は、Rust らしさだと思いました。

ただ、これだけではコンパイルできません、BinaryHeap に格納する値は　Ord trait を実装する必要があります。Ord trait を実装するためには PartialEq,Eq, PartialOrdのすべてを実装する必要があります。

impl<E> PartialEq for ScheduledEvent<E> {
    fn eq(&self, other: &Self) -> bool {
        self.time.eq(&other.time)
    }
}

impl<E> Eq for ScheduledEvent<E> {}

use std::cmp::Ordering;
impl<E> PartialOrd for ScheduledEvent<E> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.time.cmp(&other.time))
    }
}

impl<E> Ord for ScheduledEvent<E> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.time.cmp(&other.time)
    }
}

derive macro は generics に対しては使えないようでした。もしかしたら generic-derive あたりを見ると何か分かるのかもしれないです。

時刻

Environment に時刻に関する処理を追加しました。

pub struct Environment<E> {
+   time: Duration,
    event_queue: BinaryHeap<Reverse<ScheduledEvent<E>>>,
}

impl<E> Environment<E> {
    pub fn new() -> Self {
        Environment { 
+           time: Duration::default(),
            event_queue: BinaryHeap::default()
        }
    }
+    pub fn now(self) -> Duration {
+        self.time
+    }

step 実行時に新しいイベントの時刻に進みます。

impl<E> Environment<E> {
    pub fn step(&mut self) -> Result<E, String> {
        let Reverse(triggered) =
            self.event_queue.pop()
                .ok_or("No events.".to_owned())?;

        self.time = triggered.time;
        Ok(triggered.event)
    }

このとき、時刻が巻き戻ってはいけないですが、それはスケジュールのときにチェックしようと思います。

impl<E> Environment<E> {
    pub fn schedule<T: Into<E>>(&mut self, time: Duration, event: T) -> Result<(), String> {
        if time >= self.time {
            self.event_queue.push(Reverse(ScheduledEvent{ time, event: event.into() }));
            Ok(())
        } else {
            Err("".to_owned())
        }
    }

or_fun_call

ok_or() を書くと ok_or_else() の方がベターだよ、と clippy に指摘されました。

-  .ok_or("No events.".to_owned())?;
+  .ok_or_else(||"No events.".to_owned())?;

ok_or() の場合は、いつでも引数部分が評価されその分の実行コストがあるが、ok_or_else() の場合は、else に落ちた時だけ実行されるからだと思います。今回の例では String をヒープに確保する処理がたいていの場合に無駄になります。可読性のために簡潔な表現を優先してもいい場面かなとも思いますが。

https://rust-lang.github.io/rust-clippy/master/index.html#or_fun_call

同じ時刻に生起するイベントをどう扱うか

全く同じ時刻に二つのイベントがスケジュールされることがある。ライブラリの使用者は次のいずれかを期待するのではないかと考える。

1. FIFO（先にスケジュールされたイベントが先に生起する。）
2. ランダム

ランダムの場合は DES の結果が安定しない（実行するたびに変わる）。DES は状態変化が予測可能なところにメリットを見出すこともできるので今回は FIFO を採用する。

同じ priority の値を取り出す順序は BinaryHeap の実装に依存する

Rust の std::collections::BinaryHeap は priority が等しい値が二つ以上あったとき、それらを取り出す順序を定義しない。

例えば、value を priority とする次のような構造体 Element を BinaryHeap に追加することを考える。

        #[derive(PartialEq, Eq, Debug)]
        struct Element { value: usize, id: usize }

        impl PartialOrd for Element {
            fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
               self.value.partial_cmp(&other.value)
            }
        }

        impl Ord for Element {
            fn cmp(&self, other: &Self) -> Ordering {
                self.value.cmp(&other.value)
            }
        }

実際に取り出して試してみる。この例だけだと FIFO になっていると錯覚するかもしれない。

        let mut queue = std::collections::BinaryHeap::new();
        queue.push(Element { value: 1, id: 1 });
        queue.push(Element { value: 1, id: 2 });
        queue.push(Element { value: 1, id: 3 });

        assert_eq!(Some(Element { value: 1, id: 1 }), queue.pop());
        assert_eq!(Some(Element { value: 1, id: 2 }), queue.pop());
        assert_eq!(Some(Element { value: 1, id: 3 }), queue.pop());

次の例では、2番目に取り出される値が三番目に追加した値であり、少なくとも FIFO ではないと分かる。

        let mut queue = std::collections::BinaryHeap::new();
        queue.push(Element { value: 1, id: 1 });
        queue.push(Element { value: 1, id: 2 });
        queue.push(Element { value: 1, id: 3 });
        queue.push(Element { value: 1, id: 4 });

        assert_eq!(Some(Element { value: 1, id: 1 }), queue.pop());
        assert_eq!(Some(Element { value: 1, id: 3 }), queue.pop());
        assert_eq!(Some(Element { value: 1, id: 2 }), queue.pop());
        assert_eq!(Some(Element { value: 1, id: 4 }), queue.pop());

さらに追加すると、なんとなく規則性がありそうな順序で取り出されることが分かる。

        let mut queue = std::collections::BinaryHeap::new();
        queue.push(Element { value: 1, id: 1 });
        queue.push(Element { value: 1, id: 2 });
        queue.push(Element { value: 1, id: 3 });
        queue.push(Element { value: 1, id: 4 });
        queue.push(Element { value: 1, id: 5 });

        assert_eq!(Some(Element { value: 1, id: 1 }), queue.pop());
        assert_eq!(Some(Element { value: 1, id: 3 }), queue.pop());
        assert_eq!(Some(Element { value: 1, id: 5 }), queue.pop());
        assert_eq!(Some(Element { value: 1, id: 2 }), queue.pop());
        assert_eq!(Some(Element { value: 1, id: 4 }), queue.pop());

この順序は BinaryHeap の実装に依存していて、なにかランダムに決まっているわけではなく何度実行しても再現するはずだ。このまま実験を繰り返して BinaryHeap の実装を類推する遊びも楽しいかもしれない。

無限にインクリメントするカウンター

挿入順を代入するために、無限にインクリメントできる Iterator が欲しくなる。
Rust で Iterator trait を実装するときは associated type を定義する必要があるくらいで、とくに難しいことはない。

/// iterator which counts from 0 to usize::MAX
pub struct Counter {
    count: usize,
}

impl Counter {
    pub fn new() -> Counter {
        Counter { count: 0 }
    }
}

impl Iterator for Counter {
    type Item = usize;

    fn next(&mut self) -> Option<usize> {
        if self.count < usize::MAX {
            self.count += 1;
            Some(self.count)
        } else {
            None
        }
    }
}

どちらかというと Iterator を受け取る時に少しばかり面倒になる。いくつか受け取る方法があると思っている。

1. Concrete Type
2. Generics Type
3. Trait Object

Concrete Type

Concrete Type という言い方をするのか自信がないのだが、この場合 Counter として受け取る。

pub struct Environment<E: Eq> {
    time: Duration,
    counter: Counter,
    event_queue: std::collections::BinaryHeap<Reverse<ScheduledEvent<E>>>,
}

ここでは Iterator<usize> の実装を知る必要がないのに、Counter を要求するのは過度に詳細すぎる気もする。

Generics Type

適切な抽象化ができるのは Generics Type を使う場合だと思う。

pub struct Environment<E: Eq, I: Iterator<usize>> {
    time: Duration,
    counter: I,
    event_queue: std::collections::BinaryHeap<Reverse<ScheduledEvent<E>>>,
}

とはいっても、Environment.counter は private なプロパティであり、実装を差し替えて使うこともないので抽象化する意味がないと考えた。

Trait Object

もちろん Trait Object を使って書くこともできる。

pub struct Environment<E: Eq> {
    time: Duration,
    counter: Box<dyn impl Iterator<usize>>,
    event_queue: std::collections::BinaryHeap<Reverse<ScheduledEvent<E>>>,
}

実現できることは Generics Type と同様だと思うが、動的ディスパッチになるのでビルドサイズは Iterator<usize> の数に依らず小さくできる。ここでは、多様な Iterator<usize> を受け取ることを期待しないのでメリットはないのではないかと思う。