llrlのパフォーマンス

パフォーマンスはあまり意識していないが、コンパイラ自身(標準ライブラリとあわせて20k LOC程度)を25sほどでコンパイルできたり、HashMap/OrdMap のベンチマークがある程度の時間で終わるなど、最低限の速度では動作する。

code:rust

use std::collections::HashMap;

use std::collections::BTreeMap;

fn main() {

let size = 10000000;

let mut map = HashMap::new();

for i in 0..size { map.insert(i, i * 2); }

for i in 0..size { map.remove(&i); }

let mut map = BTreeMap::new();

for i in 0..size { map.insert(i, i * 2); }

for i in 0..size { map.remove(&i); }

}

code:llrl.lisp

(import "std/hash-map" _)

(import "std/ord-map" _)

(function size 10000000)

(let1 map hash-map/empty

(for (let i) (iterator/range 0 size 1) (hash-map/insert! i (* i 2) map))

(for (let i) (iterator/range 0 size 1) (hash-map/remove! i map)))

(let1 map ord-map/empty

(for (let i) (iterator/range 0 size 1) (ord-map/insert! i (* i 2) map))

(for (let i) (iterator/range 0 size 1) (ord-map/remove! i map)))

table:ベンチマーク

言語 データ構造 時間

Rust ハッシュテーブル (SwissTable) 2.971sec

Rust B木 1.166sec

llrl ハッシュテーブル (Robin Hood Hashing) 5.880sec

llrl B木 4.595sec

ところで、llrlと関係ないが、このように単純なキーだと (おそらくハッシュ関数のオーバーヘッドのため?) OrdMap(B木)の方が高速に動作しているというのも注目したい。