How to make Lisp go faster than C (2006) [pdf]

It's a fun paper that does a good job at presenting a the first few steps worth taking towards implementing well performing dynamic object models and showing that it may be worth considering those methods when writing C that requires different behaviour for different data structures over writing static code in those specific cases, but people have been writing vtable based object models for C "forever" that solves enough of those problems that it's rarely worth going the extra mile to get the dynamic model they present in the paper.

When you actually need it, it's very useful to know these tricks, though, and for those unfamiliar with dynamic object models it's a great introduction.

That said, it does miss one other simple trick that's worth considering. For inheritance it searches parents, and this is a large part of what makes the "bind" expensive and so makes the inline caching worthwhile.

Protocol extension [1] provides a way to do this which can be implemented either as cheap as vtables for calls (costs more memory) or one indirect load more expensive (more space efficient). Basically the fastest approach is to make all vtables big enough to accommodate individual slots for each method name. The "slow" approach groups methods in interfaces and gives you a "vtable of vtables". Couple that with a simple method propagation algorithm that lets you override methods like in this paper but respects sub-classes overriding a method (by seeing if the pointer to the function implementing the method matches that in the parent vtable), and that's it.

You might think this blows up really badly. But in practice in experimenting with in-progress-and-may-never-be-finished Ruby compiler, the memory overhead tends to be surprisingly small - few projects have large enough number of classes and large enough numbers of unique method names for it to be a major issue, but the two approaches can also be combined with fallback to more indirection). Even with a singly-rooted object hierarchy like Ruby it doesn't seem likely to be a big problem, and for a language implementation you can "mix and match" and put the most common method names in a shared vtable and fall back to more expensive lookup methods for less common methods if necessary to save memory.

The main benefit comes with megamorphic call-sites (places where the vtable used for the call will frequently change at any given call-site, and where you thus otherwise end up falling back to the expensive method lookup very often), which is no more expensive than monomorphic call-sites with protocol extension.

[1] Protocol Extension: A Technique for Structuring Large Extensible Software-Systems, 1995, Michael Franz https://www.semanticscholar.org/paper/Protocol-Extension%3A-...

https://news.ycombinator.com/newsguidelines.html

So yeah, the Lisp love here goes deep.

Personally I'm in favor of removing "downvote to oblivion" because it degrades my experience of using HN.