`Complex` needs more specialization.

[TravisWhitaker]

The base module Data.Complex includes specializations of most numerical functions and instances for Complex Double and sometimes Complex Float. The current set omits three sorts of specializations that may have quite severe negative performance impacts on downstream code:

1. Many functions have specializations for Complex Double only, while downstream code would benefit from Complex Float as well.
2. The Storable instance has no specializations. This is problematic for a variety of downstream applications, e.g. this observed ~100x slow down of operations on storable vectors containing Complex Doubles: Complex somehow destroys the performance of operations on storable vectors. vector#558
3. It is quite common for programs manipulating complex numbers to deal with fixed width integer types. Complex Int8 and Complex Int16 specializations would be very helpful (Complex Int32 and Complex Int64 perhaps less so).

Therefore I propose that base:

1. Add SPECIALISE ... Complex Float to the set of specialized functions and instances.
2. Add the Storable instance to the set of specialized functions and instances.
3. Add SPECIALISE ... Complex Int{8,16} to the set of specialized functions and instances.
4. Add SPECIALISE ... ComplexInt{32,64} to the set of specialized functions and instances if anyone can find a person or program who cares for them to be added.

[noughtmare]

Can you give examples of programs that use Complex Int8 and Complex Int16? I've never seen that and am inclined towards not including those specializations. I'm even a bit hesitant about Complex Float, is it really that common for Double to be unsuitable?

I'd also like to know how many functions this will affect. Will this significantly affect the binary size of the base library?

[TravisWhitaker]

All of the use cases I know of are related to signal processing, but they are nonetheless numerous.

• librtlsdr: Software library for interfacing with a common class of commodity radio receivers that all have 8-bit DACs and ADCs (Complex Int8). There are bindings on Hackage.
• libuhd: Software library for interfacing with NI's laboratory grade USRP line of SDRs. Supports streams of samples in Complex Int{8,16}, Complex Float, and Complex Double.
• FFTW: Extremely popular numerical library implementing DFT/DCT and related transforms and their inverses. It supports sample buffers of both Complex Double and Complex Float (I have a branch of vector-fftw adding support for Complex Float that I haven't gotten around to merging yet).
• libhackrf: Software library for interfacing with a popular line of radio devices that all have 8-bit DACs and ADCs (Complex Int8).
• GNU Radio: Widely used software transceiver development framework, the default gr_complex sample type is a Complex Float.
• libiio: Software library for interfacing with ADI's line of devices, including many radio devices. Supports streams of samples in Complex Int{8,16}, Complex Float, and Complex Double.
• SigMF: Common interchange format for complex-valued signal data. Supports all types mentioned above, and also includes Complex Word{8,16,32,64} (although I've never seen those formats used by any actual software ever).
• 3dB Labs' Sceptre: Proprietary signal analysis software. Supports streams of samples in Complex Int{8,16}, Complex Float, and Complex Double.
• Aaronia RTSA: Proprietary signal analysis software. Supports streams of samples in Complex Int{8,16}, Complex Float, and Complex Double.
• OmniSIG: Proprietary RF machine learning software framework. Supports streams of samples in Complex Int{8,16}, Complex Float, and Complex Double.
• Viavi Signal Workshop: Proprietary signal analysis software. Supports streams of samples in Complex Int{8,16}, Complex Float, and Complex Double.
• SDR++: Open source spectrum monitoring and software transceiver. Supports streams of samples in Complex Int{8,16}, Complex Float, and Complex Double.
• Gqrx: Open source spectrum monitoring and software transceiver. Supports streams of samples in Complex Int{8,16}, Complex Float, and Complex Double.
• SoapySDR: Multi vendor SDR IO abstraction library. Supports streams of samples in Complex Int{8,16}, Complex Float, and Complex Double.
• liquid-dsp Library of reference implementations of various DSP algorithms. Supports streams of samples in Complex Float.

Values of type Complex Float and Complex Int{8,16} and operations on them are important for Haskell code that interfaces with these kinds of systems. Honestly I'm extremely surprised that I didn't notice the lack of these specializations until very recently.

The practical reason for using these narrower types is to avoid wasting space. DACs and ADCs of width 8, 12, 14, and/or 16 are extremely common, and using Doubles to operate on the resulting values wastes memory, bandwidth, and precision.

For example, this popular lab grade SDR has a 12 bit DAC and ADC. Its maximum sample rate is 56 MHz.

Type	Rate (MB/sec)	Wasted bits / sample
Complex Double	896	104
Complex Float	448	40
Complex Int16	224	8
Complex Int8	112	4 bits dynamic range lost

The change I'm proposing would impact all currently specialized functions and instances in the Data.Complex module, along with the Storable instance defined in that module. I have not yet measured the size increase in release artifacts with this change, but the only impact should be the .o and .hi for the Data.Complex module growing a bit. If base does not include these specializations, what is the least bad way for downstream code to recover the expected performance?

[minoki]

Just out of curiosity, are Complex Int8 and Complex Int16 useful in Haskell? The standard Num (Complex a) has RealFloat a as a superclass, so there is no Num (Complex Int8). Maybe you use custom numeric classes?

[TravisWhitaker]

Requiring magnitude is one of the many tragedies of the way Num works. I don't think there are any ways to fix the situation that aren't practically useless cute tricks. This means that Num is not included in the set of specializable classes for parts 3 and 4 of what I'm proposing here.

However, without the other specializations I'm proposing, you won't reliably get good code for converting a buffer of e.g. Complex Int16 to a type that does have a Num instance. Something like Data.Vector.Storable.map (fmap fromIntegral) is susceptible to the same problems I mentioned.

[TravisWhitaker]

Shall I open an MR on GHC GitLab?

[hasufell]

Shall I open an MR on GHC GitLab?

Yes, please