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

[Karl Wagner]

> On 3 Feb 2017, at 03:57, Andrew Trick via swift-dev <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
> 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?

- Karl
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20170205/c9f9cf0b/attachment.html>