Structural inheritance doesn't work where you expect it to
10 points by rbr
10 points by rbr
Oh, thank you for posting this! (I think... I'm not sure what the etiquette is about thanking/commenting when your writing gets posted?)
Author here, so if you have some of those rotten tomatoes to throw, now is a great time :)
A few notes:
// note: fixed some types
struct BaseElement {
s16 left;
s16 top;
u16 width;
u16 height;
}
struct ButtonElement {
BaseElement base;
bool toggled;
}
struct TextElement {
BaseElement base;
char* value;
}
Our TextElement itself then probably still has a user-definable position somehow, but its width and height values become dependent on the actual text value. Depending on the details of the system, at this point the actual width and height properties might become unused as it may be cheap enough to simply calculate the resultant size of the text from the string dynamically. Even if that is not the case, the properties at the very least become merely caches of calculated values: they are not the source of truth that they once were.
In most GUI systems, a text area has a defined size, and the rendering of the text is forced into that size, and potentially occluded, with or without wrapping, and with or without scrollbars. It's actually a nightmare to deal with, or at least it was on Windows. (I never got to do much GUI work on any of the real OSs.)
--
But the big point that you seem to be missing is that columnar designs (often used by nice DOD impls) don't avoid these issues. I've done some big-data OO impls in the past wrapped around columnar data structures, and the overall waste is dramatically lower (e.g. due to region based memory management and very little pointer chasing), but columns often end up sparse as a trade-off. It's a good trade-off, but it's a trade-off. And pretending that engineering trade-offs don't exist is disingenuous and self-defeating.
Yeah, the GUI example ended up being too much of a red herring: I haven't tried to write a GUI library, so I hand waved too much of it and it ended up being too far from a real system. The idea behind the "properties become just caches" was that if we were to write the very lowest levels of a GUI from scratch and we started with a text element that just has the capability to render some text without bounding or alignment, then the way to introduce aligning, cut-offs and, ellipsis would be by adding a surrounding box element that somehow bounds the rendering. I was vaguely thinking of a DOM span element inside a div where the div gives the bounds while the span contains the actual text.
I'm not sure where I pretended that engineering trade-offs don't exist; I even refer to them explicitly twice in the text. It's all just trade-offs, and when in doubt I prefer columnar designs and interface inheritance over structural inheritance.
It also kind of sounds like your columnar design indeed did avoid much of the memory wastage at least. Sparse columns indeed follow, but that's what we wanted in the first place: to avoid storing data that is rarely needed. (Then just make sure it's actually rare data, so that you don't end up with a largely filled up sparse column taking multiple times the memory you started with! :D )
No need for thanks! I liked ghe GraphBuilder/Graph example where you show that structural inheritance works in neither direction.
I personally like it when an author announces they're on lobste.rs. I'm not aware of any formal rules.
Thank you! With the GraphBuilder/Graph example, I do of course still think that it is unfortunate that I am doing copy-paste in two different classes but at the end of the day the way the whole system shook out was one where structural inheritance in the normal TypeScript defined fashion would not have given me the features or guarantees I wanted.
If TypeScript supported it, I might use structural composition in this case to cut down on the repetition, although that is still not necessarily feasible as the GraphBuilder has many Uint32Array fields, whereas the Graph replaces those fields with Uint8Array | Uint16Array | Uint32Array: in the builder case I don't want to waste time calculating the correct byte width needed for the graph's data but once the graph is finished I do want to squeeze out any unnecessary memory usage from the final product. So here even structural composition seems like it would not work; the some field types are actually more restricted in the larger GraphBuilder class than in the smaller final Graph.
A final wrinkle is that I am now working on a third DynamicGraph class which is a mix between the two others: it contains a complete graph but it can also be extended and mutated, and finding nodes in it is often quite important, but on the other hand it should also be minimized in memory if it stays unchanged for a long time. All in all, it's a fun pickle to chew on :)
Hello!
structural inheritance (as I am talking about it) means inheriting the memory layout of the superclass, such that a pointer to a subclass instance can be directly used as a pointer to a superclass instance: reading inbounds offsets from such a pointer will read exactly the same (kind of) data regardless of if the pointer points to a subclass or superclass instance.
Do you mean to exclude calling base methods directly on the subclass instance or is that meant to be implied by the above definition?
I do imply it to be included in the definition, since a superclass method can trust that its pointer offsets are valid even if used on a subclass instance, and point to the same type of data as they did on the superclass.
Whether a language allows calling superclass methods is then of course up to the language. In JavaScript/TypeScript you can always use SuperClass.prototype.publicMethod.call(subClassInstance) to perform such a call even from outside the class. In C++ I believe you can use SuperClass::publicMethod() to do the same, at least for calling superclass virtual methods inside a subclass method, but I doubt it's possible to do so from the outside. Effectively, I think that a ReadOnly subclass that overrides all the write-methods of the ReadWrite superclass that is marked final can indeed trust that the mutable fields are actually read-only (assuming that the ReadWrite class doesn't have any public non-virtual mutating methods, of course!).
In C++ I believe you can use SuperClass::publicMethod() to do the same, at least for calling superclass virtual methods inside a subclass method, but I doubt it's possible to do so from the outside.
you actually can! you can always refer to anything by its fully-qualified name: https://gcc.godbolt.org/z/EbEnxYc9E
The GUI example mixes up a few concepts that pretty much every layout engine has to deal with: intrinsic and extrinsic sizes.
This happens every time there’s some sort of layout happening. And there’s simply no solution if you want to maintain a certain amount of API ergonomics. I see OP has some exposure to the web so let’s take that as an example.
A node has an intrisic size. Say, an img element has its intrinsic size equal to the image. That image is going to be layed out somewhere on the page. With not constraints it will just use that intrinsic size. But if we apply some sort of constrint to it the image will take a different amount of space and can be at a different position on the page. These are calculated position and size. Moreover, image can be completely hidden rendering all the positions and sizes irrelevant. A hidden image is a complete waste of memory.
However, unless you can be absolutely sure the image won’t be shown at all it’s better to keep all that memory around. It’s easier that way because you have a stable structure and interface to the image. You can save some memory by representing a hidden image with a smaller structure (you don’t need any of the positions and sizes, and even decoded pixel data) but you’d have to convert the hidden image to a regular image every time the image is shown. Likewise, you can represent image that uses intrinsic size and one that doesn’t by different structures but you’d have to convert between those every time image layout changes (and there are a lot of ways it can change: window resized, user interaction, scripts, new styles loaded, image finished loading, the image relocated in the DOM, sun position changed (and that made the system switch from light to dark mode, which triggered media query, which made new styles apply), and many, many others).
The point is that from the theroetic point of view distinct types (classes in case of OOP) are better in practice they introduce too much complexity into the final program. Collapsing multiple closely related concepts into a single type (class) greatly reduses cognitive load and many are ready to pay some price (wasted memory, performance) for that.
Yup, I didn't really want to write a whole treatise on how an actual layout engine might be built (it's not my area of expertise, I'm just a web developer by trade after all) since all I really wanted to show was a very simple structural inheritance hierarchy making some naive but seemingly reasonable assumptions (a GUI element has a location and size) and how that then leads to unfortunate results in terms of memory usage that cannot be fixed without breaking the inheritance hierarchy itself.
Or perhaps it's more accurate to say that fixing the issues requires making the inheritance closer to an interface inheritance (individual elements don't have location and size data fields, they have APIs to get or set them).
It only (partially) fixes the memory issue. Interface still has position and size methods even in contexts where those are completely ignored. For example, the element is completely laid out by the parent element (both position and size) but inherited methods for position and size are still present. And while reader methods might return some useful information, setter methods have no influence on the position or size of the element. So depending on the context in which the element resides (e.g. being completely or partially laid out by the container, or being raid out by itself) different interfaces make sense. Do we want to have different types (classes) to represent those? Do we want to convert between types (classes) when the context changes?
Yup, that's true: layout elements will make setters mostly meaningless for the elements contained within. The answers to the questions posed then of course depend on the engineering trade-offs made and preferred by the architects of the system.
I guess in an ECS-kind of system (which I am effectively promoting here, though not directly or unconditionally) the element itself would or might have a static identity, but either it's archetype would indeed change, or it would refer to a layouting component of a different archetype, depending on the context. But, I've not tried to build an ECS-based layout system do I don't really know if it works well or at all :)
I think this is an interesting discussion and has some insight, but I still don't think the concluding example is correct. First, I'm not sure that structural inheritance is really at issue, so much as the painful issues surrounding mutation. The conclusion seems much narrower than structural inheritance not working, something more like "structural inheritance cannot be used between types that differ in mutability."
And mutability is already a major pain point, even for interface inheritance. A reason generic types in Java are invariant rather than covariant or contravariant is that neither covariance or contravariance work properly for collection types that have mutation.
I also think you're giving short-shrift to the solution of having a private type that both GraphReadOnly and GraphReadWrite extend. You say this makes GraphReadOnly immutable in name-only, but as long as the mutating methods are private, it just means that you have to make sure the GraphReadOnly class doesn't call any mutating methods in its own definition.
Thank you for the comments! I definitely am painting using a broad brush of black paint here because, at my core, I simply don't think inheritance generally is a great feature; I'm thus over-eager to make it look bad :) In a sense what I wanted to highlight with the mutability example is that even when the data is largely the same and only its interpretation or usage is mildly different, structural inheritance still causes issues. In the earlier GUI case it works "fine" but you have to accept that some data members are unused and child classes keep growing in size; I consider this a problem and don't really want to accept it, so to me this is a case where structural inheritance fails. The mutability case then exists to show structural inheritance in a place where it should stand the strongest, since the data is mostly the same, yet still falls flat.
I think you're also correct in accusing me of being unfair to the "common base class" solution. Here, I am being coloured by the JavaScript language and TypeScript type definitions on top of it, as this question was asked in a TypeScript codebase: for GraphReadOnly to guarantee that mutating methods don't get called, it must be final but that is not something that TypeScript supports at all. Even if TypeScript had a final keyword for class inheritance, JavaScript does not have it so it would be at most a build-time sanity check (though that would be already be a really good thing; the readonly nature of the data fields is also just a build-time sanity check). I'm also using JavaScript private properties for the data fields and only exposing their data through methods, and private properties are not accessible in subclasses at all except through methods, and methods are either fully public (TypeScript can inject build-time sanity checks here again) or fully private and cannot be called in sublcasses. In effect, in JavaScript it isn't possible to use subclassing and methods to build a "common base class" that would have read and write methods that could then be subclassed twice such that one "half" somehow seals off the write methods. The blame is largely on the language here. (You may also notice that I'm trying to code in a fairly defensible fashion; this is both to guard against future developers from misunderstanding and making mutations to the ReadOnly class data, and to add a layer of defense in depth against actual malicious actors as the code base in question here is an automation control system user interface.)
Though I must admit, I also don't really see the "common base class" solution being all that elegant in other languages either: the best I could imagine is for the base class to define the mutable data fields and the read methods, and for the GraphReadWrite subclass to then extend that with write methods. The GraphReadOnly probably then only exists to say that it is final, which it must as otherwise a subclass of GraphReadOnly can be made that mutates the data fields again. Effectively, we've gone from having two classes to having three classes but nothing much has really changed.
So I’m not convinced that this is really a problem with inheritance itself so much as with baking things into a design too early and then being unable to remove them later even once they have become almost completely obsolete.
We see this all the time in large projects either because stuff has made it into public schemas and values must be preserved or because some small set of cases still use that thing, but they aren’t neatly contained.
I’ve hit the latter problem recently. I know I can save at least 16 bytes per struct in a system if I can find two spare mark bits in a related descriptor, and some extra work on serialisation. I am not convinced I have two free mark bits without blocking other future work, so for now every struct is going to pay the price.
That's perhaps fair, although I'd argue that a nearly obsolete is cheaper to carry around in your code base than a nearly obsolete data field. Then again, it is easy to say that interfaces make everything better but at some point the rubber has to start hitting the road, and those two mark bits need to be placed somewhere. Trying for an interface based approach to a couple of mark bits is then unlikely to win any friends in coworkers or in the CPU branch predictor.
Read and comment along.
"Structural inheritance" is a pretty unusual way to phrase the concept. By hearing "structure," I would think about structural subtyping, but this article's definition is more about inheriting data.
I don’t have much to say about the GUI example since I don’t really know that area. You seem to be talking about the semantics downside (inflexibility, multiple sources of truth) and performance issues (memory waste) together. For the former, I completely agree.
Regarding memory waste, I’m not sure how significant the impact is in practice. For most use cases, it probably doesn't matter. Though I think if you need performance, writing in a deliberate and data-oriented way can help a lot. Though this rabbit hole goes far beyond "don't use inheritance for small objects."
I like the Graph example. I have had similar experiences in the past. The copy-pasting can probably be mitigated with helper functions, and it is better than having superclasses actively interfering with subclasses' invariants.
Thank you for the read and comments!
The term of "structural inheritance" ... I'm not exactly sure where I picked it off of, but it is sometimes used to differentiate between inheriting/implementing interfaces and inheriting concrete classes.
The GUI example is admittedly both too simple and too mixed up with itself. I kind of wanted to show the "Curse" as it appears in simple cases because I do consider it a problem even though it oftentimes is bening, before I go to the Graph example where it appears in a supporting role and the main problem is that we simply cannot really find a neat way of expressing what we want using structural inheritance. I didn't really have the semantic downsides in mind, specifically.
Hmm, I’ve been using OOP heavily since Smalltalk in the mid-80s, and I can’t recall this being a problem for me.
Yes, a data member of a superclass might be unnecessary in some subclass. It’s usually just a few wasted bytes, not enough to make a difference. (Wasting a coord pair in a view is maybe 8 bytes. If you have 100 views in your window, that's 800 bytes. If you have a lot more views than that, it’s the layout engine that's going to cause performance problems, not a few KB of wasted space, and you should look at other mechanisms like AppKit's old NSCell.)
If you don’t want to inherit data, use interfaces instead. Or the PImpl idiom from C++ where the data is moved into a separate object.
It's true that this is probably often not that big of a problem, perhaps especially in native GUIs. On the Web and JavaScript side I do feel that this is more of a problem, though. Website DOM trees regularly grow into thousands of nodes or more, and the number of JavaScript objects in flight at any time is probably easily in the 100,000's. I haven't gone in and analysed what eg. Chrome's DOM tree node looks like, but I'd wager a guess that a good bit of its data goes unused in the common case. For JavaScript objects, in the common case they generally waste at least 8-16 bytes each depending on the exact browser / JS engine, and then anything more "in depth" than a plain object or array is liable to splurge on unnecessary memory to the tone of 40 bytes or more. It's little wonder that browsers eat up all of your RAM and dare to ask for seconds.
But: in the end this is just my hobby horse. This is not the most important problem in the world, it's just what I like to concentrate on :) And indeed, use interfaces instead!
This is more an issue of standards than inheritance. The origins of the DOM go back thirty years, and once something is baked into an API or structure it’s hard to ever remove it.
The standards don't define the memory layout, and it is possible to build engines to be much leaner by avoiding structural inheritance. The Nova engine (which the blog actually belongs to, though I'm kind of using it as a mildly personal blog as well) is an attempt at making such a JS engine successful, and it is my understanding that the Servo browser engine uses similar architecture in their DOM implementation.