Enumerate very slow?

My conversion of a C program into Rust was using many loops and array indexing, in typical C style. It was suggested on the "'as' considered harmful" thread that I use iterators instead of array indexing for a more Rustic style. The happy result was that the Rust translation now runs a little faster than the original C version.

Except one loop has defeated my attempts at Rustication:

        for j in i + 1..PNUM {
            p = PR[j];
            if p > pmax {
                break;
            }
            self.factors.p[fmax] = p;
            self.s = s * p;
            self.i = j;
            self.fmax = fmax;
            self.work();
        }

I noticed that clippy complained about using indices as well and suggested I write this:

        for (j, p) in PR.iter().enumerate().take(PNUM).skip(i + 1) {
            if *p > &pmax {
                break;
            }
            self.factors.p[fmax] = *p;
            self.s = s * p;
            self.i = j;
            self.fmax = fmax;
            self.work();
        }
        self.factors.n[fmax] = 0;
    }

This is not only horribly ugly and obfuscated but what is not acceptable is that it also significantly slows down the code. From a run time of 4 minuets 41 seconds to 5 minutes 10 seconds.

I also tried

        for (j, p) in PR.iter().enumerate().skip(i + 1) {

Which works but is the same slow.

I don't think clippy should be suggesting pessimizations

Perhaps someone has a better suggestion than clippy?

Full code here: https://github.com/ZiCog/tatami-rust

3 Likes

skipping before enumerating might help a tiny bit (my thought being less to enumerate -> faster). There's definitely something else going wrong though, possibly in the compilation.

You're good at breaking rustc aren't you? :wink: The internals team are going to love/hate you :stuck_out_tongue:

This will yield wrong results (indexes will be shifted).

2 Likes

You mean:

for (j, p) in PR.iter().skip(i + 1).enumerate() {...

That gives me the wrong result!

Huh! Well, I'll be...
How is that happening?

Simple example:

[1, 2].iter().enumerate().skip(1).collect::<Vec<_>>() == vec![(1, 2)];
[1, 2].iter().skip(1).enumerate().collect::<Vec<_>>() == vec![(0, 2)];

The difference is that enumerate don't know anything about skip, it simply enumerates anything it gets. If skip already consumed first item, enumerate will see the second one as first.

1 Like

This caught me out before, enumerate and skip don't commute.

Oh good. It's not just me. This proposed Rustic style of iter.skip.zip.zip.ect is way more confusing that just using C style array indices.

What I don't understand now is why Cerbuser's examples produce a vector with two elements. I would have expected 'skip' to shorten the vector by the amount skipped.

Ha!. Comes from years of testing avionic control systems.

Or is it more like: If you want to know how tough your product is give it to a monkey.

7 Likes

It's not two elements, it's one tuple (index, element).

Judging just by the length of the asm with different combination of enumerate, skip and take, the problem is with skip not enumerate. Skip looks to cause a lot of weird branches to be added.

This is by far the weirdest, sets a value to zero then check if that same value is zero.

	xorl	%edi, %edi
	testq	%rdi, %rdi
	jne	.LBB0_2
8 Likes

Yes, skip is rather inefficient when used in a for loop. If you want to use skip, then use for_each. Another option is to manually skip before the loop, but I personally find that to look ugly.

3 Likes

If skip is slowing things down, why not do it manually and shift the indices to correct:

const PR: [u8; 4] = [1,2,3,4];

fn main() {
    let i = 1;
    for (j,p) in PR[i+1..].iter().enumerate() {
        println!("{:?}", (j+i+1,p));
    }
}

gives:

(2, 3)
(3, 4)

Not sure if that would be faster than skip or not.

I tried it. It works and it's a bit faster but still a lot slower than the C style loop at 4 minutes 51 seconds.

I can't accept it as a solution. It introduces a calculation that is nothing to do with the job at hand, worse still it's a repetition of the calculation in the 'for' statement. And well, it's still slow.

Oops, sorry, yes. I did not look close enough.

Do you have an example of how that might look in this case. Just now my functional foo is not strong enough to work it out from the docs https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.for_each

I notice it says one cannot use 'break' from the closure. And where do I get the index 'i' from in the closure?

All seems far too heavy weight for a simple loop.

If you have a condition you want to break, introduce it prior to the for_each() call using the take_while() method:

PR.iter().enumerate().skip(i+1).take_while(|(_,p)| *p < &pmax).for_each(|(j,p)| <your closure>)

Simple example: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=2f48ab4a958ad3bf9f5ef31c2d72775a

I do hope you are joking with me.

No way am I putting that line noise into any program I ever write. It could take me a month to figure out how to read it.

I'm not sure I see how it's harder to read than

if p > &pmax { break }

I suppose it is a whole 8 more characters in length. An iterator is passing values from one method to the next until it is consumed. You're already comfortable with iter passing to enumerate, which in turn is passing to skip. All of these are expressible in imperative syntax, but conceptually the functional and imperative approaches are essentially identical. You want to tell the for loop to break if a certain condition is met, I am suggesting you tell the iterator to stop taking values once a condition is met.

I guess its speed must depend on some other factors here. I tried it on my computer and it's terribly slow (like 3-4 times slower!).

Think of it like unix pipes. Once you get used to reading this, it becomes very clear. Every part here does what it says and for me it reads almost like prose.

1 Like