Open jenskeiner opened 1 month ago
Looks good. I also had about 20 % speed increase on my Intel 10700 CPU with GCC10 and time measured in Matlab.
I was wondering why you did the changes only in 1D, because these improvements should also work in the multivariate case as well as for the direct adjoint NFFT.
I'll make more changes, for d > 1 and possibly the adjoint transform as well. I was just going to get it in step by step so everything can be reasonably tested. There's no rush to merge this PR from my side. But I don't know how fast I'll be able to get to make more changes, so it could make sense to merge this, and then I'll just open new PRs for the rest.
Small change to improve the efficiencvy of the direct NFFT trafo in one dimension:
memset
to initialize the target vector with zeros, it's better to just write the final value to the target in the outer loop. Rationale: Using memset will need to access the entire target vector another time. This can be costly if the vector is large and does not fit inside the CPU cache.f[j]
in the inner loop in each iteration, it may be better to accumulate the value in a local variable and write only the final value tof[j]
. Rationale: May reduce potentially slow memory access tof[j]
, but iff[j]
is in the CPU cache and/or the compiler is smart, this may not make any difference.cexp
to calculate e^{-i*omega}, use real-valuedsin
andcos
functions. Rationale:cexp
supports complex-valued arguments, but the actual argument is always purely imaginary.It was difficult to test this one because there's not simple benchmark I could quickly run. Also, I tested this on arm64/v8 and
cycle.h
currently doesn't work for me. So I had to set up a scratch file to run a quick check which is not part of this PR. On my platform, the number of cycles for the direct transform drops to 60-80% compared to before.Would be good if someone could test this separately and on a different architecture (e.g. amd64) as well.