Or, IC UC we all C for ICs.
\nIn many dynamically typed programming languages, objects look like a big ol’\nmapping of names to values. The languages encourage this flexibility. Consider\nfor example Python:
\nclass C:\n def __init__(self):\n self.a = 1\n self.b = 2Or Ruby:
\nclass C\n def initialize\n @a = 1\n @b = 2\n end\nendOr JavaScript1:
\nlet obj = {};\nobj.a = 1;\nobj.b = 2;This might encourage the VM implementor to model object attributes using a hash\ntable. Hash tables, after all, are very good at mapping names to values.
\nHere is, by way of example, a Python sketch of what this object model looks\nlike. Because it is a sketch, it uses write_attr and read_attr instead of\nthe much more common syntax that your programming language comes with.
MISSING = object()\n\nclass Instance:\n def __init__(self):\n # TODO: the rest of your object system\n self.cls = ...\n self._fields = {}\n\n def read_attr(self, fieldname):\n return self._fields.get(fieldname, MISSING)\n\n def write_attr(self, fieldname, value):\n self._fields[fieldname] = value\n\nobj = Instance()\nobj.write_attr("a", 1)\nobj.write_attr("b", 2)\nprint(obj.read_attr("a") + obj.read_attr("b"))This has its benefits:
\nIt also has its drawbacks:
\nit uses a hash table for a very common operation: while this is technically
O(1), hashing and probing are very slow
it has an indirection: jumping from an object to its separate hash table
field storage requires a lot of dependent memory loads. object attributes are\naccessed frequently and should therefore be stored in-line on the object\ninstead of another memory access (and potentially cache miss) away
This is a pretty good case where the hash table doesn't have its own internal\nfragmentation.
\nThis means that literally every operation a.b is doing hundreds or thousands\nof CPU instructions, including multiple dependent memory loads. This is *not\ngood* for performance.
So runtime implementors tend to implement this thing called maps, or layouts,\nor shapes, or hidden classes, or structures, or probably a secret sixth name I\ndon’t know about, which optimizes reading, writing, and storage of attributes.
\nBut what does this shape code look like? How does it actually help performance?\nA lot of big production runtimes have pretty hairy code with domain-specific\nedge cases so they may not help get a handle on the basics. And a lot of blog\nposts, while excellent high-level overviews, are lacking in implementation. So\nhere we go once more, blogging where everyone else has already blogged before.\nWith any luck, you should be able to write a page of code and hold the whole\nthing in your head at once.
\nI decided to once more give CF Bolz-Tereick’s A Simple Object\nModel the thorough\nread it deserves. In the past, I tried a couple times and bounced off of it\nbecause it models Python with reasonable fidelity and the Python object model\nis really hairy.
\nBut did I read it thoroughly this time? Well, no. This time I allowed myself to\nskim the class- and method-related parts and instead focus on the instance\nattribute and map parts. Inside CF’s post is the core of a very clean map\nsystem and I wanted to experiment with that, so I extracted it out.
\nCF’s post starts off very similar to our own sketch, modeling objects as\nunordered maps of attributes. It also fills in some of the TODO stuff I left\nout earlier around classes. I’ll copy my reduced implementation of it here so\nyou can take a gander:
\n# The base object model code:\n\nclass Base:\n def __init__(self, cls, fields):\n self.cls = cls\n self._fields = fields\n\n def read_attr(self, fieldname):\n return self._read_dict(fieldname)\n\n def write_attr(self, fieldname, value):\n return self._write_dict(fieldname, value)\n\n def _read_dict(self, fieldname):\n return self._fields.get(fieldname, MISSING)\n\n def _write_dict(self, fieldname, value):\n self._fields[fieldname] = value\n\nMISSING = object()\n\nclass Instance(Base):\n def __init__(self, cls: "Class"):\n super().__init__(cls, {})\n\nclass Class(Base):\n def __init__(self, name, base_class, fields, metaclass):\n super().__init__(metaclass, fields)\n self.name = name\n self.base_class = base_class\n\nOBJECT = Class(name="object", base_class=None, fields={}, metaclass=None)\nTYPE = Class(name="type", base_class=OBJECT, fields={}, metaclass=None)\nTYPE.cls = TYPE\nOBJECT.cls = TYPEWhich you can use like this (test code also taken from CF’s post):
\nA = Class(name="A", base_class=OBJECT, fields={}, metaclass=TYPE)\nobj = Instance(A)\nobj.write_attr("a", 1)\nassert obj.read_attr("a") == 1\n\nobj.write_attr("b", 5)\nassert obj.read_attr("a") == 1\nassert obj.read_attr("b") == 5\n\nobj.write_attr("a", 2)\nassert obj.read_attr("a") == 2\nassert obj.read_attr("b") == 5There’s a bit of delegation going on in the Base class because the post\nalready anticipates what we’re about to do: swap out the Instance\nimplementation for _read_dict and _write_dict for better performance.
OK, let’s add on this “map” data structure. The purpose of the map is to do\nthree things:
\nGet out of the business of dealing with strings and hashing in the fast
path. We would like to instead do operations on small integers.
Remove the indirection. We would like to store the attributes in-line in the
object instead of elsewhere in memory.
For the former, we can think of an object’s map field as an (database) index or\na write-through cache. It is responsible for reflecting on the layout of a\ngiven object:
\nThis model is mostly there...
\nYou can ask the map questions like “what attributes does this object have?” and\n“where is attribute a relative to the start of the object?”
Just looking at the diagram, it may seem silly: after all, we have exchanged\none hash table for another. There’s one big difference, though, which is that\nin the shape model, we don’t have to always use the hash table. If we\nremember the offset since the last time we looked it up in the shape, we can\nre-use the offset. This mostly appears in an interpreter feature called an\ninline cache.
\nThis brings us to the second bit: if we have the offset into the object, we\ncan read right off of it. No need to go do a second load from another region of\nmemory. We have the object in hand and hopefully already in the cache.
\n…At least, until the map changes. Then we can’t re-use the offset. Remember, these languages encourage this\nflexibility. An object could gain or lose an attribute at any time. What then?\nIdeally we have a very fast check that can tell us if the object’s in-memory\nlayout changed.
\nThis brings us to the third bit. We need to be able to rely on the map to\nbe immutable, up-to-date, and a stable identifier for a given in-memory layout.\nThis way we can do a very quick check (“is the map the same as last read?”)\nbefore a load.
\nThis means that when we add a new attribute to an object, we need to give it a\nnew map. Maps are actually trees (tries?) and are allocated like a persistent\ndata structure. Every new object starts with an empty map. As the program adds\nattributes, it follows the edges in the tree to find or create its new map.
\nImage from CF Bolz-Tereick, CC BY 3.0.
\nI recommend reading the section on\nmaps\nbecause it goes into a little more detail.
\nKeeping all of that in mind, let’s take a look at CF’s Python implementation of\nobjects-with-maps and also of maps themselves:
\nclass Instance(Instance):\n def __init__(self, cls: "Class"):\n super().__init__(cls)\n self.map = EMPTY_MAP\n self.storage = []\n\n def _read_dict(self, fieldname):\n index = self.map.get_index(fieldname)\n if index == -1:\n return MISSING\n return self.storage[index]\n\n def _write_dict(self, fieldname, value):\n index = self.map.get_index(fieldname)\n if index != -1:\n self.storage[index] = value\n else:\n new_map = self.map.next_map(fieldname)\n self.storage.append(value)\n self.map = new_map\n\nclass Map:\n def __init__(self, attrs):\n self.attrs = attrs\n self.next_maps = {}\n\n def get_index(self, fieldname):\n return self.attrs.get(fieldname, -1)\n\n def next_map(self, fieldname):\n assert fieldname not in self.attrs\n if fieldname in self.next_maps:\n return self.next_maps[fieldname]\n attrs = self.attrs.copy()\n attrs[fieldname] = len(attrs)\n result = self.next_maps[fieldname] = Map(attrs)\n return result\n\nEMPTY_MAP = Map({})You may notice that the storage is not in-line, as I had originally promised.\nThis is because we don’t have that kind of object layout control in Python.\nAttribute storage, when implemented in a language such as C++ or Rust, is\ntypically in-line with the object header.
\nIgnoring that, though, we can see that the common case still seems to read and\nwrite attributes using string names. What gives? Well, let’s use the index\nstorage as intended in an inline cache.
\nLet’s start by looking at the string attribute API. We’ll make a point class and\nread the x attribute. We’ll keep the attribute name constant since this is\ngenerally fixed in the program: obj.x normally looks like some bytecode\nLOAD_ATTRIBUTE, "x" where the name x is embedded in the bytecode somehow.
This is important for the inline cache: varying the receiver is one thing but\nvarying the name being looked up adds a lot more complexity. It’s doable but\nirritating.
\nPoint = Class(name="Point", base_class=OBJECT, fields={}, metaclass=TYPE)\nP = Instance(Point)\nP.write_attr("x", 5)\nP.write_attr("y", 6)\n\n# String API :(\nP.read_attr("x")\n# Always looking up index :(\nP.read_attr("x")\n# Every time :(\nP.read_attr("x")Then we will make a memory/speed trade-off. We will allocate space for the\naforementioned expected map and the cached index mentioned earlier. This\nlets us do a really fast check followed by an indexed load in the (hopefully)\ncommon case.
\nThe logic is as follows:
\nIf the attribute is missing, we don’t (for now?) cache the negative lookup.\nHopefully this case is rare.
\nclass InlineCache:\n def __init__(self):\n self.map = None\n self.idx = None\n\n def read(self, obj, fieldname):\n obj_map = obj.map\n if obj_map is self.map:\n return obj.storage[self.idx]\n index = obj_map.get_index(fieldname)\n if index == -1:\n return MISSING\n self.map = obj_map\n self.idx = index\n return obj.storage[index]\n\nIC = InlineCache()\n# Looked up by string :(\nIC.read(P, "x")\n# Map hit! Looked up by index! :)\nIC.read(P, "x")\n# Map hit! Looked up by index! :)\nIC.read(P, "x")You may note that I used is (pointer equality) instead of ==\n(user-defined/deep equality). This is intentional! Because we are guaranteeing\nthe maps are immutable, we don’t need to check equality on the fields of the\nmap; just its pointer/numeric ID.
This InlineCache class is mostly just a “sketch” of what an inline cache\ndoes. It is an “interpreted IC”. This shape, if you make sure the fast path is\ninlined and the slow path is outlined, can help your interpreter a lot. It does\ndefinitely improve performance—I recommend benchmarking a silly little\nattribute lookup function—but most runtimes with inline caches also come with\nJIT compilers. These compilers try to remove the “interpreted”-ness of the\ninline cache implementation. See for example:
Slava’s post that
explains with IR sketches and JS-like pseudocode
\nalso this older one
which is similar
[Caio’s
post](https://caiolima.github.io/jsc/2020/03/12/jsc-inline-cache.html) that\nexplains what this looks like in JavaScriptCore with x86 asm
that explains what this looks like in pseudo-asm for speculative numeric addition
\nmostly runtimes don’t do self-modifying asm ICs like this because of W^X
protection and also you need to flush the icache
Another thing to notice is that order matters. Adding attributes in different\norders (e.g. a then b vs b then a) will result in different shapes.\nAnother frequent cause of this is conditionally storing attributes in\ninitialization (e.g. if cond: self.a = 1).
This shape and cache behavior is not really visible to the application\nprogrammer except in performance regressions2, where either\nyour inline caches will frequently miss or you will not have optimal\n(monomorphic) caches. This might not sound scary but the difference between a\ncache hit and a cache miss in a hot path could be 2x performance or more and is\nworth investigating in your application.
\nAlso, quantity matters. VM implementors measured and determined that most\nobjects are small (<20 ish fields). You may find that putting too many fields\non an object leads to it getting penalized and put back in “hash table mode”.\nRuby, for example, has some fixed number of in-object instance variables\n(attributes) before its shape becomes “complex”.
\nLast, notice that this cache is not specific to this object; any number of\nPoint instances can get a cache hit. Actually, looking at it, an object need\nnot even be a Point…
What does it mean that two objects with different classes can have the same\nshape?
\nFoo = Class(name="Foo", base_class=OBJECT, fields={}, metaclass=TYPE)\nF = Instance(Foo)\nF.write_attr("x", 1)\nF.write_attr("y", 2)\n\nBar = Class(name="Bar", base_class=OBJECT, fields={}, metaclass=TYPE)\nB = Instance(Bar)\nB.write_attr("x", 3)\nB.write_attr("y", 4)\n\n# Same shape/map!\nassert F.map is B.map\n# But different class!\nassert F.cls != B.clsFor one, it means that the inline cache may have a higher hit rate. Instances\nof subclasses that share code, for example, may still count as monomorphic in\nthe IC.
\nIt also means that you can’t use the shape as a proxy for knowing about the\nclass. If you have something like attr_reader in Ruby, where the VM generates\na synthetic method just for looking up an instance variable, you need to do two\nthings:
attr_readerThis two-stage lookup adds both complexity and run-time overhead. If we\nspecialized maps so that having a different class implied having a different\nmap, we would be able to specialize that two-stage dispatch with just one field\nload.
\nThis is kind of an interesting idea: what else can we specialize the map on?
\nPerhaps unsurprisingly, CF Bolz-Tereick reappears with Lukas Diekmann and\nLaurence Tratt in Storage Strategies for Collections in Dynamically Typed\nLanguages (PDF, 2013).
\nThe main idea is that some facts about objects (properties, attributes, har\nhar) are both:
\nworth splitting/monomorphizing on (there is some kind of “payoff” for the
increase in branches and code size)
similarly sensitive to code location (int lists allocated here, float lists
over there)
Their treatment is for collections (for example, optimizing the common cases of\nan empty list, or a list of small integers, …). In addition to giving more\ninformation to the optimizer, it helps both reduce memory and reduce pointer\nchasing.
\nThis kind of thinking extends beyond collections: do you ever have objects\nwhere an attribute is always a certain type? Maybe your Point class always\nhas floats in it? Consider, then, what I think of as CF’s follow-up paper, type\nfreezing: Type Freezing: Exploiting Attribute Type Monomorphism in Tracing JIT\nCompilers (PDF, 2020)
This paper changes object maps from {name: offset} to {name: (offset,\ntype)} to reduce guards. Then it goes further by even addressing nested\nattributes and their types. This nesting extension is mostly motivated by the\nmeta-circularity of the implementation and would have less impact for a\n“normal” runtime.
See also:
\nYou can make even stronger bets about classes. See for example the PyPy blog\nclass versioning\nsection.
\nI felt like this blog post would not be complete without a manual memory layout\nrehashing of CF’s article. It’s all well and good to write the Python but what\ndo “real” runtimes look like?
\nWell, they have compact object headers that contain the shape/map and some\nother flag bits. They allocate their attributes inline with an object. And they\nprobably also have an “overflow” slot for when their initial object sizing\nestimates were too small.
\nSo I made a very very small runtime in C++ that allocates objects and adds\nattributes and has a shape system. It is probably riddled with bugs. But it\nsketches the kind of memory layouts that underpin Skybison, V8, JSC, and so on.
\n\nIt doesn’t have the overflow slot but it’s a decent sketch of the underlying\nmodel.
\nI fear I am running out of steam on this blog post but there is more to talk\nabout. I originally wanted to go add object shapes to someone’s Lox interpreter\nand then add inline caches to the interpreter.
\nPerhaps I will come back and update this post. Or perhaps you will write a\nsequel.
\nThank you to CF Bolz-Tereick, Nery Campusano, and Jacob Denbeaux for thoughtful\nfeedback on this post.
\nOr the following equivalents…
\n // Or\n function C() {\n this.a = 1;\n this.b = 2;\n }\n // Or\n class C {\n constructor() {\n this.a = 1;\n this.b = 2;\n }\n }\n
See [this Rails
PR](https://github.com/rails/rails/pull/57020) by Hartley to make shapes\n more monomorphic. It was initially filed because ZJIT was not capable of\n handling shape polymorphic reads, but it helps other JITs stay monomorphic\n too. Also in this vein is my PR to\n optcarrot.
\nZJIT now does much better with polymorphic shapes but this kind of stuff is\n generally important across languages and runtimes. Enough for people to do\n large bodies (PDF) of\n research (PDF) about\n intelligibly surfacing this kind of information to the application\n programmer. ↩