GSoC 2019 - Work Submission

Peter Bell

For the past 3 months I have been contributing to SciPy for my Google Summer of Code project “Revamp scipy.fftpack”. As originally stated, the main goal of this project has been to: “design and implement a backend interface which will allow different libraries to be called underneath the scipy.fftpack interface.” However, from discussions in the Community Bonding period, this project has grown into a new subpackage scipy.fft that is a complete rewrite of scipy.fftpack from the ground-up. scipy.fft features a new improved interface, makes use of a new FFT implementation and of course features the backend system discussed in my original proposal.

My most significant work on scipy.fft has been split over 4 different SciPy pull-requests (PRs), with many smaller SciPy PRs and contributions to other projects happening in-between. The first of these was merged in scipy#10238. This PR defines the scipy.fft interface and integrates the vendored pypocketfft library to implement the FFTs.^[1] As part of this I also improved pypocketfft itself by changing the interface for transform normalisation and adding a complex FFT that is optimized for real input arrays. Here my edits to pypocketfft are separated into scipychanges.patch and scipy_features.h but in future pull-requests I contributed to pypocketfft directly so that updating pypocketfft within SciPy was made much simpler.

The second major PR was scipy#10383 which added backend support to scipy.fft. This is based on the uarray project which defines a protocol for dispatching function calls to different backends and provides a python library for creating uarray functions (multimethods). As part of this work I made several contributions to uarray itself (list here), the most significant of which was a complete rewrite of the uarray function call protocol into C++ using the python C-API. Bringing the function call overhead down by an order of magnitude to ~700ns per function call from ~5us. This change was merged as uarray#170. Related to this work was two scipy.fft backends that I have contributed to other FFT projects in pyFFTW#269 and cupy#2355.

Around the same time that my backend PR was merged, Martin Reinecke of pypocketfft informed me that he had expanded his library to include not just fourier transforms but also sine and cosine transforms. This lead to scipy#10493

in which I migrated scipy.fft over to these new transforms instead of the old FFTPACK transforms. With this, scipy.fft became a complete replacement for FFTPACK and I submitted scipy#10507 which both updated scipy.fftpack to remove the old fortran code entirely and updated scipy.fft to be completely independent of scipy.fftpack.

With my main project’s goals met, I also had time to work on a number of other enhancements to scipy.fft. For example, in scipy#10570 I replaced the next_fast_len implementation with a C++ version that makes use of a better search algorithm (pypocketfft!17) and takes into account the additional prime radices that are supported by the pypocketfft transforms. I have also worked on adding multi-threading to scipy.fft by contributing a custom thread-pool in pypocketfft!23. Support for this is added to SciPy in scipy#10614 which has not yet been merged.

Acknowledgements

Thanks to the SciPy community, especially my mentors Eric and Greg, for all their help and discussion surrounding the project. To Martin Reinecke for developing pypocketfft and being very responsive to suggestions and merge-requests. To Hameer Abbasi for his work on uarray. And finally to Google for running the GSoC program.

Summary of PRs

SciPy

• Adding scipy.fft based on the pypocketfft library (scipy#10238)
• A prototype backend system that was much simpler than the uarray solution that we went with in the end (peterbell10/scipy#1) [Closed]
• The final uarray-based backend system (scipy#10383)
• Synchronising the scipy.fft implementation to the advances in pypocketfft’s interface (scipy#10393)
• Adding hermitian-symmetric transforms to scipy.fft (scipy#10425)
• Fixing normalisation inconsistencies in the scipy.fft interface that were inherited from scipy.fftpack (scipy#10470)
• Improving performance of _init_nd_shape_and_axes (scipy#10490, scipy#10518)
• Using pypocketfft’s DCT and DST in the scipy.fft interface (scipy#10493)
• Removing the fortran FFTPACK entirely and migrating scipy.fftpack to use pypocketfft as wrapped in scipy.fft (scipy#10507)
• Adding thread-pool based multithreading support to the scipy.fft interface (scipy#10614) [Not yet merged]
• Refactoring and updating the tests for real transforms (scipy#10669)
• Release notes related to the new scipy.fft module were written for the upcoming 1.4.0 release of SciPy (https://github.com/scipy/scipy/wiki/Release-note-entries-for-SciPy-1.4.0#scipyfft-added)

uarray

• Canonicalization of positional arguments (uarray#168)
• Investigation into a kwarg-only calling convention (uarray#167) [Closed]
• Reimplementing uarray function calls in C++ (uarray#170)
• Adding pickle and multiprocessing support to uarray._Function (uarray#174, uarray#176)

pypocketfft

• Martin manually merged much of my code from scipychanges.patch into pypocketfft with his own modifications.
• Added an LRU eviction policy to pypocketfft’s plan cache (pypocketfft!11)
• Refactoring the multi-dimensional transform layer (pypocketfft!16, pypocketfft!20)
• Improvements to the good_size algorithm and exporting to python (pypocketfft!17)
• Implementing a custom thread-pool to replace use of OpenMP (pypocketfft!23, pypocketfft!24, pypocketfft!27)
• Expanding the custom sincospi implementation for use in discrete sine and cosine transforms (pypocketfft!22)
• Adding pre-planned transforms (pypocketfft!28) [Incomplete]

pyFFTW

• A scipy.fft interface that supports use as a backend (pyFFTW#269, pyFFTW#273)

cupy

• Adding scipy.fft to cupyx.scipy with backend support (cupy#2355) [Not yet merged]