5 ms·

For reference, a straightforward translation of the Rust code to C++, compiled using clang, halves the running time. There are two reasons for this: - `int` is

• pcwalton 12y ago
  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 :)
  • heinrich5991 12y ago
    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).
    • pcwalton 12y ago
      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).
      • gliptic 12y ago
        Doesn't it insert None checks for Option<&u32> (because of zip)? LLVM probably doesn't figure out that they'll never be NULL.
        • pcwalton 12y ago
          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.
          • AaronFriel 12y ago
            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.
            • pcwalton 12y ago
              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.
  • pbsd 12y ago
    Well Rust is checking for null pointers at the assembly level: http://goo.gl/eh2aqc http://goo.gl/eh2aqc (lines 22--27).
    • pcwalton 12y ago
      Blech. I'm pretty sure LLVM, not the frontend, is inserting those null checks for some reason.
      • kzrdude 12y ago
        The slice iterator yields `Option<&T>`, the None variant is represented by a null pointer. That's probably the null check.
    • dbaupp 12y ago
      This is https://github.com/mozilla/rust/issues/11751 https://github.com/mozilla/rust/issues/11751: LLVM doesn't understand (non)null pointers enough.
• modeless 12y ago
  What's the justification for having a variable size int as the default? That seems like a mistake to me.
  • kibwen 12y ago
    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. :)
    • bjz_ 12y ago
      I agree it is weird too.
    • pcwalton 12y ago
      I don't think it's a mistake in Rust, because of array indices.
      • kibwen 12y ago
        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
  • pcwalton 12y ago
    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.
    • modeless 12y ago
      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.
• krick 12y ago
  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?
  • pcwalton 12y ago
    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.
    • pbsd 12y ago
      For the sake of reproducibility, transparency and all that, here's the C++ version: http://pastebin.com/5pMka6ZJ http://pastebin.com/5pMka6ZJ
• ben0x539 12y ago
  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 http://ix.io/cUd
  • pbsd 12y ago
    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.
    • ben0x539 12y ago
      > 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).