Rust doesn't have null pointers, so I see no language-level reason why that wouldn't vectorize. LLVM's vectorizer tends to be pretty brittle, so probably tweaking the generated IR a bit would cause us to vectorize. Feel free to file an issue if you have time :)

Well Rust is checking for null pointers at the assembly level: http://goo.gl/eh2aqc (lines 22--27).

Blech. I'm pretty sure LLVM, not the frontend, is inserting those null checks for some reason.

The slice iterator yields `Option<&T>`, the None variant is represented by a null pointer. That's probably the null check.

This is https://github.com/mozilla/rust/issues/11751: LLVM doesn't understand (non)null pointers enough.

That might still be the case. IIRC I read somewhere that when the iterator code gets inlined, the non-nullness of the pointer gets lost, as the iterators internally use raw pointers (which can be null in Rust).

Yeah, nonnull is only allowed on parameters in LLVM IR, so it gets lost post-inlining. I'm pretty sure it's LLVM that is inserting those null checks, as we never do in the frontend (since safe pointers are not null in Rust, and unsafe pointers are never checked for null since they're unsafe).

Doesn't it insert None checks for Option<&u32> (because of zip)? LLVM probably doesn't figure out that they'll never be NULL.

Yeah, that's probably it. (The compiler isn't inserting the checks, but rather the libraries are.) The vectorizer can't safely vectorize that code without changing when failure occurs if the vectors are different lengths.

Perhaps the best thing to do is to change zip, or add a new parameter to zip, to allow it to "chunk" its inputs and thereby enable vectorization. Or we could have a special type that encapsulates two or more vectors and checks up front that they're the same length, so that zip can then assume that they're the same length. It also might be possible to add an optimization to LLVM to have it figure out that the vectors are the same length.

If zip is following the 'functional' definition, it should only return a list of the length of the shorter of the two inputs. In Haskell:

    zip :: [a] -> [b] -> [(a, b)]

Not:

    zip :: [a] -> [b] -> [(Maybe a, Maybe b)]

If you want to allow processing a sequence of tails, you could have:

    zipWithTail :: [a] -> [b] -> ([(a, b)], Either [a] [b])

Which would return a list of pairs and a list of either the tail of the first or the second input, whichever was longer.

It is following that definition, but the issue is that it's built on iterators, which are of unknown length. Haskell would have effectively the same checks if built on lists because of the way lazy thunks work.

Prompted by pcwalton I've added a tiny specialized iterator for zipping two vector slices that apparently is simple enough to avoid the null pointer checks after all. This brings the runtime on my system down from ~3.1 seconds to ~2.06 seconds. Going from i64 to i32 brings it further down to ~1.03s, beating your C++ version (thanks!) which runs in ~1.55s on my system.

Code at http://ix.io/cUd

Nice! Is this going into the standard library?

I've looked at the output of both inner loops, and it seems I put too much faith in std::valarray's expression templates. Changing the distance function to

    int distance(std::valarray<int> const& x, std::valarray<int> const& y) {
        return inner_product(begin(x), end(x), begin(y), 0, 
        std::plus<int>(), [](int x, int y){ return (x-y)*(x-y); });
    }

results in the exact same inner loop as Rust. The remaining speed difference comes from the file loading code, which admittedly is crap (way too many memory allocations). So for all intents and purposes, I admit defeat.

> Nice! Is this going into the standard library?

Possibly. There's been some talk in that direction, but also some "can't we just fix llvm?" objections. I guess someone needs to write up a pull request (and see what other iterator traits to implement, maybe).

So, after reading this thread I still didn't really get if that's something that most likely will be fixed over time, or Rust is fundamentally inferior to C++ in that sense?

I think we can fix it by adding a zip method on slices to avoid the null checks (as we just investigated).

But note that the C++ version has no bounds checks, so it's unsafe. You could always write C in Rust in the unsafe sublanguage, so saying it's "fundamentally inferior" is not true in any case.

For the sake of reproducibility, transparency and all that, here's the C++ version: http://pastebin.com/5pMka6ZJ

What's the justification for having a variable size int as the default? That seems like a mistake to me.

Variable-size as in C++, or variable-size as in Rust? Because they both seem like mistakes to me, but not everyone seems to agree. :)

I don't think it's a mistake in Rust, because of array indices.

I'm not convinced that array indexing is the primary use case of integral variables. And since this is the use case most often espoused for ints, they should probably be renamed to something more appropriate (intptr/uintptr? index/uindex? idx/uidx?). And heck, while we're at it, bare numeric literals should probably default to i32 rather than int (as gross as that feels, it's the least bad option that doesn't involve removing numeric literal type inference). But perhaps this is the wrong forum for this discussion. :P

I agree it is weird too.

Because usually ints are used as array indices, and you want them to be the same size as a pointer in that case.

There is an issue to remove the notion of a "default" integer type.

Ah, I see. Personally I think that isn't a strong enough justification, since this choice introduces possible 32/64 bit portability issues and prevents optimizations in scenarios like this. Arrays with >4 billion elements are rare and it would be a shame to compromise the language design for them.

It would also be a shame to end up with an overly restrictively language in future, where large arrays/values need special `..._64` functions (taking 64 bit integers, rather than 32 bit ones).

I like that justification, assuming there are int8, int16, int 32, int64, etc, there is no need for another int anyways.