You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Leandro Ariel Pezzente (Created) (JIRA)" <ji...@apache.org> on 2012/02/13 02:48:59 UTC
[jira] [Created] (MATH-745) up to 5x Performance Improvement on
FasFourierTransformer.java by using a recursive iterative sumation Approach
up to 5x Performance Improvement on FasFourierTransformer.java by using a recursive iterative sumation Approach
---------------------------------------------------------------------------------------------------------------
Key: MATH-745
URL: https://issues.apache.org/jira/browse/MATH-745
Project: Commons Math
Issue Type: Improvement
Affects Versions: 3.0
Reporter: Leandro Ariel Pezzente
By swithinch form a loop iterative approach to a recursive iterative approach on fastFourierTransformer.java a Perfomance Improvement of up to 5x is gained.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Resolved] (MATH-745) up to 5x Performance Improvement on
FasFourierTransformer.java by using a recursive iterative sumation Approach
Posted by "Leandro Ariel Pezzente (Resolved) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-745?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Leandro Ariel Pezzente resolved MATH-745.
-----------------------------------------
Resolution: Cannot Reproduce
Test were invalid due to test being run at different processor load instances.
> up to 5x Performance Improvement on FasFourierTransformer.java by using a recursive iterative sumation Approach
> ---------------------------------------------------------------------------------------------------------------
>
> Key: MATH-745
> URL: https://issues.apache.org/jira/browse/MATH-745
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0
> Reporter: Leandro Ariel Pezzente
> Labels: FFT, Fast, Fourier, Transform
> Attachments: FastFourierTransformer.patch.txt
>
>
> By swithinch form a loop iterative approach to a recursive iterative approach on fastFourierTransformer.java a Perfomance Improvement of up to 5x is gained.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Issue Comment Edited] (MATH-745) up to 5x Performance
Improvement on FasFourierTransformer.java by using a recursive iterative
sumation Approach
Posted by "Thomas Neidhart (Issue Comment Edited) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-745?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13206867#comment-13206867 ]
Thomas Neidhart edited comment on MATH-745 at 2/13/12 1:30 PM:
---------------------------------------------------------------
I was curious to see if a recursion is really faster than a loop. The test results can be seen here:
fft (calls per timed block: 1000, timed blocks: 100, time unit: ms)
name time/call std error total time ratio difference
Loop 6.97587976e-02 1.15353985e-02 6.9759e+03 1.0000e+00 0.00000000e+00
Recursive 7.11088946e-02 5.04734785e-03 7.1109e+03 1.0194e+00 1.35009693e+02
The function being transformed is a simple sin.
was (Author: tn):
I was curious to see if a recursion is really faster than a loop. The test results can be seen here:
fft (calls per timed block: 1000, timed blocks: 100, time unit: ms)
name time/call std error total time ratio difference
Loop 6.97587976e-02 1.15353985e-02 6.9759e+03 1.0000e+00 0.00000000e+00
Recursive 7.11088946e-02 5.04734785e-03 7.1109e+03 1.0194e+00 1.35009693e+02
The function being transformed is sin(x).
> up to 5x Performance Improvement on FasFourierTransformer.java by using a recursive iterative sumation Approach
> ---------------------------------------------------------------------------------------------------------------
>
> Key: MATH-745
> URL: https://issues.apache.org/jira/browse/MATH-745
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0
> Reporter: Leandro Ariel Pezzente
> Labels: FFT, Fast, Fourier, Transform
> Attachments: FastFourierTransformer.patch.txt
>
>
> By swithinch form a loop iterative approach to a recursive iterative approach on fastFourierTransformer.java a Perfomance Improvement of up to 5x is gained.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-745) up to 5x Performance Improvement on
FasFourierTransformer.java by using a recursive iterative sumation Approach
Posted by "Bruce A Johnson (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-745?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13206865#comment-13206865 ]
Bruce A Johnson commented on MATH-745:
--------------------------------------
Just to be clear, is this 5x faster than the old implementation (pre Math-732), or after Math-732 (and thereby ~25x faster than the old)?
> up to 5x Performance Improvement on FasFourierTransformer.java by using a recursive iterative sumation Approach
> ---------------------------------------------------------------------------------------------------------------
>
> Key: MATH-745
> URL: https://issues.apache.org/jira/browse/MATH-745
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0
> Reporter: Leandro Ariel Pezzente
> Labels: FFT, Fast, Fourier, Transform
> Attachments: FastFourierTransformer.patch.txt
>
>
> By swithinch form a loop iterative approach to a recursive iterative approach on fastFourierTransformer.java a Perfomance Improvement of up to 5x is gained.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Issue Comment Edited] (MATH-745) up to 5x Performance
Improvement on FasFourierTransformer.java by using a recursive iterative
sumation Approach
Posted by "Sébastien Brisard (Issue Comment Edited JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-745?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13206922#comment-13206922 ]
Sébastien Brisard edited comment on MATH-745 at 2/13/12 3:54 PM:
-----------------------------------------------------------------
Thomas, have you checked how this scales with the data size? Otherwise, I can do it.
was (Author: celestin):
Thomas, have you checked how this scales with the data size.
> up to 5x Performance Improvement on FasFourierTransformer.java by using a recursive iterative sumation Approach
> ---------------------------------------------------------------------------------------------------------------
>
> Key: MATH-745
> URL: https://issues.apache.org/jira/browse/MATH-745
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0
> Reporter: Leandro Ariel Pezzente
> Labels: FFT, Fast, Fourier, Transform
> Attachments: FastFourierTransformer.patch.txt
>
>
> By swithinch form a loop iterative approach to a recursive iterative approach on fastFourierTransformer.java a Perfomance Improvement of up to 5x is gained.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MATH-745) up to 5x Performance Improvement on
FasFourierTransformer.java by using a recursive iterative sumation Approach
Posted by "Leandro Ariel Pezzente (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-745?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Leandro Ariel Pezzente updated MATH-745:
----------------------------------------
Attachment: FastFourierTransformer.patch.txt
patch uploadad
> up to 5x Performance Improvement on FasFourierTransformer.java by using a recursive iterative sumation Approach
> ---------------------------------------------------------------------------------------------------------------
>
> Key: MATH-745
> URL: https://issues.apache.org/jira/browse/MATH-745
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0
> Reporter: Leandro Ariel Pezzente
> Labels: FFT, Fast, Fourier, Transform
> Attachments: FastFourierTransformer.patch.txt
>
>
> By swithinch form a loop iterative approach to a recursive iterative approach on fastFourierTransformer.java a Perfomance Improvement of up to 5x is gained.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-745) up to 5x Performance Improvement on
FasFourierTransformer.java by using a recursive iterative sumation Approach
Posted by "Thomas Neidhart (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-745?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13206931#comment-13206931 ]
Thomas Neidhart commented on MATH-745:
--------------------------------------
I have tested with different values of sample points, showing always the same results: loop variant slightly faster. Having a N of > 2 ^13^ then leads to the expected StackOverflowException.
> up to 5x Performance Improvement on FasFourierTransformer.java by using a recursive iterative sumation Approach
> ---------------------------------------------------------------------------------------------------------------
>
> Key: MATH-745
> URL: https://issues.apache.org/jira/browse/MATH-745
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0
> Reporter: Leandro Ariel Pezzente
> Labels: FFT, Fast, Fourier, Transform
> Attachments: FastFourierTransformer.patch.txt
>
>
> By swithinch form a loop iterative approach to a recursive iterative approach on fastFourierTransformer.java a Perfomance Improvement of up to 5x is gained.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-745) up to 5x Performance Improvement on
FasFourierTransformer.java by using a recursive iterative sumation Approach
Posted by "Sébastien Brisard (Commented JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-745?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13206922#comment-13206922 ]
Sébastien Brisard commented on MATH-745:
----------------------------------------
Thomas, have you checked how this scales with the data size.
> up to 5x Performance Improvement on FasFourierTransformer.java by using a recursive iterative sumation Approach
> ---------------------------------------------------------------------------------------------------------------
>
> Key: MATH-745
> URL: https://issues.apache.org/jira/browse/MATH-745
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0
> Reporter: Leandro Ariel Pezzente
> Labels: FFT, Fast, Fourier, Transform
> Attachments: FastFourierTransformer.patch.txt
>
>
> By swithinch form a loop iterative approach to a recursive iterative approach on fastFourierTransformer.java a Perfomance Improvement of up to 5x is gained.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Issue Comment Edited] (MATH-745) up to 5x Performance
Improvement on FasFourierTransformer.java by using a recursive iterative
sumation Approach
Posted by "Thomas Neidhart (Issue Comment Edited) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-745?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13206867#comment-13206867 ]
Thomas Neidhart edited comment on MATH-745 at 2/13/12 1:30 PM:
---------------------------------------------------------------
I was curious to see if a recursion is really faster than a loop. The test results can be seen here:
{noformat}
fft (calls per timed block: 1000, timed blocks: 100, time unit: ms)
name time/call std error total time ratio difference
Loop 6.97587976e-02 1.15353985e-02 6.9759e+03 1.0000e+00 0.00000000e+00
Recursive 7.11088946e-02 5.04734785e-03 7.1109e+03 1.0194e+00 1.35009693e+02
{noformat}
The function being transformed is a simple sin.
was (Author: tn):
I was curious to see if a recursion is really faster than a loop. The test results can be seen here:
fft (calls per timed block: 1000, timed blocks: 100, time unit: ms)
name time/call std error total time ratio difference
Loop 6.97587976e-02 1.15353985e-02 6.9759e+03 1.0000e+00 0.00000000e+00
Recursive 7.11088946e-02 5.04734785e-03 7.1109e+03 1.0194e+00 1.35009693e+02
The function being transformed is a simple sin.
> up to 5x Performance Improvement on FasFourierTransformer.java by using a recursive iterative sumation Approach
> ---------------------------------------------------------------------------------------------------------------
>
> Key: MATH-745
> URL: https://issues.apache.org/jira/browse/MATH-745
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0
> Reporter: Leandro Ariel Pezzente
> Labels: FFT, Fast, Fourier, Transform
> Attachments: FastFourierTransformer.patch.txt
>
>
> By swithinch form a loop iterative approach to a recursive iterative approach on fastFourierTransformer.java a Perfomance Improvement of up to 5x is gained.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Closed] (MATH-745) up to 5x Performance Improvement on
FasFourierTransformer.java by using a recursive iterative sumation Approach
Posted by "Leandro Ariel Pezzente (Closed) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-745?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Leandro Ariel Pezzente closed MATH-745.
---------------------------------------
Issue Closed due to Perfomance Test being run in an inappropiatre way.
> up to 5x Performance Improvement on FasFourierTransformer.java by using a recursive iterative sumation Approach
> ---------------------------------------------------------------------------------------------------------------
>
> Key: MATH-745
> URL: https://issues.apache.org/jira/browse/MATH-745
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0
> Reporter: Leandro Ariel Pezzente
> Labels: FFT, Fast, Fourier, Transform
> Attachments: FastFourierTransformer.patch.txt
>
>
> By swithinch form a loop iterative approach to a recursive iterative approach on fastFourierTransformer.java a Perfomance Improvement of up to 5x is gained.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-745) up to 5x Performance Improvement on
FasFourierTransformer.java by using a recursive iterative sumation Approach
Posted by "Thomas Neidhart (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-745?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13206867#comment-13206867 ]
Thomas Neidhart commented on MATH-745:
--------------------------------------
I was curious to see if a recursion is really faster than a loop. The test results can be seen here:
fft (calls per timed block: 1000, timed blocks: 100, time unit: ms)
name time/call std error total time ratio difference
Loop 6.97587976e-02 1.15353985e-02 6.9759e+03 1.0000e+00 0.00000000e+00
Recursive 7.11088946e-02 5.04734785e-03 7.1109e+03 1.0194e+00 1.35009693e+02
The function being transformed is sin(x).
> up to 5x Performance Improvement on FasFourierTransformer.java by using a recursive iterative sumation Approach
> ---------------------------------------------------------------------------------------------------------------
>
> Key: MATH-745
> URL: https://issues.apache.org/jira/browse/MATH-745
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0
> Reporter: Leandro Ariel Pezzente
> Labels: FFT, Fast, Fourier, Transform
> Attachments: FastFourierTransformer.patch.txt
>
>
> By swithinch form a loop iterative approach to a recursive iterative approach on fastFourierTransformer.java a Perfomance Improvement of up to 5x is gained.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-745) up to 5x Performance Improvement on
FasFourierTransformer.java by using a recursive iterative sumation Approach
Posted by "Sebb (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-745?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13206817#comment-13206817 ]
Sebb commented on MATH-745:
---------------------------
Also, are there any guarantees that the recursive approach cannot cause stack overflow, even with pathological input?
> up to 5x Performance Improvement on FasFourierTransformer.java by using a recursive iterative sumation Approach
> ---------------------------------------------------------------------------------------------------------------
>
> Key: MATH-745
> URL: https://issues.apache.org/jira/browse/MATH-745
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0
> Reporter: Leandro Ariel Pezzente
> Labels: FFT, Fast, Fourier, Transform
> Attachments: FastFourierTransformer.patch.txt
>
>
> By swithinch form a loop iterative approach to a recursive iterative approach on fastFourierTransformer.java a Perfomance Improvement of up to 5x is gained.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-745) up to 5x Performance Improvement on
FasFourierTransformer.java by using a recursive iterative sumation Approach
Posted by "Gilles (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-745?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13206808#comment-13206808 ]
Gilles commented on MATH-745:
-----------------------------
Would it be possible to use our little benchmark utility ("PerfTestUtils" in the "test" section of the source repository)? There are examples of usage in "o.a.c.m.util.FastMathTestPerformance").
You could run it once before the changes you propose and once after, and post the 2 tables here. Thanks!
> up to 5x Performance Improvement on FasFourierTransformer.java by using a recursive iterative sumation Approach
> ---------------------------------------------------------------------------------------------------------------
>
> Key: MATH-745
> URL: https://issues.apache.org/jira/browse/MATH-745
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0
> Reporter: Leandro Ariel Pezzente
> Labels: FFT, Fast, Fourier, Transform
> Attachments: FastFourierTransformer.patch.txt
>
>
> By swithinch form a loop iterative approach to a recursive iterative approach on fastFourierTransformer.java a Perfomance Improvement of up to 5x is gained.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-745) up to 5x Performance Improvement on
FasFourierTransformer.java by using a recursive iterative sumation Approach
Posted by "Sébastien Brisard (Commented JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-745?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13206824#comment-13206824 ]
Sébastien Brisard commented on MATH-745:
----------------------------------------
I worry about the exact same issue. Leandro, please test very large data sets.
If memory becomes an issue, we could have *two* implementations of the FFT, one being less robust than the other (I would certainly not discard a 5x speed up...).
> up to 5x Performance Improvement on FasFourierTransformer.java by using a recursive iterative sumation Approach
> ---------------------------------------------------------------------------------------------------------------
>
> Key: MATH-745
> URL: https://issues.apache.org/jira/browse/MATH-745
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0
> Reporter: Leandro Ariel Pezzente
> Labels: FFT, Fast, Fourier, Transform
> Attachments: FastFourierTransformer.patch.txt
>
>
> By swithinch form a loop iterative approach to a recursive iterative approach on fastFourierTransformer.java a Perfomance Improvement of up to 5x is gained.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-745) up to 5x Performance Improvement on
FasFourierTransformer.java by using a recursive iterative sumation Approach
Posted by "Leandro Ariel Pezzente (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-745?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13207242#comment-13207242 ]
Leandro Ariel Pezzente commented on MATH-745:
---------------------------------------------
Hmmm ... maybe i made a mistake. I probably run both test at different processor load instances. I should probably resolve this as a Won't Fix and stop trying until I learn how to this properly.
> up to 5x Performance Improvement on FasFourierTransformer.java by using a recursive iterative sumation Approach
> ---------------------------------------------------------------------------------------------------------------
>
> Key: MATH-745
> URL: https://issues.apache.org/jira/browse/MATH-745
> Project: Commons Math
> Issue Type: Improvement
> Affects Versions: 3.0
> Reporter: Leandro Ariel Pezzente
> Labels: FFT, Fast, Fourier, Transform
> Attachments: FastFourierTransformer.patch.txt
>
>
> By swithinch form a loop iterative approach to a recursive iterative approach on fastFourierTransformer.java a Perfomance Improvement of up to 5x is gained.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira