nptclのブログ

Common Lisp処理系nptの開発メモです。https://github.com/nptcl/npt

構造体とクラスの読み書きの速度

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ではただの配列を使っています。
assocplistに近い構造だと思ってもらえればいいと思います。
つまり検索には線形探索が使われるので、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-classstandard-objectstructure-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式はそのままでは実行できませんので、 evalcompileにより実行形式に変換されます。
生成された関数をはじめの引数に結びつけることで、 ようやくreader/writer/accessorが実行されます。

つまりジェネリック関数が呼ばれるたびに、 evalcompileが毎回走るかもしれないということです。
普通に考えると遅すぎます。

この辺りは規約に書かれているわけではないので処理系依存ですが、 もしかしたら本当に毎回evalが実行するような処理系があるかもしれません。
当然、これだと全く使い物にならないため、 キャッシュを用いる方法が提案されています。

The Art of the Metaobject Protocolという書籍では、 ジェネリック関数に与えられた引数の型をキーにして、 method-combinationが生成した関数をhash-tableに保存する方法が紹介されています。
その方法を用いると、初回実行は上記で説明したようにevalcompileが実行されますが、 2回目からは、引数の型をチェックし、 hash-tableを検索するだけで関数が実行できることになります。

ここでの結論は速度においては大切です。
構造体は純粋な関数を呼ぶため早いです。
しかしクラスはジェネリック関数が呼ばれるため、 早くてもhash-tableの検索が1回動いた後で関数が実行されます。

ここで言いたかったこと。

  • 構造体のアクセス関数呼び出しは、純粋な関数なので早い
  • クラスのアクセス関数呼び出しは、ジェネリック関数なので遅い

ちなみにslot-value関数も、 裏ではジェネリック関数であるslot-value-using-classを呼ぶため、 ある程度のコストがかかることを覚えておいた方がいいです。

関数による読み書き(defstruct

それでは関数が呼ばれたあとの内容について見て行きます。
構造体は、クラスと違って再定義が禁止されています(正確には未定義)。
よって、生成された関数は、その構造体のみを対象にすることができます。

構造体の定義で作成した関数なんだから当たり前じゃないかと 思われるかもしれませんが、defclassの方は再定義や変更が許されるので、 クラスのslotの内容が変わるかもしれないのです。

構造体は変更の心配がないため、 もしstructure-objectvalueの格納場所が配列であるならば、

(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
  • クラスのアクセス関数