はじめに
現在、rustレベルを上げるため、アルゴリズムクイックリファレンスを実装していますが、
rustからqsortを使用した場合と比較したく思い、rustからC関数をコールしてみました。
参考
環境
- MacBook Pro (Retina, 15-inch, Mid 2015)
- 2.8 GHz Intel Core i7
- Memory 16GB
- AMD Radeon R9 M370X 2048 MBIntel Iris Pro 1536 MB
- rustc v.1.19.0
実装
Cの型情報が定義されているlibc crateを追加します。
[dependencies]
rand = "*"
libc = "*"
以下、C関数「qsort」をコールする為の実装です。
extern crate libc;
use std::cmp::Ordering;
use libc::{size_t, c_void, c_int};
// libcライブラリをリンク.
# [link(name = "c")]
extern {
fn qsort(data: *mut c_void,
num: size_t,
size: size_t,
comp: extern fn(*const c_void, *const c_void) -> c_int);
}
// qsortコールバック関数.
extern fn _compare<T: Ord>(a: *const T, b: *const T) -> c_int {
match unsafe { (*a).cmp(&*b) } {
Ordering::Less => -1,
Ordering::Greater => 1,
Ordering::Equal => 0
}
}
// qsortラッパー.
fn c_qsort<T: Ord>(data: &mut [T]) {
// transmuteでキャスト.
let _ptr: extern fn(*const c_void, *const c_void) -> c_int
= unsafe { std::mem::transmute(_compare::<T> as (extern fn(*const T, *const T) -> c_int)) };
unsafe {
qsort(data.as_mut_ptr() as *mut c_void,
data.len() as size_t,
std::mem::size_of::<T>() as size_t,
_ptr);
}
}
説明
linkアトリビュートで、libcをリンクするよう指定します（ダブルクォーテーションの中にライブラリ名を記載。libを除いた名前で）。
externブロックの中で、C言語のシグネチャに対応した関数を定義します。
今回の場合、qsort関数とその引数に指定するコールバック関数を定義しています。
qlibcクレートで定義されている型名を使用し、関数シグネチャを定義しています。
(c_voidやc_intを使用して定義します。詳しくはこちら)
また、C言語（他言語）の関数をコールする際は、unsafeな扱いになるのでunsafeブロックで囲います。
（コンパイラに、このブロックの中のコードが安全であることを通知する）
まとめ
コールバック関数の型をキャストする部分(transmuteを使用している部分）で苦戦しました。
asキーワードを使用して明示的に型を指定しないと、コンパイルが通らないようです。
それ以外に関しては、参考サイトを閲覧しながらなんとか実装できました。
Cで作成されたライブラリは世の中に数多く存在していると思いますし、また他言語の関数に対しても同様に呼び出すことができる（他言語からrustも可)ようなので、色々と試していきたいと思います。
補足
qsortで10,000要素をソートした処理時間とstd::vec::Vec::sortでソートした処理時間を比較したところ、qsortの処理時間の方が遅かったです。
予想では、C言語であるqsortのほうが早いのかなと思っていたので、C言語プログラムからqsortをコールし、同じく10,000要素をソートしてみました。
使用したビルドコマンドなどは以下の通り。
$ gcc -v
Apple LLVM version 8.1.0 (clang-802.0.42)
$ gcc -Ofast -march=native main.c
以下、計測結果です。
| ソート種類 | 処理時間 |
|---|---|
| qsort(rust) | 0.000880520sec |
| qsort(C) | 0.000799000sec |
| vec::sort | 0.000386862sec |
rustから呼び出したqsortが遅いのではなく、そもそものqsortが遅いようです。
暇があれば、どのようなソートアルゴリズムで実装されているか見てみようかと思います。
2017/08/03追記
C言語「qsort」が思いのほか、遅かったので少し調べてみたところ、以下のサイトを見つけました。
C の qsort と STL の sort の速度比較
なるほど、インライン展開が効いていないので速度が遅かったのかと納得（アセンブラ等を見て、自分で検証はしていませんが）。
確かに昔、組込系の開発でインライン展開による最適化を実施したことを思い出しました。。。