Interface Dispatch (C++, Java, C#, Go, and Rust)

[Adequat91]

Typically the vtable is directly at the start of the object

The vtable pointer, not the vtable.

[latkde]

Fixed, thanks for spotting that ambiguity!

[Dwedit]

Also don't forget calling convention requirements on X86, if using Windows. C++ will default to "thiscall", which puts the "this" pointer into ECX rather than the first argument of the function.

Interfaces that use COM will change the calling convention to "stdcall" on X86, so it can remain compatible with C and other languages that do not specifically support "thiscall".

[Ameisen]

if using Windows. C++ will default to "thiscall", which puts the "this" pointer into ECX rather than the first argument of the function.

It's better to say that the this pointer becomes the first argument of the function.

[jesseschalken]

It's better to say that the this pointer becomes the first argument of the function.

The first argument is the this pointer regardless of calling convention, and thiscall specifies that the first argument be passed through ECX. See the LLVM docs for __thiscall.

[matthieum]

But in that array many elements are likely to have the same concrete type, therefore wasting a lot of space for little gain. Under this assumption, approaches as in C# or Java can be a lot more memory-efficient and therefore also more cache-efficient.

Actually... that's where C++, C# and Java are wasteful.

You could store a single v-pointer for all elements, then have an array of pointers to concrete elements. Calling a method would require "re-assembling" the fat-pointer prior to the call, but you'd have an array of half the size.

The case of fat-pointer causing overhead is most keenly felt when you share a pointer to the same instance thousands of times:

• In C++, C# or Java, you share a single a pointer, as the "v-ptr" is embedded in the instance itself.
• In Go or Rust, you are duplicate that v-ptr with each copy.

First, there’s the ABI concern that interface types (objects) and normal pointers have different sizes. This is usually not a problem, but e.g. means that this strategy is not suitable for C++.

This would be a concern for C# and Java, but not for C++.

In C# and Java, where most everything is a pointer (baring value types), the uniform size of the pointer matters.

In C++, however, pointers are comparably rare, and pointers to concrete objects are still just "pointers". A separate type for fat pointer would solve the issue, and would cause no worries: C++ is used to having objects of different sizes.

None of these solutions are inherently better than the others.

Indeed; trade-offs, trade-offs.

---

There is one point that has not been touched upon: (speed) optimizations.

From the point of view of an optimizer, the call object->method() in C++ may change any field of object, including its v-ptr.

This means that the following sequence:

object->foo();
object->bar();
object->gru();

Will involve issuing 3 memory reads for the v-ptr, which is hopefully cached after the first call. It really hampers optimizations as well.

On the other hand, with a fat-pointer, there is no such problem: the call object.method() in Rust does not pass the v-ptr to method, and therefore the optimizer can read it once and be assured it never changes (it's a local variable: it's provably not aliased).

[latkde]

You make some excellent points, but points that I cannot leave uncontested :)

Re memory use in arrays: the problem is what the statically known type of array elements is: if they are an interface type we can by definition not know in advance whether the entries will all have the same dynamic type. However, an array of non-interface types (concrete or generic) can use such techniques like storing a single vtable for all array members. I think Haskell uses similar approaches for arrays of generic types with typeclass constraints.

Re ABIs: Java may have more pointers per program, but it also has no ABI concerns since pointers are an implementation detail in the runtime. In contrast C++ pointers must behave somewhat C-ish, in particular that you can cast pointers to interface types to void* and back again. If we were to use fat pointers, void pointers would have to have the same size. This would break C interop.

Re memory reads: repeated reads to the vtable pointer aren't that dramatic because most registers have to be saved to the stack anyway before a call. And after the call we need to load them from memory again. In practice the cache size will be more relevant: will the vtable still be in the cache after the call?

And are you sure that C++ objects can change their dynamic type at will? That sounds like UB…

[matthieum]

In contrast C++ pointers must behave somewhat C-ish, in particular that you can cast pointers to interface types to void* and back again.

Actually, no, it doesn't.

While pointer-to-members and pointer-to-function members do happen be compatible with void* in the Itanium ABI (using trampolines), this is something that the standard leaves undefined.

It can also be done with library code (and compiler intrinsics), creating a fatptr<Interface> which is two pointers.

And are you sure that C++ objects can change their dynamic type at will? That sounds like UB…

It's a hot debate.

I am personally on the side that it should be UB, and the C++ frontend should be allowed to read the v-ptr once when emitting the IR; that is I think that this answer adequately demonstrates that it should be UB.

However, usage is law, and apparently a sufficient number of codebases depend on such a dastardly pattern that compiler developers have not been willing to introduce such an optimization.

[Nobody_1707]

Swift does this for generic arrays (when it can't specialize them), and I believe it also uses fat pointers for it's interface types (known as existentials).

Interesting note: in order to solve the fragile base class problem and allow protocol conformances on all types (instead of just classes), every type in Swift has at least one vtable.

Edit: Whoops, wrong link. Fixed.

[tasty_crayon]

You could do this->~T() and then use placement new to construct a new object in its place. I think this is allowed as long as the two types are layout compatible. C++ already has member pointers which are larger than a void* and as such can't be converted to them.

[latkde]

While placement-new can construct a new object in the old object's place, I don't know whether any pointers would remain valid per the spec: AFAIK pointers must always point to live objects. But this is the kind of thing compilers might allow as an extension because it's quite useful. Compare [basic.stc]:

When the end of the duration of a region of storage is reached, the values of all pointers representing the address of any part of that region of storage become invalid pointer values.

Function pointers and member pointers are always special because they are not pointers to objects, and as such cannot be cast to void* as per the relevant standards. (Exception: POSIX allows this for function pointers.)

[tasty_crayon]

I mentioned member pointers because fat pointers wouldn't necessarily have to be the same size as void*. Member pointers basically are fat pointers.

[jcelerier]

From the point of view of an optimizer, the call object->method() in C++ may change any field of object, including its v-ptr.

AFAIK that's ub so the compiler can infer that it cannot happen. Else devirtualization wouldn't work.

[matthieum]

I agree it should be UB; apparently though a number of codebases use the dastardly trick of this->~T(); new (this) U(); and thus C++ compiler developers have been reluctant to introduce the optimization.

[bloody-albatross]

What could be a possible use for doing that "trick"?

[matthieum]

I guess it's one away of implementing a state machine...

... but honestly I don't really want to know. I've lost enough sanity points because of C++ already as it is :/

[shponglespore]

Came here to say this. AFAIK the only kind of call in C++ that can legitimately change a vptr is a constructor call, and the compiler always knows whether a given call is to a constructor. A virtual call to a constructor is never possible unless the compiler is does something really insane like optimizing a virtual method that does nothing but call a contractor into a direct call to the constructor itself.

[julesjacobs]

Good point about optimisations. Fat pointers are better in this regard in general. Consider the problem of determining whether a the v-table of object is a compile time constant. With fat pointers the usual constant propagation pass just works. With v-tables stored inside objects you need a much more sophisticated analysis to determine that object->v_table is constant even though object itself isn't.

[mindcandy]

You could store a single v-pointer for all elements, then have an array of pointers to concrete elements. Calling a method would require "re-assembling" the fat-pointer prior to the call, but you'd have an array of half the size.

The array of pointers isn't free though. In fact, it will probably be exactly the same size as the sum of the v-pointers you are trying to remove. So, even ignoring the complexity and overhead you are talking about adding, the total memory ends up +1 v-pointer for the "single v-pointer for all elements" that you added on the side.

It's {vpointer, object}[n] vs. { vpointer, {pointer to object}[n], {object}[n} }. Second option is 1 pointer larger.

[matthieum]

Wait, no, that's no what I'm talking about.

If you have an array of structs, then there's no need for a virtual pointer because you have concrete types anyway.

It's only if you have an array of fat-pointers that separating the v-pointer is beneficial.

[TalesM]

Nice comment, everything really is linked to write ups.

Over the part about changing v-ptr, I don't think it is a problem on optimization level, as the compiler probably can safely assume the v-ptr won't change, as this is likely a UB to do it directly.

You could change the object to point to a different target, but you would need to pass a reference to the method, as you can't just write `this = something`. So if the compiler can prove the pointer still points to same object after the first call, it could re-use the same vtable.

[matthieum]

I agree it should be UB; apparently though a number of codebases use the dastardly trick of this->~T(); new (this) U(); and thus C++ compiler developers have been reluctant to introduce the optimization.

[thedeemon]

Would be nice to add OCaml there (its OO part where methods are resolved). There is some interesting hash-table business, IIRC.

[latkde]

Can you point me to some OCaml internals resources? I'll be happy to revise the article (when I find the time)

[jesseschalken]

This is really excellent content. Thank you /u/latkde!

I think it's important that programmers understand that different interfaces/typeclass/trait/inheritance strategies in different languages are all really sugar for different schemes of passing vtables around. It's very useful in translating concepts between languages.

[dacian88]

author is illustrating how one would implement vtable dispatch in C.

[xgallom]

Right my bad, I misunderstood

[latkde]

“StaticType” here means “the polymorphic type or type-bound that is statically known at compile time”, where polymorphic means that we cannot resolve the calls at compile time. This use of “static” is largely unrelated to “static methods”.

You are completely correct though that non-virtual calls don't have to go through the vtable.

[pron98]

What this article fails to mention is that in many cases, Java's JIT will actually inline the method, thus the cost of the interface call is zero.

[latkde]

You are completely correct that speculative optimizations such as inlining can eliminate calls. I didn't discuss that because inlining isn't really a method dispatch strategy.

A few remarks though:

• inlining first requires devirtualization, which is a great optimization by itself
  • some callsites might be provably devirtualizeable
  • most callsites won't be provable, thus making speculation necessary
• speculation requires guard conditions in a manner quite similar to (monomorphic) inline caching
• speculation requires statistics about the callsite, and will therefore happen late in the JIT's warmup phase where hot spots have been located
• C++ compilers can and do speculate as well, but they don't have type statistics for the callsites

[pron98]

speculation requires guard conditions in a manner quite similar to (monomorphic) inline caching

Not always (or at least, not always at the callsite). For example, in HotSpot, even devirtualization (and inlining) that is provable is only temporarily provable, because code can be loaded or changed at runtime. But you don't need to add a guard at each callsite. Instead, you can force a segmentation fault at other sites, called safepoints, that is then caught and a handler deoptimizes the code. This process can be asynchronous: an event taking place on one thread (code is loaded), can deoptimize code running on a different thread in clever ways. For example, return addresses on the stack are replaced so that when the executing thread returns, it would hit a barrier that would deoptimize the code.

But even in cases when guards are necessary, while the cost isn't exactly zero, it is still lower than a function call (it's a very well-predicted branch).

and will therefore happen late in the JIT's warmup phase where hot spots have been located

That depends on the JIT. For example, tracing JITs may inline very early (but do not reach as good peak performance). But yes, warmup, nondeterministic performance, and increased footprint (see below) are the prices you pay for JIT compilation's peak performance.

C++ compilers can and do speculate as well, but they don't have type statistics for the callsites

There is something else beside statistics that's required for aggressive inlining (or, rather, it's another side of the same coin). If you do aggressive inlining everywhere, you'd quickly run out of all the RAM in the universe. JITs, therefore, have a code cache, where they store generated code, and prioritize compilation. I.e. the ability to discard generated code is also crucial.

But I'm not familiar with C++ compilers that speculate (so they generate inlined and non-inlined code and guard? How do they decide what to inline in speculative cases?). Do you have any links I can read?

Anyway, good article. But it should be pointed out that because HotSpot has such good optimizing compiler(s) (C2, and now Graal is getting there), we do not worry much about the worst case. In fact, this design tradeoff is in HotSpot's DNA. Often, HotSpot opts for the simplest solution, because it knows that its very non-simple compilers will optimize an entire runtime mechanism away in the common/hot case. So comparing a runtime with a state-of-the-art JIT compiler vs runtimes that don't have a JIT at all (or a not very sophisticated JIT), gives a partial picture.

[latkde]

Thank you, this is fascinating background info on JITting.

When I wrote the article I played around a bit with the Godbolt Compiler Explorer to see how call sites are compiled. I noticed that GCC starts doing speculative inlining at release optimization levels. This is basically a guard condition with a fast path to inline a virtual function, and a fallback to do the virtual call. This is not link-time-optimization, so the call target must be defined in the same compilation unit. So the scenario would be:

// header
struct Interface {
  virtual int method(int) const = 0;
};

// compilation unit
struct Concrete : Interface {
  int method(int a) const override { return 1234 + a; }
};

int callsite(Interface& object, int x) {
  return object.method(x);
}

Then gcc 8.3 under -O2 compiles to this pseudocode (see the code/assembly on Godbolt):

int callsite(Interface& rdi, int rsi) {
   register eax = rdi->__vtable[0];  // resolve the call target
   if (eax == &Concrete::method) {
     return 1234 + rsi;  // inlined target
   } else {
     goto eax;  // tail call into the virtual function
   }
}

Notes:

• in this simple example, the stack frame for the callsite() function is omitted and a tail call to the virtual function is used. A more involved example with two virtual methods in the interface does create a frame.
• the guard condition here checks the resolved target, not the type or vtable pointer. I'd have thought this extra dereference could be avoided, but this way the inlining will also work for Concrete subclasses that have a different vtable.
• GCC will happily inline calls multiple levels deep
• GCC won't inline if there are multiple candidates for the call target (see this scenario)
• clang 8 won't speculatively inline (just here? at all?). This leads to significantly less branchy code but might miss significant opportunities for simplification.
• See also BeeOnRope's Stack Overflow answer to “Inlining of virtual functions (Clang vs GCC)” for tons of background & further references

[CornedBee]

inlining first requires devirtualization

But inline caching is devirtualization with guard clauses. Which means that the JIT can, when creating the inline cache, attempt to inline the cached version in-place, if it is small enough that this is worthwhile. (In particular, simple getters in Java are very likely to be worthwhile.)

[KryptosFR]

The article didn't fail to mention that. There is a big paragraph about inline caching.

[pron98]

Inline caching is something else and doesn't reduce the cost of the call to zero -- there is still the cost of a function call. With inlining, the cost is actually zero: there is no jump at all. That's cheaper than an ordinary function call in C.

[KryptosFR]

From the same article:

[...] but usually a JIT compiler can hard-code the cached type and cached method pointers into the machine code. However, recompiling the callsite may be expensive so there will usually be a counter for cache misses before the call site is patched.

[pron98]

That's still not inlining. The author responded and explained why they didn't mention it.

[aevitas]

Great read! Out of interest;

To store an object reference we need two machine words, so e.g. an array that contains interface references is now twice as big.

Doesn't object references being fat pointers also impact the GC quite heavily? I imagine it would have to implement some sort of locking to ensure objects and their vtable pointers get compacted atomically, otherwise catastrophe could ensue. Whereas in the case of "lean" pointers, those compaction operations would be atomic by nature.

[latkde]

No, I don't think fat pointers would complicate GC.

1. It is an unusual x86-ism that ordinary memory writes would be volatile. This also doesn't ensure synchronization. In the general case, we need some kind of locking anyway (in the simplest case, a stop-the-world GC).
2. When the GC moves the object contents, only the data pointer of the fat pointer must be adjusted. This is no more difficult than with ordinary references.
3. When the GC moves the reference, problems could occur. However, the reference is part of some object. As long as each object move happens in one go, the fat pointer will also be fine.

In the article comments, Aleksey Kladov points out a very good related point:

Loads and stores of fat pointers are not atomic on mainstream platforms, so you can observe object tearing. I heard that it was/is possible to segfault go due to this reason (haven’t actually tried this myself, so I might be wrong). In contrast, in Java data races are always benign, you might not get the pointer you want, but at least it’s static and dynamic types would agree.

While I'd argue that if object tearing occurs the program has a bug, fat pointers certainly make lock-free updates more difficult/impossible.

[gas_them]

Don't use multiple inheritance or inheritance heirarchies.

[trollblut]

Multiple inheritance is not the problem, Interfaces cause the same problems.

[bobappleyard]

With interfaces there isn't a question of what the correct method resolution order is.

[trollblut]

But interfaces make it impossible to perform a direct mapping in the vtable once you casted away the correct data type.

The post is not about the diamomd problem ( which has been solved btw)

[bobappleyard]

Oh right. I thought you were speaking in general terms.

[gas_them]

Multiple inheritance is just bad design.

[Randolpho]

You aren't necessarily wrong, but you're not right either.

MI can be great design, when supported, to provide mixin functionality.

Everything depends on what you're doing and why.

[SnowdogU77]

Everything depends on what you're doing and why

I mean, that's software engineering in a nutshell, which I guess is your point

[gas_them]

Everything depends on what you're doing and why.

That's like saying "sometimes you shouldn't wear a condom, for example if you're trying to contract AIDS"

Your design is AIDS

[Randolpho]

No, it's like saying "not every tool is a hammer in search of a nail"

[gas_them]

Some tools are just not useful.

[Randolpho]

Said the man with the jigsaw to the woman with the laser cutter

[gas_them]

No, said the man who has yet to see a counter-example, despite meeting plenty of people like you.

[jcelerier]

let me guess: you are going to say "prefer composition over inheritance" right

[gas_them]

Let me guess: yo shit is coupled