apple / swift-numerics

Advanced mathematical types and functions for Swift
Apache License 2.0
1.68k stars 147 forks source link

Module for digital signal processing #46

Open SusanDoggie opened 4 years ago

SusanDoggie commented 4 years ago

pull-request: #44

stephentyrone commented 4 years ago

Hi Susan -- please add some context for folks to discuss; what API would this module contain, what would the use cases be, what would the dependencies be, etc.

SusanDoggie commented 4 years ago

There are some of issues in pull-request

SusanDoggie commented 4 years ago

Avoid UnsafeBufferPointer with public interfaces if possible.

For my experience, it's helpful that having a raw pointer with public interfaces for building some graphic libraries, which is easier to process the raw image pixels with interlaced color channels.

We can also define some wrapper function for type safety.

What functions we should include?

I have implement the following

Should we have the following?

SusanDoggie commented 4 years ago

Swift forum

https://forums.swift.org/t/module-for-digital-signal-processing/30601

stephentyrone commented 4 years ago

For my experience, it's helpful that having a raw pointer with public interfaces

No question; I'm not arguing that raw-pointer interfaces shouldn't exist, rather that they shouldn't be the primary means for developers to interact with a module. You might look at the AccelerateBuffer APIs added to the Accelerate overlay in 5.1 for one possible approach (we'll eventually settle into a similar pattern that can be used throughout this package, but it's a reasonable placeholder that should be adaptable to whatever we settle on).

SusanDoggie commented 4 years ago

You might look at the AccelerateBuffer APIs added to the Accelerate overlay in 5.1 for one possible approach (we'll eventually settle into a similar pattern that can be used throughout this package, but it's a reasonable placeholder that should be adaptable to whatever we settle on).

Something like this? https://developer.apple.com/documentation/accelerate/vdsp/fft/3240738-transform

stephentyrone commented 4 years ago

The vDSP FFT interfaces still need some iteration. I was thinking more of the AccelerateBuffer protocol used in arithmetic operations, like https://developer.apple.com/documentation/accelerate/vdsp/3240822-add

SusanDoggie commented 4 years ago

Maybe something like this

enum FastFourier {

    enum Direction {
        case forward
        case inverse
    }

    static func transform<U, T>(_ vector: U, direction: Direction) -> [U.Element] where U : AccelerateBuffer, U.Element == Complex<T>

    static func splitTransform<U>(_ real: U, _ imaginary: U, direction: Direction) -> (real: [U.Element], imaginary: [U.Element]) where U : AccelerateBuffer, U.Element : Real

}
stephentyrone commented 4 years ago

Right, although we wouldn't use AccelerateBuffer directly, since we can't have a dependency on the SDK overlay.

SusanDoggie commented 4 years ago

We need a name for the new module. I have no idea for this :)

SusanDoggie commented 4 years ago

A draft works done! Everyone can have a try. https://github.com/apple/swift-numerics/pull/44/commits/9a54137f862304d7c7e335303368c3b9a5e2e956

SusanDoggie commented 4 years ago

The implementation requires some integer elementary functions, such as Int.isPower2 and log2(x)

10

https://github.com/SusanDoggie/swift-numerics/blob/9a54137f862304d7c7e335303368c3b9a5e2e956/Sources/Accelerate/Integer.swift

SusanDoggie commented 4 years ago

A little performance test on my computer

Apple's vDSP

log2N | vDSP_fft_zropD | vDSP_fft_zripD | vDSP_fft_zopD | vDSP_fft_zipD
2 | 5.2e-06 | 9.000000000000001e-07 | 9.000000000000001e-07 | 8.000000000000001e-07
3 | 1.1e-06 | 1.1e-06 | 1.8000000000000001e-06 | 9.000000000000001e-07
4 | 1.1e-06 | 7.000000000000001e-07 | 1.4000000000000001e-06 | 9.000000000000001e-07
5 | 2.8000000000000003e-06 | 1.1e-06 | 1.5e-06 | 1.2000000000000002e-06
6 | 2e-06 | 1e-06 | 1.4000000000000001e-06 | 1.6000000000000001e-06
7 | 2.1000000000000002e-06 | 1.6000000000000001e-06 | 1.9000000000000002e-06 | 1.4000000000000001e-06
8 | 3.4000000000000005e-06 | 1.6000000000000001e-06 | 1.8000000000000001e-06 | 1.9000000000000002e-06
9 | 6.300000000000001e-06 | 2.4000000000000003e-06 | 3.1e-06 | 3.4000000000000005e-06
10 | 1.2800000000000001e-05 | 4e-06 | 7.100000000000001e-06 | 5.7000000000000005e-06
11 | 2.4e-05 | 6.9e-06 | 1.16e-05 | 1.0700000000000001e-05
12 | 5.3700000000000004e-05 | 1.7e-05 | 2.5200000000000003e-05 | 2.23e-05
13 | 0.00010070000000000001 | 3.01e-05 | 6.54e-05 | 5.47e-05
14 | 0.0002385 | 5.640000000000001e-05 | 0.000127 | 0.0001094
15 | 0.0004723 | 0.0001332 | 0.00033130000000000003 | 0.000333
16 | 0.0011983 | 0.0003688 | 0.0007699000000000001 | 0.0007196
17 | 0.0022338 | 0.000752 | 0.0017381000000000002 | 0.0014909
18 | 0.0079562 | 0.0021701 | 0.005424600000000001 | 0.0047813000000000005
19 | 0.0173048 | 0.005217200000000001 | 0.014731 | 0.014450300000000001
20 | 0.0453539 | 0.0156594 | 0.0310786 | 0.0297275

pull-request

log2N | zrop | zrip | zop | zip
2 | 1.3e-06 | 4.7e-06 | 7.000000000000001e-07 | 5e-07
3 | 9.000000000000001e-07 | 7.000000000000001e-07 | 9.000000000000001e-07 | 8.000000000000001e-07
4 | 7.4e-06 | 1.5e-06 | 1e-06 | 1.3e-06
5 | 8.000000000000001e-07 | 8.000000000000001e-07 | 6.000000000000001e-07 | 9.000000000000001e-07
6 | 1.2000000000000002e-06 | 2.1000000000000002e-06 | 2.1000000000000002e-06 | 2.6e-06
7 | 1.7000000000000002e-06 | 1.5e-06 | 2.8000000000000003e-06 | 2.7e-06
8 | 2.9e-06 | 2.7e-06 | 5.1e-06 | 5.300000000000001e-06
9 | 6.6e-06 | 6.4000000000000006e-06 | 1.1e-05 | 1.59e-05
10 | 1.65e-05 | 1.4e-05 | 2.78e-05 | 3.39e-05
11 | 3.7800000000000004e-05 | 2.98e-05 | 6.76e-05 | 5.9e-05
12 | 7.66e-05 | 6.890000000000001e-05 | 0.0001265 | 0.0001232
13 | 0.0001326 | 0.00013 | 0.0002645 | 0.0003131
14 | 0.0002796 | 0.0002729 | 0.0005821 | 0.0006096000000000001
15 | 0.0006579000000000001 | 0.0006532 | 0.0013768000000000003 | 0.0013101000000000002
16 | 0.0013628000000000002 | 0.0016187 | 0.0034242 | 0.0028231000000000003
17 | 0.003287 | 0.0027447 | 0.0074725 | 0.006284100000000001
18 | 0.0081738 | 0.00708 | 0.019108 | 0.0187429
19 | 0.0173541 | 0.0150311 | 0.039219300000000006 | 0.0380876
20 | 0.036945 | 0.035979800000000006 | 0.08496420000000002 | 0.08137620000000001
SusanDoggie commented 4 years ago

https://github.com/apple/swift-numerics/pull/44/commits/f3159aec6ef00f6b81e62b0adab8e44751687b0a

I have renamed and divided framework into

All of the ugly raw functions are putting into CorePerformance.

karwa commented 4 years ago

A couple of suggestions:

  1. You can make a subfolder inside of your module directory for the "raw" implementations. No need to make 2 separate modules.
  2. The name "Performance" is a bit too generic. Might I suggest SignalProcessing or DigitalSignals?
  3. Should we maybe prefer to use Accelerate on platforms where it's available and offers equivalent functionality?

We could do that with canImport:

#if canImport(Accelerate)
import Accelerate
protocol PerformanceBuffer: AccelerateBuffer { /* ... */ }
extension PerformanceBuffer {
  // If the type-signatures don't match, implement AccelerateBuffer 
  // using PerformanceBuffer's methods.
}
#else
protocol PerformanceBuffer { /* ... */ }
#endif

func doThing(...) {
  #if canImport(Accelerate)
    doThingUsingAccelerate()
  #else
    doThingUsingCorePerformance()
  #endif
}
SusanDoggie commented 4 years ago
  1. You can make a subfolder inside of your module directory for the "raw" implementations. No need to make 2 separate modules.

I don't know should we divide the modules. Just like NumericsShims, I don't think we should implicitly import all the raw functions when people imports the Numerics module, and let people having a choice of importing the CorePerformance if they needed.

  1. The name "Performance" is a bit too generic. Might I suggest SignalProcessing or DigitalSignals?

I have no doubt about this.

  1. Should we maybe prefer to use Accelerate on platforms where it's available and offers equivalent functionality?

Because the Accelerate interface is not compatible with my algorithm, and I don't know how Apple implements it. So I do it in my way.

karwa commented 4 years ago

I don't know should we divide the modules. Just like NumericsShims, I don't think we should implicitly import all the raw functions when people imports the Numerics module, and let people having a choice of importing the CorePerformance if they needed.

NumericShims exists to import compiler built-ins which aren't otherwise accessible from Swift; it's for use within the numerics module, to implement things like generic math functions. It's not something consumers of the numerics module should be using directly, and it is not exported from the Numerics module.

If CorePerformance includes APIs which are generally useful to people, they should be exposed with proper, Swifty names and signatures (not names with underscores like _fft_zip).

I have no doubt about this.

Do you mean that you wish to stick with the name "Performance"? Do you think users will discover that easily?

Because the Accelerate interface is not compatible with my algorithm, and I don't know how Apple implements it. So I do it in my way.

Looking at the Accelerate vDSP.FFT API, they do appear incredibly similar. There are some small differences - Apple instantiates a type containing the log2(count) rather than calculating it on-the-fly, use a DSPSplitComplex type rather than asking for a stride parameter, and they have split forward and inverse transform functions. I don't see anything that is fundamentally incompatible.

It's up to you if you want to use Apple's API, or forward calls from your API to their one, or some blend of both. But I do think it is possible to express a common API and utilise Accelerate where it is available. @stephentyrone, what do you think?

SusanDoggie commented 4 years ago

NumericShims exists to import compiler built-ins which aren't otherwise accessible from Swift; it's for use within the numerics module, to implement things like generic math functions. It's not something consumers of the numerics module should be using directly, and it is not exported from the Numerics module.

If CorePerformance includes APIs which are generally useful to people, they should be exposed with proper, Swifty names and signatures (not names with underscores like _fft_zip).

Yes, i want a guideline for the naming. I think we don't want something like fftZip.

Do you mean that you wish to stick with the name "Performance"? Do you think users will discover that easily?

No, I mean I don't care about the name. If people choose a name for the module, I will change it.

Looking at the Accelerate vDSP.FFT API, they do appear incredibly similar. There are some small differences - Apple instantiates a type containing the log2(count) rather than calculating it on-the-fly, use a DSPSplitComplex type rather than asking for a stride parameter, and they have split forward and inverse transform functions. I don't see anything that is fundamentally incompatible.

Um...the most incompatible is that Accelerate requires FFTSetup, which is not needed by my algorithm. If we simply wrap the creation of FFTSetup in the transform functions, the performance loss is large.

https://github.com/Jounce/Surge/blob/e5375a62be5bb84e7422e6a213e491bfd18e11c3/Sources/Surge/Digital%20Signal%20Processing/FFT.swift