プログラミング

オブジェクト、属性、マップ、オーマイ！

Objects, attributes, maps, oh my (bernsteinbear.com)

11 pointsby ibobev2026年10月23日1 コメント

要約

この記事は、動的型付け言語におけるオブジェクトの属性アクセスを最適化するための「マップ」（またはシェイプ、隠れクラス）の概念と、インラインキャッシュ（IC）の仕組みを解説しています。ハッシュテーブルによる単純な実装の遅さを克服し、パフォーマンスを向上させるための、VM実装における重要な技術について掘り下げています。

全文翻訳

オブジェクト、属性、マップ、オーマイ！

あるいは、IC UC we all C for ICs。

多くの動的型付けプログラミング言語では、オブジェクトは名前と値のマッピングの大きな塊のように見えます。これらの言語はその柔軟性を奨励します。例えばPythonを考えてみましょう。

class C:
    def __init__(self):
        self.a = 1
        self.b = 2

あるいはRuby：

class C
  def initialize
    @a = 1
    @b = 2
  end
end

あるいはJavaScript[1]：

let obj = {};
obj.a = 1;
obj.b = 2;

これはVM実装者にオブジェクト属性をハッシュテーブルを使用してモデル化するように促すかもしれません。結局のところ、ハッシュテーブルは名前と値のマッピングに非常に優れています。

例として、このオブジェクトモデルがどのように見えるかのPythonスケッチを示します。これはスケッチであるため、より一般的な構文の代わりにwrite_attrとread_attrを使用しています。

MISSING = object()

class Instance:
    def __init__(self):
        # TODO: 残りのオブジェクトシステム
        self.cls = ...
        self._fields = {}

    def read_attr(self, fieldname):
        return self._fields.get(fieldname, MISSING)

    def write_attr(self, fieldname, value):
        self._fields[fieldname] = value

obj = Instance()
obj.write_attr("a", 1)
obj.write_attr("b", 2)
print(obj.read_attr("a") + obj.read_attr("b"))

これには利点があります。

理解しやすい
…うーん、まあ、それだけかもしれません。

欠点もあります。

非常に一般的な操作であるハッシュテーブルを使用しています。これは技術的にはO(1)ですが、ハッシュ化とプロービングは非常に遅いです。
間接参照があります。オブジェクトからその別のハッシュテーブルフィールドストレージへのジャンプには、多くの依存メモリロードが必要です。オブジェクト属性は頻繁にアクセスされるため、オブジェクト自体にインラインで格納されるべきであり、別のメモリアクセス（および潜在的なキャッシュミス）から離れた場所ではなく、インラインで格納されるべきです。

これはハッシュテーブルが独自の内部断片化を持たない、かなり良いケースです。

これは、文字通りすべての操作a.bが数百または数千のCPU命令を実行し、複数の依存メモリロードを含むことを意味します。これはパフォーマンスにとって良くありません。

そのため、ランタイム実装者はマップ、レイアウト、シェイプ、隠れクラス、構造体、あるいは私が知らない秘密の6番目の名前と呼ばれるものを実装する傾向があります。これは、属性の読み取り、書き込み、および格納を最適化します。

しかし、このシェイプコードはどのようなものでしょうか？パフォーマンスにどのように役立つのでしょうか？多くの本番ランタイムには、ドメイン固有のエッジケースを持つ非常に複雑なコードがあるため、基本を理解するのに役立たないかもしれません。そして、多くのブログ記事は、優れた高レベルの概要を提供していますが、実装が不足しています。そこで、もう一度ブログで、他の人がすでにブログで書いた場所について書きます。うまくいけば、1ページのコードを書いて、すべてを一度に頭に入れられるはずです。

500行以下

CF Bolz-TereickのA Simple Object Modelを、その価値に見合う徹底的な読書に値すると判断しました。過去に何度か試みましたが、Pythonを合理的な忠実度でモデル化しており、Pythonのオブジェクトモデルは非常に複雑であるため、挫折しました。

しかし、今回徹底的に読みましたか？まあ、いいえ。今回はクラスとメソッド関連の部分をスキップすることを許可し、代わりにインスタンス属性とマップの部分に焦点を当てました。CFの記事の中には、非常にクリーンなマップシステムの核心があり、それを実験したかったので、抽出しました。

CFの記事は、オブジェクトを属性の順序付けされていないマップとしてモデル化するという、私たち自身のスケッチと非常に似た形で始まります。また、クラスに関する私が省略したTODOの一部も埋めています。私がここでコピーした削減された実装は、あなたが確認できるようにしたものです。

# ベースオブジェクトモデルコード:

class Base:
    def __init__(self, cls, fields):
        self.cls = cls
        self._fields = fields

    def read_attr(self, fieldname):
        return self._read_dict(fieldname)

    def write_attr(self, fieldname, value):
        return self._write_dict(fieldname, value)

    def _read_dict(self, fieldname):
        return self._fields.get(fieldname, MISSING)

    def _write_dict(self, fieldname, value):
        self._fields[fieldname] = value

MISSING = object()

class Instance(Base):
    def __init__(self, cls: "Class"):
        super().__init__(cls, {})

class Class(Base):
    def __init__(self, name, base_class, fields, metaclass):
        super().__init__(metaclass, fields)
        self.name = name
        self.base_class = base_class

OBJECT = Class(name="object", base_class=None, fields={}, metaclass=None)
TYPE = Class(name="type", base_class=OBJECT, fields={}, metaclass=None)
TYPE.cls = TYPE
OBJECT.cls = TYPE

これは次のように使用できます（テストコードもCFの記事から取得しました）。

A = Class(name="A", base_class=OBJECT, fields={}, metaclass=TYPE)
obj = Instance(A)
obj.write_attr("a", 1)
assert obj.read_attr("a") == 1

obj.write_attr("b", 5)
assert obj.read_attr("a") == 1
assert obj.read_attr("b") == 5

obj.write_attr("a", 2)
assert obj.read_attr("a") == 2
assert obj.read_attr("b") == 5

Baseクラスには、記事がすでに私たちがこれから行うことを予期しているため、いくらかの委譲が行われています。Instanceの実装を_read_dictと_write_dictに切り替えて、パフォーマンスを向上させます。

カートグラフィー

さて、「マップ」データ構造を追加しましょう。マップの目的は3つのことを行うことです。

高速パスで文字列とハッシュ化の処理から抜け出す。代わりに小さな整数で操作を行いたい。
間接参照を削除する。属性をオブジェクトにインラインで格納したい。メモリの別の場所ではなく。
特定のオブジェクトレイアウトを記述する安定した識別子である/を持つ。

前者については、オブジェクトのマップフィールドを（データベース）インデックスまたはライトスルーキャッシュと考えることができます。これは、オブジェクトのレイアウトを反映する責任があります。

このモデルはほぼ完成しています...

マップに「このオブジェクトにはどのような属性がありますか？」や「属性aはオブジェクトの先頭からどの位置にありますか？」といった質問をすることができます。

図を見ただけでは、くだらないように見えるかもしれません。結局、1つのハッシュテーブルを別のハッシュテーブルに交換しただけです。しかし、大きな違いがあります。それは、シェイプモデルでは、ハッシュテーブルを常に使用する必要がないということです。最後にルックアップしてからオフセットを覚えておけば、オフセットを再利用できます。これは主に、インラインキャッシュと呼ばれるインタープリタ機能に現れます。

これが2番目の点につながります。オブジェクト内のオフセットがあれば、そこから直接読み取ることができます。別のメモリ領域から2回目のロードを行う必要はありません。オブジェクトは手元にあり、おそらくすでにキャッシュに入っています。

…少なくともマップが変更されない限り。その場合、オフセットを再利用できません。これらの言語は柔軟性を奨励することを忘れないでください。オブジェクトはいつでも属性を追加または削除できます。その場合どうなりますか？理想的には、オブジェクトのメモリレイアウトが変更されたかどうかを伝える非常に高速なチェックがあります。

これが3番目の点につながります。マップが不変で最新であり、特定のメモリレイアウトの安定した識別子であることを信頼する必要があります。これにより、ロードの前に非常に高速なチェック（「マップは前回読み取ったものと同じか？」）を実行できます。

これは、新しい属性をオブジェクトに追加するときに、新しいマップを与える必要があることを意味します。マップは実際にはツリー（トライ？）であり、永続データ構造のように割り当てられます。すべての新しいオブジェクトは空のマップから始まります。プログラムが属性を追加するにつれて、ツリーのエッジをたどって新しいマップを見つけるか作成します。

CF Bolz-Tereickによる画像、CC BY 3.0。

マップに関するセクションを読むことをお勧めします。そこでは、もう少し詳細に説明されています。

これらすべてを念頭に置いて、CFのオブジェクトとマップの実装（およびマップ自体）のPythonコードを見てみましょう。

class Instance(Instance):
    def __init__(self, cls: "Class"):
        super().__init__(cls)
        self.map = EMPTY_MAP
        self.storage = []

    def _read_dict(self, fieldname):
        index = self.map.get_index(fieldname)
        if index == -1:
            return MISSING
        return self.storage[index]

    def _write_dict(self, fieldname, value):
        index = self.map.get_index(fieldname)
        if index != -1:
            self.storage[index] = value
        else:
            new_map = self.map.next_map(fieldname)
            self.storage.append(value)
            self.map = new_map

class Map:
    def __init__(self, attrs):
        self.attrs = attrs
        self.next_maps = {}

    def get_index(self, fieldname):
        return self.attrs.get(fieldname, -1)

    def next_map(self, fieldname):
        assert fieldname not in self.attrs
        if fieldname in self.next_maps:
            return self.next_maps[fieldname]
        attrs = self.attrs.copy()
        attrs[fieldname] = len(attrs)
        result = self.next_maps[fieldname] = Map(attrs)
        return result

EMPTY_MAP = Map({})

ストレージがインラインではないことに気づくかもしれません。これは、Pythonではそのようなオブジェクトレイアウト制御ができないためです。C++やRustのような言語で実装された場合、属性ストレージは通常、オブジェクトヘッダーとインラインで格納されます。

それを無視すると、一般的なケースではまだ文字列名を使用して属性の読み取りと書き込みを行っていることがわかります。どういうことでしょうか？さて、インラインキャッシュで意図されたとおりにインデックスストレージを使用しましょう。

インラインキャッシュ

文字列属性APIから始めましょう。ポイントクラスを作成し、x属性を読み取ります。属性名を一定に保ちます。これは一般的にプログラムで固定されているためです。obj.xは通常、名前xがバイトコードに埋め込まれている何らかのバイトコードLOAD_ATTRIBUTE, "x"のようになります。

これはインラインキャッシュにとって重要です。レシーバを変更することは1つのことですが、ルックアップされる名前を変更すると、さらに多くの複雑さが追加されます。それは可能ですが、厄介です。

Point = Class(name="Point", base_class=OBJECT, fields={}, metaclass=TYPE)
P = Instance(Point)
P.write_attr("x", 5)
P.write_attr("y", 6)

# 文字列API :(
P.read_attr("x")
# 常にインデックスをルックアップ :(
P.read_attr("x")
# 毎回 :(
P.read_attr("x")

次に、メモリ/速度のトレードオフを行います。前述の期待されるマップとキャッシュされたインデックスのためにスペースを割り当てます。これにより、非常に高速なチェックの後に、（うまくいけば）一般的なケースでインデックス付きロードを実行できます。

ロジックは次のとおりです。

マッチするマップがあれば、素晴らしい！ストレージからロードします。
マッチしない場合は、文字列名で値を検索し、インデックスを付けます。
次に、マップ/インデックスの組み合わせを次回のためにキャッシュします。

属性が見つからない場合、（今のところ？）ネガティブルックアップはキャッシュしません。このケースはまれであることを願っています。

class InlineCache:
    def __init__(self):
        self.map = None
        self.idx = None

    def read(self, obj, fieldname):
        obj_map = obj.map
        if obj_map is self.map:
            return obj.storage[self.idx]
        index = obj_map.get_index(fieldname)
        if index == -1:
            return MISSING
        self.map = obj_map
        self.idx = index
        return obj.storage[index]

IC = InlineCache()
# 文字列でルックアップ :(
IC.read(P, "x")
# マップヒット！インデックスでルックアップ！:)
IC.read(P, "x")
# マップヒット！インデックスでルックアップ！:)
IC.read(P, "x")

is（ポインタ等価性）を使用し、==（ユーザー定義/ディープ等価性）を使用していないことに注意してください。これは意図的です！マップが不変であることを保証しているため、マップのフィールドの等価性をチェックする必要はありません。ポインタ/数値IDだけで十分です。

このInlineCacheクラスは、インラインキャッシュが何をするかの「スケッチ」にすぎません。これは「インタープリタIC」です。このシェイプは、高速パスがインライン化され、低速パスがアウトライン化されていることを確認すれば、インタープリタを大いに助けることができます。パフォーマンスは確かに向上します。簡単な属性ルックアップ関数をベンチマークすることをお勧めします。しかし、インラインキャッシュを備えたほとんどのランタイムには、JITコンパイラも付属しています。これらのコンパイラは、インラインキャッシュ実装の「インタープリタ的」な性質を削除しようとします。例を参照してください。

Slavaの記事（IRスケッチとJSライクな疑似コードで説明）
- この古い記事も同様です。
Caioの記事（JavaScriptCoreでのx86アセンブリでのインラインキャッシュの様子を説明）
Matthewの記事（投機的な数値加算のための疑似アセンブリでの様子を説明）
- ほとんどのランタイムは、W^X保護のため、およびicacheをフラッシュする必要があるため、自己変更アセンブリICのようなものは行いません。

もう1つ注意すべき点は、順序が重要であるということです。属性を異なる順序で追加する（例: aの後にb vs bの後にa）と、異なるシェイプになります。もう1つの一般的な原因は、初期化時に条件付きで属性を格納することです（例: if cond: self.a = 1）。

このシェイプとキャッシュの動作は、パフォーマンスの低下[2]を除いて、アプリケーションプログラマにはほとんど見えません。そこでは、インラインキャッシュが頻繁にミスするか、最適な（モノモーフィックな）キャッシュを持てないかのどちらかです。これは恐ろしく聞こえないかもしれませんが、ホットパスでのキャッシュヒットとキャッシュミスの違いは、パフォーマンスの2倍以上になる可能性があり、アプリケーションで調査する価値があります。

また、数量も重要です。VM実装者は、ほとんどのオブジェクトは小さい（約20フィールド未満）と測定および判断しました。オブジェクトにフィールドを多すぎると、ペナルティを受けて「ハッシュテーブルモード」に戻される可能性があります。たとえばRubyでは、シェイプが「複雑」になる前に、オブジェクト内に固定数のインスタンス変数（属性）があります。

最後に、このキャッシュはこのオブジェクトに固有ではないことに注意してください。任意の数のPointインスタンスがキャッシュヒットを得ることができます。実際、これを見ると、オブジェクトはPointである必要さえありません...

クラス対シェイプ

クラスが異なる2つのオブジェクトが同じシェイプを持つことができるとはどういう意味でしょうか？

Foo = Class(name="Foo", base_class=OBJECT, fields={}, metaclass=TYPE)
F = Instance(Foo)
F.write_attr("x", 1)
F.write_attr("y", 2)

Bar = Class(name="Bar", base_class=OBJECT, fields={}, metaclass=TYPE)
B = Instance(Bar)
B.write_attr("x", 3)
B.write_attr("y", 4)

# 同じシェイプ/マップ！
assert F.map is B.map
# しかしクラスは異なる！
assert F.cls != B.cls

1つは、インラインキャッシュのヒット率が高くなる可能性があるということです。たとえば、コードを共有するサブクラスのインスタンスは、ICでは依然としてモノモーフィックとしてカウントされる可能性があります。

また、シェイプをクラスを知るためのプロキシとして使用できないことも意味します。Rubyのattr_readerのようなものがある場合、VMがインスタンス変数をルックアップするためだけに合成メソッドを生成する場合、2つのことを行う必要があります。

オブジェクトのクラスに基づいてメソッドを解決して、それがattr_readerであることを確認します。
オブジェクトのシェイプに基づいてインスタンス変数を解決します。

この2段階のルックアップは、複雑さと実行時オーバーヘッドの両方を追加します。マップを、異なるクラスを持つことは異なるマップを持つことを意味するように特殊化した場合、1回のフィールドロードでその2段階ディスパッチを特殊化できます。

これは興味深い考え方です。マップを他に何を特殊化できるでしょうか？

ストレージ戦略

予想どおり、CF Bolz-Tereickは、Lukas DiekmannおよびLaurence Trattと共に、Storage Strategies for Collections in Dynamically Typed Languages（PDF、2013）で再び登場します。

主なアイデアは、オブジェクトに関するいくつかの事実（プロパティ、属性、ハハ）が両方とも：

分割/モノモーフィングする価値がある（ブランチとコードサイズの増加に対する「報酬」がある）。
コードの場所にも同様に敏感である（整数リストはここに割り当てられ、浮動小数点リストはあちらに）。

彼らの扱いはコレクション用です（たとえば、空のリストや小さな整数のリストの一般的なケースを最適化するなど）。オプティマイザにさらに情報を提供するだけでなく、メモリとポインタチェイシングの両方を削減するのに役立ちます。

この種の考え方はコレクションを超えて拡張されます。オブジェクトで属性が常に特定のタイプであることはありますか？おそらくあなたのPointクラスは常に浮動小数点数を含んでいますか？それなら、私がCFのフォローアップペーパーと考えるもの、タイプフリーズを検討してください。Type Freezing: Exploiting Attribute Type Monomorphism in Tracing JIT Compilers（PDF、2020）。

この論文は、ガードを減らすためにオブジェクトマップを{name: offset}から{name: (offset, type)}に変更します。次に、ネストされた属性とそのタイプに対処することによってさらに進みます。このネスト拡張は、主に実装のメタ循環性によって動機付けられており、「通常の」ランタイムへの影響は少ないでしょう。

以下も参照してください。

An Efficient Implementation of SELF, a Dynamically-Typed Object-Oriented Language Based on Prototypes（PDF、1991）
Optimizing Dynamically-Dispatched Calls with Run-Time Type Feedback（PDF、1994）
An Object Storage Model for the Truffle Language Implementation Framework（PDF、2014）
Extending Basic Block Versioning with Typed Object Shapes（PDF、2015）
Just-in-Time Data Structures（PDF、2015）
Efficient and thread-safe objects for dynamically-typed languages（PDF、2016）
Parallelization of dynamic languages: synchronizing built-in collections（PDF、2018）
Profile Guided Offline Optimization of Hidden Class Graphs for JavaScript VMs in Embedded Systems（PDF、2022）
Optimizations for Dynamic Collections（PDF、2025）

クラスのバージョン管理

クラスについてさらに強力な賭けをすることができます。たとえば、PyPyブログのクラスバージョン管理セクションを参照してください。

もう一度、感情 C++で

このブログ記事が、CFの記事の手動メモリレイアウトの再ハッシュなしでは完了しないと感じました。Pythonで書くのは良いとしても、「実際の」ランタイムはどのようになっているのでしょうか？

コンパクトなオブジェクトヘッダーがあり、シェイプ/マップといくつかのフラグビットが含まれています。属性はオブジェクトとインラインで割り当てられます。また、初期オブジェクトサイジングの見積もりが小さすぎた場合の「オーバーフロー」スロットもあるでしょう。

そこで、オブジェクトを割り当て、属性を追加し、シェイプシステムを持つ非常に小さなC++ランタイムを作成しました。おそらくバグだらけでしょう。しかし、Skybison、V8、JSCなどの基盤となるメモリレイアウトのスケッチを提供します。

見てみる。

オーバーフロースロットはありませんが、基盤となるモデルのまともなスケッチです。

そしてさらに

このブログ記事で勢いを失いつつありますが、話すべきことは他にもあります。元々は誰かのLoxインタープリタにオブジェクトシェイプを追加し、次にインタープリタにインラインキャッシュを追加したかったのです。

おそらく、この投稿を更新するかもしれません。あるいは、あなたが続編を書くかもしれません。

ありがとうございます

CF Bolz-Tereick、Nery Campusano、Jacob Denbeauxに、この投稿に関する思慮深いフィードバックをいただきありがとうございます。

または、以下の同等のもの...

// または
function C() {
    this.a = 1;
    this.b = 2;
}
// または
class C {
    constructor() {
        this.a = 1;
        this.b = 2;
    }
}

↩

HartleyによるこのRails PRを参照してください。これはシェイプをよりモノモーフィックにするためのものです。当初はZJITがシェイプポリモーフィックな読み取りを処理できなかったために提出されましたが、他のJITもモノモーフィックに保つのに役立ちます。この系統では、私のoptcarrotへのPRもあります。

ZJITは現在、ポリモーフィックシェイプでよりうまく機能しますが、このようなものは一般的に言語やランタイム全体で重要です。人々が大規模な（PDF）研究（PDF）を行って、この種の情報をアプリケーションプログラマにインテリジェントに公開するほどです。↩