Iterator-based approach performs 10x worse than manual implementation

[bradleyharden]

I'm not sure if this qualifies as a bug or not.

In short, the following two functions give the same output, but fft performs about 10x worse than fft_manaul.

const LUT: [i16; 8] = [0, 1, 2, 3, 4, 5, 6, 7];

pub fn fft(samples: &[i16; 16]) -> (i32, i32) {
    let sin = LUT.iter().cycle();
    let cos = LUT.iter().cycle().skip(LUT.len() / 4);
    sin.zip(cos).zip(samples).fold(
        (0, 0), |(mut real, mut imag), ((sin, cos), &sample)| {
            real += sample as i32 * (*cos as i32);
            imag += sample as i32 * (*sin as i32);
            (real, imag)
    })
}

const LUT: [i16; 8] = [0, 1, 2, 3, 4, 5, 6, 7];

pub fn fft_manual(samples: &[i16; 16]) -> (i32, i32) {
    const LUT_LEN: usize = LUT.len();
    let mut real = 0;
    let mut imag = 0;
    for i in 0..(samples.len() / LUT_LEN) {
        for j in 0..LUT_LEN {
            let sin = LUT[j];
            let cos = LUT[(j + (LUT_LEN / 4)) % LUT_LEN];
            let sample = samples[i * LUT_LEN + j];
            real += sample as i32 * (cos as i32);
            imag += sample as i32 * (sin as i32);
        }
    }
    (real, imag)
}

I originally ran into this in an embedded context, targeting thumbv7em-none-eabihf. The original function took a GenericArray and used fixed-point types from the fixed crate, but I was able to reproduce the issue using only primitive types targetting x86_64-pc-windows-msvc.

Here are the results of benchmarks from selected nightly versions from the past 18 months. The benchmarks were run using the code here.

Version	Results
nightly-2020-12-21	test tests::bench_fft ... bench: 63 ns/iter (+/- 16) test tests::bench_fft_manual ... bench: 5 ns/iter (+/- 1)
nightly-2020-06-01	test tests::bench_fft ... bench: 36 ns/iter (+/- 15) test tests::bench_fft_manual ... bench: 4 ns/iter (+/- 2)
nightly-2020-01-02	test tests::bench_fft ... bench: 45 ns/iter (+/- 20) test tests::bench_fft_manual ... bench: 5 ns/iter (+/- 1)
nightly-2019-06-01 (with #![feature(const_slice_len)])	test tests::bench_fft ... bench: 52 ns/iter (+/- 23) test tests::bench_fft_manual ... bench: 5 ns/iter (+/- 1)

I took a look at the output of cargo asm for each version. The output of fft has 28 branch instructions, while the output of fft_manual has none. I guess the compiler is able to completely unroll the loop when it's written manually, but not when it's written using Iterators.

Unfortunately, this is about the limit of my debugging ability currently. With some guidance, I might be able to do more of the leg work on my own.

Is this a known/expected performance difference? I hope not. I was really impressed at the elegance of the Iterator-based approach. I would be disappointed if the performance is really that bad.

[leonardo-m]

Perhaps it's because those cycle()?

[the8472]

Unfortunately, this is about the limit of my debugging ability currently. With some guidance, I might be able to do more of the leg work on my own.

Try compiling benchmarks with debuginfo = 2 and then running them under perf record --call-graph dwarf and perf report (or some GUI equivalent). That can get you the assembly + corresponding source lines + whole call tree including inlining + information which instructions take most of the time. The usefulness of source annotation varies though due to the heavy optimizations.

Perhaps it's because those cycle()?

Possible. zip has a specialized implementation that applies when both iterators implement TrustedRandomAccess, which Cycle currently doesn't but probably could if the underlying one does.

Edit: nevermind, it can't implement that because TRA must have a finite size, which Cycle doesn't have.

[JulianKnodt]

I've found zip to be the main cause for slowness, because it has to check whenever the first item terminates, and has trouble reasoning about the length of iterators

[bradleyharden]

@JulianKnodt and @the8472, if zip + cycle is the likely culprit and there's nothing that can done to improve it, is the best solution a manual implementation, like I did? Is it still worth it for me to dig deeper into debugging?

[JulianKnodt]

This is a purely personal POV, so take it as you will, but I think certainly the manual implementation is fine and it's not always worth making very neat abstractions due to increased burden on the compiler.
That being said, there are probably spectializations that can be added to make zip & cycle better, so if you're really focusing on implementing FFT, you probably want to stick to the manual impl, but if you're doing it as an exercise it could be good to look at the library implementations of those and see if anything can be added to speed it up.

[bradleyharden]

For the particular use case at hand, I think it probably makes sense to stick with the manual implementation. I need to calculate the FFT coefficients for a single frequency in an embedded context with a real-time deadline.

However, before I discovered the poor performance, I remember being impressed by this specific iteration example, because I was able express the entire problem in terms of iterator adapters (cycle, skip and zip). I was excited to share it with some of my coworkers as a great example of the zero-cost abstractions that Rust could offer. But then I found out it's not so zero-cost, which is disappointing.

I might look into it more, but I don't know that I really have the expertise to improve the implementation. I would think these issues have already been considered in depth by people with a lot more experience in compilers.

[leonardo-m]

I would think these issues have already been considered in depth by people with a lot more experience in compilers.

Very smart and dedicated people have worked on the stdlib, but the stdlib isn't perfect nor complete. If you see a possible hole, then see if it's worth filling, if you have time to do it :-) Perhaps cycle+zip is worth improving.

[bradleyharden]

I played around with the example just now and found something interesting. Apparently zip and cycle are not the problem, it's actually skip. Removing skip, or giving it an argument of 0, is enough to erase the performance differences.

Based on that, does anyone have any immediate insight into what the problem might be?

[bradleyharden]

Looks like it's the interaction between cycle and skip. Interesting.

This compiles to a constant:

pub fn skip_manual() -> i16 {
    let mut sum = 0;
    for i in 0..LUT_LEN {
        sum += LUT[(i + 2) % LUT_LEN];
    }
    sum
}

But this does not.

pub fn skip() -> i16 {
    LUT.iter().cycle().skip(2).take(8).sum()
}

Yet this does

pub fn skip() -> i16 {
    LUT.iter().skip(2).sum()
}

[JulianKnodt]

Interesting, I think skip + iteration still adds some complexity, but I imagine having skip of 0 means that a bunch of branches can be compiled out from the impl. It might be because cycle doesn't implement any traits like TrustedLen etc, and skip propagates those impls, & zip then uses those for specialization. @the8472 where does it mention that TRA needs finite size? I looked for it briefly but couldn't find it

You can also remove the skip just by iterating thru eagerly and it removes some branches:

pub fn fft(samples: &[i16; 16]) -> (i32, i32) {
    let sin = LUT.iter().cycle();
    let mut cos = LUT.iter().cycle();
    cos.nth(LUT.len() / 4);
    ...
}

[bradleyharden]

Can someone explain what's going on here? On both Godbolt and with cargo-asm, I'm getting strange behavior.

In this example, skip, cycle_take and cycle_nth_take all compile to the same function, which simply returns a constant. However, if you uncomment cycle_skip_take, then cycle_nth_take no longer compiles to a constant. How can that be? Is that some weird artifact of both Godbolt and cargo-asm? Or is it a real bug?

[the8472]

Another approach, I haven't benchmarked it but on O3 it gives branch-free assembly only consisting of memory and simple arithmetic operations, similar to @JulianKnodt's approach with nth.
O2 doesn't look as rosy, producing a loop and two multiplications.

const LUT: [i16; 8] = [0, 1, 2, 3, 4, 5, 6, 7];

pub fn fft(samples: &[i16; 16]) -> (i32, i32) {
    let sin = (0..).map(|i| LUT[i % LUT.len()]);
    let cos = ((LUT.len()/4)..).map(|i| LUT[i % LUT.len()]);
    sin.zip(cos).zip(samples).fold(
        (0, 0), |(mut real, mut imag), ((sin, cos), &sample)| {
            real += sample as i32 * (cos as i32);
            imag += sample as i32 * (sin as i32);
            (real, imag)
    })
}

In this case skip can actually be used for cos, at least on O3.

---

@JulianKnodt

@the8472 where does it mention that TRA needs finite size? I looked for it briefly but couldn't find it

rust/library/core/src/iter/adapters/zip.rs

Line 386 in 32da90b

/// The iterator's `size_hint` must be exact and cheap to call.

It can only be exact (upper bound == lower bound) if an upper bound exists which means it needs to fit into usize.

---

@bradleyharden

How can that be? Is that some weird artifact of both Godbolt and cargo-asm? Or is it a real bug?

I would guess that llvm is simply making different inlining decisions based on the number of calls to one of the functions in the iterator chain and duplicating parts of that code goes over a threshold. Iterator optimizations are heavily dependent on inlining.

[bradleyharden]

I would guess that llvm is simply making different inlining decisions based on the number of calls to one of the functions in the iterator chain and duplicating parts of that code goes over a threshold. Iterator optimizations are heavily dependent on inlining.

@the8472, I just want to clarify, in case there was any miscommunication. In that example the same function gives two different results based on the presence or absence of a different function. It doesn't seem like inlining could explain that. It seems more like it's skipping an optimization pass when another function is present, or something.