Objects, attributen, maps, oh my!

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

Of Ruby:

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

Of JavaScript:

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

Dit kan een implementator van een Virtual Machine (VM) aanmoedigen om objectattributen te modelleren met behulp van een hash-tabel. Hash-tabellen zijn immers zeer effectief in het mappen van namen naar waarden.

Hieronder volgt een Python-schets van hoe dit objectmodel eruitziet. Omdat het een schets is, wordt writeattr en readattr gebruikt in plaats van de gebruikelijke syntax van de programmeertaal.

MISSING = object()

class Instance:
    def __init__(self):
        # TODO: de rest van het objectsysteem
        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"))

Dit heeft voordelen:

• Het is eenvoudig te begrijpen.
• ... tja, dat is eigenlijk wel alles.

Er zijn echter ook nadelen:

• Het gebruikt een hash-tabel voor een zeer veel voorkomende operatie. Hoewel dit technisch gezien $O(1)$ is, zijn hashing en probing erg traag.
• Er is sprake van indirectie: het springen van een object naar een aparte hash-tabel voor veldopslag vereist veel afhankelijke geheugenladingen. Objectattributen worden frequent benaderd en zouden daarom in-line op het object moeten worden opgeslagen in plaats van via een extra geheugenbenadering (wat potentieel tot een cache-miss leidt).

Dit is een goed voorbeeld van een situatie waarin de hash-tabel geen eigen interne fragmentatie heeft. Toch betekent dit dat letterlijk elke operatie a.b honderden of duizenden CPU-instructies uitvoert, inclusief meerdere afhankelijke geheugenladingen. Dit is slecht voor de prestaties.

Daarom implementeren runtime-ontwikkelaars vaak iets dat maps, layouts, shapes, hidden classes of structures wordt genoemd, om het lezen, schrijven en opslaan van attributen te optimaliseren.

Maar hoe ziet deze "shape"-code eruit? En hoe helpt het precies bij de prestaties? Veel grote productie-runtimes hebben zeer complexe code met domeinspecifieke uitzonderingen, waardoor het lastig is de basis te begrijpen. Veel blogposts bieden weliswaar uitstekende overzichten op hoog niveau, maar missen de concrete implementatie. Daarom doen we het hier nog eens, met als doel dat je in een pagina code het hele concept in één keer kunt overzien.

500 regels of minder

Ik heb besloten om A Simple Object Model van CF Bolz-Tereick opnieuw grondig te lezen. In het verleden ben ik daar telkens vanaf gebonst omdat het Python met een redelijke getrouwheid modelleert, en het Python-objectmodel is erg complex.

Deze keer heb ik me toegestaan om de delen over klassen en methoden te scannen en me in plaats daarvan te concentreren op de instance-attributen en de maps. In het artikel van CF staat de kern van een zeer schoon map-systeem, dat ik heb geëxtraheerd om mee te experimenteren.

Het begint vergelijkbaar met onze eerdere schets, waarbij objecten worden gemodelleerd als ongeordende maps van attributen. Hier is de gereduceerde implementatie:

# De basiscode voor het objectmodel:
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

Dit kun je als volgt gebruiken:

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

Er vindt wat delegatie plaats in de Base-klasse, omdat het artikel al anticipeert op wat we nu gaan doen: de implementatie van Instance voor readdict en writedict vervangen voor betere prestaties.

Cartografie

Laten we nu de "map"-datastructuur toevoegen. Het doel van de map is drieledig:

1. Vermijden van strings en hashing in het 'fast path'. We willen operaties uitvoeren op kleine integers in plaats van strings.
2. Verwijderen van de indirectie. We willen attributen in-line in het object opslaan in plaats van elders in het geheugen.
3. Een stabiele identificatie hebben. Er moet een identifier zijn die een specifieke object-layout beschrijft.

Voor het eerste punt kunnen we het map-veld van een object zien als een index of een write-through cache. Het is verantwoordelijk voor het weerspiegelen van de layout van een gegeven object. Je kunt de map vragen: "Welke attributen heeft dit object?" en "Waar bevindt attribuut a zich ten opzichte van het begin van het object?".

Het lijkt misschien vreemd: we hebben in feite één hash-tabel vervangen door een andere. Er is echter één groot verschil: in het shape-model hoeven we niet altijd de hash-tabel te gebruiken. Als we de offset onthouden vanaf de laatste keer dat we deze in de shape opzochten, kunnen we die offset hergebruiken. Dit komt vooral voor bij een interpreter-functie genaamd een inline cache.

Dit brengt ons bij het tweede punt: als we de offset in het object hebben, kunnen we daar direct uit lezen. Er is geen tweede load uit een ander geheugengebied nodig. We hebben het object al in handen en hopelijk al in de cache.

Dit werkt totdat de map verandert. Omdat dynamische talen flexibel zijn, kan een object op elk moment een attribuut winnen of verliezen. In dat geval hebben we een zeer snelle controle nodig om te zien of de in-memory layout van het object is gewijzigd.

Dit is het derde punt: we moeten kunnen vertrouwen op het feit dat de map onveranderlijk (immutable) is, up-to-date is en een stabiele identifier is voor een specifieke in-memory layout. Zo kunnen we een zeer snelle check uitvoeren ("is de map dezelfde als bij de laatste leesactie?") voordat we een load uitvoeren.

Dit betekent dat wanneer we een nieuw attribuut aan een object toevoegen, we het een nieuwe map moeten geven. Maps zijn in feite bomen (tries) en worden toegewezen als een persistente datastructuur. Elk nieuw object begint met een lege map. Terwijl het programma attributen toevoegt, volgt het de randen in de boom om zijn nieuwe map te vinden of te maken.

Hier is de Python-implementatie van objecten met maps:

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({})

Opmerking: de opslag is hier niet echt "in-line", omdat Python geen directe controle geeft over object-layouts. In talen als C++ of Rust wordt attribuutopslag doorgaans in-line met de object-header geïmplementeerd.

Inline Caches

Hoewel de bovenstaande code nog steeds string-namen gebruikt voor het lezen en schrijven, is het de bedoeling om de index-opslag te gebruiken in een inline cache.

Stel we hebben een Point-klasse en we lezen het x-attribuut. De naam x is meestal constant in het programma (bijvoorbeeld vastgelegd in bytecode als LOAD_ATTRIBUTE "x"). Dit is cruciaal voor de inline cache: het variëren van het object is één ding, maar het variëren van de naam die wordt opgezocht, voegt veel complexiteit toe.

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

# String API (traag):
P.read_attr("x")

We maken nu een afweging tussen geheugen en snelheid. We reserveren ruimte voor de verwachte map en de gecachte index. De logica is als volgt:

1. Hebben we een matching map? Geweldig! Laad direct uit de storage via de index.
2. Zo niet, zoek dan de waarde en index op via de string-naam.
3. Cache vervolgens de map/index-combinatie voor de volgende keer.

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()
# Eerste keer: opzoeken via string
IC.read(P, "x")
# Tweede keer: Map hit! Opzoeken via index!
IC.read(P, "x")

Ik gebruik hier is (pointer-gelijkheid) in plaats van ==. Omdat we garanderen dat maps onveranderlijk zijn, hoeven we alleen de pointer of numerieke ID te controleren, niet de inhoud van de map.

Deze InlineCache-klasse is een schets van een "geïnterpreteerde IC". In echte runtimes wordt het snelle pad vaak inlined en het trage pad outlined. JIT-compilers proberen de "geïnterpreteerde" aard van de inline cache verder te verwijderen door bijvoorbeeld zelf-modificerende assembly te gebruiken (hoewel dit tegenwoordig lastiger is door W^X-beveiliging).

Belangrijk om te onthouden: de volgorde van het toevoegen van attributen is bepalend. Het toevoegen van a dan b resulteert in een andere shape dan b dan a. Dit kan leiden tot prestatieverlies als inline caches vaak missen (polymorfisme).

Ook de hoeveelheid attributen speelt een rol. Veel VM-implementators hebben gemerkt dat de meeste objecten klein zijn (< 20 velden). Te veel velden kunnen ertoe leiden dat een object wordt teruggezet naar de "hash-tabel modus".

Klasse versus Shape

Wat betekent het als twee objecten met verschillende klassen dezelfde shape hebben?

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)

# Dezelfde shape/map!
assert F.map is B.map
# Maar een andere klasse!
assert F.cls != B.cls

Dit betekent dat de inline cache een hogere hit-rate kan hebben; instanties van subklassen die code delen, kunnen nog steeds als monomorf worden beschouwd in de IC.

Het betekent echter ook dat je de shape niet als proxy voor de klasse kunt gebruiken. Bij functies zoals attr_reader in Ruby moet de VM twee dingen doen:

1. De methode oplossen op basis van de klasse van het object.
2. De instance-variabele oplossen op basis van de shape van het object.

Deze tweetraps-lookup voegt complexiteit en overhead toe. Als maps gespecialiseerd zouden zijn zodat een andere klasse altijd een andere map impliceert, zou dit kunnen worden gereduceerd tot één enkele load.

Opslagstrategieën

In Storage Strategies for Collections in Dynamically Typed Languages (2013) wordt betoogd dat sommige feiten over objecten het waard zijn om op te splitsen of te monomorfiseren, omdat dit geheugen bespaart en pointer-chasing vermindert.

Dit denken strekt zich uit tot "Type Freezing" (2020), waarbij object-maps veranderen van {naam: offset} naar {naam: (offset, type)} om guards te verminderen. Dit helpt vooral in tracing JIT-compilers.

Relevante literatuur over dit onderwerp:

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

Klasseversiebeheer

Er kunnen nog sterkere aannames worden gedaan over klassen. Zie hiervoor bijvoorbeeld de sectie over class versioning op de PyPy-blog.

Nogmaals in C++

In "echte" runtimes (zoals V8 of JSC) ziet de geheugenlayout er anders uit: ze hebben compacte object-headers die de shape/map bevatten en andere vlaggen. Attributen worden in-line met het object gealloceerd, vaak met een "overflow"-slot voor het geval de initiële schatting van de objectgrootte te klein was.

Een kleine runtime in C++ die dit simuleert, laat zien hoe de onderliggende geheugenlayouts werken die systemen als Skybison, V8 en JSC ondersteunen.

***

Voetnoten:

1. Zie de Rails PR door Hartley om shapes monomorfer te maken. Dit was aanvankelijk nodig omdat ZJIT geen polymorfe reads kon afhandelen.
2. Het verschil tussen een cache hit en een cache miss in een 'hot path' kan een prestatieverschil van 2x of meer betekenen.