[swift-users] Extending Arrays of specific type, and specialization
Hooman Mehr
hooman at mac.com
Tue Nov 22 18:59:48 CST 2016
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 at 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 at 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 at latencyzero.com> wrote:
>>>
>>> That sounds interesting. Would you mind making that pitch on swift-evolution? I just barely understood what you said :/
>>>
>>>> On Nov 22, 2016, at 07:46 , Hooman Mehr <hooman at 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 at 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 at 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 at 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 at latencyzero.com
>>>>>>>
>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> swift-users mailing list
>>>>>>> swift-users at swift.org
>>>>>>> https://lists.swift.org/mailman/listinfo/swift-users
>>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> Rick Mann
>>>>> rmann at latencyzero.com
>>>>>
>>>>>
>>>>
>>>
>>>
>>> --
>>> Rick Mann
>>> rmann at latencyzero.com
>>>
>>>
>>
>
>
> --
> Rick Mann
> rmann at latencyzero.com
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-users/attachments/20161122/59802d3b/attachment.html>
More information about the swift-users
mailing list