{"action":"created","issue":{"url":"https://api.github.com/repos/rgommers/pywt/issues/59","labels_url":"https://api.github.com/repos/rgommers/pywt/issues/59/labels{/name}","comments_url":"https://api.github.com/repos/rgommers/pywt/issues/59/comments","events_url":"https://api.github.com/repos/rgommers/pywt/issues/59/events","html_url":"https://github.com/rgommers/pywt/pull/59","id":90959195,"number":59,"title":"Refactor convolution.c.src","user":{"login":"kwohlfahrt","id":2422454,"avatar_url":"https://avatars.githubusercontent.com/u/2422454?v=3","gravatar_id":"","url":"https://api.github.com/users/kwohlfahrt","html_url":"https://github.com/kwohlfahrt","followers_url":"https://api.github.com/users/kwohlfahrt/followers","following_url":"https://api.github.com/users/kwohlfahrt/following{/other_user}","gists_url":"https://api.github.com/users/kwohlfahrt/gists{/gist_id}","starred_url":"https://api.github.com/users/kwohlfahrt/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kwohlfahrt/subscriptions","organizations_url":"https://api.github.com/users/kwohlfahrt/orgs","repos_url":"https://api.github.com/users/kwohlfahrt/repos","events_url":"https://api.github.com/users/kwohlfahrt/events{/privacy}","received_events_url":"https://api.github.com/users/kwohlfahrt/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":4,"created_at":"2015-06-25T13:07:58Z","updated_at":"2015-06-28T20:49:36Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/rgommers/pywt/pulls/59","html_url":"https://github.com/rgommers/pywt/pull/59","diff_url":"https://github.com/rgommers/pywt/pull/59.diff","patch_url":"https://github.com/rgommers/pywt/pull/59.patch"},"body":"Looking into `idwtn` I got somewhat confused by the internals of convolution.c.src. I decided to clean it up for my own benefit, and I think the result is somewhat cleaner (especially for `MODE_PERIODIZATION` cases).\r\n\r\nMajor changes are:\r\n- Both short (`F <= N`) and long (`F > N`) signals now share the same code\r\n  - There is now no allocation in convolution.c.src\r\n- Loop counters are not re-used throughout a function unless necessary\r\n  - requires -std=c99 for loop initial declarations\r\n\r\nMinor changes:\r\n- input arrays are restrict-qualified\r\n  - Allows loop vectorization with -ffast-math\r\n- Variables are const-qualified where possible\r\n- unsigned type used for indices\r\n\r\nQuestions:\r\n- Some lines marked FIXME/TODO are holdovers to match the original behaviour that I am not sure are correct?\r\n- To what extent is the C-api considered stable?\r\n  - Now that there is no allocation, it would be simple to re-define the convolution functions to be valid for all inputs (i.e. `F%2 != 0`). Size checking could be done in wt.c.src or _pywt.pyx, and they wouldn't have to worry about exceptions from C.\r\n  - Should output sizes be checked? They are currently not, but probably should be.\r\n\r\nI did rough measures of relative performance for both up-sampling and down-sampling convolutions, for signal lengths between 7 and 601, and filter lengths between 2 and 32. There were some changes both ways for different modes, though overall it is comparable or better in my opinion. Some examples are below.\r\n\r\nNote also that the structure of the loops would allow addition of OpenMP relatively cleanly (though IIRC there were objections last time this was raised re scipy policy).\r\n\r\nDown-sampling convolution performance is comparable. There are significant speed-ups for large N and F, especially `MODE_ZEROPAD`. This takes at best 0.4x as long as previously, for `N=601` and `F = 32` (the largest values tested). The worst change is `down-sampling_convolution` for `MODE_SMOOTH` and `N < F`. The worst result is for `N < 10` and `F = 32`, which takes 2.3x as long as previously. I expect this is because the short signal down-sampling convolution allocated a temporary buffer and saved the extension. If necessary, this could be implemented for all lengths of signal now.\r\n\r\nUp-sampling convolution performance is overall better. For `N < F`, there is generally an increase. `MODE_PERIODIC` shows the largest increase, taking 0.02x (yes, 0.02x reproducibly) as long as the original for `N=8` and `F=32`, and 0.73x as long as the original for `N=31` and `F=8`. The worst is `MODE_PERIODIZATION`, which takes 1.4x as long for `N=250` and `F=32`, and 0.7x as long for `N=7 and F=12`."},"comment":{"url":"https://api.github.com/repos/rgommers/pywt/issues/comments/116333192","html_url":"https://github.com/rgommers/pywt/pull/59#issuecomment-116333192","issue_url":"https://api.github.com/repos/rgommers/pywt/issues/59","id":116333192,"user":{"login":"rgommers","id":98330,"avatar_url":"https://avatars.githubusercontent.com/u/98330?v=3","gravatar_id":"","url":"https://api.github.com/users/rgommers","html_url":"https://github.com/rgommers","followers_url":"https://api.github.com/users/rgommers/followers","following_url":"https://api.github.com/users/rgommers/following{/other_user}","gists_url":"https://api.github.com/users/rgommers/gists{/gist_id}","starred_url":"https://api.github.com/users/rgommers/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rgommers/subscriptions","organizations_url":"https://api.github.com/users/rgommers/orgs","repos_url":"https://api.github.com/users/rgommers/repos","events_url":"https://api.github.com/users/rgommers/events{/privacy}","received_events_url":"https://api.github.com/users/rgommers/received_events","type":"User","site_admin":false},"created_at":"2015-06-28T20:49:36Z","updated_at":"2015-06-28T20:49:36Z","body":"From a quick browse, this looks quite good. A few initial responses:\r\n\r\n- There is no public C API for ``pywt``, so no need to worry about breaking anything there.\r\n- OpenMP isn't portable, so I'd stay away from it.\r\n- MSVC doesn't support all of C99, which may be an issue. There's also other compilers to worry about, like Clang and icc. So you'll want to stay away from adding gcc-specific flags I think. Adding an optional optimization is possible, adding a flag because otherwise the code doesn't compile is going to be very fragile.\r\n\r\n"}}