Rust入門３日目のけーさんです．
Rustを使ってスタックを実装したいとき， 再帰的データ構造を意識すれば，次のようにスタックを実装できると思います．
struct Stack<T> {
head: Option<Box<Node<T>>>
}
struct Node<T> {
elem: T,
next: Option<Box<Node<T>>>
}
impl<T> Stack<T> {
pub fn new() -> Self {
Stack { head: None }
}
pub fn pop(&mut self) -> Option<T> {
// ...省略
}
pub fn push(&mut self, e: T) {
// ...省略
}
}
このStack<T>はもちろんちゃんと次のテストが通ります．
（そのようにpush, popを実装します）
let mut stack = Stack::new();
assert_eq!(stack.pop(), None);
stack.push(123);
assert_eq!(stack.pop(), Some(123));
stack.push(1);
stack.push(2);
stack.push(3);
assert_eq!(stack.pop(), Some(3));
assert_eq!(stack.pop(), Some(2));
assert_eq!(stack.pop(), Some(1));
assert_eq!(stack.pop(), None);
しかし，次のコードはfatal runtime error: stack overflowでプログラムが異常終了してしまいます．
let mut stack = Stack::new();
for i in 0..20_000 {
stack.push(i)
}
たったこれだけのコードで，このStackの何がいけないのでしょうか？
結論からいえば，タイトルにもある通りデストラクタが原因です．
この場合はstackのデストラクタの呼び出しを皮切りに，再帰的にNodeのデストラクタが呼び出されることでスタックオーバーフローになります．
もう少し噛み砕くと，まずstackのデストラクタが行われますが，stackのデストラクタの内部ではstack.headのデストラクタが行われます．
同様にstack.headのデストラクタではstack.head.elemとstack.head.nextがデストラクタが実行されますが，stack.head.next.nextも．．．というように再帰的にデストラクタが実行されるのです．
この問題はStackに数個要素を追加するだけでは発生しませんが，しかし2万個程度要素があるだけでデストラクタはスタック領域を食いつぶしてしまうのです．
僕がこの問題に直面したとき，なぜスタックオーバーフローとなっているのか全く理解が出来ませんでした．
この問題に気づきにくい原因は２つあると思います．
特に2つ目が主な原因だと思います． C++やD言語でもそうですが，構造体のデストラクタはコンパイラが自動的に生成してくれるので，プログラマがわざわざ自分で書く必要がない場合が多いと思います．
しかし，再帰的なデータ構造ではこのデフォルトのデストラクタが悪さをしてプログラムをスタックオーバーフローへと導きます．
この問題はRustのみの問題ではなく，C++でも同様に起こります．
template <typename T>
struct StackNode {
StackNode(T e, std::unique_ptr<StackNode<T>> && n)
: elem(e), next(std::move(n)) {}
T elem;
std::unique_ptr<StackNode<T>> next;
};
template <typename T>
struct Stack {
std::unique_ptr<StackNode<T>> head;
void push(T elem) { /* ...*/ }
};
int main() {
Stack<int> stack{};
for(int i = 0; i < 1000000; ++i) {
stack.push(i);
}
}
自分でちゃんとデストラクタ，つまりRustではDropトレイトのdropを実装すれば問題は起こりません．
impl<T> Drop for List<T> {
fn drop(&mut self) {
let mut node = mem::replace(&mut self.head, None);
while let Some(x) = node {
node = x.next;
}
}
}
C++でも同じです．
template <typename T>
Stack<T>::~Stack()
{
while(head) {
auto h = std::move(head);
head = std::move(h->next);
}
}
この記事は、TUT Advent Calendarの22日目の記事であり、さらにD言語 Advent Calendarの23日目の記事です。
私は某国立大学の大学院の電気・電子情報系学科に所属していて、来年からは博士課程に進学する予定です。 研究の分野は無線通信で、特に「全二重通信」と呼ばれる次世代の無線通信方式についてディジタル信号処理の観点から研究しています。
今回の記事では、私が今年一年間で研究室にてD言語で作った成果について紹介します。
無現在のディジタル線通信は数百MHzから数GHz以上の周波数の電波を使用します。 この電波に載せる信号をシミュレーションするソフトウェアをベースバンド信号シミュレータといいます。 オープンソースのベースバンド信号シミュレータ系ライブラリのといえば、GNU RadioやIT++が有名だと思います。 しかし、GNU Radioは拡張性が良いとは言えず、IT++はここ数年全く保守されていません。 あと、GNU RadioはPythonかC++で、IT++はC++で記述できますが、やっぱりD言語で研究したいです。 ということで、ベースバンド信号シミュレータ系ライブラリをD言語で作りました。 論文の関係上まだGitHubにはソースコードを上げていませんが、現在IEEE Trans. on Wireless Communicationsに出している論文がAcceptされ次第ソースコードの公開をします。 ちなみに、このライブラリを使用してシミュレーションした結果は2017年3月にサンフランシスコで開催された国際会議IEEE WCNC (Wireless Communications and Networking Conference)にて発表しました。 そのときの会議論文はこちら（ちゃんと論文中にシミュレータがD言語製であると記述しています！）。
こちらも無線通信関係です。 USRPというソフトウェア無線用RFフロントエンド用のD言語ライブラリを作りました。 ソフトウェア無線とは、ソフトウェアによってベースバンド信号処理を行い、その信号を電波に載せたり、逆に電波をベースバンド信号に変換しソフトウェアで受信処理を行う無線機です。 USRPはソフトウェアによって作られたベースバンド信号を電波に載せたり、電波からベースバンド信号に変換する装置で、一つ20万円から100万円くらいします。 USRPはGNU RadioやUHDというC++用のライブラリを用いて制御でき、実際に弊研究室では従来までこれらを利用してC++で書かれたソフトウェアでベースバンド信号を生成したり、受信処理を記述していましたが、コードが煩雑になってしまってました。
やっぱりD言語でソフトウェア無線できると嬉しいので、研究の合間にちまちまコードを書いていました。 このライブラリでは、UHDが公開しているC言語用APIを利用して、UHDよりも扱いやすいように作っています。 このライブラリはすでにGitHubにて公開しています。
また、このライブラリを用いて実際にUSRPを3台制御するデモを2017年11月29,30日、12月1日の3日間開催されたマイクロウェーブ展にて展示してきました。 当日の様子はこんな感じです。
実機の展示はこんな感じです。D言語で書かれたソフトウェアで信号処理をして無線機から高周波信号を出しています #dlang pic.twitter.com/LhyuYYm0L4
— けーさん@緊急復活 (@k3k0ma) 2017年11月29日
豊橋技術科学大学には10コアのXeonが二つ載ったノードが30ノード繋がったクラスタ計算機が設置されており、学生が研究や学習用途に自由に利用することができます。 私も最近ではシミュレーション条件をたくさん振ったり、乱数のシードを変えて試行回数をたくさん稼いでシミュレーションをしているので、どうしてもクラスタ計算機のようなHPC環境がないとシミュレーション時間がかかってしまいます。
しかし、クラスタ計算機のジョブスケジューラにジョブを投げるために投入用スクリプトを書かないといけないのが少しめんどくさいです。 たとえば、変数tを1から100まで変えてプログラムprogを走らせるジョブの投入スクリプトは次のような感じになります。
#PBS -l nodes=1:ppn=1
#PBS -t 1-100
#PBS -q wLrchq
cd $PBS_O_WORKDIR
./prog ${PBS_ARRAYID}
このように、ジョブスケジューラの機能だけだと、イテレートする変数が整数一つだけで、たとえばforeach(e1; param1) foreach(e2; param2) {...}のように複数パラメータを総当りしてシミュレーションすることも簡単にはできません。
また、同じソースコードで、手元のPC上ではCPU個数分だけ並列動作し、クラスタ計算機では複数ノードで並列処理されるようなコードを書くのも困難でしょう。
私が作ったクラスタ計算機用ジョブ投入ライブラリでは、以下のような感じで簡単にD言語からジョブ投入できます。
import std.stdio;
import tuthpc.taskqueue;
void main()
{
JobEnvironment env;
auto list = new MultiTaskList();
// 2変数を総当りして256個のジョブ生成
foreach(i; 0 .. 16)
foreach(j; 0 .. 16)
list.append!writefln("Hello, TUTHPCLib4D! %s", i);
// クラスタ計算機で動かすとジョブ投入、それ以外では並列実行
run(list, env);
}
実行もパッケージマネージャdubを使えばdubだけで、ローカルでもクラスタ計算機でも動きます。
また、クラスタ計算機上のN個のノードで各M個のコアを専有したい場合にはdub -- --th:g=M --th:m=Nと実行すればその通りにジョブ投入されます。
また、C言語から扱う場合やC++から扱う場合のサンプルコードもリポジトリに添付しています。 このライブラリはわりと便利で実用的なので技科大生でクラスタ計算機利用している人にはおすすめです。
振り返ってみると、2017年はわりといろいろと作ってた感じでした。 来年にはこの記事の最初に紹介したシミュレータ用のライブラリも公開できると思いますので、そのときにはまた記事を書きたいと思います。
突然今週初めに，研究のソースコードを管理しているGitリポジトリが壊れてしまったので， 一部始終をまとめておきます．
dubで提供されているロックフリーなパッケージlock-freeのベンチマークを取ってみました．
前のリポジトリが非常に扱いづらかったので新しく移行しました．
タイトルの通り，使おうとしたらハマったので書いておきます．