1

現在、動的型付け言語を開発しています。

開発中に私が直面している主な問題の 1 つは、実行時のシンボル検索を高速に行う方法です。

一般的な無料のグローバル シンボルとローカル シンボルについては、単純にインデックスを付けて、各スコープ (グローバルまたはローカル) にシンボルの配列を保持させ、インデックスを使用してすばやく検索します。私はこのアプローチにとても満足しています。

ただし、オブジェクトの属性の場合、問題ははるかに困難です。現在アクセスしているオブジェクトがわからないため、同じインデックス スキームを使用することはできません。したがって、どのインデックスを使用すればよいかわかりません。

私の言語で働きたいことを反映したPythonの例を次に示します。

class A:
    def __init__(self):
        self.a = 10
        self.c = 30

class B:
    def __init__(self):
        self.c = 20

def test():
    if random():
        foo = A()
    else:
        foo = B()
    # There could even be an eval here that sets foo
    # to something different or removes attribute c from foo.
    print foo.c

検索をすばやく行うための巧妙なトリックを知っている人はいますか? 私はハッシュ マップとスプレイ ツリーについて知っているので、他のルックアップと同じくらい効率的に行う方法があれば興味深いです。

4

2 に答える 2

1

マップと呼ばれる手法を使用すると、各属性の値をコンパクトな配列に格納できます。どの属性名がどのインデックスに対応するかという知識は、補助データ構造 (同名のマップ) で維持されるため、すぐにパフォーマンス上の利点が得られるわけではありません (ただし、多くのオブジェクトが一連の属性を共有している場合は、メモリをより効率的に使用します)。JIT コンパイラーを使用すると、マップを永続化して定数フォールド ルックアップを作成できるため、最終的なマシン コードで属性配列 (定数属性名の場合) への定数オフセットを使用できます。

インタープリター (バイトコードと仮定します) では、特定のオブジェクト用にコードを特殊化する機会があまりないため、状況ははるかに難しくなります。しかし、属性名を整数のキーに変換するというアイデアを私は自分で持っています。整数 ID を属性名に割り当てるグローバル マッピングを維持します。新しいバイト コードを VM に追加するとき (ディスクからの読み込みまたはメモリでのコンパイル)、属性として使用される文字列をスキャンし、それらを関連付けられた ID に置き換えて、文字列が以前に見られなかった場合は新しい ID を作成します。ハッシュ テーブルや同様のマッピングを各オブジェクト (またはマップを使用する場合はマップ) に格納する代わりに、スパース配列を使用できるようになりました。

これを実装してテストするための変更は行っていませんが、まだスパース配列が必要です。すべてのオブジェクト (またはマップ) に、プログラム全体で異なる属性名が存在するのと同じくらい多くのメモリ ワードを使用させたい場合を除きます。少なくとも、文字列ハッシュ テーブルを整数ハッシュ テーブルに置き換えることができます。キーとして ID のハッシュ テーブルを調整するだけで、いくつかの最適化を行うことができます: ハッシュ関数を呼び出さない (ID をハッシュとして使用する)、いくつかの間接性を削除してキャッシュ ミスをなくす、病理学的に悪いハッシュを処理する複雑さを回避する機能など

于 2013-05-31T16:23:40.300 に答える