[swift-dev] Resilient dynamic dispatch ABI. Notes and mini-proposal.

[Joe Groff]

> On Feb 5, 2017, at 7:45 AM, Karl Wagner via swift-dev <swift-dev at swift.org> wrote:
> 
> 
>> On 3 Feb 2017, at 03:57, Andrew Trick via swift-dev <swift-dev at swift.org <mailto:swift-dev at swift.org>> wrote:
>> 
>> I'm following up on a resilient dynamic dispatch discussion kicked off by
>> Slava during a performance team meeting to summarize some key
>> points on public [swift-dev].
>> 
>> It's easy to get sidetracked by the details of dynamic
>> dispatch and various ways to generate code. I suggest approaching the
>> problem by focusing on the ABI aspects and flexibility the ABI affords
>> for future optimization. I'm including a proposal for one specific
>> approach (#3) that wasn't discussed yet.
>> 
>> ---
>> #1. (thunk export) The simplest, most flexible way to expose dispatch
>> across resilience boundaries is by exporting a single per-method entry
>> point. Future compilers could improve dispatch and gradually expose
>> more ABI details.
>> 
>> Cost: We're forced to export all those symbols in perpetuity.
>> 
>> [The cost of the symbols is questionable. The symbol trie should compress the
>> names, so the size may be small, and they should be lazily resolved,
>> so the startup cost should be amortized].
>> 
>> ---
>> #2. (offset export) An alternative approach was proposed by JoeG a
>> while ago and revisited in the meeting yesterday. It involves a
>> client-side vtable offset lookup helper.
>> 
>> This allows more opportunity for micro-optimization on the client
>> side. This exposes the isa-based vtable mechanism as ABI. However, it
>> stops short of exposing the vtable layout itself. Guaranteeing vtable
>> dispatch may become a problem in the future because it forces an
>> explosion of metadata. It also has the same problem as #1 because the
>> framework must export a per-method symbol for the dispatch
>> offset. What's worse, the symbols need to be eagerly resolved (AFAIK).
>> 
>> ---
>> #3. (method index) This is an alternative that I've alluded to before,
>> but was not discussed in yesterday's meeting. One that makes a
>> tradeoff between exporting symbols vs. exposing vtable layout. I want
>> to focus on direct cost of the ABI support and flexibility of this
>> approach vs. approach #1 without arguing over how to micro-optimize
>> various dispatching schemes. Here's how it works:
>> 
>> The ABI specifies a sort function for public methods that gives each
>> one a per-class index. Version availability takes sort precedence, so
>> public methods can be added without affecting other
>> indices. [Apparently this is the same approach we're taking with
>> witness tables].
>> 
>> As with #2 this avoids locking down the vtable format for now--in the
>> future we'll likely optimize it further. To avoid locking all methods
>> into the vtable mechanism, the offset can be tagged. The alternative
>> dispatch mechanism for tagged offsets will be hidden within the
>> class-defining framework.
>> 
>> This avoids the potential explosion of exported symbols--it's limited
>> to one per public class. It avoids explosion of metadata by allowing
>> alternative dispatch for some subset of methods. These tradeoffs can
>> be explored in the future, independent of the ABI.
>> 
>> ---
>> #3a. (offset table export) A single per-class entry point provides a
>> pointer to an offset table. [It can be optionally cached on the client
>> side].
>> 
>>  method_index = immediate
>>  { // common per-class method lookup
>>    isa = load[obj]
>>    isa = isa & @isa_mask
>>    offset = load[@class_method_table + method_index]
>>    if (isVtableOffset(offset))
>>      method_entry = load[isa + offset]
>>    else
>>      method_entry = @resolveMethodAddress(isa, @class_method_table, method_index)
>>  }
>>  call method_entry
>> 
>> Cost - client code size: Worst case 3 instructions to dispatch vs 1
>> instruction for approach #1. Method lookups can be combined, so groups
>> of calls will be more compact.
>> 
>> Cost - library size: the offset tables themselves need to be
>> materialized on the framework side. I believe this can be done
>> statically in read-only memory, but that needs to be verified.
>> 
>> ABI: The offset table format and tag bit are baked into the ABI.
>> 
>> ---
>> #3b. (lazy resolution) Offset tables can be completely localized.
>> 
>>  method_index = immediate
>>  { // common per-class method lookup
>>    isa = load[obj]
>>    offset = load[@local_class_method_table + method_index]
>>    if (!isInitializedOffset(offset)) {
>>      offset = @resolveMethodOffset(@class_id, method_index)
>>      store [@local_class_method_table + method_index]
>>    }
>>    if (isVtableOffset(offset))
>>      method_entry = load[isa + offset]
>>    else
>>      method_entry = @resolveMethodAddress(isa, @class_id, method_index)
>>  }
>>  call method_entry
>> 
>> ABI: This avoids exposing the offset table format as ABI. All that's
>> needed is a symbol for the class, a single entry point for method
>> offset resolution, and a single entry point for non-vtable method
>> resolution.
>> 
>> Benefit: The library no longer needs to statically materialize
>> tables. Instead they are initialized lazilly in each client module.
>> 
>> Cost: Lazy initialization of local tables requires an extra check and
>> burns some code size.
>> 
>> ---
>> Caveat:
>> 
>> This is the first time I've thought through approach #3, and it hasn't
>> been discussed, so there are likely a few things I'm missing at the
>> moment.
>> 
>> ---
>> Side Note:
>> 
>> Regardless of the resilient dispatch mechanism, within a module the
>> dispatch mechanism should be implemented with thunks to avoid type
>> checking classes from other files and improve compile time in non-WMO
>> builds, as Slava requested.
>> 
>> -Andy
>> _______________________________________________
>> swift-dev mailing list
>> swift-dev at swift.org <mailto:swift-dev at swift.org>
>> https://lists.swift.org/mailman/listinfo/swift-dev
> 
> I have a question about current dispatching behaviour with protocols and ‘Self’.
> 
> protocol CustomEquatable {
>     func equal(to: Self) -> Bool
> }
> 
> open class Super : CustomEquatable {
>     func equal(to: Super) -> Bool { print("super"); return false }
> }
> class Sub: Super {
>     func equal(to: Sub) -> Bool { print("sub-sub"); return true }
>     override func equal(to: Super) -> Bool { print("sub-super"); return true }
> }
> 
> Sub().equal(to: Sub())     // sub-sub
> Sub().equal(to: Super())   // sub-super 
> Super().equal(to: Sub())   // super
> Super().equal(to: Super()) // super
> 
> (Sub() as Super).equal(to: Sub)              // sub-super — dynamically dispatched to callee’s type, not param
> (Sub() as Super).equal(to: (Sub() as Super)) // sub-super — as above
> 
> 
> Currently, we dynamically dispatch to the callee’s type to find ‘Self’, but we don’t apply that consistently when dispatching to ‘Self’-type parameters. Is that expected behaviour?

It strikes me as a bug that we accept the `func equal(to: Sub)` method quietly as an overload instead of raising an error, or at least a warning about it. Nonetheless, this is correct behavior given that the code is accepted: `equal(to: Sub)` is a different method from `equal(to: Super)` that's only visible when we statically have a `Sub`. It isn't used as the protocol witness, since the witness is chosen for `Super` and has to work for all its subclasses, and it isn't an override of `equal(to: Super)`, since it only accepts `Sub`s and not all `Super`s.

-Joe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20170206/2b840800/attachment.html>