> On Jul 28, 2017, at 6:34 PM, Joe Groff <jgr...@apple.com> wrote: >> On Jul 28, 2017, at 3:30 PM, John McCall <rjmcc...@apple.com> wrote: >>> On Jul 28, 2017, at 6:24 PM, Joe Groff <jgr...@apple.com> wrote: >>>> On Jul 28, 2017, at 3:15 PM, John McCall <rjmcc...@apple.com> wrote: >>>> >>>> >>>>> On Jul 28, 2017, at 6:02 PM, Andrew Trick via swift-dev >>>>> <swift-dev@swift.org> wrote: >>>>> >>>>> >>>>>> On Jul 28, 2017, at 2:20 PM, Joe Groff via swift-dev >>>>>> <swift-dev@swift.org> wrote: >>>>>> >>>>>> The Swift runtime currently maintains globally unique pointer identities >>>>>> for type metadata and protocol conformances. This makes checking type >>>>>> equivalence a trivial pointer equality comparison, but most operations >>>>>> on generic values do not really care about exact type identity and only >>>>>> need to invoke value or protocol witness methods or consult other data >>>>>> in the type metadata structure. I think it's worth reevaluating whether >>>>>> having globally unique type metadata objects is the correct design >>>>>> choice. Maintaining global uniqueness of metadata instances carries a >>>>>> number of costs. Any code that wants type metadata for an instance of a >>>>>> generic type, even a fully concrete one, must make a potentially >>>>>> expensive runtime call to get the canonical metadata instance. This also >>>>>> greatly complicates our ability to emit specializations of type >>>>>> metadata, value witness tables, or protocol witness tables for concrete >>>>>> instances of generic types, since specializations would need to be >>>>>> registered with the runtime as canonical metadata objects, and it would >>>>>> be difficult to do this lazily and still reliably favor specializations >>>>>> over more generic witnesses. The lack of witness table specializations >>>>>> leaves an obnoxious performance cliff for instances of generic types >>>>>> that end up inside existential containers or cross into unspecialized >>>>>> code. The runtime also obligates binaries to provide the canonical >>>>>> metadata for all of their public types, along with all the dependent >>>>>> value witnesses, class methods, and protocol witness tables, meaning a >>>>>> type abstraction can never be completely "zero-cost" across modules. >>>>>> >>>>>> On the other hand, if type metadata did not need to be unique, then the >>>>>> compiler would be free to emit specialized type metadata and protocol >>>>>> witness tables for fully concrete non-concrete value types without >>>>>> consulting the runtime. This would let us avoid runtime calls to fetch >>>>>> metadata in specialized code, and would make it much easier for us to >>>>>> implement witness specialization. It would also give us the ability to >>>>>> potentially extend the "inlinable" concept to public fragile types, >>>>>> making it a client's responsibility to emit metadata for the type when >>>>>> needed and keeping the type from affecting its home module's ABI. This >>>>>> could significantly reduce the size and ABI surface area of the standard >>>>>> library, since the standard library contains a lot of generic >>>>>> lightweight adapter types for collections and other abstractions that >>>>>> are intended to be optimized away in most use cases. >>>>>> >>>>>> There are of course benefits to globally unique metadata objects that we >>>>>> would lose if we gave up uniqueness. Operations that do check type >>>>>> identity, such as comparison, hashing, and dynamic casting, would have >>>>>> to perform more expensive checks, and nonunique metadata objects would >>>>>> need to carry additional information to enable those checks. It is >>>>>> likely that class objects would have to remain globally unique, if for >>>>>> no other reason than that the Objective-C runtime requires it on Apple >>>>>> platforms. Having multiple equivalent copies of type metadata has the >>>>>> potential to increase the working set of an app in some situations, >>>>>> although it's likely that redundant compiler-emitted copies of value >>>>>> type metadata would at least be able to live in constant pages mapped >>>>>> from disk instead of getting dynamically instantiated by the runtime >>>>>> like everything is today. There could also be subtle source-breaking >>>>>> behavior for code that bitcasts metatype values to integers or pointers >>>>>> and expects bit-level equality to indicate type equality. It's unlikely >>>>>> to me that giving up uniqueness would buy us any simplification to the >>>>>> runtime, since the runtime would still need to be able to instantiate >>>>>> metadata for unspecialized code, and we would still want to unique >>>>>> runtime-instantiated metadata objects as an optimization. >>>>>> >>>>>> Overall, my intuition is that the tradeoffs come out in favor for >>>>>> nonunique metadata objects, but what do you all think? Is there anything >>>>>> I'm missing? >>>>>> >>>>>> -Joe >>>>> >>>>> In a premature proposal two years ago, we agreed to ditch unique protocol >>>>> conformances but install the canonical address as the first entry in each >>>>> specialized table. >>>> >>>> This would be a reference to (unique) global data about the conformance, >>>> not a reference to some canonical version of the protocol witness table. >>>> We do not rely on having a canonical protocol witness table. The only >>>> reason we unique them (when we do need to instantiate) is because we don't >>>> want to track their lifetimes. >>>> >>>>> That would mitigate the disadvantages that you pointed to. But, we would >>>>> also lose the ability to emit specialized metadata/conformances in >>>>> constant pages. How do you feel about that tradeoff? >>>> >>>> Note that, per above, it's only specialized constant type metadata that we >>>> would lose. >>>> >>>> I continue to feel that having to do structural equality tests on type >>>> metadata would be a huge loss. >>> >>> I don't think it necessarily needs to be deep structural equality. If the >>> type metadata object or value witness table had a pointer to a mangled type >>> name string, we could strcmp those strings to compare equality, which >>> doesn't seem terribly onerous to me, though if it were we could perhaps use >>> the string to lazily resolve the canonical type metadata pointer, sort of >>> like we do with type metadata for imported C types today. >> >> So generic code to instantiate type metadata would have to construct these >> mangled strings eagerly? > > We already do exactly that for the ObjC runtime name of generic class > instantiations, for what it's worth, but it could conceivably be lazy as > well, at the cost of making the comparison yet more expensive. There aren't > that many runtime operations that need to do type comparison, though—the ones > I can think of are casting and the equality/hashing operations on Any.Type—so > how important is efficient type comparison?
A fair question. It's extremely important for type uniquing — of course, you're talking about making that less important, but when it does happen, it will cost more. The way I see it is that the importance of specialization is 95% about specializing tables of function pointers, i.e. value witness tables, protocol witness tables, and class v-tables. There's no reason we can't use specialized protocol witness tables today. Your proposal still leaves us uniquing class v-tables. So this is just about making it easier (on us as implementors) to create specialized value witness tables, plus the trade-off of being able to refer to non-dependent type metadata slightly more cheaply vs. making type comparisons vastly more expensive. John. _______________________________________________ swift-dev mailing list swift-dev@swift.org https://lists.swift.org/mailman/listinfo/swift-dev
