Migrate from Float/Double to T: FloatingPoint

[regexident]

tl;dr

Surge currently provides separate implementations for each function for Float and Double, respectively. This makes Surge basically incompatible with Swift's T: FloatingPoint generics. By introducing a little bit of internal runtime dynamism we aim to migrate existing function pairs to their generic equivalent for T: FloatingPoint.

What?

With the recent refactors we have managed to reduce the implementations of each computation into a function set consisting of a single internal core-implementation, acting as a single source of truth, and a bunch of thin public convenience wrapper functions.

Scalar-Division ([Scalar] / Scalar) is implemented like this:

public func / <L>(lhs: L, rhs: Float) -> [Float] where L: UnsafeMemoryAccessible, L.Element == Float {
    return div(lhs, rhs)
}

public func div<L>(_ lhs: L, _ rhs: Float) -> [Float] where L: UnsafeMemoryAccessible, L.Element == Float {
    return withArray(from: lhs) { divInPlace(&$0, rhs) }
}

func divInPlace<L>(_ lhs: inout L, _ rhs: Float) where L: UnsafeMutableMemoryAccessible, L.Element == Float {
    lhs.withUnsafeMutableMemory { lm in
        var scalar = rhs
        vDSP_vsdiv(lm.pointer, numericCast(lm.stride), &scalar, lm.pointer, numericCast(lm.stride), numericCast(lm.count))
    }
}

… with an almost identical copy existing for each of these functions for Double, instead of Float.

Why?

While the project's current state is quite an improvement over its previous state it has a couple of remaining deficits:

• We have literally everything in two near-identical flavors: Float and Double.
• One cannot currently use Surge in contexts where one is using T: FloatingPoint over Float/Double.

So this got me thinking: What if we migrated Surge from using Float/Double to an API with T: FloatingPoint and then internally make use of some dynamic language features to roll our own polymorphism over the closed set of Float and Double with a fatalError(…) on type-mismatch?

Aforementioned dynamism would add a certain amount of runtime overhead to Surge. It is important to note however that we would be adding a constant overhead (O(1) vs. O(N)), as a single call of Surge.divInPlace(_:_:) over a pair of 10_000-element arrays only adds a single branch per execution, not 10_000 branches in a loop, as would be the case for a naïve non-parallel looping implementation.

How?

So how would this look like? What would we need to change?

1. We would replace every existing pair of thin public wrapper functions for Float/Double with a single equivalent function that is generic over T: FloatingPoint, instead.
2. We would merge every existing pair of internal …InPlace(…) core-implementation functions for Float/Double into a single equivalent function that is generic over T: FloatingPoint on the outside and then performs a switch on T.self on the inside, instead.
3. We would add func withMemoryRebound(to:_:) to UnsafeMemory<T> and UnsafeMutableMemory<T>, so that we can efficiently cast from UnsafeMemory<T: FloatingPoint> to UnsafeMemory<Double>, without having to copy/cast any individual values.
4. We would add func withUnsafeMemory(as:…) convenience functions for retrieving type-cast variants of UnsafeMemory<T> from instances of UnsafeMemoryAccessible/UnsafeMutableMemoryAccessible.
5. We would refactor the func …InPlace(…) implementations into something like this:

func divInPlace<L, T>(_ lhs: inout L, _ rhs: T) where L: UnsafeMutableMemoryAccessible, L.Element == T, T: FloatingPoint & ExpressibleByFloatLiteral {
    let rhs = CollectionOfOne(rhs)
    withUnsafeMemory(
        &lhs,
        rhs,
        float: { lhs, rhs in
            vDSP_vsdiv(lhs.pointer, numericCast(lhs.stride), rhs.pointer, lhs.pointer, numericCast(lhs.stride), numericCast(lhs.count))
        },
        double: { lhs, rhs in
            vDSP_vsdivD(lhs.pointer, numericCast(lhs.stride), rhs.pointer, lhs.pointer, numericCast(lhs.stride), numericCast(lhs.count))
        }
    )
}

So far I have not been able to measure any noticeable performance regressions introduced by this change.

There also should be very little breakage from the changes, as T: FloatingPoint is for the most part a strict superset of either Float or Double.

(I already have a proof-of-concept for this on a local branch and will push it as a PR at some point.)

[mattt]

A few questions:

• FloatingPoint has three conforming types in the Swift Standard Library: Float, Double, and Float80. How would Float80 be handled using this approach?
• FloatingPoint is a public type, which allows other types to conform to it. How would this approach deal with, for example, a library that vends its own Float16 type that conforms to FloatingPoint?

[regexident]

It wouldn't, unfortunately. 😕

I would expect the API to fatalError(<helpful error message>) on anything but Float or Double.

I agree though, that this might not be the desired behavior for a default API.

I wish SwiftPM allowed for specifying settings on dependencies (e.g. swiftSettings: [.define("GENERICS")]), allowing us to hide the optional generic API behind conditional compilation (e.g. #if GENERICS … #endif). Then users of Surge could opt into such a generic API.

Alas SwiftPM only allows for settings on direct targets.

[mattt]

I would expect the API to fatalError(<helpful error message>) on anything but Float or Double.

I think this would be a step backwards in terms of API usability. Taking the current approach as a baseline, the proposed change would:

1. Require less code duplication in the implementation (+)
2. Introduce runtime errors for type mismatches (-)
3. Introduce a small (perhaps negligible) runtime cost for type introspection (-)

By comparison, the proposed alternative to use code generation would solve 1) without introducing 2) or 3). So currently, I'm leaning towards this alternative approach.

---

I also think it paints us into a corner when it comes to supporting additional floating point types should they be introduced.

Imagine if a future version of Swift and Accelerate adds a Float16 type, in support of post-training quantization to yield smaller machine learning models:

If Surge 3.0 makes functions generic — supporting only Float and Double — a change to support Float16 could only be done in Surge itself, communicated only through documentation, and (arguably) necessitate a new major semantic version. By comparison, if we don't do that, support for Float16 would be purely additive, and could be accomplished in a separate library.

Or actually, here's the worst-case scenario: Let's say that a Float16 type is added, but Accelerate only adds support for a subset of BLAS functions, for whatever reason. If we wanted to support Float16 in Surge, we'd now have to go out of our way to document which functions do and which do not support Float16 on an individual basis. That'd be much worse than the compiler being able to tell us that function overload does or doesn't exist.

---

In another thread you mentioned that:

For me the main driver for #147 is for Surge to be compatible with codebases using generic T: FloatingPoint.

I was hoping to draw that out, as I think that's the information I'm missing to understand the motivation for this change. Could you tell me more about what you've seen in this respect? Do you have examples of how people are using T: FloatingPoint in the wild --- especially in combination with Surge?

[mattt]

Let's say that a Float16 type is added ...

Well, that didn't take long! apple/swift-numerics#8

[regexident]

I would expect the API to fatalError(<helpful error message>) on anything but Float or Double.

I think this would be a step backwards in terms of API usability. Taking the current approach as a baseline, the proposed change would:

1. Require less code duplication in the implementation (+)
2. Introduce runtime errors for type mismatches (-)
3. Introduce a small (perhaps negligible) runtime cost for type introspection (-)

By comparison, the proposed alternative to use code generation would solve 1) without introducing 2) or 3). So currently, I'm leaning towards this alternative approach.

Code generation alone unfortunately does not solve the issue that without an API with signature <T: FloatingPoint> Surge remains unavailable from generic code.

My goal with adding (or merging into) <T: FloatingPoint> is not about code reduction, but primarily about making Surge available to scenarios where want to keep your implementation indipendent from your choice of floating-point type.

I also think it paints us into a corner when it comes to supporting additional floating point types should they be introduced.

Imagine if a future version of Swift and Accelerate adds a Float16 type, in support of post-training quantization to yield smaller machine learning models:

It actually doesn't take an addition of Float16 for this. We already have Float80 in Swift. 😬

If Surge 3.0 makes functions generic — supporting only Float and Double — a change to support Float16 could only be done in Surge itself, communicated only through documentation, and (arguably) necessitate a new major semantic version. By comparison, if we don't do that, support for Float16 would be purely additive, and could be accomplished in a separate library.

100% agree.

Or actually, here's the worst-case scenario: Let's say that a Float16 type is added, but Accelerate only adds support for a subset of BLAS functions, for whatever reason. If we wanted to support Float16 in Surge, we'd now have to go out of our way to document which functions do and which do not support Float16 on an individual basis. That'd be much worse than the compiler being able to tell us that function overload does or doesn't exist.

Again, I 100% agree.

My best-case solution would be to have a way to generate a generic wrapper for a concrete (i.e. Double, Float) API. This way we would

1. keep our API pristine and safe
2. provide an opt-in unsafe escape hook for those who absolutely positively want generics and are fine with doing the hard work of ensuring safety within their code-base themselves.

And it happens I might have found a proof-of-concept solution for exactly that, actually. I'll keep you posted. Don't want to promise too much, too early.

In another thread you mentioned that:

For me the main driver for #147 is for Surge to be compatible with codebases using generic T: FloatingPoint.

I was hoping to draw that out, as I think that's the information I'm missing to understand the motivation for this change. Could you tell me more about what you've seen in this respect? Do you have examples of how people are using T: FloatingPoint in the wild --- especially in combination with Surge?

Well, for me personally as someone who does their other 50% share of coding mostly in Rust I tend to aim for my code to be maximally generic in Swift, too.

It's a habit, I guess.

But judging from the existence of projects such as …

https://github.com/cloutiertyler/Jolt (abandoned)

… it seems like I'm not alone in this.

---

Let's say that a Float16 type is added ...

Well, that didn't take long! apple/swift-numerics#8

Heh, nice!

It won't really change that much for Surge though, will it?
Still great to see a realistic possibility of Swift getting some actual usable numeric protocols. Finally. The status quo of numeric protocols is pretty much useless for generic programming (i.e. far too coarse).

[regexident]

With Swift already supporting Float80 and Float16 being scheduled for addition in Swift 5.3 simply providing a generic API for T: FloatingPoint is a dead-end, safety-wise.

As such initial thought was to provide a specialized protocol SurgeFloatingPoint and urge users to stick to the implied semantics:

// Consider this protocol "closed", i.e. NO types must conform to it other than the ones listed below.
public protocol SurgeFloatingPoint: FloatingPoint {}

extension Float: SurgeFloatingPoint {}
extension Double: SurgeFloatingPoint {}

While this would provide a safe API as long as the user plays by the rules it is far from optimal, in respect to type-safety.

Not all is lost though! While Swift doesn't have closed protocols @anandabits found a brilliant way to make protocols effectively closed:

// Adapted from: https://gist.github.com/anandabits/bd73521e0c5c06371f4a268ab8c482c9

// This somewhat obscure code emulates `closed protocol` semantics for `SurgeFloatingPoint`:

/* closed */ public protocol SurgeFloatingPoint: BinaryFloatingPoint {
    associatedtype _Validator: _SurgeFloatingPointValidator where _Validator.Validated == Self
}

public class _SurgeFloatingPointValidatorBase {}

public protocol _SurgeFloatingPointValidator where Self: _SurgeFloatingPointValidatorBase {
    associatedtype Validated
}

extension Float: SurgeFloatingPoint {
    public final class _Validator: _SurgeFloatingPointValidatorBase, _SurgeFloatingPointValidator {
        public typealias Validated = Float
    }
}

extension Double: SurgeFloatingPoint {
    public final class _Validator: _SurgeFloatingPointValidatorBase, _SurgeFloatingPointValidator {
        public typealias Validated = Double
    }
}

With this in place Surge could provide a generic API for T: SurgeFloatingPoint, while ensuring that the API can only ever be used for types that actually are supported by Accelerate.