scheme.rs

ちょいとevalに改造を加えて、入口と出口でS式を表示するようにしてみた。gitから落したやつは、整形されていなかったので、整形してからの修整。

--- /home/sakae/scheme.rs/src/evaluator.rs      2022-02-03 06:57:22.370245952 +0900
+++ src/evaluator.rs    2022-02-03 07:10:46.490399558 +0900
@@ -31,14 +31,17 @@
 pub fn eval(sexpr_: &SExpr, env_: &EnvRef) -> SResult<SExpr> {
     let mut sexpr = sexpr_.clone();
     let mut env = env_.clone_ref();
-
+    println!("==> {}", sexpr);
     loop {
         match sexpr {
             SExpr::Atom(Token::Symbol(x)) => return env.get(&x),
             x @ SExpr::Atom(_)
             | x @ SExpr::Procedure(_)
             | x @ SExpr::Port(_)
-            | x @ SExpr::Unspecified => return Ok(x),
+            | x @ SExpr::Unspecified => {
+                println!("<== {}", x);
+                return Ok(x);
+            }
             list @ SExpr::DottedList(_, _) => {
                 fn flatten(list: SExpr) -> SExprs {
                     match list {
@@ -96,7 +99,10 @@

                         match procedure {
                             SExpr::Procedure(proc) => match proc {
-                                ProcedureData::Primitive(x) => return x.apply(args),
+                                ProcedureData::Primitive(x) => {
+                                    println!("<== {}", &symbol);
+                                    return x.apply(args);
+                                }
                                 ProcedureData::Compound(x) => {
                                     env = x.build_env(args)?;
                                     sexpr = *x.body;

複数の場所から return で抜けているけど、全部は網羅していないと言う、中途半端版です。

scheme.rs> (+ 123 456)
==> (+ 123 456)
<== +
==> 123
<== 123
==> 456
<== 456
$0 = 579

プロンプトが出て来るまでに、かなり沢山のS式が評価されてる。これは嬉しい？副作用かな。 これらは、どこに定義されてる？ ざっと見scmファイルなんて無かったぞ。

調べたら、いかにもって所に有った。primitives/prelude.rs

pub const PRELUDE: &'static str = "
;; some functions are from:
;; https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours/Towards_a_Standard_Library

(define (id x) x)
  :
(define (call-with-input-file str proc)
  (define f (open-input-file str))
  (proc f)
  (close-port f))
";

よくやる手であります。

しょうがないので、consを外側から観察。cons一発に対してmallocを律儀に実行してるのではなかろうか。mallocのカーネル側挙動ったら、K&RのC言語教本に載ってたあれだか。 ならば、straceしてみよう。

sakae@deb:/tmp/scheme.rs/target/release$ strace -o LOG ./scheme-rs ever.scm

何となくリナで動かしていたんでstraceです。 ログを眺めてみる。

278write(1, "1000", 4)                     = 4
279write(1, "\n", 1)                       = 1
280brk(0xf4d000)                           = 0xf4d000
281brk(0xf22000)                           = 0xf22000
282brk(0xf4d000)                           = 0xf4d000
 :
851mmap2(NULL, 266240, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0     ) = 0xb7bc9000
852munmap(0xb7bc9000, 266240)              = 0
 :
942brk(0xf37000)                           = 0xf37000
943brk(0xf77000)                           = 0xf77000
944write(1, "2000", 4)                     = 4
945write(1, "\n", 1)                       = 1

冒頭につけた数字は、行番号。これを見ると、完全にcons一発についてシステムコールのbrkが発行されてる訳ではないけど、高頻度でカーネルを呼び出している亊が分る。加えて、mmap2とかも割り込んでいるし。これじゃ、重いわけだ。

ちなみに、brkってのは、

SYNOPSIS
       #include <unistd.h>

       int brk(void *addr);

       brk()  sets the end of the data segment to the value specified by addr,
       when that value is reasonable, the system has enough  memory,  and  the
       process does not exceed its maximum data size (see setrlimit(2)).

ログをbrkで検索してくと、最初はbrk(NULL)を渡して、システム側からアドレスを教えてもらっている。後は、小まめにdata segmentを増減させてる。rust側では、allocの仕業なんだろうね。

もう少しallocが利口になって、sbk発行の頻度を下げて欲しいぞ。いや、そんなのは、ユーザーの責任だろう。Box型でドーンとメモリーを確保。それをユーザーがプールしながら使い倒す。なにそれ。結局自前でGCしろってなっちゃうじゃん。すると、rustの効用が失われてしまう。

この世の中に、銀の弾 なんて、ないのさ(by 人月の神話)。

既に結論は出てるけど、BSD野郎としては、確かめずにはいられない。 target/release の中で、直接バイナリーを指定します。

ob$ ktrace -tc ./scheme-rs ever.scm
(0)
(1 0)
(2 1 0)
1000
2000
3000
^C

後は、kdumpすれば、ktrace.outをエンコードして、結果が出て来る。

73913 scheme-rs CALL  write(1,0x1f8233dd6a6,0x1)
73913 scheme-rs RET   write 1
73913 scheme-rs CALL  mmap(0,0x16000,0x3<PROT_READ|PROT_WRITE>,0x1002<MAP_PRIVATE|MAP_ANON>,-1,0)
73913 scheme-rs RET   mmap 2174107910144/0x1fa32ee0000
73913 scheme-rs CALL  mquery(0x1fa32ef6000,0x15000,0x3<PROT_READ|PROT_WRITE>,0x1012<MAP_PRIVATE|MAP_FIXED|MAP_ANON>,-1,0)
73913 scheme-rs RET   mquery 2174108000256/0x1fa32ef6000
73913 scheme-rs CALL  mmap(0x1fa32ef6000,0x15000,0x3<PROT_READ|PROT_WRITE>,0x1002<MAP_PRIVATE|MAP_ANON>,-1,0)
73913 scheme-rs RET   mmap 2174108000256/0x1fa32ef6000
73913 scheme-rs CALL  munmap(0x1faf44cb000,0x2b000)
73913 scheme-rs RET   munmap 0

こんな感じにmmapが使われているようだ。ざっと見、cons一発にmmapがもろに対応してる風だ。これじゃ、時間がかかるの、頷けるな。

いきがかり上FreeBSDでも確認した。mmapは顕著に使われていなかった。従って、グローバルに観測出来た、カーネルの呼出具合も、下記のように小さい。

42000
43000
44000
^C

real    1m1.784s
user    1m1.368s
sys     0m0.169s

それにも拘わらず、ドンドコとメモリーが消費される風でもない。上のモニターの数値表示の時間間隔が、段々と遅くなって行く。これは、何か無駄してる公算が大だ、な。

consのソースを眺めてる。なんたって、gdbで分け入っていかれないからね。

入ってすぐの所で、引数が２つ有る亊を確認しつつ、引数をx,xsに分配。 続いて、マッチ式で確認・分岐させてる。haskellを彷彿させるな。

ListとDottedListって型は分るんだけど、その他のマッチ、y って何だろう？ 考えても解らないので、コンパイラーに教えてもらおう。そう、y => SExpr::DottedList( … ) をコメントにしてあげるのさ。

error[E0004]: non-exhaustive patterns: `Atom(_)`, `Procedure(_)`, `Port(_)` and 1 more not covered
  --> src/primitives/list.rs:8:24
   |
8  |       let result = match xs {
   |                          ^^ patterns `Atom(_)`, `Procedure(_)`, `Port(_)` and 1 more not covered

ほー、そういう亊ですかい。全ての場合を尽していないとな。parser.rsに定義してある

pub type SExprs = Vec<SExpr>;

#[derive(Debug, Clone, PartialEq)]
pub enum SExpr { 16 implementations
    Atom(Token),
    List(SExprs),
    DottedList(Vec<SExpr>, Box<SExpr>),
    Procedure(ProcedureData),
    Port(PortData),
    Unspecified,
}

これを根拠に、お前は抜けてるって言ってきたんだな。

gdbが使えないって言った。そう、consでbreakした後、stepすると、すぐにconsを抜けちゃうんで、使えねー奴だなとなってたんだ。

心を入れ替えて、matchのそれぞれの分岐先にBPを置いてみた。

(gdb) info breakpoints
Num     Type           Disp Enb Address    What
1       breakpoint     keep y   0x004daf5f in scheme_rs::primitives::list::cons at src/primitives/list.rs:6
        breakpoint already hit 2 times
2       breakpoint     keep y   0x004db39c in scheme_rs::primitives::list::cons at src/primitives/list.rs:10
        breakpoint already hit 1 time
3       breakpoint     keep y   0x004db45c in scheme_rs::primitives::list::cons at src/primitives/list.rs:14
4       breakpoint     keep y   <MULTIPLE>
        breakpoint already hit 2 times

そして実行

scheme.rs> (cons 111 (list 222 333 444))

Breakpoint 1, scheme_rs::primitives::list::cons (args=...)
    at src/primitives/list.rs:6
6           let (x, xs) = args.evaled()?.own_two()?;
(gdb) c
Continuing.

Breakpoint 2, scheme_rs::primitives::list::cons (args=...)
    at src/primitives/list.rs:10
10                  xs.insert(0, x);
(gdb) n
11                  SExpr::List(xs)
(gdb) p x
$4 = scheme_rs::parser::SExpr::Atom(scheme_rs::lexer::Token::Integer(111))
(gdb) p xs
$5 = Vec(size=4) = {
  scheme_rs::parser::SExpr::Atom(scheme_rs::lexer::Token::Integer(111)),
  scheme_rs::parser::SExpr::Atom(scheme_rs::lexer::Token::Integer(222)),
  scheme_rs::parser::SExpr::Atom(scheme_rs::lexer::Token::Integer(333)),
  scheme_rs::parser::SExpr::Atom(scheme_rs::lexer::Token::Integer(444))}

xs.insert(0,x)は、xsってやつのindex番号0(すなわち先頭)にxを入れ込めって指示。11行目で、その結果をS式としてmatchの結果とせよ。

(gdb) c
Continuing.
$5 = (111 222 333 444)

で、これが、最終的な回答だ。

gdbは、matchを一つの実行単位としちゃうから、内側までは(今回のように指示しないと)入り込まないのね。よーく、挙動が分かりましたよ。

これらの状況証拠、pub type SExprs = Vec<SExpr>; と、gdbでの観察結果より、consの実体は、Vecに格納されてる奴の頭に、インサートだ。そのインサートは、先頭になされる。場所をあけてから、データを入れる亊になる。今迄有ったデータを移動。これにO(n)の時間がかかるんだな。なお、nは、リストの長さだ。

すなわち、リストが長くなればなる程、一回のconsの時間がかかるって亊だ。今迄のconsの実装とは、全く違ったものになってる。青天の霹靂だ。consはただの方便と言ったら言い過ぎ？

で、肝心のinsertの実装は、src/alloc/vec/mod.rs にある。

unsafe {
    {
        let p = self.as_mut_ptr().add(index);
        ptr::copy(p, p.offset(1), len - index);
        ptr::write(p, element);
    }
    self.set_len(len + 1);
}

時間がかかる部分はcopy(src, dst, size) て部分。場所を空けて、データを必要個数分コピー(移動)して、空いた所に新しいデータを突っ込むって動作になってる。