Odd bug with VS2017 and latest from master ...

[g40]

Hello. Thanks for kissfft.

I'm building with code cloned from the repo today with VS2017. Here's a snippet that demonstrates the problem. Any thoughts welcomed.

[edit]

See https://github.com/mborgerding/kissfft/blob/master/kissfft.hh#L268 for the problem.

A fix can be hacked in by declaring scatchbuf thusly: std::vector<cpx_type> scratchbuf(p);

        #include <complex>
        #include <kissfft.h>
	static void test()
	{
		typedef kissfft<float> fft_t;
		typedef std::complex<float> fft_type;

		const int nfft = 256;

		fft_t fwd(nfft, false);
		fft_t inv(nfft, true);

		std::vector<fft_type> x(nfft, fft_type());
		std::vector<fft_type> fx(nfft, fft_type());

		x[0] = 2;

		fwd.transform(&x[0], &fx[0]);
	}

This gives the resulting error(s):

1>r:\src\xmos\lib_mp3_test_tools\xcorr\kissfft\kissfft.hh(268): error C2131: expression did not evaluate to a constant
1>r:\src\xmos\lib_mp3_test_tools\xcorr\kissfft\kissfft.hh(268): note: failure was caused by a read of a variable outside its lifetime
1>r:\src\xmos\lib_mp3_test_tools\xcorr\kissfft\kissfft.hh(268): note: see usage of 'p'
1>r:\src\xmos\lib_mp3_test_tools\xcorr\kissfft\kissfft.hh(263): note: while compiling class template member function 'void kissfft<float,kissfft_utils::traits<T_Scalar>>::kf_bfly_generic(std::complex<float> *,const size_t,int,int)'
1>        with
1>        [
1>            T_Scalar=float
1>        ]
1>r:\src\xmos\lib_mp3_test_tools\xcorr\kissfft\kissfft.hh(110): note: see reference to function template instantiation 'void kissfft<float,kissfft_utils::traits<T_Scalar>>::kf_bfly_generic(std::complex<float> *,const size_t,int,int)' being compiled
1>        with
1>        [
1>            T_Scalar=float
1>        ]
1>r:\src\xmos\lib_mp3_test_tools\xcorr\fftxcorr2.h(16): note: see reference to class template instantiation 'kissfft<float,kissfft_utils::traits<T_Scalar>>' being compiled
1>        with
1>        [
1>            T_Scalar=float
1>        ]
1>r:\src\xmos\lib_mp3_test_tools\xcorr\kissfft\kissfft.hh(273): error C3863: array type 'std::complex<float> [p]' is not assignable
1>Done building project "xcorr.vcxproj" -- FAILED.

[mborgerding]

Curious...does changing 'int p' to 'const int p' fix it?

[g40]

Indeed. And no.

[mborgerding]

Jerry, I'd be happy to merge a PR that replaced that scratchbuf with a std::vector<cpx_type>.
Although my gut reaction is to avoid the extraneous allocation, and initialization, I concede that the vector is probably the best solution, considering robustness to different C++ standards and the fact this code will only be called when the FFT size is not an aggregate of 2,3,5.

[mborgerding]

Hmmm, I just noticed a pull request from @lhprojects over on the related (for now) project bazaar-projects/kissfft. It uses a static buffer up to size 32, otherwise allocates dynamically.
bazaar-projects/old-kissfft#10

I'm torn between liking the efficiency of skipping the dynamic allocation and default initialization costs for smallish prime factors, vs the slight ugliness required to do so (not very KISS-like, no RAII guards).

We've got two proposed solutions to the problem. @g40 and @lhprojects, what do you think?

[g40]

Hello Mark,

Thanks for reaching out. I'd be tempted by simplicity in this case. How often is this path hit?

[mborgerding]

That code only gets hit when the fft size has prime factors other than {2,3,5}; in other words, a slower FFT size.

[lhprojects]

For me, both solutions are OK. Indeed I have the third option. we can add a member data of std::vector type, and we resize it in the kf_bfly_generic. This buffer will be reused for all invocation Fourier transforms.

On the consideration of the performance. Firstly, Because people are likely to use the 10^x or 2^x as the FFT size. In this case, the kf_bfly_generic will never be invoked. If kf_bfly_generic will be invoked, we should note that it would be invoked many times in one whole Fourier transform. For example, it will be invoked three times in one Fourier transform (not many) for size 7000.

I have written a simple program to test performance.The time used for the transformation of size 7000 are listed below:
static buffer 1.1us
vector(member) 1.1us
vector(stack) 1.5us

So my suggestion is that: Use a vector as member data. When p > vector::size() resize it in kf_bfly_generic. (The other options are still good, I think.)

[mborgerding]

Wouldn't using a vector as a data member fail in the case where there is more than one factor not from {2,3,5}?, e.g. with N=770=prod(2,5,7,11), both the 7 butterfly and the 11 butterfly would want to use the vector.

[lhprojects]

By the implementation, kf_bfly_generic will never (directly or indirectly) call itself. I don't think there is any problem.

[mborgerding]

Good point! That sounds like a nice solution.

[lhprojects]

Sorry for that the numbers in one before the previous post were totally wrong. the correct numbers are 1000 times in one Fourier transform for size 7000. The time used for the transformation of size 7000 are listed below:
static buffer 580us
vector(member) 600us
vector(stack) 750us
(I don't have a supercomputer, indeed.)

[mborgerding]

@lhprojects, I look forward to a PR with a member vector.

[fake-name]

This is caused by #16, and is still a problem.

TL;DR Variable length arrays are C99, not technically in-spec for C++, and MSVC is C90 only.

Fixed as #6 was merged.