What are the benefits of witness table over vtable?

Using Swift
1

what are the benefits of witness table over vtable?
why can't swift just use vtable?

1 Like
2

I thought they were just different names for the same concept. Do you have a source/article that claims they're different?

1 Like
3

They are not the same. But they both do dynamic dispatch.

1 Like
4

vtables and witness tables are two related but distinct concepts in the Swift implementation.

A vtable is a table of function pointers attached to a class instance. The vtable contains an entry for every overridable method:

class Fruit {
  func eat() {}
  func squeeze() {}
}

class Apple: Fruit {
  override func eat() {}
}

The vtable for Fruit has two entries. The vtable for Apple replaces the second entry with its own implementation of eat(). When you call eat() on an instance of Fruit, we compile the call by loading the vtable entry and performing an indirect jump.

A witness table is the same thing, but for a protocol conformance. Protocol conformances can be defined independently of types, so we can make Int conform to a new protocol for instance:

protocol P {
  func foo()
}

extension Int: P {
  func foo() {}
}

This will generate a global symbol that stores the witness table for “Int: P”, which contains one entry, the implementation of foo().

Now if I declare a generic function and call it with an Int:

func g<T: P>(_ t: T) {
  t.foo()
}

g(123)

Then we compile the call to g() by passing in a reference to the “Int: P” witness table. Inside the function, the call to t.foo() loads the right function pointer from the witness table and performs an indirect call.

26 Likes
5

So is the only functional difference that an object holds a pointer to the vtable, while the witness table is a global?

1 Like
6

They’re both global in the sense that ultimately they’re emitted by the compiler, it’s more that the vtable is always part of the value, while a witness table is separate from the value itself.

This is why a generic “an array of T that conforms to P” is a homogeneous array; the function receives just one T and one witness table for P:

func foo<T: P>(_: [T]) {}

An existential type is then just a value together with a witness table, so an array of existential types is heterogeneous because every element has its own witness table:

func foo(_: [any P]) {}

(A class instance in Swift is just a special kind of existential type, because the idea is the same, it packages together a value with a description of its dynamic type, in the form of the isa pointer and vtable.)

10 Likes
7

So, what are the benefits?

1 Like
8

They’re implementation techniques for two different language features, so really it just comes down to your opinion of protocols vs OOP.

4 Likes
9

but the other languages only have vtable. for example, rust can't inherit. but it has vtable for trait. why was swift implemented this way? Because I can't see witness table has any benefits. for example, embedded swift, it only allows to use vtable. it cant use witness. as my understand, because witness is too big to implement in runtime. I may be wrong. I am not a compiler engineer.

10

I suspect that the confusion here is in terminology. I think Rust's dyn trait feature uses an implementation scheme similar to Swift's witness tables. You could look at the LLVM IR generated from something like &dyn Trait1 + Trait2 in Rust to see whether they're storing two separate tables (I suspect they are) vs. a single merged table. Rust has no need to differentiate between what Swift calls vtables (which are embedded in the class) and what Swift calls wtables (which are separate from the type), whereas Swift needs two terms. I think that's it.

This is a choice for Embedded Swift that could get revisited. We could bring witness tables into embedded Swift (along with support for any types) without introducing a large runtime. It would have a code-size impact relative to the number of witness tables you actually put into any types.

Doug

6 Likes
11

FWIW, Embedded Swift supports existential any with a class-constrained protocol already, and this is implemented by packaging a witness table with the value, like in regular Swift. What Embedded Swift doesn't know how to generate is a value witness table, which is a special kind of witness table for the primitive move/copy/destroy operations for an arbitrary value type, which is why Embedded Swift does not support any with non-class-constrained protocols.

4 Likes