Compile-time generic specialization


(Abe Schneider) #1

Hi all,

The current behavior of generics in Swift causes it lose type information at compile time due to the desire of maintaining a single version of the function. This runs counter to how c++ works, which creates a new copy of a function per type, but preserves information to be preserved. This can cause unexpected behavior from the user’s perspective:

  protocol DispatchType {}
  class DispatchType1: DispatchType {}

  func doBar<D:DispatchType>(value:D) {
    print(“General function called")
  }

  func doBar(value:DispatchType1) {
    print("DispatchType1 called")
  }

  func test<D:DispatchType>(value:D) {
    doBar(value: value)
  }

  test(value: d1) // “General function called”, but it’s not obvious why

The suggested method to get around this issue is to use a protocol to create a witness table, allowing for runtime dispatch. However, this approach is not ideal in all cases because: (a) the overhead of runtime dispatch may not be desirable, especially because this is something that can be determined at compile time; and (b) there are some designs in which this behavior can complicate things.

One example of a design where this behavior can be problematic is when a protocol is used to determine what functions get dispatched:

  protocol Storage { … }
  class Tensor<S:Storage> { … }

  class CBlasStorage: Storage { … }
  class OpenCLStorage: Storage { … }

  func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> { … }

  // like behavior, these will not work if called from another generic function (but will work for non-generic functions)
  func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> where S:CBlasStorage { … }
  func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> where S:OpenCLStorage { … }

In this case, depending on the underlying storage, we want an optimized version of `dot` to be called. To make this work correctly we can add static methods to `Tensor`, but this has several drawbacks: (a) it makes the `Tensor` class monolithic, every possible method must be determine a priori and be defined in the class; (b) it doesn’t allow new methods to be added Tensor without touching the main class; and (c) it unnecessarily forces users to user the more verbose `Tensor.dot(a, b)`.

Point (a) in theory could be made better by creating a `TensorOps` protocols. However, because type constraints cannot currently be placed on extensions, it is not currently possible to implement.

One potential solution would be to add/extend an attribute for generic functions that would force multiple versions of that function to be created. There is already there is a `@_specialize` attribute, but you have to: (a) manually write out all the cases you want to cover; and (b) only affects the compiled code, which does not change this behavior. Due to the fact that `@_specialize` exists, I’m going to assume it wouldn’t be a major change to the language to extend the behavior to compile-time dispatch.

Thanks!
Abe


(Robert Widmann) #2

I don't understand how this change would cause method dispatch to invoke a different prototype. Specialization in either language mentioned doesn't do that.

~Robert Widmann

2017/02/05 11:28、Abe Schneider via swift-evolution <swift-evolution@swift.org> のメッセージ:

···

Hi all,

The current behavior of generics in Swift causes it lose type information at compile time due to the desire of maintaining a single version of the function. This runs counter to how c++ works, which creates a new copy of a function per type, but preserves information to be preserved. This can cause unexpected behavior from the user’s perspective:

   protocol DispatchType {}
   class DispatchType1: DispatchType {}

   func doBar<D:DispatchType>(value:D) {
       print(“General function called")
   }

   func doBar(value:DispatchType1) {
       print("DispatchType1 called")
   }

   func test<D:DispatchType>(value:D) {
       doBar(value: value)
   }

   test(value: d1) // “General function called”, but it’s not obvious why

The suggested method to get around this issue is to use a protocol to create a witness table, allowing for runtime dispatch. However, this approach is not ideal in all cases because: (a) the overhead of runtime dispatch may not be desirable, especially because this is something that can be determined at compile time; and (b) there are some designs in which this behavior can complicate things.

One example of a design where this behavior can be problematic is when a protocol is used to determine what functions get dispatched:

   protocol Storage { … }
   class Tensor<S:Storage> { … }

   class CBlasStorage: Storage { … }
   class OpenCLStorage: Storage { … }

   func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> { … }

   // like behavior, these will not work if called from another generic function (but will work for non-generic functions)
   func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> where S:CBlasStorage { … }
   func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> where S:OpenCLStorage { … }

In this case, depending on the underlying storage, we want an optimized version of `dot` to be called. To make this work correctly we can add static methods to `Tensor`, but this has several drawbacks: (a) it makes the `Tensor` class monolithic, every possible method must be determine a priori and be defined in the class; (b) it doesn’t allow new methods to be added Tensor without touching the main class; and (c) it unnecessarily forces users to user the more verbose `Tensor.dot(a, b)`.

Point (a) in theory could be made better by creating a `TensorOps` protocols. However, because type constraints cannot currently be placed on extensions, it is not currently possible to implement.

One potential solution would be to add/extend an attribute for generic functions that would force multiple versions of that function to be created. There is already there is a `@_specialize` attribute, but you have to: (a) manually write out all the cases you want to cover; and (b) only affects the compiled code, which does not change this behavior. Due to the fact that `@_specialize` exists, I’m going to assume it wouldn’t be a major change to the language to extend the behavior to compile-time dispatch.

Thanks!
Abe
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Slava Pestov) #3

The suggested method to get around this issue is to use a protocol to create a witness table, allowing for runtime dispatch. However, this approach is not ideal in all cases because: (a) the overhead of runtime dispatch may not be desirable, especially because this is something that can be determined at compile time; and

Just as the compiler is able to generate specializations of generic functions, it can also devirtualize protocol method calls. The two optimizations go hand-in-hand.

One potential solution would be to add/extend an attribute for generic functions that would force multiple versions of that function to be created. There is already there is a `@_specialize` attribute, but you have to: (a) manually write out all the cases you want to cover; and (b) only affects the compiled code, which does not change this behavior. Due to the fact that `@_specialize` exists, I’m going to assume it wouldn’t be a major change to the language to extend the behavior to compile-time dispatch.

In Swift, specialization and devirtualization are optimization passes which are performed in the SIL intermediate representation, long after type checking, name lookup and overload resolution. In this sense it is completely different from C++, where parsed templates are stored as a sort of untyped AST, allowing some delayed name lookup to be performed.

Implementing C++-style templates would be a major complication in Swift and not something we’re likely to attempt at any point in time. The combination of specialization and devirtualization should give you similar performance characteristics, with the improved type safety gained from being able to type-check the unspecialized generic function itself.

···

On Feb 5, 2017, at 8:28 AM, Abe Schneider via swift-evolution <swift-evolution@swift.org> wrote:

Thanks!
Abe
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Abe Schneider) #4

Hi Robert,

Sorry, I’m not sure I understand your question. In c++ you can do the following:

struct Storage {};
struct CBlasStorage: Storage {};

template <typename S> class Tensor {};

template <typename S>
Tensor<S> dot(const Tensor<S> &lhs, const Tensor<S> &rhs) {
  std::cout << "general version called" << std::endl;
  Tensor<S> result;
  return result;
}

// specialized version for CBlasStorage
template <>
Tensor<CBlasStorage> dot(const Tensor<CBlasStorage> &lhs, const Tensor<CBlasStorage> &rhs) {
  std::cout << "specialized version called" << std::endl;
  Tensor<CBlasStorage> result;
  return result;
}

// this preserves type information and will call the appropriate `dot`
template <typename T>
void doSomething(const Tensor<T> &lhs, const Tensor<T> &rhs) {
  auto result = dot(lhs, rhs);
}

int main(int argc, char **argv) {
  Tensor<CBlasStorage> a, b;
  doSomething(a, b); // we should get "specialized version called"
}

The potential equivalent for Swift could look like:

@_specialize_all
func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> { … }

Which would cause the compile to create a version of `dot` per S type that it gets called with. Thus, when `doSomething` is called, it would dispatch to that version of `dot`, allowing the type information to be preserved in the same way it does in c++.

Abe

···

On Feb 5, 2017, at 11:35 AM, Robert Widmann <devteam.codafi@gmail.com> wrote:

I don't understand how this change would cause method dispatch to invoke a different prototype. Specialization in either language mentioned doesn't do that.

~Robert Widmann

2017/02/05 11:28、Abe Schneider via swift-evolution <swift-evolution@swift.org> のメッセージ:

Hi all,

The current behavior of generics in Swift causes it lose type information at compile time due to the desire of maintaining a single version of the function. This runs counter to how c++ works, which creates a new copy of a function per type, but preserves information to be preserved. This can cause unexpected behavior from the user’s perspective:

  protocol DispatchType {}
  class DispatchType1: DispatchType {}

  func doBar<D:DispatchType>(value:D) {
      print(“General function called")
  }

  func doBar(value:DispatchType1) {
      print("DispatchType1 called")
  }

  func test<D:DispatchType>(value:D) {
      doBar(value: value)
  }

  test(value: d1) // “General function called”, but it’s not obvious why

The suggested method to get around this issue is to use a protocol to create a witness table, allowing for runtime dispatch. However, this approach is not ideal in all cases because: (a) the overhead of runtime dispatch may not be desirable, especially because this is something that can be determined at compile time; and (b) there are some designs in which this behavior can complicate things.

One example of a design where this behavior can be problematic is when a protocol is used to determine what functions get dispatched:

  protocol Storage { … }
  class Tensor<S:Storage> { … }

  class CBlasStorage: Storage { … }
  class OpenCLStorage: Storage { … }

  func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> { … }

  // like behavior, these will not work if called from another generic function (but will work for non-generic functions)
  func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> where S:CBlasStorage { … }
  func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> where S:OpenCLStorage { … }

In this case, depending on the underlying storage, we want an optimized version of `dot` to be called. To make this work correctly we can add static methods to `Tensor`, but this has several drawbacks: (a) it makes the `Tensor` class monolithic, every possible method must be determine a priori and be defined in the class; (b) it doesn’t allow new methods to be added Tensor without touching the main class; and (c) it unnecessarily forces users to user the more verbose `Tensor.dot(a, b)`.

Point (a) in theory could be made better by creating a `TensorOps` protocols. However, because type constraints cannot currently be placed on extensions, it is not currently possible to implement.

One potential solution would be to add/extend an attribute for generic functions that would force multiple versions of that function to be created. There is already there is a `@_specialize` attribute, but you have to: (a) manually write out all the cases you want to cover; and (b) only affects the compiled code, which does not change this behavior. Due to the fact that `@_specialize` exists, I’m going to assume it wouldn’t be a major change to the language to extend the behavior to compile-time dispatch.

Thanks!
Abe
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Abe Schneider) #5

Hi Slava,

I'm actually less worried about the performance issue and more on the
impact on design. Specifically, calling one generic from another
effectively loses type information. Because of this, specializations
stop working, disallowing certain design patterns. While you can put
your functions inside a protocol or class to overcome this problem,
this can create large monolithic classes (in my case it makes one of
my classes go from ~300 lines to ~1500 lines of code).

I think it might be possible to deal with some of these issues if: (a)
extensions could define methods, not in the protocol, that got
dynamically called; (b) constraints could be placed on extensions of
protocols.

My preference is still allow generics to behave in a fashion similar
to C++ templates (regardless of the underlying implementation), as
making everything have to rely on protocols or classes makes Swift
feel less mixed paradigm (like c++) and more OOP focused (like Java).
That said, it sounds like that may be difficult to accomplish at least
in the immediate future.

Thanks!
Abe

···

On Wed, Feb 8, 2017 at 12:03 AM, Slava Pestov <spestov@apple.com> wrote:

On Feb 5, 2017, at 8:28 AM, Abe Schneider via swift-evolution <swift-evolution@swift.org> wrote:

The suggested method to get around this issue is to use a protocol to create a witness table, allowing for runtime dispatch. However, this approach is not ideal in all cases because: (a) the overhead of runtime dispatch may not be desirable, especially because this is something that can be determined at compile time; and

Just as the compiler is able to generate specializations of generic functions, it can also devirtualize protocol method calls. The two optimizations go hand-in-hand.

One potential solution would be to add/extend an attribute for generic functions that would force multiple versions of that function to be created. There is already there is a `@_specialize` attribute, but you have to: (a) manually write out all the cases you want to cover; and (b) only affects the compiled code, which does not change this behavior. Due to the fact that `@_specialize` exists, I’m going to assume it wouldn’t be a major change to the language to extend the behavior to compile-time dispatch.

In Swift, specialization and devirtualization are optimization passes which are performed in the SIL intermediate representation, long after type checking, name lookup and overload resolution. In this sense it is completely different from C++, where parsed templates are stored as a sort of untyped AST, allowing some delayed name lookup to be performed.

Implementing C++-style templates would be a major complication in Swift and not something we’re likely to attempt at any point in time. The combination of specialization and devirtualization should give you similar performance characteristics, with the improved type safety gained from being able to type-check the unspecialized generic function itself.

Thanks!
Abe
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Robert Widmann) #6

Oh, I see. The constraint solver is picking an overload that better matches the caller rather than the callee's type, which differs from C++ because the template expansion process considers specific-type overloads more specific. We don't consider less-generic prototypes than the caller here because we aren't performing a (major) syntactic transformation in the process of solving a system of type variables. In order to change the language to adopt this feature, Sema would have to have knowledge of the candidate set of specializations, either user-specified or SILOptimizer-generated, beforehand. It's not impossible to imagine, but it does create an interesting backdependency on future potential optimizations, and would potentially majorly change the behavior of a Debug or Release build (unless specialization were forced at all optimization levels).

~Robert Widmann

2017/02/05 12:37、Abe Schneider <abe.schneider@gmail.com> のメッセージ:

···

Hi Robert,

Sorry, I’m not sure I understand your question. In c++ you can do the following:

struct Storage {};
struct CBlasStorage: Storage {};

template <typename S> class Tensor {};

template <typename S>
Tensor<S> dot(const Tensor<S> &lhs, const Tensor<S> &rhs) {
  std::cout << "general version called" << std::endl;
  Tensor<S> result;
  return result;
}

// specialized version for CBlasStorage
template <>
Tensor<CBlasStorage> dot(const Tensor<CBlasStorage> &lhs, const Tensor<CBlasStorage> &rhs) {
  std::cout << "specialized version called" << std::endl;
  Tensor<CBlasStorage> result;
  return result;
}

// this preserves type information and will call the appropriate `dot`
template <typename T>
void doSomething(const Tensor<T> &lhs, const Tensor<T> &rhs) {
  auto result = dot(lhs, rhs);
}

int main(int argc, char **argv) {
  Tensor<CBlasStorage> a, b;
  doSomething(a, b); // we should get "specialized version called"
}

The potential equivalent for Swift could look like:

@_specialize_all
func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> { … }

Which would cause the compile to create a version of `dot` per S type that it gets called with. Thus, when `doSomething` is called, it would dispatch to that version of `dot`, allowing the type information to be preserved in the same way it does in c++.

Abe

On Feb 5, 2017, at 11:35 AM, Robert Widmann <devteam.codafi@gmail.com> wrote:

I don't understand how this change would cause method dispatch to invoke a different prototype. Specialization in either language mentioned doesn't do that.

~Robert Widmann

2017/02/05 11:28、Abe Schneider via swift-evolution <swift-evolution@swift.org> のメッセージ:

Hi all,

The current behavior of generics in Swift causes it lose type information at compile time due to the desire of maintaining a single version of the function. This runs counter to how c++ works, which creates a new copy of a function per type, but preserves information to be preserved. This can cause unexpected behavior from the user’s perspective:

  protocol DispatchType {}
  class DispatchType1: DispatchType {}

  func doBar<D:DispatchType>(value:D) {
      print(“General function called")
  }

  func doBar(value:DispatchType1) {
      print("DispatchType1 called")
  }

  func test<D:DispatchType>(value:D) {
      doBar(value: value)
  }

  test(value: d1) // “General function called”, but it’s not obvious why

The suggested method to get around this issue is to use a protocol to create a witness table, allowing for runtime dispatch. However, this approach is not ideal in all cases because: (a) the overhead of runtime dispatch may not be desirable, especially because this is something that can be determined at compile time; and (b) there are some designs in which this behavior can complicate things.

One example of a design where this behavior can be problematic is when a protocol is used to determine what functions get dispatched:

  protocol Storage { … }
  class Tensor<S:Storage> { … }

  class CBlasStorage: Storage { … }
  class OpenCLStorage: Storage { … }

  func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> { … }

  // like behavior, these will not work if called from another generic function (but will work for non-generic functions)
  func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> where S:CBlasStorage { … }
  func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> where S:OpenCLStorage { … }

In this case, depending on the underlying storage, we want an optimized version of `dot` to be called. To make this work correctly we can add static methods to `Tensor`, but this has several drawbacks: (a) it makes the `Tensor` class monolithic, every possible method must be determine a priori and be defined in the class; (b) it doesn’t allow new methods to be added Tensor without touching the main class; and (c) it unnecessarily forces users to user the more verbose `Tensor.dot(a, b)`.

Point (a) in theory could be made better by creating a `TensorOps` protocols. However, because type constraints cannot currently be placed on extensions, it is not currently possible to implement.

One potential solution would be to add/extend an attribute for generic functions that would force multiple versions of that function to be created. There is already there is a `@_specialize` attribute, but you have to: (a) manually write out all the cases you want to cover; and (b) only affects the compiled code, which does not change this behavior. Due to the fact that `@_specialize` exists, I’m going to assume it wouldn’t be a major change to the language to extend the behavior to compile-time dispatch.

Thanks!
Abe
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Abe Schneider) #7

Hi Robert,

Exactly. The benefit being that you can figure out the correct function to dispatch entirely at compile time. My understanding is that Swift doesn’t do this because of the associated code bloat (and it’s usually not necessary). However, I think there is some important functionality by allowing specialization to control dispatch in a similar way to c++. There is also the design element — my (fairly) succinct Tensor class that used to be ~300 lines is now already close to an additional 1000 lines of code and growing. While the type of library I’m writing might be outside of what is normally done with Swift, I suspect the design pattern I’m using crops up in other places, as well as the need for dispatch on specialization (e.g. http://stackoverflow.com/questions/41640321/extending-collection-with-a-recursive-property-method-that-depends-on-the-elemen).

As far as changes to Swift, `@_specialize` already does exactly this (except it is treated as a hint). You would need to transform the function to something like <function-name>_<mangled-type-name>(…) and a table of transformed functions, but after that you can just treat the functions as normal functions (and ignore the fact they were defined as generic). So, yes, specializations should be forced at every level. While this will lead to some code bloat, since it only occurs for the functions marked by the user, I would imagine it’s: (a) limited to the extent it occurs; and (b) manageable by simply not using the attribute (and using protocol witness tables instead). But at least that way you give the user the choice to do what is best for the particular situation.

Thanks!
A

···

On Feb 5, 2017, at 1:46 PM, Robert Widmann <devteam.codafi@gmail.com> wrote:

Oh, I see. The constraint solver is picking an overload that better matches the caller rather than the callee's type, which differs from C++ because the template expansion process considers specific-type overloads more specific. We don't consider less-generic prototypes than the caller here because we aren't performing a (major) syntactic transformation in the process of solving a system of type variables. In order to change the language to adopt this feature, Sema would have to have knowledge of the candidate set of specializations, either user-specified or SILOptimizer-generated, beforehand. It's not impossible to imagine, but it does create an interesting backdependency on future potential optimizations, and would potentially majorly change the behavior of a Debug or Release build (unless specialization were forced at all optimization levels).

~Robert Widmann

2017/02/05 12:37、Abe Schneider <abe.schneider@gmail.com <mailto:abe.schneider@gmail.com>> のメッセージ:

Hi Robert,

Sorry, I’m not sure I understand your question. In c++ you can do the following:

struct Storage {};
struct CBlasStorage: Storage {};

template <typename S> class Tensor {};

template <typename S>
Tensor<S> dot(const Tensor<S> &lhs, const Tensor<S> &rhs) {
  std::cout << "general version called" << std::endl;
  Tensor<S> result;
  return result;
}

// specialized version for CBlasStorage
template <>
Tensor<CBlasStorage> dot(const Tensor<CBlasStorage> &lhs, const Tensor<CBlasStorage> &rhs) {
  std::cout << "specialized version called" << std::endl;
  Tensor<CBlasStorage> result;
  return result;
}

// this preserves type information and will call the appropriate `dot`
template <typename T>
void doSomething(const Tensor<T> &lhs, const Tensor<T> &rhs) {
  auto result = dot(lhs, rhs);
}

int main(int argc, char **argv) {
  Tensor<CBlasStorage> a, b;
  doSomething(a, b); // we should get "specialized version called"
}

The potential equivalent for Swift could look like:

@_specialize_all
func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> { … }

Which would cause the compile to create a version of `dot` per S type that it gets called with. Thus, when `doSomething` is called, it would dispatch to that version of `dot`, allowing the type information to be preserved in the same way it does in c++.

Abe

On Feb 5, 2017, at 11:35 AM, Robert Widmann <devteam.codafi@gmail.com <mailto:devteam.codafi@gmail.com>> wrote:

I don't understand how this change would cause method dispatch to invoke a different prototype. Specialization in either language mentioned doesn't do that.

~Robert Widmann

2017/02/05 11:28、Abe Schneider via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> のメッセージ:

Hi all,

The current behavior of generics in Swift causes it lose type information at compile time due to the desire of maintaining a single version of the function. This runs counter to how c++ works, which creates a new copy of a function per type, but preserves information to be preserved. This can cause unexpected behavior from the user’s perspective:

  protocol DispatchType {}
  class DispatchType1: DispatchType {}

  func doBar<D:DispatchType>(value:D) {
      print(“General function called")
  }

  func doBar(value:DispatchType1) {
      print("DispatchType1 called")
  }

  func test<D:DispatchType>(value:D) {
      doBar(value: value)
  }

  test(value: d1) // “General function called”, but it’s not obvious why

The suggested method to get around this issue is to use a protocol to create a witness table, allowing for runtime dispatch. However, this approach is not ideal in all cases because: (a) the overhead of runtime dispatch may not be desirable, especially because this is something that can be determined at compile time; and (b) there are some designs in which this behavior can complicate things.

One example of a design where this behavior can be problematic is when a protocol is used to determine what functions get dispatched:

  protocol Storage { … }
  class Tensor<S:Storage> { … }

  class CBlasStorage: Storage { … }
  class OpenCLStorage: Storage { … }

  func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> { … }

  // like behavior, these will not work if called from another generic function (but will work for non-generic functions)
  func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> where S:CBlasStorage { … }
  func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> where S:OpenCLStorage { … }

In this case, depending on the underlying storage, we want an optimized version of `dot` to be called. To make this work correctly we can add static methods to `Tensor`, but this has several drawbacks: (a) it makes the `Tensor` class monolithic, every possible method must be determine a priori and be defined in the class; (b) it doesn’t allow new methods to be added Tensor without touching the main class; and (c) it unnecessarily forces users to user the more verbose `Tensor.dot(a, b)`.

Point (a) in theory could be made better by creating a `TensorOps` protocols. However, because type constraints cannot currently be placed on extensions, it is not currently possible to implement.

One potential solution would be to add/extend an attribute for generic functions that would force multiple versions of that function to be created. There is already there is a `@_specialize` attribute, but you have to: (a) manually write out all the cases you want to cover; and (b) only affects the compiled code, which does not change this behavior. Due to the fact that `@_specialize` exists, I’m going to assume it wouldn’t be a major change to the language to extend the behavior to compile-time dispatch.

Thanks!
Abe
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution


(Douglas Gregor) #8

Hi Robert,

Exactly. The benefit being that you can figure out the correct function to dispatch entirely at compile time. My understanding is that Swift doesn’t do this because of the associated code bloat (and it’s usually not necessary). However, I think there is some important functionality by allowing specialization to control dispatch in a similar way to c++. There is also the design element — my (fairly) succinct Tensor class that used to be ~300 lines is now already close to an additional 1000 lines of code and growing. While the type of library I’m writing might be outside of what is normally done with Swift, I suspect the design pattern I’m using crops up in other places, as well as the need for dispatch on specialization (e.g. http://stackoverflow.com/questions/41640321/extending-collection-with-a-recursive-property-method-that-depends-on-the-elemen).

You can’t figure out the correct function to dispatch entirely at compile time because Swift supports retroactive modeling. Let’s make this a super-simple example:

  // Module A
  public protocol P { }
  public func f<T>(_:T) { print(“unspecialized”) }
  public func f<T: P>(_: T) { print(“specialized”) }

  public func g<T>(_ x: T) { f(x) }

  // Module B
  import A
  func testG(x: Int) {
    g(x) // the best we can statically do is print “unspecialized”; Int doesn’t conform to A.P, but...
  }

  // Module C
  import A
  public extension A: P { } // dynamically, Int does conform to A.P!

Swift’s model is that the selection among ad hoc overloads is performed statically based on local knowledge, and is consistent across all “specializations” of a generic function. Protocol requirements and overridable methods are the customization points.

Selecting ad hoc overloads at runtime is possible, but of course it has downsides. You could run into run-time ambiguities, for example:

  // Module A
  public protocol P { }
  public protocol Q { }
  public func f<T>(_:T) { print(“unspecialized”) }
  public func f<T: P>(_: T) { print(“specialized for P”) }
  public func f<T: Q>(_: T) { print(“specialized for Q”) }

  public func g<T>(_ x: T) { f(x) }

  // Module B
  import A
  public extension Int: P { }

  // Module C
  import A
  public extension Int: Q { }

  // Module C
  import A
  func testG(x: Int) {
    g(x) // run-time ambiguity: which specialized “f” do we get?
  }

There are reasonable answers here if we know what the potential set of overloads is at compile-time. It’s a problem I’ve been interested in for a long time <https://parasol.tamu.edu/~jarvi/papers/pldi06.pdf>. That dynamic dispatch can be implemented somewhat reasonably (the compiler can emit a static decision tree so long as we’re willing to limit the set of overloads to the ones that are visible from g(_:), and can be folded away by the optimizer when we’re specializing the function and the visibility of the types and/or protocols in question is limited.

As far as changes to Swift, `@_specialize` already does exactly this (except it is treated as a hint). You would need to transform the function to something like <function-name>_<mangled-type-name>(…) and a table of transformed functions, but after that you can just treat the functions as normal functions (and ignore the fact they were defined as generic). So, yes, specializations should be forced at every level. While this will lead to some code bloat, since it only occurs for the functions marked by the user, I would imagine it’s: (a) limited to the extent it occurs; and (b) manageable by simply not using the attribute (and using protocol witness tables instead). But at least that way you give the user the choice to do what is best for the particular situation.

For reference, `@_specialize` is doing dynamic dispatch. That dynamic dispatch gets optimized away when we specialize the generic function, the same way I mentioned about.

There might be a reasonable solution to the problem you’re encountering. I don’t think it’s “force specialization at compile time like C++”, but something akin to grouping together multiple overloads where we want dynamic dispatch of callers that invoke them, statically diagnosing when that set of overloads can have ambiguities in it (see the paper I referenced above), and teaching the optimizers to resolve that dynamic dispatch statically whenever possible.

  - Doug

···

On Feb 5, 2017, at 5:36 PM, Abe Schneider via swift-evolution <swift-evolution@swift.org> wrote:

Thanks!
A

On Feb 5, 2017, at 1:46 PM, Robert Widmann <devteam.codafi@gmail.com <mailto:devteam.codafi@gmail.com>> wrote:

Oh, I see. The constraint solver is picking an overload that better matches the caller rather than the callee's type, which differs from C++ because the template expansion process considers specific-type overloads more specific. We don't consider less-generic prototypes than the caller here because we aren't performing a (major) syntactic transformation in the process of solving a system of type variables. In order to change the language to adopt this feature, Sema would have to have knowledge of the candidate set of specializations, either user-specified or SILOptimizer-generated, beforehand. It's not impossible to imagine, but it does create an interesting backdependency on future potential optimizations, and would potentially majorly change the behavior of a Debug or Release build (unless specialization were forced at all optimization levels).

~Robert Widmann

2017/02/05 12:37、Abe Schneider <abe.schneider@gmail.com <mailto:abe.schneider@gmail.com>> のメッセージ:

Hi Robert,

Sorry, I’m not sure I understand your question. In c++ you can do the following:

struct Storage {};
struct CBlasStorage: Storage {};

template <typename S> class Tensor {};

template <typename S>
Tensor<S> dot(const Tensor<S> &lhs, const Tensor<S> &rhs) {
  std::cout << "general version called" << std::endl;
  Tensor<S> result;
  return result;
}

// specialized version for CBlasStorage
template <>
Tensor<CBlasStorage> dot(const Tensor<CBlasStorage> &lhs, const Tensor<CBlasStorage> &rhs) {
  std::cout << "specialized version called" << std::endl;
  Tensor<CBlasStorage> result;
  return result;
}

// this preserves type information and will call the appropriate `dot`
template <typename T>
void doSomething(const Tensor<T> &lhs, const Tensor<T> &rhs) {
  auto result = dot(lhs, rhs);
}

int main(int argc, char **argv) {
  Tensor<CBlasStorage> a, b;
  doSomething(a, b); // we should get "specialized version called"
}

The potential equivalent for Swift could look like:

@_specialize_all
func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> { … }

Which would cause the compile to create a version of `dot` per S type that it gets called with. Thus, when `doSomething` is called, it would dispatch to that version of `dot`, allowing the type information to be preserved in the same way it does in c++.

Abe

On Feb 5, 2017, at 11:35 AM, Robert Widmann <devteam.codafi@gmail.com <mailto:devteam.codafi@gmail.com>> wrote:

I don't understand how this change would cause method dispatch to invoke a different prototype. Specialization in either language mentioned doesn't do that.

~Robert Widmann

2017/02/05 11:28、Abe Schneider via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> のメッセージ:

Hi all,

The current behavior of generics in Swift causes it lose type information at compile time due to the desire of maintaining a single version of the function. This runs counter to how c++ works, which creates a new copy of a function per type, but preserves information to be preserved. This can cause unexpected behavior from the user’s perspective:

  protocol DispatchType {}
  class DispatchType1: DispatchType {}

  func doBar<D:DispatchType>(value:D) {
      print(“General function called")
  }

  func doBar(value:DispatchType1) {
      print("DispatchType1 called")
  }

  func test<D:DispatchType>(value:D) {
      doBar(value: value)
  }

  test(value: d1) // “General function called”, but it’s not obvious why

The suggested method to get around this issue is to use a protocol to create a witness table, allowing for runtime dispatch. However, this approach is not ideal in all cases because: (a) the overhead of runtime dispatch may not be desirable, especially because this is something that can be determined at compile time; and (b) there are some designs in which this behavior can complicate things.

One example of a design where this behavior can be problematic is when a protocol is used to determine what functions get dispatched:

  protocol Storage { … }
  class Tensor<S:Storage> { … }

  class CBlasStorage: Storage { … }
  class OpenCLStorage: Storage { … }

  func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> { … }

  // like behavior, these will not work if called from another generic function (but will work for non-generic functions)
  func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> where S:CBlasStorage { … }
  func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> where S:OpenCLStorage { … }

In this case, depending on the underlying storage, we want an optimized version of `dot` to be called. To make this work correctly we can add static methods to `Tensor`, but this has several drawbacks: (a) it makes the `Tensor` class monolithic, every possible method must be determine a priori and be defined in the class; (b) it doesn’t allow new methods to be added Tensor without touching the main class; and (c) it unnecessarily forces users to user the more verbose `Tensor.dot(a, b)`.

Point (a) in theory could be made better by creating a `TensorOps` protocols. However, because type constraints cannot currently be placed on extensions, it is not currently possible to implement.

One potential solution would be to add/extend an attribute for generic functions that would force multiple versions of that function to be created. There is already there is a `@_specialize` attribute, but you have to: (a) manually write out all the cases you want to cover; and (b) only affects the compiled code, which does not change this behavior. Due to the fact that `@_specialize` exists, I’m going to assume it wouldn’t be a major change to the language to extend the behavior to compile-time dispatch.

Thanks!
Abe
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Abe Schneider) #9

Thank you for the explanation, that makes sense. Do you think it makes sense to create a proposal to allow handling of specialized overloads in Swift? I suspect the issues caused by the current behavior: (a) will continue to confuse a lot of people coming from c++; and (b) affects a wider audience than just the library I’m developing.

Abe

···

On Feb 6, 2017, at 1:06 PM, Douglas Gregor <dgregor@apple.com> wrote:

On Feb 5, 2017, at 5:36 PM, Abe Schneider via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hi Robert,

Exactly. The benefit being that you can figure out the correct function to dispatch entirely at compile time. My understanding is that Swift doesn’t do this because of the associated code bloat (and it’s usually not necessary). However, I think there is some important functionality by allowing specialization to control dispatch in a similar way to c++. There is also the design element — my (fairly) succinct Tensor class that used to be ~300 lines is now already close to an additional 1000 lines of code and growing. While the type of library I’m writing might be outside of what is normally done with Swift, I suspect the design pattern I’m using crops up in other places, as well as the need for dispatch on specialization (e.g. http://stackoverflow.com/questions/41640321/extending-collection-with-a-recursive-property-method-that-depends-on-the-elemen).

You can’t figure out the correct function to dispatch entirely at compile time because Swift supports retroactive modeling. Let’s make this a super-simple example:

  // Module A
  public protocol P { }
  public func f<T>(_:T) { print(“unspecialized”) }
  public func f<T: P>(_: T) { print(“specialized”) }

  public func g<T>(_ x: T) { f(x) }

  // Module B
  import A
  func testG(x: Int) {
    g(x) // the best we can statically do is print “unspecialized”; Int doesn’t conform to A.P, but...
  }

  // Module C
  import A
  public extension A: P { } // dynamically, Int does conform to A.P!

Swift’s model is that the selection among ad hoc overloads is performed statically based on local knowledge, and is consistent across all “specializations” of a generic function. Protocol requirements and overridable methods are the customization points.

Selecting ad hoc overloads at runtime is possible, but of course it has downsides. You could run into run-time ambiguities, for example:

  // Module A
  public protocol P { }
  public protocol Q { }
  public func f<T>(_:T) { print(“unspecialized”) }
  public func f<T: P>(_: T) { print(“specialized for P”) }
  public func f<T: Q>(_: T) { print(“specialized for Q”) }

  public func g<T>(_ x: T) { f(x) }

  // Module B
  import A
  public extension Int: P { }

  // Module C
  import A
  public extension Int: Q { }

  // Module C
  import A
  func testG(x: Int) {
    g(x) // run-time ambiguity: which specialized “f” do we get?
  }

There are reasonable answers here if we know what the potential set of overloads is at compile-time. It’s a problem I’ve been interested in for a long time <https://parasol.tamu.edu/~jarvi/papers/pldi06.pdf>. That dynamic dispatch can be implemented somewhat reasonably (the compiler can emit a static decision tree so long as we’re willing to limit the set of overloads to the ones that are visible from g(_:), and can be folded away by the optimizer when we’re specializing the function and the visibility of the types and/or protocols in question is limited.

As far as changes to Swift, `@_specialize` already does exactly this (except it is treated as a hint). You would need to transform the function to something like <function-name>_<mangled-type-name>(…) and a table of transformed functions, but after that you can just treat the functions as normal functions (and ignore the fact they were defined as generic). So, yes, specializations should be forced at every level. While this will lead to some code bloat, since it only occurs for the functions marked by the user, I would imagine it’s: (a) limited to the extent it occurs; and (b) manageable by simply not using the attribute (and using protocol witness tables instead). But at least that way you give the user the choice to do what is best for the particular situation.

For reference, `@_specialize` is doing dynamic dispatch. That dynamic dispatch gets optimized away when we specialize the generic function, the same way I mentioned about.

There might be a reasonable solution to the problem you’re encountering. I don’t think it’s “force specialization at compile time like C++”, but something akin to grouping together multiple overloads where we want dynamic dispatch of callers that invoke them, statically diagnosing when that set of overloads can have ambiguities in it (see the paper I referenced above), and teaching the optimizers to resolve that dynamic dispatch statically whenever possible.

  - Doug

Thanks!
A

On Feb 5, 2017, at 1:46 PM, Robert Widmann <devteam.codafi@gmail.com <mailto:devteam.codafi@gmail.com>> wrote:

Oh, I see. The constraint solver is picking an overload that better matches the caller rather than the callee's type, which differs from C++ because the template expansion process considers specific-type overloads more specific. We don't consider less-generic prototypes than the caller here because we aren't performing a (major) syntactic transformation in the process of solving a system of type variables. In order to change the language to adopt this feature, Sema would have to have knowledge of the candidate set of specializations, either user-specified or SILOptimizer-generated, beforehand. It's not impossible to imagine, but it does create an interesting backdependency on future potential optimizations, and would potentially majorly change the behavior of a Debug or Release build (unless specialization were forced at all optimization levels).

~Robert Widmann

2017/02/05 12:37、Abe Schneider <abe.schneider@gmail.com <mailto:abe.schneider@gmail.com>> のメッセージ:

Hi Robert,

Sorry, I’m not sure I understand your question. In c++ you can do the following:

struct Storage {};
struct CBlasStorage: Storage {};

template <typename S> class Tensor {};

template <typename S>
Tensor<S> dot(const Tensor<S> &lhs, const Tensor<S> &rhs) {
  std::cout << "general version called" << std::endl;
  Tensor<S> result;
  return result;
}

// specialized version for CBlasStorage
template <>
Tensor<CBlasStorage> dot(const Tensor<CBlasStorage> &lhs, const Tensor<CBlasStorage> &rhs) {
  std::cout << "specialized version called" << std::endl;
  Tensor<CBlasStorage> result;
  return result;
}

// this preserves type information and will call the appropriate `dot`
template <typename T>
void doSomething(const Tensor<T> &lhs, const Tensor<T> &rhs) {
  auto result = dot(lhs, rhs);
}

int main(int argc, char **argv) {
  Tensor<CBlasStorage> a, b;
  doSomething(a, b); // we should get "specialized version called"
}

The potential equivalent for Swift could look like:

@_specialize_all
func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> { … }

Which would cause the compile to create a version of `dot` per S type that it gets called with. Thus, when `doSomething` is called, it would dispatch to that version of `dot`, allowing the type information to be preserved in the same way it does in c++.

Abe

On Feb 5, 2017, at 11:35 AM, Robert Widmann <devteam.codafi@gmail.com <mailto:devteam.codafi@gmail.com>> wrote:

I don't understand how this change would cause method dispatch to invoke a different prototype. Specialization in either language mentioned doesn't do that.

~Robert Widmann

2017/02/05 11:28、Abe Schneider via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> のメッセージ:

Hi all,

The current behavior of generics in Swift causes it lose type information at compile time due to the desire of maintaining a single version of the function. This runs counter to how c++ works, which creates a new copy of a function per type, but preserves information to be preserved. This can cause unexpected behavior from the user’s perspective:

  protocol DispatchType {}
  class DispatchType1: DispatchType {}

  func doBar<D:DispatchType>(value:D) {
      print(“General function called")
  }

  func doBar(value:DispatchType1) {
      print("DispatchType1 called")
  }

  func test<D:DispatchType>(value:D) {
      doBar(value: value)
  }

  test(value: d1) // “General function called”, but it’s not obvious why

The suggested method to get around this issue is to use a protocol to create a witness table, allowing for runtime dispatch. However, this approach is not ideal in all cases because: (a) the overhead of runtime dispatch may not be desirable, especially because this is something that can be determined at compile time; and (b) there are some designs in which this behavior can complicate things.

One example of a design where this behavior can be problematic is when a protocol is used to determine what functions get dispatched:

  protocol Storage { … }
  class Tensor<S:Storage> { … }

  class CBlasStorage: Storage { … }
  class OpenCLStorage: Storage { … }

  func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> { … }

  // like behavior, these will not work if called from another generic function (but will work for non-generic functions)
  func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> where S:CBlasStorage { … }
  func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> where S:OpenCLStorage { … }

In this case, depending on the underlying storage, we want an optimized version of `dot` to be called. To make this work correctly we can add static methods to `Tensor`, but this has several drawbacks: (a) it makes the `Tensor` class monolithic, every possible method must be determine a priori and be defined in the class; (b) it doesn’t allow new methods to be added Tensor without touching the main class; and (c) it unnecessarily forces users to user the more verbose `Tensor.dot(a, b)`.

Point (a) in theory could be made better by creating a `TensorOps` protocols. However, because type constraints cannot currently be placed on extensions, it is not currently possible to implement.

One potential solution would be to add/extend an attribute for generic functions that would force multiple versions of that function to be created. There is already there is a `@_specialize` attribute, but you have to: (a) manually write out all the cases you want to cover; and (b) only affects the compiled code, which does not change this behavior. Due to the fact that `@_specialize` exists, I’m going to assume it wouldn’t be a major change to the language to extend the behavior to compile-time dispatch.

Thanks!
Abe
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution


(Joe Groff) #10

Specialization handles casts, so you can handle some cases today by writing the implementation selection logic out:

func f<T>(x: T) {
  if let i = x as? Int { fooImplForInt(i) }
  else if let f = x as? Float { fooImplForFloat(f) }
  else { fooImplForGeneric(x) }
}

And you'll get the `Int` or `Float` implementation when the specializer optimizes for T == Int or T == Float. This approach has some limitations today, since protocol existentials in particular have limited functionality, and you don't get type refinement of T from the cast. Perhaps we could support testing general type constraints as a form of statement condition, something like this:

func f<T>(x: T) {
  if <T: P> {
    // we can assume T: P here
    x.fooImplFromP()
  } else if <T: Q> {
    // we can assume T: Q here
    x.fooImplFromQ()
  } else {
    fooImplForGeneric(x)
  }
}

I think the fact that one call site maps to one implementation is a feature, and dispatch by control flow is easier to understand than overload resolution. If we want the optimizer to still be able to specialize reliably, the set of overloads that could be dispatched to would likely have to be closed anyway.

-Joe

···

On Feb 6, 2017, at 10:06 AM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

On Feb 5, 2017, at 5:36 PM, Abe Schneider via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hi Robert,

Exactly. The benefit being that you can figure out the correct function to dispatch entirely at compile time. My understanding is that Swift doesn’t do this because of the associated code bloat (and it’s usually not necessary). However, I think there is some important functionality by allowing specialization to control dispatch in a similar way to c++. There is also the design element — my (fairly) succinct Tensor class that used to be ~300 lines is now already close to an additional 1000 lines of code and growing. While the type of library I’m writing might be outside of what is normally done with Swift, I suspect the design pattern I’m using crops up in other places, as well as the need for dispatch on specialization (e.g. http://stackoverflow.com/questions/41640321/extending-collection-with-a-recursive-property-method-that-depends-on-the-elemen).

You can’t figure out the correct function to dispatch entirely at compile time because Swift supports retroactive modeling. Let’s make this a super-simple example:

  // Module A
  public protocol P { }
  public func f<T>(_:T) { print(“unspecialized”) }
  public func f<T: P>(_: T) { print(“specialized”) }

  public func g<T>(_ x: T) { f(x) }

  // Module B
  import A
  func testG(x: Int) {
    g(x) // the best we can statically do is print “unspecialized”; Int doesn’t conform to A.P, but...
  }

  // Module C
  import A
  public extension A: P { } // dynamically, Int does conform to A.P!

Swift’s model is that the selection among ad hoc overloads is performed statically based on local knowledge, and is consistent across all “specializations” of a generic function. Protocol requirements and overridable methods are the customization points.

Selecting ad hoc overloads at runtime is possible, but of course it has downsides. You could run into run-time ambiguities, for example:

  // Module A
  public protocol P { }
  public protocol Q { }
  public func f<T>(_:T) { print(“unspecialized”) }
  public func f<T: P>(_: T) { print(“specialized for P”) }
  public func f<T: Q>(_: T) { print(“specialized for Q”) }

  public func g<T>(_ x: T) { f(x) }

  // Module B
  import A
  public extension Int: P { }

  // Module C
  import A
  public extension Int: Q { }

  // Module C
  import A
  func testG(x: Int) {
    g(x) // run-time ambiguity: which specialized “f” do we get?
  }

There are reasonable answers here if we know what the potential set of overloads is at compile-time. It’s a problem I’ve been interested in for a long time <https://parasol.tamu.edu/~jarvi/papers/pldi06.pdf>. That dynamic dispatch can be implemented somewhat reasonably (the compiler can emit a static decision tree so long as we’re willing to limit the set of overloads to the ones that are visible from g(_:), and can be folded away by the optimizer when we’re specializing the function and the visibility of the types and/or protocols in question is limited.

As far as changes to Swift, `@_specialize` already does exactly this (except it is treated as a hint). You would need to transform the function to something like <function-name>_<mangled-type-name>(…) and a table of transformed functions, but after that you can just treat the functions as normal functions (and ignore the fact they were defined as generic). So, yes, specializations should be forced at every level. While this will lead to some code bloat, since it only occurs for the functions marked by the user, I would imagine it’s: (a) limited to the extent it occurs; and (b) manageable by simply not using the attribute (and using protocol witness tables instead). But at least that way you give the user the choice to do what is best for the particular situation.

For reference, `@_specialize` is doing dynamic dispatch. That dynamic dispatch gets optimized away when we specialize the generic function, the same way I mentioned about.

There might be a reasonable solution to the problem you’re encountering. I don’t think it’s “force specialization at compile time like C++”, but something akin to grouping together multiple overloads where we want dynamic dispatch of callers that invoke them, statically diagnosing when that set of overloads can have ambiguities in it (see the paper I referenced above), and teaching the optimizers to resolve that dynamic dispatch statically whenever possible.


(Douglas Gregor) #11

Thank you for the explanation, that makes sense. Do you think it makes sense to create a proposal to allow handling of specialized overloads in Swift?

I don't think it's a particularly good time in Swift's evolution to introduce such a feature. Swift 4 actually has a pile of Generics improvements already, and relative to those, this kind of specialization is a bit of a niche feature. That said, it's not totally afield---the conditional conformances proposal talks about a similar issue in the context of existing dynamic dispatch (protocol requirements), and we're not quite sure how big of an issue it will be.

I suspect the issues caused by the current behavior: (a) will continue to confuse a lot of people coming from c++; and (b) affects a wider audience than just the library I’m developing.

Swift's generics system is quite drastically different from C++ templates, so I (personally) am not strongly motivated by the first argument: there's a big leap to make going from C++ to Swift, particularly if you know C++ templates well, and this seems a small part of that. The second argument I agree with---it does come up from time to time.

  - Doug

···

Sent from my iPhone

On Feb 7, 2017, at 4:13 AM, Abe Schneider <abe.schneider@gmail.com> wrote:

Abe

On Feb 6, 2017, at 1:06 PM, Douglas Gregor <dgregor@apple.com> wrote:

On Feb 5, 2017, at 5:36 PM, Abe Schneider via swift-evolution <swift-evolution@swift.org> wrote:

Hi Robert,

Exactly. The benefit being that you can figure out the correct function to dispatch entirely at compile time. My understanding is that Swift doesn’t do this because of the associated code bloat (and it’s usually not necessary). However, I think there is some important functionality by allowing specialization to control dispatch in a similar way to c++. There is also the design element — my (fairly) succinct Tensor class that used to be ~300 lines is now already close to an additional 1000 lines of code and growing. While the type of library I’m writing might be outside of what is normally done with Swift, I suspect the design pattern I’m using crops up in other places, as well as the need for dispatch on specialization (e.g. http://stackoverflow.com/questions/41640321/extending-collection-with-a-recursive-property-method-that-depends-on-the-elemen).

You can’t figure out the correct function to dispatch entirely at compile time because Swift supports retroactive modeling. Let’s make this a super-simple example:

  // Module A
  public protocol P { }
  public func f<T>(_:T) { print(“unspecialized”) }
  public func f<T: P>(_: T) { print(“specialized”) }

  public func g<T>(_ x: T) { f(x) }

  // Module B
  import A
  func testG(x: Int) {
    g(x) // the best we can statically do is print “unspecialized”; Int doesn’t conform to A.P, but...
  }

  // Module C
  import A
  public extension A: P { } // dynamically, Int does conform to A.P!

Swift’s model is that the selection among ad hoc overloads is performed statically based on local knowledge, and is consistent across all “specializations” of a generic function. Protocol requirements and overridable methods are the customization points.

Selecting ad hoc overloads at runtime is possible, but of course it has downsides. You could run into run-time ambiguities, for example:

  // Module A
  public protocol P { }
  public protocol Q { }
  public func f<T>(_:T) { print(“unspecialized”) }
  public func f<T: P>(_: T) { print(“specialized for P”) }
  public func f<T: Q>(_: T) { print(“specialized for Q”) }

  public func g<T>(_ x: T) { f(x) }

  // Module B
  import A
  public extension Int: P { }

  // Module C
  import A
  public extension Int: Q { }

  // Module C
  import A
  func testG(x: Int) {
    g(x) // run-time ambiguity: which specialized “f” do we get?
  }

There are reasonable answers here if we know what the potential set of overloads is at compile-time. It’s a problem I’ve been interested in for a long time. That dynamic dispatch can be implemented somewhat reasonably (the compiler can emit a static decision tree so long as we’re willing to limit the set of overloads to the ones that are visible from g(_:), and can be folded away by the optimizer when we’re specializing the function and the visibility of the types and/or protocols in question is limited.

As far as changes to Swift, `@_specialize` already does exactly this (except it is treated as a hint). You would need to transform the function to something like <function-name>_<mangled-type-name>(…) and a table of transformed functions, but after that you can just treat the functions as normal functions (and ignore the fact they were defined as generic). So, yes, specializations should be forced at every level. While this will lead to some code bloat, since it only occurs for the functions marked by the user, I would imagine it’s: (a) limited to the extent it occurs; and (b) manageable by simply not using the attribute (and using protocol witness tables instead). But at least that way you give the user the choice to do what is best for the particular situation.

For reference, `@_specialize` is doing dynamic dispatch. That dynamic dispatch gets optimized away when we specialize the generic function, the same way I mentioned about.

There might be a reasonable solution to the problem you’re encountering. I don’t think it’s “force specialization at compile time like C++”, but something akin to grouping together multiple overloads where we want dynamic dispatch of callers that invoke them, statically diagnosing when that set of overloads can have ambiguities in it (see the paper I referenced above), and teaching the optimizers to resolve that dynamic dispatch statically whenever possible.

  - Doug

Thanks!
A

On Feb 5, 2017, at 1:46 PM, Robert Widmann <devteam.codafi@gmail.com> wrote:

Oh, I see. The constraint solver is picking an overload that better matches the caller rather than the callee's type, which differs from C++ because the template expansion process considers specific-type overloads more specific. We don't consider less-generic prototypes than the caller here because we aren't performing a (major) syntactic transformation in the process of solving a system of type variables. In order to change the language to adopt this feature, Sema would have to have knowledge of the candidate set of specializations, either user-specified or SILOptimizer-generated, beforehand. It's not impossible to imagine, but it does create an interesting backdependency on future potential optimizations, and would potentially majorly change the behavior of a Debug or Release build (unless specialization were forced at all optimization levels).

~Robert Widmann

2017/02/05 12:37、Abe Schneider <abe.schneider@gmail.com> のメッセージ:

Hi Robert,

Sorry, I’m not sure I understand your question. In c++ you can do the following:

struct Storage {};
struct CBlasStorage: Storage {};

template <typename S> class Tensor {};

template <typename S>
Tensor<S> dot(const Tensor<S> &lhs, const Tensor<S> &rhs) {
  std::cout << "general version called" << std::endl;
  Tensor<S> result;
  return result;
}

// specialized version for CBlasStorage
template <>
Tensor<CBlasStorage> dot(const Tensor<CBlasStorage> &lhs, const Tensor<CBlasStorage> &rhs) {
  std::cout << "specialized version called" << std::endl;
  Tensor<CBlasStorage> result;
  return result;
}

// this preserves type information and will call the appropriate `dot`
template <typename T>
void doSomething(const Tensor<T> &lhs, const Tensor<T> &rhs) {
  auto result = dot(lhs, rhs);
}

int main(int argc, char **argv) {
  Tensor<CBlasStorage> a, b;
  doSomething(a, b); // we should get "specialized version called"
}

The potential equivalent for Swift could look like:

@_specialize_all
func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> { … }

Which would cause the compile to create a version of `dot` per S type that it gets called with. Thus, when `doSomething` is called, it would dispatch to that version of `dot`, allowing the type information to be preserved in the same way it does in c++.

Abe

On Feb 5, 2017, at 11:35 AM, Robert Widmann <devteam.codafi@gmail.com> wrote:

I don't understand how this change would cause method dispatch to invoke a different prototype. Specialization in either language mentioned doesn't do that.

~Robert Widmann

2017/02/05 11:28、Abe Schneider via swift-evolution <swift-evolution@swift.org> のメッセージ:

Hi all,

The current behavior of generics in Swift causes it lose type information at compile time due to the desire of maintaining a single version of the function. This runs counter to how c++ works, which creates a new copy of a function per type, but preserves information to be preserved. This can cause unexpected behavior from the user’s perspective:

  protocol DispatchType {}
  class DispatchType1: DispatchType {}

  func doBar<D:DispatchType>(value:D) {
      print(“General function called")
  }

  func doBar(value:DispatchType1) {
      print("DispatchType1 called")
  }

  func test<D:DispatchType>(value:D) {
      doBar(value: value)
  }

  test(value: d1) // “General function called”, but it’s not obvious why

The suggested method to get around this issue is to use a protocol to create a witness table, allowing for runtime dispatch. However, this approach is not ideal in all cases because: (a) the overhead of runtime dispatch may not be desirable, especially because this is something that can be determined at compile time; and (b) there are some designs in which this behavior can complicate things.

One example of a design where this behavior can be problematic is when a protocol is used to determine what functions get dispatched:

  protocol Storage { … }
  class Tensor<S:Storage> { … }

  class CBlasStorage: Storage { … }
  class OpenCLStorage: Storage { … }

  func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> { … }

  // like behavior, these will not work if called from another generic function (but will work for non-generic functions)
  func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> where S:CBlasStorage { … }
  func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> where S:OpenCLStorage { … }

In this case, depending on the underlying storage, we want an optimized version of `dot` to be called. To make this work correctly we can add static methods to `Tensor`, but this has several drawbacks: (a) it makes the `Tensor` class monolithic, every possible method must be determine a priori and be defined in the class; (b) it doesn’t allow new methods to be added Tensor without touching the main class; and (c) it unnecessarily forces users to user the more verbose `Tensor.dot(a, b)`.

Point (a) in theory could be made better by creating a `TensorOps` protocols. However, because type constraints cannot currently be placed on extensions, it is not currently possible to implement.

One potential solution would be to add/extend an attribute for generic functions that would force multiple versions of that function to be created. There is already there is a `@_specialize` attribute, but you have to: (a) manually write out all the cases you want to cover; and (b) only affects the compiled code, which does not change this behavior. Due to the fact that `@_specialize` exists, I’m going to assume it wouldn’t be a major change to the language to extend the behavior to compile-time dispatch.

Thanks!
Abe
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Abe Schneider) #12

Hi Joe,

The issue re-dispatching from a function is that it can make
maintenance of the library difficult. For every function I define I
would need to have a large if-else tree. This means that the
introduction of both new functions and storage types becomes
expensive. For example, if I had:

    func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> {
      if let s = lhs as? Tensor<NativeStorage<Float>> { ... }
     else if if let s = lhs as? Tensor<NativeStorage<Double>> { ... }
     else if let s = lhs as? Tensor<NativeStorage<Int>> { ... }
      if let s = lhs as? Tensor<CBlasStorage<Float>> { ... }
     else if if let s = lhs as? Tensor<CBlasStorage<Double>> { ... }
     else if let s = lhs as? Tensor< CBlasStorage <Int>> { ... }
      if let s = lhs as? Tensor<OpenCLStorage<Float>> { ... }
     else if if let s = lhs as? Tensor< OpenCLStorage <Double>> { ... }
     else if let s = lhs as? Tensor< OpenCLStorage <Int>> { ... }
   }

with the same number of Impls to go along. If I added a new storage
type (e.g. CUDA) I would have to add each type specified (and I
haven't added Byte and Short) to every function that can be performed
on a Tensor (which is currently ~20-30). For my library this doesn't
lead to maintainable code.

In C++ this is what templates are supposed to help solve. In Swift,
generics solve this problem if called from a non-generic function or
if your generic is defined in a protocol/class, so it would seem to
fall within the pattern of what should be expected from generics.

Thanks!
Abe

···

On Wed, Feb 8, 2017 at 12:55 PM, Joe Groff <jgroff@apple.com> wrote:

On Feb 6, 2017, at 10:06 AM, Douglas Gregor via swift-evolution > <swift-evolution@swift.org> wrote:

On Feb 5, 2017, at 5:36 PM, Abe Schneider via swift-evolution > <swift-evolution@swift.org> wrote:

Hi Robert,

Exactly. The benefit being that you can figure out the correct function to
dispatch entirely at compile time. My understanding is that Swift doesn’t do
this because of the associated code bloat (and it’s usually not necessary).
However, I think there is some important functionality by allowing
specialization to control dispatch in a similar way to c++. There is also
the design element — my (fairly) succinct Tensor class that used to be ~300
lines is now already close to an additional 1000 lines of code and growing.
While the type of library I’m writing might be outside of what is normally
done with Swift, I suspect the design pattern I’m using crops up in other
places, as well as the need for dispatch on specialization (e.g.
http://stackoverflow.com/questions/41640321/extending-collection-with-a-recursive-property-method-that-depends-on-the-elemen).

You can’t figure out the correct function to dispatch entirely at compile
time because Swift supports retroactive modeling. Let’s make this a
super-simple example:

// Module A
public protocol P { }
public func f<T>(_:T) { print(“unspecialized”) }
public func f<T: P>(_: T) { print(“specialized”) }

public func g<T>(_ x: T) { f(x) }

// Module B
import A
func testG(x: Int) {
  g(x) // the best we can statically do is print “unspecialized”; Int
doesn’t conform to A.P, but...
}

// Module C
import A
public extension A: P { } // dynamically, Int does conform to A.P!

Swift’s model is that the selection among ad hoc overloads is performed
statically based on local knowledge, and is consistent across all
“specializations” of a generic function. Protocol requirements and
overridable methods are the customization points.

Selecting ad hoc overloads at runtime is possible, but of course it has
downsides. You could run into run-time ambiguities, for example:

// Module A
public protocol P { }
public protocol Q { }
public func f<T>(_:T) { print(“unspecialized”) }
public func f<T: P>(_: T) { print(“specialized for P”) }
public func f<T: Q>(_: T) { print(“specialized for Q”) }

public func g<T>(_ x: T) { f(x) }

// Module B
import A
public extension Int: P { }

// Module C
import A
public extension Int: Q { }

// Module C
import A
func testG(x: Int) {
  g(x) // run-time ambiguity: which specialized “f” do we get?
}

There are reasonable answers here if we know what the potential set of
overloads is at compile-time. It’s a problem I’ve been interested in for a
long time. That dynamic dispatch can be implemented somewhat reasonably (the
compiler can emit a static decision tree so long as we’re willing to limit
the set of overloads to the ones that are visible from g(_:), and can be
folded away by the optimizer when we’re specializing the function and the
visibility of the types and/or protocols in question is limited.

As far as changes to Swift, `@_specialize` already does exactly this (except
it is treated as a hint). You would need to transform the function to
something like <function-name>_<mangled-type-name>(…) and a table of
transformed functions, but after that you can just treat the functions as
normal functions (and ignore the fact they were defined as generic). So,
yes, specializations should be forced at every level. While this will lead
to some code bloat, since it only occurs for the functions marked by the
user, I would imagine it’s: (a) limited to the extent it occurs; and (b)
manageable by simply not using the attribute (and using protocol witness
tables instead). But at least that way you give the user the choice to do
what is best for the particular situation.

For reference, `@_specialize` is doing dynamic dispatch. That dynamic
dispatch gets optimized away when we specialize the generic function, the
same way I mentioned about.

There might be a reasonable solution to the problem you’re encountering. I
don’t think it’s “force specialization at compile time like C++”, but
something akin to grouping together multiple overloads where we want dynamic
dispatch of callers that invoke them, statically diagnosing when that set of
overloads can have ambiguities in it (see the paper I referenced above), and
teaching the optimizers to resolve that dynamic dispatch statically whenever
possible.

Specialization handles casts, so you can handle some cases today by writing
the implementation selection logic out:

func f<T>(x: T) {
  if let i = x as? Int { fooImplForInt(i) }
  else if let f = x as? Float { fooImplForFloat(f) }
  else { fooImplForGeneric(x) }
}

And you'll get the `Int` or `Float` implementation when the specializer
optimizes for T == Int or T == Float. This approach has some limitations
today, since protocol existentials in particular have limited functionality,
and you don't get type refinement of T from the cast. Perhaps we could
support testing general type constraints as a form of statement condition,
something like this:

func f<T>(x: T) {
  if <T: P> {
    // we can assume T: P here
    x.fooImplFromP()
  } else if <T: Q> {
    // we can assume T: Q here
    x.fooImplFromQ()
  } else {
    fooImplForGeneric(x)
  }
}

I think the fact that one call site maps to one implementation is a feature,
and dispatch by control flow is easier to understand than overload
resolution. If we want the optimizer to still be able to specialize
reliably, the set of overloads that could be dispatched to would likely have
to be closed anyway.

-Joe


(Joe Groff) #13

If there's really an independent implementation for each `S: Storage`, then you can make `tensorDot` a requirement of `Storage` and avoid the explosion that way. Ad-hoc type dispatch by either overloading or if chains should be a last resort when protocols really can't model what you're trying to do. Ad-hoc overloading wouldn't really save you any work compared to the if chain—you'd have all the exact problems you mentioned, having to add an overload for every new combo of types, but you'd also have to also think about the implicit relationships among the overloads according to the language's overloading rules instead of in explicit logic.

-Joe

···

On Feb 10, 2017, at 8:13 AM, Abe Schneider <abe.schneider@gmail.com> wrote:

Hi Joe,

The issue re-dispatching from a function is that it can make
maintenance of the library difficult. For every function I define I
would need to have a large if-else tree. This means that the
introduction of both new functions and storage types becomes
expensive. For example, if I had:

   func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S> {
     if let s = lhs as? Tensor<NativeStorage<Float>> { ... }
    else if if let s = lhs as? Tensor<NativeStorage<Double>> { ... }
    else if let s = lhs as? Tensor<NativeStorage<Int>> { ... }
     if let s = lhs as? Tensor<CBlasStorage<Float>> { ... }
    else if if let s = lhs as? Tensor<CBlasStorage<Double>> { ... }
    else if let s = lhs as? Tensor< CBlasStorage <Int>> { ... }
     if let s = lhs as? Tensor<OpenCLStorage<Float>> { ... }
    else if if let s = lhs as? Tensor< OpenCLStorage <Double>> { ... }
    else if let s = lhs as? Tensor< OpenCLStorage <Int>> { ... }
  }

with the same number of Impls to go along. If I added a new storage
type (e.g. CUDA) I would have to add each type specified (and I
haven't added Byte and Short) to every function that can be performed
on a Tensor (which is currently ~20-30). For my library this doesn't
lead to maintainable code.


(Abe Schneider) #14

Hi Douglas,

I don't think it's a particularly good time in Swift's evolution to
introduce such a feature. Swift 4 actually has a pile of Generics
improvements already, and relative to those, this kind of specialization is
a bit of a niche feature. That said, it's not totally afield---the
conditional conformances proposal talks about a similar issue in the context
of existing dynamic dispatch (protocol requirements), and we're not quite
sure how big of an issue it will be.

Okay, that's fair. My main goal was to at least raise the issue and
hope that at least some day it may get added to the roadmap. More
immediately, if some of the changes being discussed are made to how
protocols/extensions work, I think that could a potential solution.

Also, since I don't want to come off as sounding like I'm just
complaining, thank you everyone who have put so much effort and
thought into Swift! It's quickly made it's way into one of my favorite
languages.

Swift's generics system is quite drastically different from C++ templates,
so I (personally) am not strongly motivated by the first argument: there's a
big leap to make going from C++ to Swift, particularly if you know C++
templates well, and this seems a small part of that. The second argument I
agree with---it does come up from time to time.

I wouldn't expect Swift's generics to work exactly the same as C++.
However, I have seen discussion come up in discussion that Swift
should cause the least amount of surprises for people coming from a
C-based language. Thus, for people coming from C++, this will cause a
lot of surprise -- especially since it does the correct behavior when
being called from a non-generic function. I hadn't noticed the
difference in behavior until much later in development of my library
(which is now causing a lot of refactoring to occur).

Thanks!
Abe


(Abe Schneider) #15

Hi Joe,

If there's really an independent implementation for each `S: Storage`, then you can make `tensorDot` a requirement of `Storage` and avoid the explosion that way. Ad-hoc type dispatch by either overloading or if chains should be a last resort when protocols really can't model what you're trying to do. Ad-hoc overloading wouldn't really save you any work compared to the if chain—you'd have all the exact problems you mentioned, having to add an overload for every new combo of types, but you'd also have to also think about the implicit relationships among the overloads according to the language's overloading rules instead of in explicit logic.

You are correct in the number of Impls I need (I was incorrect in that
statement). But I think the if-branches are still problematic. I may
need the same number of functions as branches, but I think the code is
cleaner/easier to read and maintain:

   func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S>
where S:CBlasStorage<Float> { .. }
   func dot<S:Storage>(_ lhs:Tensor<S>, _ rhs:Tensor<S>) -> Tensor<S>
where S:CBlasStorage<Double> { .. }

   // NativeStorage has no optimization per type, so we can lump all
of these into a single Impl
   func dot<T>(_ lhs:Tensor<NativeStorage<T>>, _
rhs:Tensor<NativeStorage<T>>) -> Tensor<NativeStorage<T>> { .. }

The advantages from this approach are: (a) it has less repeated code
(i.e. I don't have to create both an Impl and an if-branch); (b)
adding a new storage type does require redefining some (if not all) of
the functions (though it provides a nice mechanism for dealing with
defaults), but that code can be kept as a separate module; and (c) You
are effectively rolling your own dynamic dispatch, which is something
I much rather leave up to the compiler to do.

Thanks!
Abe


(Douglas Gregor) #16

Other languages in the C family (e.g., C#, Java) that have both generics and ad hoc overloading provide the same static-resolution behavior that Swift does, so someone coming from a language in the general “C” family will be confounded whatever we choose. Personally, I think C++ got this wrong—I feel that generic algorithm customization points and algorithm specializations should be explicitly stated, because it makes it easier to reason about the generic code if you know where those points are. Swift uses protocol requirements for customization points, but hasn’t tackled algorithm specialization yet.

  - Doug

···

On Feb 10, 2017, at 8:41 AM, Abe Schneider <abe.schneider@gmail.com> wrote:

Hi Douglas,

Swift's generics system is quite drastically different from C++ templates,
so I (personally) am not strongly motivated by the first argument: there's a
big leap to make going from C++ to Swift, particularly if you know C++
templates well, and this seems a small part of that. The second argument I
agree with---it does come up from time to time.

I wouldn't expect Swift's generics to work exactly the same as C++.
However, I have seen discussion come up in discussion that Swift
should cause the least amount of surprises for people coming from a
C-based language. Thus, for people coming from C++, this will cause a
lot of surprise -- especially since it does the correct behavior when
being called from a non-generic function. I hadn't noticed the
difference in behavior until much later in development of my library
(which is now causing a lot of refactoring to occur).


(Abe Schneider) #17

Other languages in the C family (e.g., C#, Java) that have both generics and ad hoc overloading provide the same static-resolution behavior that Swift does, so someone coming from a language in the general “C” family will be confounded whatever we choose. Personally, I think C++ got this wrong—I feel that generic algorithm customization points and algorithm specializations should be explicitly stated, because it makes it easier to reason about the generic code if you know where those points are. Swift uses protocol requirements for customization points, but hasn’t tackled algorithm specialization yet.

That's a fair point, though I think Java's type erasure in generics
surprises/confuses a lot of people (and takes away a lot of the
potential power of generics). That's not to say C++ templates are easy
to understand (e.g. SFINAE), but at least to me it operates in a more
intuitive manner until you get to the esoteric parts. And that is
admittedly a very subjective point.

I can see the advantage of protocols if they allowed this type of design:

protocol LinearOperations {
   associatedtype StorageType
   static func dot(_ lhs:Tensor<StorageType>, _
rhs:Tensor<StorageType>) -> Tensor<StorageType>
   ...
}

extension Tensor: LinearOperations {
...
}

extension Tensor: LinearOperations where StorageType:CBlasStorage<Float> {
...
}

The advantage of this design is that the available functions are
clearly defined, but it still allows new operations to be defined
without having to touch the main code base. You can also easily add
new functionality to the Tensor class by creating a new protocol:

protocol StatisticsOperations {
   associatedtype StorageType
   static func histogram(_ tensor:Tensor<StorageType>) -> Tensor<StorageType>
}

extension Tensor: StatisticsOperations {
...
}

The two disadvantages are: (a) Swift currently doesn't allow this; and
(b) it's a little more verbose because you have to write:

let result = Tensor.histogram(mydata)

versus:

let result = histogram(mydata)

which has the redundant piece of information that it's a Tensor (which
can be inferred from `mydata`).

Abe


(Douglas Gregor) #18

Other languages in the C family (e.g., C#, Java) that have both generics and ad hoc overloading provide the same static-resolution behavior that Swift does, so someone coming from a language in the general “C” family will be confounded whatever we choose. Personally, I think C++ got this wrong—I feel that generic algorithm customization points and algorithm specializations should be explicitly stated, because it makes it easier to reason about the generic code if you know where those points are. Swift uses protocol requirements for customization points, but hasn’t tackled algorithm specialization yet.

That's a fair point, though I think Java's type erasure in generics
surprises/confuses a lot of people (and takes away a lot of the
potential power of generics).

I consider Java’s type erasure to be orthogonal to the overloading/customization point issue, but of course I agree that it’s surprising.

I can see the advantage of protocols if they allowed this type of design:

protocol LinearOperations {
  associatedtype StorageType
  static func dot(_ lhs:Tensor<StorageType>, _
rhs:Tensor<StorageType>) -> Tensor<StorageType>
  ...
}

extension Tensor: LinearOperations {
...
}

extension Tensor: LinearOperations where StorageType:CBlasStorage<Float> {
...
}

The advantage of this design is that the available functions are
clearly defined, but it still allows new operations to be defined
without having to touch the main code base.

I’m assuming that both of these extensions implement the static func dot(_:_:). This is more interesting direction for me, because it’s taking the existing notion of customization points via protocol requirements and extending that to also support some level of customization.

  - Doug

···

On Feb 10, 2017, at 10:08 AM, Abe Schneider <abe.schneider@gmail.com> wrote:


(Abe Schneider) #19

protocol LinearOperations {
  associatedtype StorageType
  static func dot(_ lhs:Tensor<StorageType>, _
rhs:Tensor<StorageType>) -> Tensor<StorageType>
  ...
}

extension Tensor: LinearOperations {
...
}

extension Tensor: LinearOperations where StorageType:CBlasStorage<Float> {
...
}

I’m assuming that both of these extensions implement the static func dot(_:_:). This is more interesting direction for me, because it’s taking the existing notion of customization points via protocol requirements and extending that to also support some level of customization.

Exactly (sorry, I should've made that explicit). I'd be super happy if
this functionality got added to Swift.

Abe


(Abe Schneider) #20

Sorry, just following up with a few more thoughts.

I consider Java’s type erasure to be orthogonal to the overloading/customization point issue, but of course I agree that it’s surprising.

While the underlying reason may be different, Swift has a similar potential for surprise with generics. Yes, it might not be a surprise for people coming from the world of Java, but mostly because Java’s generics are extremely limited.

I can see the advantage of protocols if they allowed this type of design:

protocol LinearOperations {
associatedtype StorageType
static func dot(_ lhs:Tensor<StorageType>, _
rhs:Tensor<StorageType>) -> Tensor<StorageType>
...
}

extension Tensor: LinearOperations {
...
}

extension Tensor: LinearOperations where StorageType:CBlasStorage<Float> {
...
}

The advantage of this design is that the available functions are
clearly defined, but it still allows new operations to be defined
without having to touch the main code base.

I’m assuming that both of these extensions implement the static func dot(_:_:). This is more interesting direction for me, because it’s taking the existing notion of customization points via protocol requirements and extending that to also support some level of customization.

So what needs to change in the language to enable this behavior? The obvious candidate is allowing creating extensions with constraints. However, even if I include all the necessary functions within a single class (to avoid that issue), I’m still running into more design issues. For example, for this toy example (sorry for the verbosity — this was the shortest version I could come up with):

class Tensor<S:Storage> {
    var storage:S
    
    init(size:Int) {
        storage = S(size: size)
    }
    
    // default implementation
    static func cos(_ tensor:Tensor<S>) -> Tensor<S> {
  // ...
    }
}

With specializations defined for the storage types:

extension Tensor where S:IntStorage {
    static func cos(_ tensor:Tensor<S>) -> Tensor<S> {
  // ...
    }
}

extension Tensor where S:FloatStorage {
    static func cos(_ tensor:Tensor<S>) -> Tensor<S> {
  // ...
    }
}

This works:

let floatTensor = Tensor<FloatStorage>(size: 10)
let result1 = T.cos(floatTensor) // calls Tensor<FloatStorage>.cos(…)

let intTensor = Tensor<IntStorage>(size: 10)
let result2 = T.cos(intTensor) // calls Tensor<IntStorage>.cos(…)

However, if I define an operation to on the Tensor:

class SomeOp<S:Storage> {
    typealias StorageType = S
    var output:Tensor<S>
    
    init() {
        output = Tensor<S>(size: 10)
    }
    
    func apply() -> Tensor<S> {
        let result = T.cos(output)
        return result
    }
}

let op1 = SomeOp<FloatStorage>()
let result3 = op1.apply() // calls default `cos` instead of FloatStorage version

So one question I have is why doesn’t the correct version of `cos` get called? Before it was because there wasn’t a vtable available to figure out which function to call. However, in this case since the function was defined in the class, I would assume there would be (I also tried variants of this with an accompanying protocol and non-static versions of the function).

I can get `SomeOp` to work correctly if I create specializations of the class:

extension SomeOp where S:FloatStorage {
    func apply() -> Tensor<S> {
        let result = T.cos(output)
        return result
    }
}

extension SomeOp where S:IntStorage {
    func apply() -> Tensor<S> {
        let result = T.cos(output)
        return result
    }
}

However, this doesn’t seem like a good design to me, as it requires copying the same code for each StorageType introduced.

Thanks!