Extending Arrays of specific type, and specialization


(Rick M) #1

My googling is not turning up an answer that works in Xcode 8.1. I'd like to do this:

import Accelerate

extension
Array
  where Element == Double
{
  func
  sum()
    -> Double
  {
    var result: Double = 0.0
    vDSP_sveD(self, 1, &result, vDSP_Length(self.count))
    return result
  }
}

But I get "same-type requirement makes generic parameter 'Element' non-generic."

Also, will there ever be any way to specialize something like

  let numbers: [Double] = ...
  let sum = numbers.reduce(0.0, +)

Into a call to vDSP_sveD()? Would it require compiler optimizations for Accelerate?

Thanks!

···

--
Rick Mann
rmann@latencyzero.com


(Hooman Mehr) #2

This is not possible in Swift 3.0. Swift 4.0 will improve things with conditional conformances.

For now, the best solution is using global functions instead of extending types or protocols.

For example you can do this now:

extension Array where Element: FloatingPoint {
    
    func sum() -> Element {
        guard count > 0 else { return 0 }
        switch self[0] {
        case is Double:
            var result = Double()
            vDSP_sveD(unsafeBitCast(self, to: Array<Double>.self), 1, &result, vDSP_Length(count))
            print("vDSP")
            return unsafeBitCast(result, to: Element.self)
        case is Float:
            var result = Float()
            vDSP_sve(unsafeBitCast(self, to: Array<Float>.self), 1, &result, vDSP_Length(count))
            print("vDSP")
            return unsafeBitCast(result, to: Element.self)
        default:
            print("default")
            return reduce(0, +)
        }
    }
}

But this is not very efficient, especially if it is defined in another module, which limits optimizations.

Instead, a family of overloaded global functions gives you the most coverage and best performance, at the expense of repetition and boilerplate code:

func sum<S: Sequence>(_ sequence: S) -> S.Iterator.Element where S.Iterator.Element: Integer {
    var result: S.Iterator.Element = 0
    for element in sequence { result += element }
    return result
}

func sum<S: Sequence>(_ sequence: S) -> S.Iterator.Element where S.Iterator.Element: FloatingPoint {
    var result: S.Iterator.Element = 0
    for element in sequence { result += element }
    return result
}

func sum(_ array: Array<Double>) -> Double {
    var result = Double()
    vDSP_sveD(array, 1, &result, vDSP_Length(array.count))
    return result
}

func sum(_ array: ContiguousArray<Double>) -> Double {
    var result = Double()
    array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
    return result
}

func sum(_ array: ArraySlice<Double>) -> Double {
    var result = Double()
    array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
    return result
}

func sum(_ array: Array<Float>) -> Float {
    var result = Float()
    vDSP_sve(array, 1, &result, vDSP_Length(array.count))
    return result
}

func sum(_ array: ContiguousArray<Float>) -> Float {
    var result = Float()
    array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
    return result
}

func sum(_ array: ArraySlice<Float>) -> Float {
    var result = Float()
    array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
    return result
}

The above code covers summing any integer or floating point sequence of numbers, while being accelerated for Float and Double array types (Array, ContiguousArray and ArraySlice)

···

On Nov 21, 2016, at 4:32 PM, Rick Mann via swift-users <swift-users@swift.org> wrote:

My googling is not turning up an answer that works in Xcode 8.1. I'd like to do this:

import Accelerate

extension
Array
  where Element == Double
{
  func
  sum()
    -> Double
  {
    var result: Double = 0.0
    vDSP_sveD(self, 1, &result, vDSP_Length(self.count))
    return result
  }
}

But I get "same-type requirement makes generic parameter 'Element' non-generic."

Also, will there ever be any way to specialize something like

  let numbers: [Double] = ...
  let sum = numbers.reduce(0.0, +)

Into a call to vDSP_sveD()? Would it require compiler optimizations for Accelerate?

Thanks!

--
Rick Mann
rmann@latencyzero.com

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


(Tino) #3

Hi Rick,

as evolution is somewhat paused, swift-users seems to gain more traction :wink:

Imho the most natural would be
extension Array<Double> {

}

I hope to see this addition included when the topic is discussed again.

- Tino


(Adrian Zubarev) #4

It’s already fixed for Swift 3.1.

Here is the change log.

···

--
Adrian Zubarev
Sent with Airmail

Am 22. November 2016 um 01:32:42, Rick Mann via swift-users (swift-users@swift.org) schrieb:

My googling is not turning up an answer that works in Xcode 8.1. I'd like to do this:

import Accelerate

extension
Array
where Element == Double
{
func
sum()
-> Double
{
var result: Double = 0.0
vDSP_sveD(self, 1, &result, vDSP_Length(self.count))
return result
}
}

But I get "same-type requirement makes generic parameter 'Element' non-generic."

Also, will there ever be any way to specialize something like

let numbers: [Double] = ...
let sum = numbers.reduce(0.0, +)

Into a call to vDSP_sveD()? Would it require compiler optimizations for Accelerate?

Thanks!

--
Rick Mann
rmann@latencyzero.com

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


(Rick M) #5

Thanks, Hooman. Is it worth posting on swift-evolution the question about specializing something like reduce(0, +) (it's complicated because it would mean specializing reduce() based on both the type and the closure passed, and that seems like something that would be difficult to specify concisely in the syntax).

···

On Nov 21, 2016, at 18:29 , Hooman Mehr <hooman@mac.com> wrote:

This is not possible in Swift 3.0. Swift 4.0 will improve things with conditional conformances.

For now, the best solution is using global functions instead of extending types or protocols.

For example you can do this now:

extension Array where Element: FloatingPoint {
    
    func sum() -> Element {
        guard count > 0 else { return 0 }
        switch self[0] {
        case is Double:
            var result = Double()
            vDSP_sveD(unsafeBitCast(self, to: Array<Double>.self), 1, &result, vDSP_Length(count))
            print("vDSP")
            return unsafeBitCast(result, to: Element.self)
        case is Float:
            var result = Float()
            vDSP_sve(unsafeBitCast(self, to: Array<Float>.self), 1, &result, vDSP_Length(count))
            print("vDSP")
            return unsafeBitCast(result, to: Element.self)
        default:
            print("default")
            return reduce(0, +)
        }
    }
}

But this is not very efficient, especially if it is defined in another module, which limits optimizations.

Instead, a family of overloaded global functions gives you the most coverage and best performance, at the expense of repetition and boilerplate code:

func sum<S: Sequence>(_ sequence: S) -> S.Iterator.Element where S.Iterator.Element: Integer {
    var result: S.Iterator.Element = 0
    for element in sequence { result += element }
    return result
}

func sum<S: Sequence>(_ sequence: S) -> S.Iterator.Element where S.Iterator.Element: FloatingPoint {
    var result: S.Iterator.Element = 0
    for element in sequence { result += element }
    return result
}

func sum(_ array: Array<Double>) -> Double {
    var result = Double()
    vDSP_sveD(array, 1, &result, vDSP_Length(array.count))
    return result
}

func sum(_ array: ContiguousArray<Double>) -> Double {
    var result = Double()
    array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
    return result
}

func sum(_ array: ArraySlice<Double>) -> Double {
    var result = Double()
    array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
    return result
}

func sum(_ array: Array<Float>) -> Float {
    var result = Float()
    vDSP_sve(array, 1, &result, vDSP_Length(array.count))
    return result
}

func sum(_ array: ContiguousArray<Float>) -> Float {
    var result = Float()
    array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
    return result
}

func sum(_ array: ArraySlice<Float>) -> Float {
    var result = Float()
    array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
    return result
}

The above code covers summing any integer or floating point sequence of numbers, while being accelerated for Float and Double array types (Array, ContiguousArray and ArraySlice)

On Nov 21, 2016, at 4:32 PM, Rick Mann via swift-users <swift-users@swift.org> wrote:

My googling is not turning up an answer that works in Xcode 8.1. I'd like to do this:

import Accelerate

extension
Array
  where Element == Double
{
  func
  sum()
    -> Double
  {
    var result: Double = 0.0
    vDSP_sveD(self, 1, &result, vDSP_Length(self.count))
    return result
  }
}

But I get "same-type requirement makes generic parameter 'Element' non-generic."

Also, will there ever be any way to specialize something like

  let numbers: [Double] = ...
  let sum = numbers.reduce(0.0, +)

Into a call to vDSP_sveD()? Would it require compiler optimizations for Accelerate?

Thanks!

--
Rick Mann
rmann@latencyzero.com

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

--
Rick Mann
rmann@latencyzero.com


(Rick M) #6

Agreed, since that was the first thing I tried to do :slight_smile:

···

On Nov 22, 2016, at 03:04 , Tino Heth <2th@gmx.de> wrote:

Hi Rick,

as evolution is somewhat paused, swift-users seems to gain more traction :wink:

Imho the most natural would be
extension Array<Double> {

}

I hope to see this addition included when the topic is discussed again.

--
Rick Mann
rmann@latencyzero.com


(Rick M) #7

It’s already fixed for Swift 3.1.

Here is the change log.

Cool. I wonder when it will appear in a shipping Xcode.

So, dumb question: how do you know that "Element" is the name of the thing you want to constrain? Is it just the name of the thing in angle brackets in the declaration of Array?

I still find this more intuitive and legible. Could it be added as an alternative? Does that pollute the language?

    extension Array<Double> {}

Forgive me if that was already discussed and dismissed.

···

On Nov 22, 2016, at 03:39 , Adrian Zubarev <adrian.zubarev@devandartist.com> wrote:

--
Adrian Zubarev
Sent with Airmail

Am 22. November 2016 um 01:32:42, Rick Mann via swift-users (swift-users@swift.org) schrieb:

My googling is not turning up an answer that works in Xcode 8.1. I'd like to do this:

import Accelerate

extension
Array
where Element == Double
{
func
sum()
-> Double
{
var result: Double = 0.0
vDSP_sveD(self, 1, &result, vDSP_Length(self.count))
return result
}
}

But I get "same-type requirement makes generic parameter 'Element' non-generic."

Also, will there ever be any way to specialize something like

let numbers: [Double] = ...
let sum = numbers.reduce(0.0, +)

Into a call to vDSP_sveD()? Would it require compiler optimizations for Accelerate?

Thanks!

--
Rick Mann
rmann@latencyzero.com

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

--
Rick Mann
rmann@latencyzero.com


(Matt Whiteside) #8

I agree. This syntax:

extension Array<Double> { … }

seems simpler than

extension Array where Element == Double { … }

-Matt

···

On Nov 22, 2016, at 03:04, Tino Heth via swift-users <swift-users@swift.org> wrote:

Hi Rick,

as evolution is somewhat paused, swift-users seems to gain more traction :wink:

Imho the most natural would be
extension Array<Double> {

}

I hope to see this addition included when the topic is discussed again.

- Tino


(Hooman Mehr) #9

It is good to know that

extension Array where Element == Double { }

will work pretty soon with Swift 3.1.

Back to reduce(0,+):

If we get specialized instance for a reduce(0,+), so that it is known that “+” is a (Double, Double)->Double function, LLVM’s auto-vectorization should be able to optimize it for the CPU’s vector unit. In theory, it should be possible to add additional optimizers to LLVM layer to use other hardware or numeric libraries for that purpose, but I don’t think it would be a Swift-specific thing.

Swift’s generics still has a long way to go. Since they are aiming for ABI stability by Swift 4.0, and there isn’t much time left, I don’t think many of the bigger generics improvements fit with the current Swift evolution discussions, although they could have huge impact on standard library (hence the ABI stability).

One thing that might be worth discussing on Swift evolution and can potentially make it to standard library and Swift 4.0 is adding a common protocol for array-like types that have (or can have) contiguous buffers so that manually vectorizing operations on their elements becomes easier and cleaner.

At the moment, we can manually define a protocol that extends RandomAccessCollection and provides `withUnsafeBufferPointer` and then declare the conformance of all of the standard library array variants to it so that we can provide a single generic sum global function for summing all of them using vDSP. This protocol may be worth adding to the standard library.

···

On Nov 21, 2016, at 7:05 PM, Rick Mann <rmann@latencyzero.com> wrote:

Thanks, Hooman. Is it worth posting on swift-evolution the question about specializing something like reduce(0, +) (it's complicated because it would mean specializing reduce() based on both the type and the closure passed, and that seems like something that would be difficult to specify concisely in the syntax).

On Nov 21, 2016, at 18:29 , Hooman Mehr <hooman@mac.com> wrote:

This is not possible in Swift 3.0. Swift 4.0 will improve things with conditional conformances.

For now, the best solution is using global functions instead of extending types or protocols.

For example you can do this now:

extension Array where Element: FloatingPoint {

   func sum() -> Element {
       guard count > 0 else { return 0 }
       switch self[0] {
       case is Double:
           var result = Double()
           vDSP_sveD(unsafeBitCast(self, to: Array<Double>.self), 1, &result, vDSP_Length(count))
           print("vDSP")
           return unsafeBitCast(result, to: Element.self)
       case is Float:
           var result = Float()
           vDSP_sve(unsafeBitCast(self, to: Array<Float>.self), 1, &result, vDSP_Length(count))
           print("vDSP")
           return unsafeBitCast(result, to: Element.self)
       default:
           print("default")
           return reduce(0, +)
       }
   }
}

But this is not very efficient, especially if it is defined in another module, which limits optimizations.

Instead, a family of overloaded global functions gives you the most coverage and best performance, at the expense of repetition and boilerplate code:

func sum<S: Sequence>(_ sequence: S) -> S.Iterator.Element where S.Iterator.Element: Integer {
   var result: S.Iterator.Element = 0
   for element in sequence { result += element }
   return result
}

func sum<S: Sequence>(_ sequence: S) -> S.Iterator.Element where S.Iterator.Element: FloatingPoint {
   var result: S.Iterator.Element = 0
   for element in sequence { result += element }
   return result
}

func sum(_ array: Array<Double>) -> Double {
   var result = Double()
   vDSP_sveD(array, 1, &result, vDSP_Length(array.count))
   return result
}

func sum(_ array: ContiguousArray<Double>) -> Double {
   var result = Double()
   array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
   return result
}

func sum(_ array: ArraySlice<Double>) -> Double {
   var result = Double()
   array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
   return result
}

func sum(_ array: Array<Float>) -> Float {
   var result = Float()
   vDSP_sve(array, 1, &result, vDSP_Length(array.count))
   return result
}

func sum(_ array: ContiguousArray<Float>) -> Float {
   var result = Float()
   array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
   return result
}

func sum(_ array: ArraySlice<Float>) -> Float {
   var result = Float()
   array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
   return result
}

The above code covers summing any integer or floating point sequence of numbers, while being accelerated for Float and Double array types (Array, ContiguousArray and ArraySlice)

On Nov 21, 2016, at 4:32 PM, Rick Mann via swift-users <swift-users@swift.org> wrote:

My googling is not turning up an answer that works in Xcode 8.1. I'd like to do this:

import Accelerate

extension
Array
  where Element == Double
{
  func
  sum()
    -> Double
  {
    var result: Double = 0.0
    vDSP_sveD(self, 1, &result, vDSP_Length(self.count))
    return result
  }
}

But I get "same-type requirement makes generic parameter 'Element' non-generic."

Also, will there ever be any way to specialize something like

  let numbers: [Double] = ...
  let sum = numbers.reduce(0.0, +)

Into a call to vDSP_sveD()? Would it require compiler optimizations for Accelerate?

Thanks!

--
Rick Mann
rmann@latencyzero.com

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

--
Rick Mann
rmann@latencyzero.com


(Rick M) #10

That sounds interesting. Would you mind making that pitch on swift-evolution? I just barely understood what you said :confused:

···

On Nov 22, 2016, at 07:46 , Hooman Mehr <hooman@mac.com> wrote:

It is good to know that

extension Array where Element == Double { }

will work pretty soon with Swift 3.1.

Back to reduce(0,+):

If we get specialized instance for a reduce(0,+), so that it is known that “+” is a (Double, Double)->Double function, LLVM’s auto-vectorization should be able to optimize it for the CPU’s vector unit. In theory, it should be possible to add additional optimizers to LLVM layer to use other hardware or numeric libraries for that purpose, but I don’t think it would be a Swift-specific thing.

Swift’s generics still has a long way to go. Since they are aiming for ABI stability by Swift 4.0, and there isn’t much time left, I don’t think many of the bigger generics improvements fit with the current Swift evolution discussions, although they could have huge impact on standard library (hence the ABI stability).

One thing that might be worth discussing on Swift evolution and can potentially make it to standard library and Swift 4.0 is adding a common protocol for array-like types that have (or can have) contiguous buffers so that manually vectorizing operations on their elements becomes easier and cleaner.

At the moment, we can manually define a protocol that extends RandomAccessCollection and provides `withUnsafeBufferPointer` and then declare the conformance of all of the standard library array variants to it so that we can provide a single generic sum global function for summing all of them using vDSP. This protocol may be worth adding to the standard library.

On Nov 21, 2016, at 7:05 PM, Rick Mann <rmann@latencyzero.com> wrote:

Thanks, Hooman. Is it worth posting on swift-evolution the question about specializing something like reduce(0, +) (it's complicated because it would mean specializing reduce() based on both the type and the closure passed, and that seems like something that would be difficult to specify concisely in the syntax).

On Nov 21, 2016, at 18:29 , Hooman Mehr <hooman@mac.com> wrote:

This is not possible in Swift 3.0. Swift 4.0 will improve things with conditional conformances.

For now, the best solution is using global functions instead of extending types or protocols.

For example you can do this now:

extension Array where Element: FloatingPoint {

  func sum() -> Element {
      guard count > 0 else { return 0 }
      switch self[0] {
      case is Double:
          var result = Double()
          vDSP_sveD(unsafeBitCast(self, to: Array<Double>.self), 1, &result, vDSP_Length(count))
          print("vDSP")
          return unsafeBitCast(result, to: Element.self)
      case is Float:
          var result = Float()
          vDSP_sve(unsafeBitCast(self, to: Array<Float>.self), 1, &result, vDSP_Length(count))
          print("vDSP")
          return unsafeBitCast(result, to: Element.self)
      default:
          print("default")
          return reduce(0, +)
      }
  }
}

But this is not very efficient, especially if it is defined in another module, which limits optimizations.

Instead, a family of overloaded global functions gives you the most coverage and best performance, at the expense of repetition and boilerplate code:

func sum<S: Sequence>(_ sequence: S) -> S.Iterator.Element where S.Iterator.Element: Integer {
  var result: S.Iterator.Element = 0
  for element in sequence { result += element }
  return result
}

func sum<S: Sequence>(_ sequence: S) -> S.Iterator.Element where S.Iterator.Element: FloatingPoint {
  var result: S.Iterator.Element = 0
  for element in sequence { result += element }
  return result
}

func sum(_ array: Array<Double>) -> Double {
  var result = Double()
  vDSP_sveD(array, 1, &result, vDSP_Length(array.count))
  return result
}

func sum(_ array: ContiguousArray<Double>) -> Double {
  var result = Double()
  array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
  return result
}

func sum(_ array: ArraySlice<Double>) -> Double {
  var result = Double()
  array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
  return result
}

func sum(_ array: Array<Float>) -> Float {
  var result = Float()
  vDSP_sve(array, 1, &result, vDSP_Length(array.count))
  return result
}

func sum(_ array: ContiguousArray<Float>) -> Float {
  var result = Float()
  array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
  return result
}

func sum(_ array: ArraySlice<Float>) -> Float {
  var result = Float()
  array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
  return result
}

The above code covers summing any integer or floating point sequence of numbers, while being accelerated for Float and Double array types (Array, ContiguousArray and ArraySlice)

On Nov 21, 2016, at 4:32 PM, Rick Mann via swift-users <swift-users@swift.org> wrote:

My googling is not turning up an answer that works in Xcode 8.1. I'd like to do this:

import Accelerate

extension
Array
  where Element == Double
{
  func
  sum()
    -> Double
  {
    var result: Double = 0.0
    vDSP_sveD(self, 1, &result, vDSP_Length(self.count))
    return result
  }
}

But I get "same-type requirement makes generic parameter 'Element' non-generic."

Also, will there ever be any way to specialize something like

  let numbers: [Double] = ...
  let sum = numbers.reduce(0.0, +)

Into a call to vDSP_sveD()? Would it require compiler optimizations for Accelerate?

Thanks!

--
Rick Mann
rmann@latencyzero.com

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

--
Rick Mann
rmann@latencyzero.com

--
Rick Mann
rmann@latencyzero.com


(Hooman Mehr) #11

For example, this reduces the six variants of sum to two:

public protocol ContiguousBufferedArray: RandomAccessCollection {
    
    func withUnsafeBufferPointer<R>(_ body: (UnsafeBufferPointer<Iterator.Element>) throws -> R) rethrows -> R
}

extension Array: ContiguousBufferedArray {}
extension ContiguousArray: ContiguousBufferedArray {}
extension ArraySlice: ContiguousBufferedArray {}

func sum<A>(_ array: A) -> Double where A: ContiguousBufferedArray, A.Iterator.Element == Double {
    var result = Double()
    array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, numericCast(array.count)) }
    return result
}

func sum<A>(_ array: A) -> Float where A: ContiguousBufferedArray, A.Iterator.Element == Float {
    var result = Float()
    array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, numericCast(array.count)) }
    return result
}

I have to think a bit more to see what common API we can extract from array that can be generally useful. I will put up a pic on evolution once I get a clearer idea.

···

On Nov 22, 2016, at 4:46 PM, Rick Mann <rmann@latencyzero.com> wrote:

That sounds interesting. Would you mind making that pitch on swift-evolution? I just barely understood what you said :confused:

On Nov 22, 2016, at 07:46 , Hooman Mehr <hooman@mac.com> wrote:

It is good to know that

extension Array where Element == Double { }

will work pretty soon with Swift 3.1.

Back to reduce(0,+):

If we get specialized instance for a reduce(0,+), so that it is known that “+” is a (Double, Double)->Double function, LLVM’s auto-vectorization should be able to optimize it for the CPU’s vector unit. In theory, it should be possible to add additional optimizers to LLVM layer to use other hardware or numeric libraries for that purpose, but I don’t think it would be a Swift-specific thing.

Swift’s generics still has a long way to go. Since they are aiming for ABI stability by Swift 4.0, and there isn’t much time left, I don’t think many of the bigger generics improvements fit with the current Swift evolution discussions, although they could have huge impact on standard library (hence the ABI stability).

One thing that might be worth discussing on Swift evolution and can potentially make it to standard library and Swift 4.0 is adding a common protocol for array-like types that have (or can have) contiguous buffers so that manually vectorizing operations on their elements becomes easier and cleaner.

At the moment, we can manually define a protocol that extends RandomAccessCollection and provides `withUnsafeBufferPointer` and then declare the conformance of all of the standard library array variants to it so that we can provide a single generic sum global function for summing all of them using vDSP. This protocol may be worth adding to the standard library.

On Nov 21, 2016, at 7:05 PM, Rick Mann <rmann@latencyzero.com> wrote:

Thanks, Hooman. Is it worth posting on swift-evolution the question about specializing something like reduce(0, +) (it's complicated because it would mean specializing reduce() based on both the type and the closure passed, and that seems like something that would be difficult to specify concisely in the syntax).

On Nov 21, 2016, at 18:29 , Hooman Mehr <hooman@mac.com> wrote:

This is not possible in Swift 3.0. Swift 4.0 will improve things with conditional conformances.

For now, the best solution is using global functions instead of extending types or protocols.

For example you can do this now:

extension Array where Element: FloatingPoint {

func sum() -> Element {
     guard count > 0 else { return 0 }
     switch self[0] {
     case is Double:
         var result = Double()
         vDSP_sveD(unsafeBitCast(self, to: Array<Double>.self), 1, &result, vDSP_Length(count))
         print("vDSP")
         return unsafeBitCast(result, to: Element.self)
     case is Float:
         var result = Float()
         vDSP_sve(unsafeBitCast(self, to: Array<Float>.self), 1, &result, vDSP_Length(count))
         print("vDSP")
         return unsafeBitCast(result, to: Element.self)
     default:
         print("default")
         return reduce(0, +)
     }
}
}

But this is not very efficient, especially if it is defined in another module, which limits optimizations.

Instead, a family of overloaded global functions gives you the most coverage and best performance, at the expense of repetition and boilerplate code:

func sum<S: Sequence>(_ sequence: S) -> S.Iterator.Element where S.Iterator.Element: Integer {
var result: S.Iterator.Element = 0
for element in sequence { result += element }
return result
}

func sum<S: Sequence>(_ sequence: S) -> S.Iterator.Element where S.Iterator.Element: FloatingPoint {
var result: S.Iterator.Element = 0
for element in sequence { result += element }
return result
}

func sum(_ array: Array<Double>) -> Double {
var result = Double()
vDSP_sveD(array, 1, &result, vDSP_Length(array.count))
return result
}

func sum(_ array: ContiguousArray<Double>) -> Double {
var result = Double()
array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
return result
}

func sum(_ array: ArraySlice<Double>) -> Double {
var result = Double()
array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
return result
}

func sum(_ array: Array<Float>) -> Float {
var result = Float()
vDSP_sve(array, 1, &result, vDSP_Length(array.count))
return result
}

func sum(_ array: ContiguousArray<Float>) -> Float {
var result = Float()
array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
return result
}

func sum(_ array: ArraySlice<Float>) -> Float {
var result = Float()
array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
return result
}

The above code covers summing any integer or floating point sequence of numbers, while being accelerated for Float and Double array types (Array, ContiguousArray and ArraySlice)

On Nov 21, 2016, at 4:32 PM, Rick Mann via swift-users <swift-users@swift.org> wrote:

My googling is not turning up an answer that works in Xcode 8.1. I'd like to do this:

import Accelerate

extension
Array
  where Element == Double
{
  func
  sum()
    -> Double
  {
    var result: Double = 0.0
    vDSP_sveD(self, 1, &result, vDSP_Length(self.count))
    return result
  }
}

But I get "same-type requirement makes generic parameter 'Element' non-generic."

Also, will there ever be any way to specialize something like

  let numbers: [Double] = ...
  let sum = numbers.reduce(0.0, +)

Into a call to vDSP_sveD()? Would it require compiler optimizations for Accelerate?

Thanks!

--
Rick Mann
rmann@latencyzero.com

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

--
Rick Mann
rmann@latencyzero.com

--
Rick Mann
rmann@latencyzero.com


(Rick M) #12

Thanks! It's all very educational, at the least.

Obviously the ideal would be for LLVM to recognize and optimize (there are many ways to write the sum of an array), but this is cool.

···

On Nov 22, 2016, at 16:50 , Hooman Mehr <hooman@mac.com> wrote:

For example, this reduces the six variants of sum to two:

public protocol ContiguousBufferedArray: RandomAccessCollection {
    
    func withUnsafeBufferPointer<R>(_ body: (UnsafeBufferPointer<Iterator.Element>) throws -> R) rethrows -> R
}

extension Array: ContiguousBufferedArray {}
extension ContiguousArray: ContiguousBufferedArray {}
extension ArraySlice: ContiguousBufferedArray {}

func sum<A>(_ array: A) -> Double where A: ContiguousBufferedArray, A.Iterator.Element == Double {
    var result = Double()
    array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, numericCast(array.count)) }
    return result
}

func sum<A>(_ array: A) -> Float where A: ContiguousBufferedArray, A.Iterator.Element == Float {
    var result = Float()
    array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, numericCast(array.count)) }
    return result
}

I have to think a bit more to see what common API we can extract from array that can be generally useful. I will put up a pic on evolution once I get a clearer idea.

On Nov 22, 2016, at 4:46 PM, Rick Mann <rmann@latencyzero.com> wrote:

That sounds interesting. Would you mind making that pitch on swift-evolution? I just barely understood what you said :confused:

On Nov 22, 2016, at 07:46 , Hooman Mehr <hooman@mac.com> wrote:

It is good to know that

extension Array where Element == Double { }

will work pretty soon with Swift 3.1.

Back to reduce(0,+):

If we get specialized instance for a reduce(0,+), so that it is known that “+” is a (Double, Double)->Double function, LLVM’s auto-vectorization should be able to optimize it for the CPU’s vector unit. In theory, it should be possible to add additional optimizers to LLVM layer to use other hardware or numeric libraries for that purpose, but I don’t think it would be a Swift-specific thing.

Swift’s generics still has a long way to go. Since they are aiming for ABI stability by Swift 4.0, and there isn’t much time left, I don’t think many of the bigger generics improvements fit with the current Swift evolution discussions, although they could have huge impact on standard library (hence the ABI stability).

One thing that might be worth discussing on Swift evolution and can potentially make it to standard library and Swift 4.0 is adding a common protocol for array-like types that have (or can have) contiguous buffers so that manually vectorizing operations on their elements becomes easier and cleaner.

At the moment, we can manually define a protocol that extends RandomAccessCollection and provides `withUnsafeBufferPointer` and then declare the conformance of all of the standard library array variants to it so that we can provide a single generic sum global function for summing all of them using vDSP. This protocol may be worth adding to the standard library.

On Nov 21, 2016, at 7:05 PM, Rick Mann <rmann@latencyzero.com> wrote:

Thanks, Hooman. Is it worth posting on swift-evolution the question about specializing something like reduce(0, +) (it's complicated because it would mean specializing reduce() based on both the type and the closure passed, and that seems like something that would be difficult to specify concisely in the syntax).

On Nov 21, 2016, at 18:29 , Hooman Mehr <hooman@mac.com> wrote:

This is not possible in Swift 3.0. Swift 4.0 will improve things with conditional conformances.

For now, the best solution is using global functions instead of extending types or protocols.

For example you can do this now:

extension Array where Element: FloatingPoint {

func sum() -> Element {
     guard count > 0 else { return 0 }
     switch self[0] {
     case is Double:
         var result = Double()
         vDSP_sveD(unsafeBitCast(self, to: Array<Double>.self), 1, &result, vDSP_Length(count))
         print("vDSP")
         return unsafeBitCast(result, to: Element.self)
     case is Float:
         var result = Float()
         vDSP_sve(unsafeBitCast(self, to: Array<Float>.self), 1, &result, vDSP_Length(count))
         print("vDSP")
         return unsafeBitCast(result, to: Element.self)
     default:
         print("default")
         return reduce(0, +)
     }
}
}

But this is not very efficient, especially if it is defined in another module, which limits optimizations.

Instead, a family of overloaded global functions gives you the most coverage and best performance, at the expense of repetition and boilerplate code:

func sum<S: Sequence>(_ sequence: S) -> S.Iterator.Element where S.Iterator.Element: Integer {
var result: S.Iterator.Element = 0
for element in sequence { result += element }
return result
}

func sum<S: Sequence>(_ sequence: S) -> S.Iterator.Element where S.Iterator.Element: FloatingPoint {
var result: S.Iterator.Element = 0
for element in sequence { result += element }
return result
}

func sum(_ array: Array<Double>) -> Double {
var result = Double()
vDSP_sveD(array, 1, &result, vDSP_Length(array.count))
return result
}

func sum(_ array: ContiguousArray<Double>) -> Double {
var result = Double()
array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
return result
}

func sum(_ array: ArraySlice<Double>) -> Double {
var result = Double()
array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
return result
}

func sum(_ array: Array<Float>) -> Float {
var result = Float()
vDSP_sve(array, 1, &result, vDSP_Length(array.count))
return result
}

func sum(_ array: ContiguousArray<Float>) -> Float {
var result = Float()
array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
return result
}

func sum(_ array: ArraySlice<Float>) -> Float {
var result = Float()
array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
return result
}

The above code covers summing any integer or floating point sequence of numbers, while being accelerated for Float and Double array types (Array, ContiguousArray and ArraySlice)

On Nov 21, 2016, at 4:32 PM, Rick Mann via swift-users <swift-users@swift.org> wrote:

My googling is not turning up an answer that works in Xcode 8.1. I'd like to do this:

import Accelerate

extension
Array
  where Element == Double
{
  func
  sum()
    -> Double
  {
    var result: Double = 0.0
    vDSP_sveD(self, 1, &result, vDSP_Length(self.count))
    return result
  }
}

But I get "same-type requirement makes generic parameter 'Element' non-generic."

Also, will there ever be any way to specialize something like

  let numbers: [Double] = ...
  let sum = numbers.reduce(0.0, +)

Into a call to vDSP_sveD()? Would it require compiler optimizations for Accelerate?

Thanks!

--
Rick Mann
rmann@latencyzero.com

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

--
Rick Mann
rmann@latencyzero.com

--
Rick Mann
rmann@latencyzero.com

--
Rick Mann
rmann@latencyzero.com


(Karl) #13

For example, this reduces the six variants of sum to two:

public protocol ContiguousBufferedArray: RandomAccessCollection {
    
    func withUnsafeBufferPointer<R>(_ body: (UnsafeBufferPointer<Iterator.Element>) throws -> R) rethrows -> R
}

extension Array: ContiguousBufferedArray {}
extension ContiguousArray: ContiguousBufferedArray {}
extension ArraySlice: ContiguousBufferedArray {}

func sum<A>(_ array: A) -> Double where A: ContiguousBufferedArray, A.Iterator.Element == Double {
    var result = Double()
    array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, numericCast(array.count)) }
    return result
}

func sum<A>(_ array: A) -> Float where A: ContiguousBufferedArray, A.Iterator.Element == Float {
    var result = Float()
    array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, numericCast(array.count)) }
    return result
}

I have to think a bit more to see what common API we can extract from array that can be generally useful. I will put up a pic on evolution once I get a clearer idea.

DaveA mentioned at the start of the month that they were looking at ways to allow better contiguous memory optimisations (including vectorisation).

If you think about what it means to build APIs for contiguous memory
into abstractions like Sequence or Collection, at least without
penalizing the lowest-level code, it means exposing UnsafeBufferPointers
as a first-class part of the protocols, which is really
unappealing... unless you consider that *borrowed* UnsafeBufferPointers
can be made safe.

- Karl

···

On 23 Nov 2016, at 01:50, Hooman Mehr via swift-users <swift-users@swift.org> wrote:

https://www.mail-archive.com/swift-evolution@swift.org/msg18395.html

On Nov 22, 2016, at 4:46 PM, Rick Mann <rmann@latencyzero.com <mailto:rmann@latencyzero.com>> wrote:

That sounds interesting. Would you mind making that pitch on swift-evolution? I just barely understood what you said :confused:

On Nov 22, 2016, at 07:46 , Hooman Mehr <hooman@mac.com <mailto:hooman@mac.com>> wrote:

It is good to know that

extension Array where Element == Double { }

will work pretty soon with Swift 3.1.

Back to reduce(0,+):

If we get specialized instance for a reduce(0,+), so that it is known that “+” is a (Double, Double)->Double function, LLVM’s auto-vectorization should be able to optimize it for the CPU’s vector unit. In theory, it should be possible to add additional optimizers to LLVM layer to use other hardware or numeric libraries for that purpose, but I don’t think it would be a Swift-specific thing.

Swift’s generics still has a long way to go. Since they are aiming for ABI stability by Swift 4.0, and there isn’t much time left, I don’t think many of the bigger generics improvements fit with the current Swift evolution discussions, although they could have huge impact on standard library (hence the ABI stability).

One thing that might be worth discussing on Swift evolution and can potentially make it to standard library and Swift 4.0 is adding a common protocol for array-like types that have (or can have) contiguous buffers so that manually vectorizing operations on their elements becomes easier and cleaner.

At the moment, we can manually define a protocol that extends RandomAccessCollection and provides `withUnsafeBufferPointer` and then declare the conformance of all of the standard library array variants to it so that we can provide a single generic sum global function for summing all of them using vDSP. This protocol may be worth adding to the standard library.

On Nov 21, 2016, at 7:05 PM, Rick Mann <rmann@latencyzero.com <mailto:rmann@latencyzero.com>> wrote:

Thanks, Hooman. Is it worth posting on swift-evolution the question about specializing something like reduce(0, +) (it's complicated because it would mean specializing reduce() based on both the type and the closure passed, and that seems like something that would be difficult to specify concisely in the syntax).

On Nov 21, 2016, at 18:29 , Hooman Mehr <hooman@mac.com <mailto:hooman@mac.com>> wrote:

This is not possible in Swift 3.0. Swift 4.0 will improve things with conditional conformances.

For now, the best solution is using global functions instead of extending types or protocols.

For example you can do this now:

extension Array where Element: FloatingPoint {

func sum() -> Element {
     guard count > 0 else { return 0 }
     switch self[0] {
     case is Double:
         var result = Double()
         vDSP_sveD(unsafeBitCast(self, to: Array<Double>.self), 1, &result, vDSP_Length(count))
         print("vDSP")
         return unsafeBitCast(result, to: Element.self)
     case is Float:
         var result = Float()
         vDSP_sve(unsafeBitCast(self, to: Array<Float>.self), 1, &result, vDSP_Length(count))
         print("vDSP")
         return unsafeBitCast(result, to: Element.self)
     default:
         print("default")
         return reduce(0, +)
     }
}
}

But this is not very efficient, especially if it is defined in another module, which limits optimizations.

Instead, a family of overloaded global functions gives you the most coverage and best performance, at the expense of repetition and boilerplate code:

func sum<S: Sequence>(_ sequence: S) -> S.Iterator.Element where S.Iterator.Element: Integer {
var result: S.Iterator.Element = 0
for element in sequence { result += element }
return result
}

func sum<S: Sequence>(_ sequence: S) -> S.Iterator.Element where S.Iterator.Element: FloatingPoint {
var result: S.Iterator.Element = 0
for element in sequence { result += element }
return result
}

func sum(_ array: Array<Double>) -> Double {
var result = Double()
vDSP_sveD(array, 1, &result, vDSP_Length(array.count))
return result
}

func sum(_ array: ContiguousArray<Double>) -> Double {
var result = Double()
array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
return result
}

func sum(_ array: ArraySlice<Double>) -> Double {
var result = Double()
array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
return result
}

func sum(_ array: Array<Float>) -> Float {
var result = Float()
vDSP_sve(array, 1, &result, vDSP_Length(array.count))
return result
}

func sum(_ array: ContiguousArray<Float>) -> Float {
var result = Float()
array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
return result
}

func sum(_ array: ArraySlice<Float>) -> Float {
var result = Float()
array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
return result
}

The above code covers summing any integer or floating point sequence of numbers, while being accelerated for Float and Double array types (Array, ContiguousArray and ArraySlice)

On Nov 21, 2016, at 4:32 PM, Rick Mann via swift-users <swift-users@swift.org <mailto:swift-users@swift.org>> wrote:

My googling is not turning up an answer that works in Xcode 8.1. I'd like to do this:

import Accelerate

extension
Array
  where Element == Double
{
  func
  sum()
    -> Double
  {
    var result: Double = 0.0
    vDSP_sveD(self, 1, &result, vDSP_Length(self.count))
    return result
  }
}

But I get "same-type requirement makes generic parameter 'Element' non-generic."

Also, will there ever be any way to specialize something like

  let numbers: [Double] = ...
  let sum = numbers.reduce(0.0, +)

Into a call to vDSP_sveD()? Would it require compiler optimizations for Accelerate?

Thanks!

--
Rick Mann
rmann@latencyzero.com <mailto:rmann@latencyzero.com>

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

--
Rick Mann
rmann@latencyzero.com <mailto:rmann@latencyzero.com>

--
Rick Mann
rmann@latencyzero.com <mailto:rmann@latencyzero.com>

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


(Hooman Mehr) #14

By the way, even without new Swift 3.1 feature, this works, providing optimized sum function for all three types:

extension ContiguousBufferedArray where Iterator.Element == Double {
    
    func sum() -> Double {
        
        var result = Double()
        withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, numericCast(count)) }
        return result
    }
}

extension ContiguousBufferedArray where Iterator.Element == Float {
    
    func sum() -> Float {
        
        var result = Float()
        withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, numericCast(count)) }
        return result
    }
}

···

On Nov 22, 2016, at 4:56 PM, Rick Mann <rmann@latencyzero.com> wrote:

Thanks! It's all very educational, at the least.

Obviously the ideal would be for LLVM to recognize and optimize (there are many ways to write the sum of an array), but this is cool.

On Nov 22, 2016, at 16:50 , Hooman Mehr <hooman@mac.com> wrote:

For example, this reduces the six variants of sum to two:

public protocol ContiguousBufferedArray: RandomAccessCollection {

   func withUnsafeBufferPointer<R>(_ body: (UnsafeBufferPointer<Iterator.Element>) throws -> R) rethrows -> R
}

extension Array: ContiguousBufferedArray {}
extension ContiguousArray: ContiguousBufferedArray {}
extension ArraySlice: ContiguousBufferedArray {}

func sum<A>(_ array: A) -> Double where A: ContiguousBufferedArray, A.Iterator.Element == Double {
   var result = Double()
   array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, numericCast(array.count)) }
   return result
}

func sum<A>(_ array: A) -> Float where A: ContiguousBufferedArray, A.Iterator.Element == Float {
   var result = Float()
   array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, numericCast(array.count)) }
   return result
}

I have to think a bit more to see what common API we can extract from array that can be generally useful. I will put up a pic on evolution once I get a clearer idea.

On Nov 22, 2016, at 4:46 PM, Rick Mann <rmann@latencyzero.com> wrote:

That sounds interesting. Would you mind making that pitch on swift-evolution? I just barely understood what you said :confused:

On Nov 22, 2016, at 07:46 , Hooman Mehr <hooman@mac.com> wrote:

It is good to know that

extension Array where Element == Double { }

will work pretty soon with Swift 3.1.

Back to reduce(0,+):

If we get specialized instance for a reduce(0,+), so that it is known that “+” is a (Double, Double)->Double function, LLVM’s auto-vectorization should be able to optimize it for the CPU’s vector unit. In theory, it should be possible to add additional optimizers to LLVM layer to use other hardware or numeric libraries for that purpose, but I don’t think it would be a Swift-specific thing.

Swift’s generics still has a long way to go. Since they are aiming for ABI stability by Swift 4.0, and there isn’t much time left, I don’t think many of the bigger generics improvements fit with the current Swift evolution discussions, although they could have huge impact on standard library (hence the ABI stability).

One thing that might be worth discussing on Swift evolution and can potentially make it to standard library and Swift 4.0 is adding a common protocol for array-like types that have (or can have) contiguous buffers so that manually vectorizing operations on their elements becomes easier and cleaner.

At the moment, we can manually define a protocol that extends RandomAccessCollection and provides `withUnsafeBufferPointer` and then declare the conformance of all of the standard library array variants to it so that we can provide a single generic sum global function for summing all of them using vDSP. This protocol may be worth adding to the standard library.

On Nov 21, 2016, at 7:05 PM, Rick Mann <rmann@latencyzero.com> wrote:

Thanks, Hooman. Is it worth posting on swift-evolution the question about specializing something like reduce(0, +) (it's complicated because it would mean specializing reduce() based on both the type and the closure passed, and that seems like something that would be difficult to specify concisely in the syntax).

On Nov 21, 2016, at 18:29 , Hooman Mehr <hooman@mac.com> wrote:

This is not possible in Swift 3.0. Swift 4.0 will improve things with conditional conformances.

For now, the best solution is using global functions instead of extending types or protocols.

For example you can do this now:

extension Array where Element: FloatingPoint {

func sum() -> Element {
    guard count > 0 else { return 0 }
    switch self[0] {
    case is Double:
        var result = Double()
        vDSP_sveD(unsafeBitCast(self, to: Array<Double>.self), 1, &result, vDSP_Length(count))
        print("vDSP")
        return unsafeBitCast(result, to: Element.self)
    case is Float:
        var result = Float()
        vDSP_sve(unsafeBitCast(self, to: Array<Float>.self), 1, &result, vDSP_Length(count))
        print("vDSP")
        return unsafeBitCast(result, to: Element.self)
    default:
        print("default")
        return reduce(0, +)
    }
}
}

But this is not very efficient, especially if it is defined in another module, which limits optimizations.

Instead, a family of overloaded global functions gives you the most coverage and best performance, at the expense of repetition and boilerplate code:

func sum<S: Sequence>(_ sequence: S) -> S.Iterator.Element where S.Iterator.Element: Integer {
var result: S.Iterator.Element = 0
for element in sequence { result += element }
return result
}

func sum<S: Sequence>(_ sequence: S) -> S.Iterator.Element where S.Iterator.Element: FloatingPoint {
var result: S.Iterator.Element = 0
for element in sequence { result += element }
return result
}

func sum(_ array: Array<Double>) -> Double {
var result = Double()
vDSP_sveD(array, 1, &result, vDSP_Length(array.count))
return result
}

func sum(_ array: ContiguousArray<Double>) -> Double {
var result = Double()
array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
return result
}

func sum(_ array: ArraySlice<Double>) -> Double {
var result = Double()
array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
return result
}

func sum(_ array: Array<Float>) -> Float {
var result = Float()
vDSP_sve(array, 1, &result, vDSP_Length(array.count))
return result
}

func sum(_ array: ContiguousArray<Float>) -> Float {
var result = Float()
array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
return result
}

func sum(_ array: ArraySlice<Float>) -> Float {
var result = Float()
array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
return result
}

The above code covers summing any integer or floating point sequence of numbers, while being accelerated for Float and Double array types (Array, ContiguousArray and ArraySlice)

On Nov 21, 2016, at 4:32 PM, Rick Mann via swift-users <swift-users@swift.org> wrote:

My googling is not turning up an answer that works in Xcode 8.1. I'd like to do this:

import Accelerate

extension
Array
  where Element == Double
{
  func
  sum()
    -> Double
  {
    var result: Double = 0.0
    vDSP_sveD(self, 1, &result, vDSP_Length(self.count))
    return result
  }
}

But I get "same-type requirement makes generic parameter 'Element' non-generic."

Also, will there ever be any way to specialize something like

  let numbers: [Double] = ...
  let sum = numbers.reduce(0.0, +)

Into a call to vDSP_sveD()? Would it require compiler optimizations for Accelerate?

Thanks!

--
Rick Mann
rmann@latencyzero.com

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

--
Rick Mann
rmann@latencyzero.com

--
Rick Mann
rmann@latencyzero.com

--
Rick Mann
rmann@latencyzero.com


(Rick M) #15

That seems to work well, thanks!

···

On Nov 22, 2016, at 16:59 , Hooman Mehr <hooman@mac.com> wrote:

By the way, even without new Swift 3.1 feature, this works, providing optimized sum function for all three types:

extension ContiguousBufferedArray where Iterator.Element == Double {
    
    func sum() -> Double {
        
        var result = Double()
        withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, numericCast(count)) }
        return result
    }
}

extension ContiguousBufferedArray where Iterator.Element == Float {
    
    func sum() -> Float {
        
        var result = Float()
        withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, numericCast(count)) }
        return result
    }
}

On Nov 22, 2016, at 4:56 PM, Rick Mann <rmann@latencyzero.com> wrote:

Thanks! It's all very educational, at the least.

Obviously the ideal would be for LLVM to recognize and optimize (there are many ways to write the sum of an array), but this is cool.

On Nov 22, 2016, at 16:50 , Hooman Mehr <hooman@mac.com> wrote:

For example, this reduces the six variants of sum to two:

public protocol ContiguousBufferedArray: RandomAccessCollection {

   func withUnsafeBufferPointer<R>(_ body: (UnsafeBufferPointer<Iterator.Element>) throws -> R) rethrows -> R
}

extension Array: ContiguousBufferedArray {}
extension ContiguousArray: ContiguousBufferedArray {}
extension ArraySlice: ContiguousBufferedArray {}

func sum<A>(_ array: A) -> Double where A: ContiguousBufferedArray, A.Iterator.Element == Double {
   var result = Double()
   array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, numericCast(array.count)) }
   return result
}

func sum<A>(_ array: A) -> Float where A: ContiguousBufferedArray, A.Iterator.Element == Float {
   var result = Float()
   array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, numericCast(array.count)) }
   return result
}

I have to think a bit more to see what common API we can extract from array that can be generally useful. I will put up a pic on evolution once I get a clearer idea.

On Nov 22, 2016, at 4:46 PM, Rick Mann <rmann@latencyzero.com> wrote:

That sounds interesting. Would you mind making that pitch on swift-evolution? I just barely understood what you said :confused:

On Nov 22, 2016, at 07:46 , Hooman Mehr <hooman@mac.com> wrote:

It is good to know that

extension Array where Element == Double { }

will work pretty soon with Swift 3.1.

Back to reduce(0,+):

If we get specialized instance for a reduce(0,+), so that it is known that “+” is a (Double, Double)->Double function, LLVM’s auto-vectorization should be able to optimize it for the CPU’s vector unit. In theory, it should be possible to add additional optimizers to LLVM layer to use other hardware or numeric libraries for that purpose, but I don’t think it would be a Swift-specific thing.

Swift’s generics still has a long way to go. Since they are aiming for ABI stability by Swift 4.0, and there isn’t much time left, I don’t think many of the bigger generics improvements fit with the current Swift evolution discussions, although they could have huge impact on standard library (hence the ABI stability).

One thing that might be worth discussing on Swift evolution and can potentially make it to standard library and Swift 4.0 is adding a common protocol for array-like types that have (or can have) contiguous buffers so that manually vectorizing operations on their elements becomes easier and cleaner.

At the moment, we can manually define a protocol that extends RandomAccessCollection and provides `withUnsafeBufferPointer` and then declare the conformance of all of the standard library array variants to it so that we can provide a single generic sum global function for summing all of them using vDSP. This protocol may be worth adding to the standard library.

On Nov 21, 2016, at 7:05 PM, Rick Mann <rmann@latencyzero.com> wrote:

Thanks, Hooman. Is it worth posting on swift-evolution the question about specializing something like reduce(0, +) (it's complicated because it would mean specializing reduce() based on both the type and the closure passed, and that seems like something that would be difficult to specify concisely in the syntax).

On Nov 21, 2016, at 18:29 , Hooman Mehr <hooman@mac.com> wrote:

This is not possible in Swift 3.0. Swift 4.0 will improve things with conditional conformances.

For now, the best solution is using global functions instead of extending types or protocols.

For example you can do this now:

extension Array where Element: FloatingPoint {

func sum() -> Element {
    guard count > 0 else { return 0 }
    switch self[0] {
    case is Double:
        var result = Double()
        vDSP_sveD(unsafeBitCast(self, to: Array<Double>.self), 1, &result, vDSP_Length(count))
        print("vDSP")
        return unsafeBitCast(result, to: Element.self)
    case is Float:
        var result = Float()
        vDSP_sve(unsafeBitCast(self, to: Array<Float>.self), 1, &result, vDSP_Length(count))
        print("vDSP")
        return unsafeBitCast(result, to: Element.self)
    default:
        print("default")
        return reduce(0, +)
    }
}
}

But this is not very efficient, especially if it is defined in another module, which limits optimizations.

Instead, a family of overloaded global functions gives you the most coverage and best performance, at the expense of repetition and boilerplate code:

func sum<S: Sequence>(_ sequence: S) -> S.Iterator.Element where S.Iterator.Element: Integer {
var result: S.Iterator.Element = 0
for element in sequence { result += element }
return result
}

func sum<S: Sequence>(_ sequence: S) -> S.Iterator.Element where S.Iterator.Element: FloatingPoint {
var result: S.Iterator.Element = 0
for element in sequence { result += element }
return result
}

func sum(_ array: Array<Double>) -> Double {
var result = Double()
vDSP_sveD(array, 1, &result, vDSP_Length(array.count))
return result
}

func sum(_ array: ContiguousArray<Double>) -> Double {
var result = Double()
array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
return result
}

func sum(_ array: ArraySlice<Double>) -> Double {
var result = Double()
array.withUnsafeBufferPointer { vDSP_sveD($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
return result
}

func sum(_ array: Array<Float>) -> Float {
var result = Float()
vDSP_sve(array, 1, &result, vDSP_Length(array.count))
return result
}

func sum(_ array: ContiguousArray<Float>) -> Float {
var result = Float()
array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
return result
}

func sum(_ array: ArraySlice<Float>) -> Float {
var result = Float()
array.withUnsafeBufferPointer { vDSP_sve($0.baseAddress!, 1, &result, vDSP_Length(array.count)) }
return result
}

The above code covers summing any integer or floating point sequence of numbers, while being accelerated for Float and Double array types (Array, ContiguousArray and ArraySlice)

On Nov 21, 2016, at 4:32 PM, Rick Mann via swift-users <swift-users@swift.org> wrote:

My googling is not turning up an answer that works in Xcode 8.1. I'd like to do this:

import Accelerate

extension
Array
  where Element == Double
{
  func
  sum()
    -> Double
  {
    var result: Double = 0.0
    vDSP_sveD(self, 1, &result, vDSP_Length(self.count))
    return result
  }
}

But I get "same-type requirement makes generic parameter 'Element' non-generic."

Also, will there ever be any way to specialize something like

  let numbers: [Double] = ...
  let sum = numbers.reduce(0.0, +)

Into a call to vDSP_sveD()? Would it require compiler optimizations for Accelerate?

Thanks!

--
Rick Mann
rmann@latencyzero.com

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

--
Rick Mann
rmann@latencyzero.com

--
Rick Mann
rmann@latencyzero.com

--
Rick Mann
rmann@latencyzero.com

--
Rick Mann
rmann@latencyzero.com