3 ms·

I don't know anything about FFTW, but the question/answer seem misleading: GitHub language details of the non-generated sources say 75% C: https://github.com/F

by sambe 8y ago

I don't know anything about FFTW, but the question/answer seem misleading: GitHub language details of the non-generated sources say 75% C: https://github.com/FFTW/fftw3 https://github.com/FFTW/fftw3 FFTW author comment linked from Quora answer contradicts said answer (~2/3 C): https://groups.google.com/d/msg/fa.caml/B5kFMTl67MU/9c8swiOE0M8J https://groups.google.com/d/msg/fa.caml/B5kFMTl67MU/9c8swiOE... Am I missing something here? Double generation?

tanderson92 8y ago
FFTW author is commenting on LOC and Github appears to be going off of number of files. Github also incorrectly counts C headers as C++.
al_chemist 8y ago
From article "Note that some people (such as Frank) get confused because FFTW is commonly distributed in the form of precompiled C code. That is not the source code. Most of the C code is generated by OCaml source code"
- sambe 8y ago
  My comment contains references which refute that claim, which is why I made it.
ziotom78 8y ago
The author of the answer is Jon Harrop, a well-known former Ocaml evangelist (and author of an awesome book, "Ocaml for scientists", [1]). He sometimes gets a bit too far in explaining the virtues of Ocaml... I carefully studied the source code of FFTW a few years ago and read a few of Frigo's papers (e.g., [2]). The purpose of FFTW is to apply direct/inverse Fourier transforms to vectors of N elements, and it does so by employing a number of algorithms to split the data into many smaller chunks and then applying the transform to each of these sub-chunks. (This is basically the idea of the FFT.) When a chunk is small enough (e.g., 10 elements), it can be worth to stop splitting it into smaller subpieces but instead to apply a direct brute-force formula. This is where OCaml comes into the game. FFTW's authors have written OCaml snippets to compute the Fourier Transform in a number of ways. This code is written using custom operators, so that the snippet is not compiled down to machine code but instead kept in a AST. An optimizing complier (written in OCaml) is then ran on the AST to perform a number of optimizations to the snippet, and finally output C code is generated out of the optimized AST. Among the optimizations there are some classical ones (e.g., constant folding); others are domain-specific, because they employ some property or symmetry of the Fourier Transform. The C code that is produced as output is taylored for some specific situation, e.g., direct transform of 13 purely real numbers. The algorithm that takes N numbers and splits them in chunks is written in C, as well as the code that decides when to stop the recursive splitting and which OCaml-generated snippet is best suited for each chunk. Moreover, C is used for all the function that allocate and handle the many data structures used by the library. Therefore, it is a bit of a stretch to say that FFTW is written in OCaml, although its most interesting part (the optimizing compiler) is indeed. This is the reason why Frigo's paper [2] deals mainly with the OCaml part. [1] http://www.ffconsultancy.com/products/ocaml_for_scientists/ http://www.ffconsultancy.com/products/ocaml_for_scientists/ [2] http://www.fftw.org/fftw-paper-ieee.pdf http://www.fftw.org/fftw-paper-ieee.pdf

by sambe 8y ago

tanderson92 8y ago

FFTW author is commenting on LOC and Github appears to be going off of number of files. Github also incorrectly counts C headers as C++.

al_chemist 8y ago

From article "Note that some people (such as Frank) get confused because FFTW is commonly distributed in the form of precompiled C code. That is not the source code. Most of the C code is generated by OCaml source code"

sambe 8y ago
My comment contains references which refute that claim, which is why I made it.

ziotom78 8y ago

The author of the answer is Jon Harrop, a well-known former Ocaml evangelist (and author of an awesome book, "Ocaml for scientists", [1]). He sometimes gets a bit too far in explaining the virtues of Ocaml... I carefully studied the source code of FFTW a few years ago and read a few of Frigo's papers (e.g., [2]). The purpose of FFTW is to apply direct/inverse Fourier transforms to vectors of N elements, and it does so by employing a number of algorithms to split the data into many smaller chunks and then applying the transform to each of these sub-chunks. (This is basically the idea of the FFT.) When a chunk is small enough (e.g., 10 elements), it can be worth to stop splitting it into smaller subpieces but instead to apply a direct brute-force formula. This is where OCaml comes into the game. FFTW's authors have written OCaml snippets to compute the Fourier Transform in a number of ways. This code is written using custom operators, so that the snippet is not compiled down to machine code but instead kept in a AST. An optimizing complier (written in OCaml) is then ran on the AST to perform a number of optimizations to the snippet, and finally output C code is generated out of the optimized AST. Among the optimizations there are some classical ones (e.g., constant folding); others are domain-specific, because they employ some property or symmetry of the Fourier Transform. The C code that is produced as output is taylored for some specific situation, e.g., direct transform of 13 purely real numbers. The algorithm that takes N numbers and splits them in chunks is written in C, as well as the code that decides when to stop the recursive splitting and which OCaml-generated snippet is best suited for each chunk. Moreover, C is used for all the function that allocate and handle the many data structures used by the library. Therefore, it is a bit of a stretch to say that FFTW is written in OCaml, although its most interesting part (the optimizing compiler) is indeed. This is the reason why Frigo's paper [2] deals mainly with the OCaml part. [1] http://www.ffconsultancy.com/products/ocaml_for_scientists/ http://www.ffconsultancy.com/products/ocaml_for_scientists/ [2] http://www.fftw.org/fftw-paper-ieee.pdf http://www.fftw.org/fftw-paper-ieee.pdf