Articles on peterbell10's Blog

Final week

PeterBell10@live.co.uk (peterbell10) — Tue, 27 Aug 2019 01:17:48 +0000

What did you do this week?

With the coding period coming to an end, this week I've wound down coding and focused on writing up my final work submission. This means I've been looking back at the work I've been doing; reading through my old PRs and comparing against my project's original goals.

My original proposal focused solely on adding backend support to scipy.fftpack, yet the scope of my work over the past 3 months was not limited there. The resulting scipy.fft subpackage is a complete rewrite of scipy.fftpack from the ground-up featuring not just the backend system but also an improved interface and the replacement of FFTPACK with pypocketfft under the hood.

My contributions were also not just limited to SciPy; I've also made contributed to pypocketfft, uarray, pyFFTW and cupy. I've really enjoyed getting to collaborate with this range of open source projects and am very pleased with how my work has gone over GSoC. I would thoroughly recommend that any students interested in open source software should consider doing a project themself.

Working towards pre-planned transforms

PeterBell10@live.co.uk (peterbell10) — Tue, 20 Aug 2019 01:44:27 +0000

What did you do this week?

The main feature I've been working on this week has been adding pre-planned transforms to pypocketfft in (pypocketfft!28). This will allow users to speed-up cases where many transforms of the same shape are done, without needing to rely on any internal caches. This gives the users a small performance improvement in pypocketfft but adding this to the scipy.fft interface will also allow other backends to benefit. e.g. pyFFTW can have a significantly more expensive planning phase.

Plans have now been added into the c++ interface of pypocketfft but I have still got to expose these in the python interface. Additionally, I've made a number of other contributions in several other places:

Refactored the real transform tests to use pytest and to test all the transforms in long double precision as well (scipy#10669)
Fixed a race condition in my custom threadpool code that was causing crashes on macOS (pypocketfft!27)
Added benchmarks to my multithreading PR (scipy#10614)
Opened an issue in mkl_fft about adding a scipy.fft interface (mkl_fft#42). Unfortunately, mkl_ffl doesn't seem to be very active and the issue hasn't received any response yet.
Fixed a compile warning in uarray (uarray#195)

What is coming up next?

The coding period has officially ended and it's now time to "submit the code". Most of my code has already been merged into the SciPy master branch so this will just involve writing a summary of my work over the whole GSoC project.

I would also like to finish up the pre-planned transform code but it's likely too late to get this merged in time for the evaluation.

Did you get stuck anywhere?

Fixing the race condition in pypocketfft was quite challenging. The only symptom was a SEGFAULT that occurred only rarely and only on macOS, a platform which I don't use and so couldn't reproduce the issue locally. This made diagnosing and solving the issue very tricky. Thankfully, Martin (pypocketfft's author) had access to apple hardware and was eventually able to give me enough details that I found an issue from another project that had run into almost exactly the same issue.

Adding multithreading to scipy.fft

PeterBell10@live.co.uk (peterbell10) — Mon, 12 Aug 2019 22:16:00 +0000

What did you do this week?

Fixed a small inconsistency with the numpy.fft API when the transform shape is given but not the axes (scipy#10594)
Gotten my CuPy PR into a review ready state. Fixing uarray backend support (scipy#2355)
Migrated pypocketfft from OpenMP to a custom thread-pool that I wrote to handle fork on POSIX systems. This addresses all the main concerns with adding OpenMP into SciPy (pypocketfft!23, pypocketfft!24)
Using the updated pypocketfft, I was then able to open a PR adding multithreading support to the scipy.fft API (scipy#10614)

What is coming up next?

- Create, or at least open issue for, a mkl-fft backend
- Expand the scipy.fft tutorial to include installing and using new FFT backends

There are also a number of minor features that could be added to pypocketfft such as shape changing transforms or pre-planned transforms. Though at this late stage in the project, my focus is on polishing the current feature set.

Did you get stuck anywhere?

No significant blockers this week.

CuPy backend and pypocketfft cleanup

PeterBell10@live.co.uk (peterbell10) — Tue, 06 Aug 2019 01:16:02 +0000

What did you do this week?

I have opened a PR on cupy adding a scipy.fft backend
Fixed a few small incompatibilities with the numpy.fft interface
Updated next_fast_len, a utility function to find the fastest lengths for computing the FFT (pypocketfft!17, scipy#10570)
Various clean-ups and refactoring of pypocketfft's multi-dimensional transform functions (pypocketfft!16, pypocketfft!20)
Restarted a discussions about use of OpenMP in SciPy. pypocketfft already supports OpenMP for parallelising transforms over multidimensional arrays, however there are a number of issues preventing SciPy from building with this feature enabled.

What is coming up next?

Replace OpenMP in pypocketfft with a custom thread-pool. The discussions on SciPy-dev have suggested that OpenMP isn't going to be a suitable solution so I will attempt to replace it.
Finishing up my CuPy backend PR. It is mostly completed but needs a few more tests.
Implement shape-changing transforms in pypocketfft.

Did you get stuck anywhere?

I found it quite difficult to get cuda and CuPy working properly on my computer and still occasionally have problems with it stopping recognising my cuda device. However, it's at least functional now if not quite perfect.

So long, FFTPACK

PeterBell10@live.co.uk (peterbell10) — Mon, 29 Jul 2019 15:29:16 +0000

What did you do this week?

Perhaps the most significant task this week was completely removing the fortran FFTPACK code from SciPy and rewriting scipy.fftpack using scipy.fft's pocketfft backend. This drastically simplifies the code with a diff of -8,856 lines of code.

I've also made a number of smaller improvements to scipy.fft as well as a significant performance improvement to scipy.signal.fftconvolve.

The first scipy.fft backend has also been created after my pyFFTW PR was merged this week. This means that SciPy users can accelerate their FFT transforms with all of pyFFTW's features using nothing more than a few function calls.

What is coming up next?

Adding a CuPy backend for scipy.fft
Implementing efficient shape-changing transforms in pypocketfft
Writing tests for the pyFFTW real-to-real transforms PR
Adding the ability to query active backends for uarray

Did you get stuck anywhere?

No blockers this week.

Backend support merged

PeterBell10@live.co.uk (peterbell10) — Mon, 22 Jul 2019 12:51:49 +0000

What did you do this week?

This has been a very exciting week for me, with lots of progress made on my GSoC project. For the past couple of months I've been working on adding the new scipy.fft module which supercedes the existing scipy.fftpack submodule and adds a range of new features and interface improvements. Chief among these planned features was a backend system, allowing users to install their own fft libraries as implementations for the scipy.fft interface.

I'm pleased to say that this week, my backend PR was merged into master. scipy.fft can now be implemented by any backend supporting the uarray protocol and provides a range of ways for the user to control their installed backends [1]. Around the same time, it was also announced that I've officially been accepted into the scipy core developers along with one of my mentors - Greg.

But even with my projects main goals out of the way, there are still a number of improvements and stretch goals that I've been working on:

continued work on a pyFFTW backend which should be merged soon (pyFFTW#269)
improved normalization of idct/idst which is inconsistent in scipy.fftpack (scipy#10470)
improved the performance of the n-dimensional FFT interface (scipy#10490)
a new PR wrapping pypocketfft's new sine and cosine transforms (DCT & DST) (scipy#10493)

What is coming up next?

With the DCT and DST transforms now in pypocketfft, the scipy.fft submodule will no longer depend on scipy.fftpack for any of it's transforms. So, it should be time to flip the dependecy on its head and remove all of the old fortran fftpack code, replacing it with a very thin wrapper around scipy.fft.

I can also work on one of the main stretch goals for this project which was finializing the addition of DCT and DST wrappers to pyFFTW. There has been a PR for this on pyFFTW for many years (pyFFTW#95) but they have lacked the man-power to finally finish it off and merge. Similar to pypocketfft, these real transforms were the
main feature missing from pyFFTW's interfaces.

Did you get stuck anywhere?

No blockers this week.

For fork's sake - Fixing multiprocessing issues

PeterBell10@live.co.uk (peterbell10) — Mon, 15 Jul 2019 12:42:59 +0000

What did you do this week?

It was also reported that scipy.fft does not interact well with python's multiprocessing library. I was able to track down the issue and resolve it within a few hours, adding a unit test to ensure this wouldn't be broken again. However, when I went to update my uarray PR to use the new fast C++ version, the test started to fail. It turns out, the uarray multimethod objects needed to be pickleable in a very specific way that mimicks the behaviour of python Function types. Thankfully, after applying this fix the issue was resolved.

I've also this week:

added Hermitian symmetric transforms to scipy.fft (merged in scipy#10425)
added scipy.fft to the 1.4.0 release notes
updated my PR adding uarray support to scipy.fft
started work on adding a `scipy.fft` compatible interface to pyfftw in pyFFTW#269. This will be one of the first useful backend implementations for the new backend system.

What is coming up next?

The backend system PR is set to be merged very soon so I should be able to focus on adding the uarray protocol to pyfftw and possibly contributing compatible backends to other FFT libraries.

I can also work on pre-planned transforms.

Did you get stuck anywhere?

The multiprocessing incompatibilities posed an unexpected challange but I was able to work though the problems alright.

Improving uarray performance

PeterBell10@live.co.uk (peterbell10) — Mon, 08 Jul 2019 13:51:16 +0000

What did you do this week?

I have been focused on my uarray PR (uarray#1780). uarray defines a protocol for dispatching function calls to multiple different backend implentations. In my PR, I've been reimplementing the core function dispatch mechanism in C++ using the Python C-API. This week I've moved the backend registration system in to C++ which means the protocol is now 100% C++. This has brought the overhead down from ~5 us per function call to just ~700 ns or about 10 times more than a normal python function call. This overhead was one of the main blockers for the adoption of uarray so is very nice to see it come down.

I've also updated the vendored version of pypocketfft in scipy#10393. This new version includes a small cache for the FFT "twiddle factors" which I helped implement. This improves benchmarks by ~20% in most cases or as much as 60% for some input sizes.

What is coming up next?

My uarray PR has already been merged over the weekend so I can update my scipy.fft code and update the benchmarks there. I also plan on using the new version of pypocketfft to add support for Hermitian FFTs (like numpy's hfft). This would make scipy.fft a complete replacement for numpy.fft's functionality.

I can also work on adding pre-planned transforms to the scipy.fft interface. This would also require pocketfft's plan cacheing much more flexible so I expect we can add user config options to our automatic plan cacheing.

Did you get stuck anywhere?

No significan blockers this week.

scipy.fft has been merged!

PeterBell10@live.co.uk (peterbell10) — Mon, 01 Jul 2019 12:59:42 +0000

What did you do this week?

My PR for scipy.fft has been merged into SciPy's master branch and is now slated for release in version 1.4. I've been doing some follow-up PRs responding to some late feedback with follow-up PRs, mostly focused on documentation.

I've also started learning the Python C-API and written a proof of concept implementation of uarray's __ua_function__ protocol in C++. It still relies on some python code which is slowing it down but even still I've measured around a 2x reduction in function call overhead.

What is coming up next?

Now that scipy.fft has been merged into SciPy, I can open a new draft PR with the uarray code. This should allow for more feedback from the SciPy community and we can move towards getting backend support into scipy.fft.
While that is ongoing I can continue to work on my C++ implementation of uarray to move more of it into native code and bring down the overhead further.

pypocketfft has also just released an update with a new interface that should allow for a nice refactoring of the scipy.fft code.

Did you get stuck anywhere?

I spent a lot of my time trying to debug some segfaults that were happening in uarray's test suite. I assumed the issue must be in my C++ code since I was unfamiliar with the Python C-API. However, after a lot of investigation the bugs turned out to be in NumPy and Dask, not my code.

Fourth Weekly Check-in

PeterBell10@live.co.uk (peterbell10) — Mon, 24 Jun 2019 00:35:32 +0000

What did you do this week?

My main scipy.fft PR is now very close to being merged and so I've been responding to some final review comments and making minor tweaks. Otherwise, I'm keeping the changes minimal to give it a chance to be reviewed fully.

I've also been collaborating with the author of the pypocketfft library: many of the changes I made for my PR have now been merged into the upstream repo. I've also been having discussions with him about improving the API such as adding real-to-complex inverse FFTs and a cache for FFT plans to improve performace of repeated transforms. These have already been prototyped and show promising results.

On the backend front, I've been actively contributing to uarray. I've been working with the maintainer to solidify the protocol, as well as contributing a new feature to remove default-valued positional arguments. It's currently looking like the performance overhead of uarray is the biggest hurdle so I've been benchmarking the overhead involved and discussing how to mitigate that.

What is coming up next?

I plan to rewrite the core of the uarray using the python C API to try and bring down the overhead to a more acceptable level. This would be my first time using the C API, so progress may be slow at first but since this is key to the backend system's performance, it should be well worth the effort.

Once my first PR is merged, I can also open a new PR which updates to the latest version of pypocketfft which has a reworked API and also includes many of the features I added for use in SciPy. Updating now should also make it easier to maintain in future since it will reduce the size of the patch added over the library.

Did you get stuck anywhere?

I haven't had any real blockers this week and I think good progress has been made.

Third Weekly Check-in

PeterBell10@live.co.uk (peterbell10) — Mon, 17 Jun 2019 00:15:17 +0000

What did you do this week?

I started off looking into uarray, a library for multi-method dispatch for different backends. I created a working prototype for uarray support in scipy.fft and used this to start benchmarking the overheads involved. I've also been looking into it's design and had online discussions with one of the authors.

I also made some requested changes to my scipy.fft pull-request, including updating the tutorials and benchmark suite. This revealed some serious performance regressions for 1D FFTs, as compared with scipy.fftpack. So, I deverted my attention to resolving these issues which saw over 10x improvement for small FFTs.

What is coming up next?

I need to evaluate the uarray aproach in comparison to my custom backend solution that I implemented last week. Of particular interest is the performance overhead which will need to be compared and possibly optimised. There are also a number of design choices that differ between uarray and my custom solution which I will need to reconsider and discuss on the mailing list.

Did you get stuck anywhere?

No significant blockers, although the work on optimising for 1D FFTs did take time away from the backend work that I had planned to focusing on.

Second Weekly Check-in

PeterBell10@live.co.uk (peterbell10) — Sun, 09 Jun 2019 19:47:22 +0000

What did you do this week?

I have been working on my pull request to add scipy.fft. This included:

Investigating and fixing test failures
Adding an optimized general purpose FFT for real input
Writing documentation
Solving build issues

I've also created a working prototype backend system, with tests for the basic functionality of switching between backends and calling functions.

What is coming up next?

I will hopefully start to get reviews for my open pull request and can respond to feedback. I'll also continue to work on the backend system by expanding my current prototype and creating a parallel implementation using uarray which implements a similar backend system. This will be used to open a discussion about whether or not uarray is suitable and ready to be deployed within SciPy.

There are also a number of improvements that can be made to the general state of FFTs within SciPy. For example, scipy.fftpack can be made to use the faster PocketFFT implementation and PocketFFT itself can be expanded to include the sine and cosine transforms that are in fftpack.

Did you get stuck anywhere?

SciPy imports most of the NumPy API into it's own namespace. In particular, I discovered that numpy.fft.fft is imported as scipy.fft; conflicting with my new scipy.fft module. This will hopefully be deprecated and removed in a future version of SciPy but for the time being I've had to use a workaround for the issue. By overriding the module's __class__, we can make the scipy.fft module callable as if it were a function. This works, but has some unfortunate side effects, one of which was thoroughly confusing the documentation generator (sphinx) which silently ignored the whole scipy.fft module.

This whole tangle took a while to work out but I got there in the end.

First Weekly Check-in

PeterBell10@live.co.uk (peterbell10) — Sun, 02 Jun 2019 21:38:38 +0000

What did you do this week?

I have been working towards a minimum viable product for the scipy.fft submodule. This involved writing a wrapper around pypocketfft to satisfy the numpy.fft interface, as well as integrating pypocketfft into SciPy's build system. I have opened a draft PR in which all of numpy's fft tests are passing and all but one of the fftpack tests are passing.

What is coming up next?

The draft PR needs to be polished to the point where it is review ready:

Some small precision issues need to be resolved
Documentation needs to be written
fftpack had various optimisations for real input which need to be reimplemented with pocketfft

I can also begin work on the backend system:

mechanism for installing a backend
configuration API to give users more control over each backend

Did you get stuck anywhere?

I initially had a lot of trouble getting the build system to work. Any attempt to add or modify scipy submodules were causing build failures in completely unrelated parts of SciPy. I was only able to resolve this after reinstalling my entire python environment. After solving that, I had no major blockers.

Hello World!

PeterBell10@live.co.uk (peterbell10) — Tue, 28 May 2019 18:43:33 +0000

Hello, my name is Peter from the UK where I'm studing computational physics. I've used scipy a lot throughout my degree and through my participation in GSoC, I hope to return the favour! Over the summer I'll be working to enhance scipy's fast-fourier transform (fft) library. This will include the ability for users to supply their own implementations at run time.

Initially, this was just going to be a new backend system for the existing module scipy.fftpack. Over the past few weeks, I've already had lots of great discussion with the community; both on the mailing list (SciPy-Dev) and on GitHub in a related issue. From this discussion, the project has now evolved into creating a new module scipy.fft which will now also have:

support for multiple backends
default to using pocketfft for improved performance and accuray
an interface that matches better with numpy.fft

The next steps will be to draft up the interface to scipy.fft with the new default implementation. This will no doubt be iterated on in a pull request on github. Once that gets merged, I should be in a good place to start implementing support for different backends.