Nested generic trouble

scanon · 2023-02-16T17:04:35.264Z

Not something "in Swift" but it would have been contrary to the goals of the language. From the introductory material of @Slava_Pestov's generics document:

Swift generics were designed with four primary goals in mind:

Generic definitions should be independently type checked, without knowledge of all possible concrete type substitutions that they are invoked with.

Shared libraries that export generic definitions should be able to evolve resiliently without requiring recompilation of clients.

...

The C++ template model does not satisfy the first two goals, which are critical for the task of distributing an SDK for binary-stable libraries shipped in the OS.

taylorswift · 2023-02-16T17:10:07.374Z

tera:

I am not suggesting the change, but wonder could Swift have chosen to use C++ template model (when that design decision was made) or was there something in Swift that prevented it?

my take on this is that there has been quite a bit of convergent evolution and most real world uses of generics just end up lowering them to templates through hilarious overuse of @frozen and @inlinable. there really isn’t any other way to get C++ level performance with generics, you have to turn them into templates either way.

i do have a carveout to this strategy for generics constrained to AnyObject, since those are pretty cheap. but i would rarely leave a non-reference type constrained generic unspecialized.

stuchlej · 2023-02-16T17:15:51.591Z

I have struggled with this myself few years ago (coming from C++).

taylorswift:

most real world uses of generics just end up lowering them to templates through hilarious overuse of @frozen and @inlinable

I would be really interested if you have a concrete example. Can I specify completely different implementation of a generic function for a given type parameter (essentially template specialisation in C++)?

Edit: My understanding of the difference between Swift generics and C++ Templates is, that Template is essentially a special macro, that always gets fully resolved at build time - since unlike Swift generics, all template code must be inside a public header file. And thus it can resolve a "specialisation" from within a context of another template.

taylorswift · 2023-02-16T17:19:56.367Z

stuchlej:

Can I specify completely different implementation of a generic function for a given type parameter (essentially template specialisation in C++)?

yes, this can be used to add type safety for APIs that come in multiple "flavors". but that's not really the use case described in this thread, since you wouldn't need to inline those generics, since they aren't being used in the actual algorithm, they are only being used to gate an API.

taylorswift · 2023-02-16T17:24:11.158Z

stuchlej:

Edit: My understanding of the difference between Swift generics and C++ Templates is, that Template is essentially a special macro, that always gets fully resolved at build time - since unlike Swift generics, all template code must be inside a public header file. And thus it can resolve a "specialisation" from within a context of another template.

when you spray inlinable over a type that is effectively the swift equivalent of moving it into a header file.

the ugly secret of swift is we are hilariously dependent on inlining to accomplish even the most basic of things, and the only reason this isn't seen as a problem is because the situation in C++ is even worse.

this is the real reason why we in the swift world tend to write very large modules that contain many files and many types, whereas a C++ "module" usually consists of a single cc file with a single type and a single associated header file.

tcldr · 2023-02-16T17:32:12.796Z

I asked a similar question just the another day and the answer was 'it just doesn't work like that'. Essentially the concrete type info is stripped away as soon as its passed into a generic function.

stuchlej · 2023-02-16T17:42:01.173Z

tcldr:

'it just doesn't work like that'

I thought this to be correct.

taylorswift:

when you spray inlinable over a type that is effectively the swift equivalent of moving it into a header file.

OK, but unlike in C++, I can't just create a generic type and an overloaded function like

public struct Container<T: Encodable> {
  public var value: T
  @persisted var storage: Data

  public func bytes(_ val: Int) -> Data { /* return a bit pattern */ }
  public func bytes(_ val: String) -> Data { /* return a C String */ }
  public func bytes<A: Encodable>(_ val: A) -> Data { /* use JSONEncoder */ }

  public func store() {
    _storage = bytes(value)
  }
}

even if I use @inlinable, correct? I am aware, that @inlinable (and other things like open) emmit something (ast?) into the .swiftmodule file. But will this change the behaviour of the func store(), so it works as a C++ Templated type would?

taylorswift · 2023-02-16T17:49:48.955Z

i don't understand what you're asking here. all three methods would be available on every specialization of Container because you have not added any where constraints to any of them.

lukasa · 2023-02-16T17:50:45.503Z

taylorswift:

the ugly secret of swift is we are hilariously dependent on inlining to accomplish even the most basic of things, and the only reason this isn't seen as a problem is because the situation in C++ is even worse.

I don't think this is accurate. Swift has (modulo a couple of limitations that have not been mentioned in this thread) a "best of both worlds" situation, where it is simultaneously possible to a) write an ABI-stable generic function that can evolve without recompiling the application, and b) write a high-performance generic algorithm that is monomorphized into caller's code, depending on what the implementer requires.

I think a case can be made that non-resilient code (i.e. SwiftPM packages) could benefit from letting the compiler have much freer reign with exposing implementation details. But I don't think that's quite what you said here.

lukasa · 2023-02-16T17:51:24.803Z

stuchlej:

I am aware, that @inlinable (and other things like open) emmit something (ast?) into the .swiftmodule file.

@inlinable and open behave very differently.

@inlinable doesn't emit AST, it literally emits source code.

taylorswift · 2023-02-16T18:04:07.668Z

lukasa:

I don't think this is accurate. Swift has (modulo a couple of limitations that have not been mentioned in this thread) a "best of both worlds" situation, where it is simultaneously possible to a) write an ABI-stable generic function that can evolve without recompiling the application, and b) write a high-performance generic algorithm that is monomorphized into caller's code, depending on what the implementer requires.

in C++ you do the "stable generic function" thing with class inheritance, so it's not quite that swift generics are more powerful than C++ templates, it's just that swift has combined the two features into one, and inlinability is how you select between the two subfeatures.

on the other hand @inlinable is way more widespread in swift code than you would expect in similarly written C++ code, because we copy everything by default in swift, whereas we usually pass-by-reference in C++. and a lot of the time the @inlinable in swift serves no purpose other than to expose the copy constructor. and that is why i think C/C++ people are sometimes surprised by how much inlining swift uses.

stuchlej · 2023-02-16T18:12:53.167Z

Essentially, my point was, that I've made assumption in the past, that Swift generics work like C++ template and since following C++ program has such output:

#include <iostream>

template<typename T>
struct Container {
    public:
    T value;

    // Templated function bytes
  template <typename A>
  void bytes(A arg) {
    std::cout << "A" << std::endl;
  }
  
  void bytes(std::string arg) {
    std::cout << "std::string" << std::endl;
  }

  void bytes(int arg) {
    std::cout << "int" << std::endl;
  }

  void store() {
    bytes(value);
  }
};

int main() {
    Container<int> inst;
    inst.store(); // prints "int"
    std::string str = "Hello";
    inst.bytes(str); // prints "std::string"
    return 0;
}

the Swift program should have output "Int" and "String" for this program

public struct Container<T: Encodable> {
  public var value: T

  public func bytes(_ val: Int) { print("Int") }
  public func bytes(_ val: String) { print("String") }
  public func bytes<A: Encodable>(_ val: A) { print("A") }

  public func store() {
    bytes(value)
  }
}

let inst = Container<Int>(value: 10)
inst.store() // prints "A"
inst.bytes("hi") // prints "String"

and I was confused, since I thought you were saying, that I can change this behaviour by suing @inlinable.

ksluder · 2023-02-16T18:17:22.689Z

taylorswift:

on the other hand @inlinable is way more widespread in swift code than you would expect in similarly written C++ code, because we copy everything by default in swift, whereas we usually pass-by-reference in C++. and a lot of the time the @inlinable in swift serves no purpose other than to expose the copy constructor.

I would be interested in any performance analysis you are able to share that informed the decision to lean heavily on @inlinable.

Alejandro · 2023-02-16T18:23:48.523Z

C++ templates are an entirely compile time construct. There is no runtime support nor is there an exported symbol that gets emitted into a binary from C++ template functions unlike Swift generics.

@inlinable/@frozen/@usableFromInline in my opinion are quite useless outside of resilient modules and its only used in SPM packages because either SPM doesn't pass the correct flags to the compiler to allow it to see the entirety of the package source, or the compiler just doesn't have this free reign that @lukasa mentioned. (I have no idea what binary packages do, so this argument only applies to packages who's sources are readily available).

taylorswift · 2023-02-16T18:41:54.535Z

around 4 or 5 years ago i discovered underspecialization was responsible for about a factor 10x slowdown in swift-png, because its pixel types are generic over FixedWidthInteger & UnsignedInteger to handle varying color depth.

about a year ago i discovered a very similar issue in swift-json, because its parser is generic over RandomAccessCollection<UInt8>.

you can also diagnose this issue directly with profiling tools like perf, by looking for clumps of "type metadata"-related samples.

but more often i discover it because i add a public convenience API somewhere else that uses some concrete type like [UInt8], and all of a sudden the generic benchmarks run 10x faster because the compiler generates a specialization for the convenience API to use, and the benchmarks all start calling the specialized function instead of the unspecialized one.

as a side note, even @inlinable isn't enough sometimes to fix this problem. sometimes even the mere presence of generics from outer scopes can cause major performance changes when nesting and unnesting types from namespaces, see Un-nesting a type from an enum namespace results in a 6x slowdown

ksluder · 2023-02-16T18:56:40.367Z

This is good information, but it doesn’t sound related to “copy-by-default”.

taylorswift · 2023-02-16T19:04:10.786Z

copy-by-default is simply the observation that marshaling a pixel buffer of [RGBA<UInt16>] is always going to be faster than marshaling a pixel buffer of [RGBA<T>], because the compiler knows that RGBA<UInt16> is a trivial type, but it has no idea how to copy RGBA<T> without consulting the value witness.

on the other hand, passing the array itself wouldn't be affected. pass by reference would only really help when you have the "giant structs" pattern.

lukasa · 2023-02-17T10:43:27.889Z

Alejandro:

its only used in SPM packages because either SPM doesn't pass the correct flags to the compiler to allow it to see the entirety of the package source, or the compiler just doesn't have this free reign that @lukasa mentioned

It is my understanding (from chats with @Erik_Eckstein) that there are good reasons that "just behave as though everything is @frozen and @inlinable is not a behaviour that SPM chooses by default. However, a good start might be for SPM to start passing -cross-module-optimization, whose default heuristic targets generic and small functions.

Apropos of nothing, but the much more substantial limitations to highly generic code IMO come in places where @inlinable simply cannot fix the problem in Swift today, as those areas are also resistant to cross-module optimization. The most notable of these is "generic types held in protocol existentials". In this circumstance, the protocol witness table will always be one for the generic functions, even if at the point of constructing the existential the compiler knew the generic types and could provide specialized alternatives.

tera · 2023-02-17T11:11:46.606Z

lukasa:

Apropos of nothing, but the much more substantial limitations to highly generic code IMO come in places where @inlinable simply cannot fix the problem in Swift today, as those areas are also resistant to cross-module optimization. The most notable of these is "generic types held in protocol existentials". In this circumstance, the protocol witness table will always be one for the generic functions, even if at the point of constructing the existential the compiler knew the generic types and could provide specialized alternatives.

This is somewhat in contradiction to the spirit if not the letter of the fourth goal from the mentioned document:

Abstraction over concrete types with generic parameters should only impose a cost across module boundaries, or in other situations where type information is not available at compile time.

Slava_Pestov · 2023-02-17T15:35:37.357Z

taylorswift:

my take on this is that there has been quite a bit of convergent evolution and most real world uses of generics just end up lowering them to templates through hilarious overuse of @frozen and @inlinable. there really isn’t any other way to get C++ level performance with generics, you have to turn them into templates either way.

Even if you monomorphize all of your generics (the way Rust does) there's still benefit to type checking generic definitions separately, and not after template expansion (like Rust and Swift do).