> On Feb 3, 2017, at 7:12 PM, Joe Groff via swift-dev <swift-dev@swift.org>
> wrote:
> Given that most open-coded resilient method lookup paths require an extra
> load dependency to grab the method offset before loading the method address
> itself, we might possibly consider indirecting the vtables for each class, so
> that the top-level vtable contains [address of root class vtable, address of
> first child class vtable, etc.]. If a class hierarchy is fixed once exported
> (in other words, you can't insert a superclass into an inheritance chain
> without an ABI break), then the offset into each superclass's pointer in the
> vtable would be statically known, and the offset into each second-level
> vtable could be statically known via sorting by availability. This somewhat
> matches how we lay out protocol witness tables, where each parent protocol's
> witness table is indirectly referenced instead of being inlined into the leaf
> witness table. (OTOH, method offsets can be cached and reused to dispatch the
> same method on different objects, whereas we would have to perform the load
> chain once per object per method with this approach.)
Great point.
I'm still uncomfortable with the idea of assuming that we can't insert a
superclass into an inheritance chain. This isn't an assumption that's
otherwise necessary or even useful, unless we decide to start optimizing
dynamic casts.
Assuming it's valid, some additional trade-offs that come to mind:
- It adds a load dependency to non-resilient dispatch, which is probably what
we should be optimizing for. We have an easy answer when someone asks why
their resilient dispatch is a bit slower. We don't have easy ways to make
non-resilient dispatch faster.
- It still forces us to put every non-final method in the subtable.
+ It would be possible to share subtables between classes, e.g. when a
subclass doesn't override anything from a particular parent.
+ It would allow us to put the subtables in constant memory.
John.
>
> -Joe
>
>> On Feb 2, 2017, at 6:57 PM, Andrew Trick <atr...@apple.com> 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@swift.org
> https://lists.swift.org/mailman/listinfo/swift-dev
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev
