構造体とクラスの読み書きの速度
Common Lispの構造体とクラスはとても似ています。
一体何が違うのかというと、クラスの方が高機能であるというのは何となくわかります。
では、構造体なんていらないのでは? と思われるかもしれませんが、
CLtL2には次のような記載があります。
https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node170.html The defstruct feature is intended to provide ``the most efficient'' structure class. CLOS classes defined by defclass allow much more flexible structures to be defined and redefined.
つまり効率はstructure
を、柔軟性はclass
を。
そういう方針で両者は設計されています。
今回の話題は構造体とクラスの効率について記載します。
具体的にはslotの読み書きに関することです。
ちょうどdefstruct
を実装し終わった所なので、記憶が残っているうちに書き残します。
slot-value
によるslotの読み書き
クラスも構造体も、どちらもslot-value
が使えます。
まずはこいつから見て行きます。
通常のクラスシステムにおいて、slotを保有しているのは
standard-object
のインスタンスです。
つまりは、standard-class
に関わる全てのオブジェクトです。
とても分かりづらいですね。
クラスに関係するもの全部だと思ってもらえればいいと思います。
純粋な意味での「オブジェクト指向」とは、
全てを「オブジェクト」で表すことです。
で、その「オブジェクト」とは一体何かなのですが、
本処理系やCommon Lispに限ったことではなく、
オブジェクト指向と呼ばれるものすべてに共通すると思うのですが、
オブジェクトはkey-value構造体です。
つまり、keyが与えられたらvalueを返却するというもの。
ここで言うkeyとはslotの名前のことであり、
(slot-value instance 'key) -> value
ということになります。
このkey-value構造体を実装する方法は色々ありますが、
npt
ではただの配列を使っています。
assoc
やplist
に近い構造だと思ってもらえればいいと思います。
つまり検索には線形探索が使われるので、O(n)
だけの時間がかかります。
これはどうなんだろう?
遅くはないかどうか少し考えました。
以前、インスタンスにhash-table
を使うように実装したことがありました。
うまく行けば探索がO(1)
で済むようになるわけです。
でもやめました。
やめた理由はメモリ容量が多い事です。
あとhash-table
は何だかんだでオーバーヘッドが大きいので、
slotが一万個、十万個くらいないとhash-table
の恩恵が受けられないのではないでしょうか。
オブジェクト指向というシステムにおいて何が大量に生成されるかというと、
スロットではなくインスタンスだと思います。
それなのにひとつひとつにhash-table
は余りに無駄が多すぎると判断しました。
調べたわけではありませんが、たぶんどの実装も
線形探索になっているのではないでしょうか。
つまり、slotは大量にあればあるだけ動作は遅くなります。
slotにアクセスする命令は下記の4つにまとまっています。
slot-value
slot-boundp
slot-exists-p
slot-makunbound
この関数すべてが線形探索を実施していると考えてください。
そんなに安くはない関数なのです。
今までの話はクラスだけではなく構造体にも当てはまりますが、 クラスとは違っている部分がいくつかあります。
まず構造体のインスタンスはstandard-object
ではなくstructure-object
です。
両者の違いは何でしょうか。
構造体でもクラスでも、どちらもslot-value
が扱えるということは、
実装面から見れば、ジェネリック関数であるslot-value-using-class
に
standard-object
とstructure-object
を両方定義しておいて、
別々の方法で読み書きをするということになります。
しかしnpt
の場合はどちらも全く同じものを使っています。
分ける必要性があまりありませんから。
他の処理系であるsbcl
やらclisp
やらも同じように実装しているのかと思います。
ここで言いたかったことは、構造体もクラスもslot-value
を使うのであれば違いはなく、
次のようなコストがかかるということです。
slot-value
は線形探索でO(n)
だけの時間がかかりますslot-value
はジェネリック関数を裏で呼んでいます
次はアクセス関数について見て行きます。
関数による読み書き(defstruct
, defclass
共通)
関数による読み書きとは、slotに対してreader
/writer
/accessor
を経由するやり方です。
つまり、slot-value
を使わずに値を取得します。
構造体の場合は、何もオプションを指定しなければ、
全てのスロットに対して自動的に関数が生成されます。
クラスは、オプションを指定することでジェネリック関数が生成されます。
・構造体の場合 (defstruct aaa bbb) -> aaa-bbb, (setf aaa-bbb) という関数が生成される ・クラスの場合 (defclass aaa () ((bbb :accessor aaa-bbb))) -> aaa-bbb, (setf aaa-bbb) というジェネリック関数が生成される
構造体は、関数を生成します。
クラスは、ジェネリック関数を生成します。
両者は似ていますが、速度面においては差が出てきます。
関数を使っている構造体の方が圧倒的に早く処理されます。
ジェネリック関数はどのような動きをするでしょうか。
最悪なケースとしては、実行するとまずはジェネリック関数に
登録されているすべてのmethod
を寄せ集め、
引数の型から合致するmethod
を選別します。
そのあと、method-combination
の実行によりLisp式が生成されます。
Lisp式はそのままでは実行できませんので、
eval
かcompile
により実行形式に変換されます。
生成された関数をはじめの引数に結びつけることで、
ようやくreader
/writer
/accessor
が実行されます。
つまりジェネリック関数が呼ばれるたびに、
eval
かcompile
が毎回走るかもしれないということです。
普通に考えると遅すぎます。
この辺りは規約に書かれているわけではないので処理系依存ですが、
もしかしたら本当に毎回eval
が実行するような処理系があるかもしれません。
当然、これだと全く使い物にならないため、
キャッシュを用いる方法が提案されています。
The Art of the Metaobject Protocolという書籍では、
ジェネリック関数に与えられた引数の型をキーにして、
method-combination
が生成した関数をhash-table
に保存する方法が紹介されています。
その方法を用いると、初回実行は上記で説明したようにeval
やcompile
が実行されますが、
2回目からは、引数の型をチェックし、
hash-table
を検索するだけで関数が実行できることになります。
ここでの結論は速度においては大切です。
構造体は純粋な関数を呼ぶため早いです。
しかしクラスはジェネリック関数が呼ばれるため、
早くてもhash-table
の検索が1回動いた後で関数が実行されます。
ここで言いたかったこと。
- 構造体のアクセス関数呼び出しは、純粋な関数なので早い
- クラスのアクセス関数呼び出しは、ジェネリック関数なので遅い
ちなみにslot-value
関数も、
裏ではジェネリック関数であるslot-value-using-class
を呼ぶため、
ある程度のコストがかかることを覚えておいた方がいいです。
関数による読み書き(defstruct
)
それでは関数が呼ばれたあとの内容について見て行きます。
構造体は、クラスと違って再定義が禁止されています(正確には未定義)。
よって、生成された関数は、その構造体のみを対象にすることができます。
構造体の定義で作成した関数なんだから当たり前じゃないかと
思われるかもしれませんが、defclass
の方は再定義や変更が許されるので、
クラスのslotの内容が変わるかもしれないのです。
構造体は変更の心配がないため、
もしstructure-object
のvalueの格納場所が配列であるならば、
(elt slots 3) ;; このスロットに対応する値は3番目
のように数値を直接指定しておくことができます。
線形探索ではないので、処理はたぶんO(1)
で完了します。
例外があり、構造体が(:type list)
で生成された場合は
nth
関数が呼ばれるのと同じなのでそんなに早くはありません。
実際には値の返却だけではなく前処理が少しあります。
それは、引数が構造体であるかどうかと、
構造体が:include
含めて型と合っているかどうかの判定です。
構造体の関数は、slot-value
に比べると、とても速いことがわかります。
slot-value
は便利ですが、それほど早くないかもしれないということも
わかってもらえるかと思います。
ここで言いたかったこと。
- 構造体のアクセス関数は、配列指定なので早い
- 構造体の
slot-value
関数は、線形探索なので遅い
関数による読み書き(defclass
)
一方、クラスの場合は構造体とは全く変わり、slot-value
と何も変わりません。
せっかく苦労して呼び出されたジェネリック関数ですが、
ただ単純にslot-value
を呼んでいるだけなのです。
理由は再定義とクラス変更があるためです。
変更されたあと、関数は一体何を対象に読み込めばよいのかということと、
関数を実行したときに、例えばupdate-instance-for-redefined-class
みたいな関数を
どうやって呼べばいいかなどの色々な問題があり、
それらをすべて考慮しなければならないのは大変だということで、
slot-value
を使った処理と一致するようにと規約で制定されています。
以前は構造体と同じように配列を直で指定しようと考えていました。
つまり、クラス再定義やchange-class
などの実行契機で
アクセス関数の対象メソッドを総入れ替えするというものです。
でも規約でそこまでするなと書かれているような気がするので、
今では単純にslot-value
を呼ぶだけです。
slotが既に存在していないとか、そういうのを一切気にしていません。
ここで言いたかったこと。
- クラスのアクセス関数は、
slot-value
と同じなので遅い。
まとめ
slotのアクセスは次の順に早い
- 構造体のアクセス関数 ★一番早い
- 構造体とクラスの
slot-value
- クラスのアクセス関数