[jira] [Commented] (MATH-732) Major Speed Improvement to 1D Discrete Fourier Transform (approximately 5x-9x improvement). Preserved public API 100%. Removed unnecessary use of instance variables and i
[ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13205558#comment-13205558 ] Kurt Ostfeld commented on MATH-732: --- Just checked the latest version from SVN. These changes look excellent. > Major Speed Improvement to 1D Discrete Fourier Transform (approximately 5x-9x > improvement). Preserved public API 100%. Removed unnecessary use of instance > variables and instance state. > > > Key: MATH-732 > URL: https://issues.apache.org/jira/browse/MATH-732 > Project: Commons Math > Issue Type: Improvement >Affects Versions: 3.0 >Reporter: Kurt Ostfeld >Assignee: Sébastien Brisard > Labels: api, perfomance > Fix For: 3.0 > > Attachments: DFTPerformanceWithPatch.png, > DFTPerformanceWithoutPatch.png, FastFourierTransformer.java, > FastFourierTransformerTest.java, Main.java > > > I wrote my own Discrete Fourier Transform function in Java and ran some > benchmarks and found that it ran dramatically faster than the Apache library > implementation. This is a pretty straight forward implementation of the > standard Cooley Tukey algorithm that I read out of a textbook. This passes > all the Apache library test cases plus several I had written on my own. I > created a source code library patch that preserves the public API completely > while changing the internal implementation to achieve the performance > improvement. > In addition to the performance issue, I suggest that Discrete Fourier > Transform functionality be provided as stateless pure functions (in Java this > would be implemented with static methods) just like most other math > functions. As-is, the library requires the user to instantiate a Transformer > instance which maintains instance state, which is an unecessary complexity > for a pure math function. I held off on this change since it would change the > public API and affect existing code. However, I see similar backward > compatability breaking API changes are already in the FastFourierTransformer > class in the 3.0 code base. -- 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-732) Major Speed Improvement to 1D Discrete Fourier Transform (approximately 5x-9x improvement). Preserved public API 100%. Removed unnecessary use of instance variables and i
[ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13204252#comment-13204252 ] Kurt Ostfeld commented on MATH-732: --- Great news. Thanks for the help! I looked at the updated version of trunk. Here are my thoughts: - Math functions, like DFT, should be pure functions, which in Java is a static function, like Math.sqrt. I see your point that similar classes inherit from RealTransformer, so the DFT class should be consistent with that style. The library should offer both interfaces (static and RealTransformer instance style) to the user and internally one should call the other. We should add the unitary option to the static transformInPlace function to be consistent. - Making bitReversalShuffle2 private sounds like a good idea. I can't think of another external use for that logic. - The other changes that you made look great. Here is some JavaDoc for bitReversalShuffle2: /** * Performs identical index bit reversal shuffles on two arrays of identical size. * Each element in the array is swapped with another element based on the bit-reversal * of the index. * For example, in an array with length 16, item at binary index 0011 (decimal 3) * would be swapped with the item at binary index 1100 (decimal 12). * * @param a The first array to be shuffled. * @param b The second array to be shuffled. */ > Major Speed Improvement to 1D Discrete Fourier Transform (approximately 5x-9x > improvement). Preserved public API 100%. Removed unnecessary use of instance > variables and instance state. > > > Key: MATH-732 > URL: https://issues.apache.org/jira/browse/MATH-732 > Project: Commons Math > Issue Type: Improvement >Affects Versions: 3.0 >Reporter: Kurt Ostfeld >Assignee: Sébastien Brisard > Labels: api, perfomance > Fix For: 3.0 > > Attachments: DFTPerformanceWithPatch.png, > DFTPerformanceWithoutPatch.png, FastFourierTransformer.java, > FastFourierTransformerTest.java, Main.java > > > I wrote my own Discrete Fourier Transform function in Java and ran some > benchmarks and found that it ran dramatically faster than the Apache library > implementation. This is a pretty straight forward implementation of the > standard Cooley Tukey algorithm that I read out of a textbook. This passes > all the Apache library test cases plus several I had written on my own. I > created a source code library patch that preserves the public API completely > while changing the internal implementation to achieve the performance > improvement. > In addition to the performance issue, I suggest that Discrete Fourier > Transform functionality be provided as stateless pure functions (in Java this > would be implemented with static methods) just like most other math > functions. As-is, the library requires the user to instantiate a Transformer > instance which maintains instance state, which is an unecessary complexity > for a pure math function. I held off on this change since it would change the > public API and affect existing code. However, I see similar backward > compatability breaking API changes are already in the FastFourierTransformer > class in the 3.0 code base. -- 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-732) Major Speed Improvement to 1D Discrete Fourier Transform (approximately 5x-9x improvement). Preserved public API 100%. Removed unnecessary use of instance variables and i
[ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13199214#comment-13199214 ] Kurt Ostfeld commented on MATH-732: --- Thanks so much for your consideration, Sébastien. Let me know if there is anything else that I can do on my end. > Major Speed Improvement to 1D Discrete Fourier Transform (approximately 5x-9x > improvement). Preserved public API 100%. Removed unnecessary use of instance > variables and instance state. > > > Key: MATH-732 > URL: https://issues.apache.org/jira/browse/MATH-732 > Project: Commons Math > Issue Type: Improvement >Affects Versions: 3.0 >Reporter: Kurt Ostfeld >Assignee: Sébastien Brisard > Labels: api, perfomance > Fix For: 3.0 > > Attachments: DFTPerformanceWithPatch.png, > DFTPerformanceWithoutPatch.png, FastFourierTransformer.java, > FastFourierTransformerTest.java, Main.java > > > I wrote my own Discrete Fourier Transform function in Java and ran some > benchmarks and found that it ran dramatically faster than the Apache library > implementation. This is a pretty straight forward implementation of the > standard Cooley Tukey algorithm that I read out of a textbook. This passes > all the Apache library test cases plus several I had written on my own. I > created a source code library patch that preserves the public API completely > while changing the internal implementation to achieve the performance > improvement. > In addition to the performance issue, I suggest that Discrete Fourier > Transform functionality be provided as stateless pure functions (in Java this > would be implemented with static methods) just like most other math > functions. As-is, the library requires the user to instantiate a Transformer > instance which maintains instance state, which is an unecessary complexity > for a pure math function. I held off on this change since it would change the > public API and affect existing code. However, I see similar backward > compatability breaking API changes are already in the FastFourierTransformer > class in the 3.0 code base. -- 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-732) Major Speed Improvement to 1D Discrete Fourier Transform (approximately 5x-9x improvement). Preserved public API 100%. Removed unnecessary use of instance variables and i
[ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13199019#comment-13199019 ] Kurt Ostfeld commented on MATH-732: --- I'm hoping this should be a fairly easy drop-in replacement. I'm still seeing large (~10x) performance improvements in my benchmarks. I had to make very small tweaks to the unit tests: In three cases, I had to reduce testing tolerance by one, because the output results differed passed the 13th decimal value. > Major Speed Improvement to 1D Discrete Fourier Transform (approximately 5x-9x > improvement). Preserved public API 100%. Removed unnecessary use of instance > variables and instance state. > > > Key: MATH-732 > URL: https://issues.apache.org/jira/browse/MATH-732 > Project: Commons Math > Issue Type: Improvement >Affects Versions: 3.0 >Reporter: Kurt Ostfeld >Assignee: Sébastien Brisard > Labels: api, perfomance > Fix For: 3.0 > > Attachments: DFTPerformanceWithPatch.png, > DFTPerformanceWithoutPatch.png, FastFourierTransformer.java, > FastFourierTransformerTest.java, Main.java > > > I wrote my own Discrete Fourier Transform function in Java and ran some > benchmarks and found that it ran dramatically faster than the Apache library > implementation. This is a pretty straight forward implementation of the > standard Cooley Tukey algorithm that I read out of a textbook. This passes > all the Apache library test cases plus several I had written on my own. I > created a source code library patch that preserves the public API completely > while changing the internal implementation to achieve the performance > improvement. > In addition to the performance issue, I suggest that Discrete Fourier > Transform functionality be provided as stateless pure functions (in Java this > would be implemented with static methods) just like most other math > functions. As-is, the library requires the user to instantiate a Transformer > instance which maintains instance state, which is an unecessary complexity > for a pure math function. I held off on this change since it would change the > public API and affect existing code. However, I see similar backward > compatability breaking API changes are already in the FastFourierTransformer > class in the 3.0 code base. -- 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-732) Major Speed Improvement to 1D Discrete Fourier Transform (approximately 5x-9x improvement). Preserved public API 100%. Removed unnecessary use of instance variables and i
[ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13193152#comment-13193152 ] Kurt Ostfeld commented on MATH-732: --- I ran the updated benchmark that uses complex data (with non-zero imaginary values) and got more pronounced speed improvements with the patched library. > Major Speed Improvement to 1D Discrete Fourier Transform (approximately 5x-9x > improvement). Preserved public API 100%. Removed unnecessary use of instance > variables and instance state. > > > Key: MATH-732 > URL: https://issues.apache.org/jira/browse/MATH-732 > Project: Commons Math > Issue Type: Improvement >Affects Versions: 3.0 >Reporter: Kurt Ostfeld > Labels: api, perfomance > Fix For: 3.0 > > Attachments: DFTPerformanceWithPatch.png, > DFTPerformanceWithoutPatch.png, FastFourierTransformer.java.diff, > FastFourierTransformer.java.diff, FastFourierTransformerTest.java.diff, > FastFourierTransformerTest.java.diff, Main.java, Main.java > > > I wrote my own Discrete Fourier Transform function in Java and ran some > benchmarks and found that it ran dramatically faster than the Apache library > implementation. This is a pretty straight forward implementation of the > standard Cooley Tukey algorithm that I read out of a textbook. This passes > all the Apache library test cases plus several I had written on my own. I > created a source code library patch that preserves the public API completely > while changing the internal implementation to achieve the performance > improvement. > In addition to the performance issue, I suggest that Discrete Fourier > Transform functionality be provided as stateless pure functions (in Java this > would be implemented with static methods) just like most other math > functions. As-is, the library requires the user to instantiate a Transformer > instance which maintains instance state, which is an unecessary complexity > for a pure math function. I held off on this change since it would change the > public API and affect existing code. However, I see similar backward > compatability breaking API changes are already in the FastFourierTransformer > class in the 3.0 code base. -- 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-732) Major Speed Improvement to 1D Discrete Fourier Transform (approximately 5x-9x improvement). Preserved public API 100%. Removed unnecessary use of instance variables and i
[ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13191248#comment-13191248 ] Kurt Ostfeld commented on MATH-732: --- Thank you so much, Sebastien! I signed the ICLA and it's filed. > Major Speed Improvement to 1D Discrete Fourier Transform (approximately 5x-9x > improvement). Preserved public API 100%. Removed unnecessary use of instance > variables and instance state. > > > Key: MATH-732 > URL: https://issues.apache.org/jira/browse/MATH-732 > Project: Commons Math > Issue Type: Improvement >Affects Versions: 3.0 >Reporter: Kurt Ostfeld > Labels: api, perfomance > Fix For: 3.0 > > Attachments: DFTPerformanceWithPatch.png, > DFTPerformanceWithoutPatch.png, FastFourierTransformer.java.diff, > FastFourierTransformer.java.diff, FastFourierTransformerTest.java.diff, > FastFourierTransformerTest.java.diff, Main.java > > > I wrote my own Discrete Fourier Transform function in Java and ran some > benchmarks and found that it ran dramatically faster than the Apache library > implementation. This is a pretty straight forward implementation of the > standard Cooley Tukey algorithm that I read out of a textbook. This passes > all the Apache library test cases plus several I had written on my own. I > created a source code library patch that preserves the public API completely > while changing the internal implementation to achieve the performance > improvement. > In addition to the performance issue, I suggest that Discrete Fourier > Transform functionality be provided as stateless pure functions (in Java this > would be implemented with static methods) just like most other math > functions. As-is, the library requires the user to instantiate a Transformer > instance which maintains instance state, which is an unecessary complexity > for a pure math function. I held off on this change since it would change the > public API and affect existing code. However, I see similar backward > compatability breaking API changes are already in the FastFourierTransformer > class in the 3.0 code base. -- 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
