6 ms·

> Rust's Vec indexing is bound-checked by default. Just something like this is abysmal for performance Unless you can provide numbers to back this claim up, I'

by titzer 5y ago

> Rust's Vec indexing is bound-checked by default. Just something like this is abysmal for performance Unless you can provide numbers to back this claim up, I'll continue to rely on my measurements that bounds checking (in Virgil) costs anywhere from 0.5% to 3% of performance. It's sometimes more or less in other languages, but it is by far not the reason any programming language has bad performance. I have no reason to suspect that it costs more in Rust, other than misleading microbenchmarks.

jcelerier 5y ago
Here's a quick and dirty example: https://gcc.godbolt.org/z/3WK7eYM4z https://gcc.godbolt.org/z/3WK7eYM4z I observe (-Ofast -march=native -std=c++20 ; CPU is intel 6900k with performance governor on Arch... blasting at 4GHz) : - clang 13: 8.93 ms per iteration - gcc 11: 9.46 ms per iteration so roughly around 9ms. Replacing return mat[r * matrix_size + c]; by return mat.at(r * matrix_size + c); I observe - clang 13: 20.95 ms per iteration - gcc 11: 18.11 ms per iteration so literally more than twice as slow. I also tried with libc++ instead of libstdc++ for clang and the results did not meaningfully change (around 9ms without bound-checking and 21 ms with).
- titzer 5y ago
  From the godbolt link, it looked like most of the vector operations were not getting inlined. You'll need -O2 or higher to have representative results. I could counter by just writing a Virgil program and turning off bounds check with a compiler flag. We could stare at the machine code together; it's literally an additional load, compare, and branch. The Virgil compiler loves eliminating bounds checks when it can. I know your original comment was in the context of the STL, but it really muddies the waters to see huge piles of code get inlined or not depending on compiler flags. Machine code is what matters. Regardless, this is still microbenchmarking. Maybe matrix multiply is an important kernel, but we need to benchmark whole programs. If I turn off bounds checks in a big program like the Virgil compiler, I cannot measure more than about 1.5% performance difference.
  - jcelerier 5y ago
    > From the godbolt link, I just used godbolt to quickly share the code. On my computer I tried with -Ofast -march=native (broadwell) > I could counter by just writing a Virgil program and turning off bounds check with a compiler flag. We could stare at the machine code together; it's literally an additional load, compare, and branch. This sounds like Virgil is not vectorizing, which makes the comparison much less useful. I see much more than a couple instructions changed there: https://gcc.godbolt.org/z/8jPMb734x https://gcc.godbolt.org/z/8jPMb734x
    - titzer 5y ago
      > Virgil is not vectorizing That's just even more confounding variables. We are, after all, not even doing experiments with Rust vectors, which is what your original comment was about. You wrote examples in C++ and we went down a wormhole already, but I let it slip since at least it was empirical. But I think we shouldn't get distracted with even more side alleys now. Bounds checks are literally just a couple machine instructions, and often eliminated by the compiler anyway, which enables vectorization.
      - steveklabnik 5y ago
        I think you’re confusing two different senses of “vector”, there is the contiguous series of items “vector” data structure that both C++ and Rust have in their standard libraries that’s used in the code example, and there’s “vectorizing” which is an optimization to use things like SIMD to operate on multiple things at the same time.
        titzer 5y ago
        I understood what was meant by these terms.
        steveklabnik 5y ago
        Okay, then I got lost reading your comment, my apologies.
- nybble41 5y ago
  Part of the problem is that the multiply() function takes variable-size matrices as inputs and isn't inlined because it's declared as an external function and so could, in theory, be called from another compilation unit. If it's declared as "static" instead then the compiler generates identical code (modulo register selection) at -Ofast for both versions—eliminating the bounds checking at compile-time: https://gcc.godbolt.org/z/qqWr1xjT8 https://gcc.godbolt.org/z/qqWr1xjT8
  - jcelerier 5y ago
    > Part of the problem is that the multiply() function takes variable-size matrices as inputs so does real-life code ? I don't know about you but I pretty much never know the size of my data at compile time. > If it's declared as "static" again, real-life code calls math operations defined in other libraries, sometimes even proprietary.
    - titzer 5y ago
      In Java or other languages with bounds-checked arrays, you would typically just loop from 0 to the end of the array. In Java the JIT will analyze the loop, see that it is bounded by the length of the array, conclude all accesses are in-bounds and eliminate bounds checks. Virgil does this simple type of bounds check elimination as well in its static compiler, but its analysis is not quite as sophisticated as Java JITs.
    - nybble41 5y ago
      > I don't know about you but I pretty much never know the size of my data at compile time. Whole-program optimization (LTO) can deal with that. Also, Rust inlines across modules much more aggressively than C++ does, even without LTO, so optimization will be more effective and its bounds-checking won't have as much (if any) runtime overhead. Especially if you write your Rust code idiomatically, as others have already suggested. Your earlier Rust example was practically designed to inhibit any attempt at optimization. Simply iterating over a slice of the vector, rather than the indices, results in a much tighter inner loop as it only needs to check the bounds once. That being said, in this case I think it would be better to have fixed-size matrices (using const generic/template arguments) so that the bounds are encoded in the types and known to the compiler locally without relying on whole-program optimization.

by titzer 5y ago

jcelerier 5y ago

Here's a quick and dirty example: https://gcc.godbolt.org/z/3WK7eYM4z https://gcc.godbolt.org/z/3WK7eYM4z I observe (-Ofast -march=native -std=c++20 ; CPU is intel 6900k with performance governor on Arch... blasting at 4GHz) : - clang 13: 8.93 ms per iteration - gcc 11: 9.46 ms per iteration so roughly around 9ms. Replacing return mat[r * matrix_size + c]; by return mat.at(r * matrix_size + c); I observe - clang 13: 20.95 ms per iteration - gcc 11: 18.11 ms per iteration so literally more than twice as slow. I also tried with libc++ instead of libstdc++ for clang and the results did not meaningfully change (around 9ms without bound-checking and 21 ms with).

titzer 5y ago
From the godbolt link, it looked like most of the vector operations were not getting inlined. You'll need -O2 or higher to have representative results. I could counter by just writing a Virgil program and turning off bounds check with a compiler flag. We could stare at the machine code together; it's literally an additional load, compare, and branch. The Virgil compiler loves eliminating bounds checks when it can. I know your original comment was in the context of the STL, but it really muddies the waters to see huge piles of code get inlined or not depending on compiler flags. Machine code is what matters. Regardless, this is still microbenchmarking. Maybe matrix multiply is an important kernel, but we need to benchmark whole programs. If I turn off bounds checks in a big program like the Virgil compiler, I cannot measure more than about 1.5% performance difference.
- jcelerier 5y ago
  > From the godbolt link, I just used godbolt to quickly share the code. On my computer I tried with -Ofast -march=native (broadwell) > I could counter by just writing a Virgil program and turning off bounds check with a compiler flag. We could stare at the machine code together; it's literally an additional load, compare, and branch. This sounds like Virgil is not vectorizing, which makes the comparison much less useful. I see much more than a couple instructions changed there: https://gcc.godbolt.org/z/8jPMb734x https://gcc.godbolt.org/z/8jPMb734x
  - titzer 5y ago
    > Virgil is not vectorizing That's just even more confounding variables. We are, after all, not even doing experiments with Rust vectors, which is what your original comment was about. You wrote examples in C++ and we went down a wormhole already, but I let it slip since at least it was empirical. But I think we shouldn't get distracted with even more side alleys now. Bounds checks are literally just a couple machine instructions, and often eliminated by the compiler anyway, which enables vectorization.
    - steveklabnik 5y ago
      I think you’re confusing two different senses of “vector”, there is the contiguous series of items “vector” data structure that both C++ and Rust have in their standard libraries that’s used in the code example, and there’s “vectorizing” which is an optimization to use things like SIMD to operate on multiple things at the same time.
      - titzer 5y ago
        I understood what was meant by these terms.
        steveklabnik 5y ago
        Okay, then I got lost reading your comment, my apologies.
nybble41 5y ago
Part of the problem is that the multiply() function takes variable-size matrices as inputs and isn't inlined because it's declared as an external function and so could, in theory, be called from another compilation unit. If it's declared as "static" instead then the compiler generates identical code (modulo register selection) at -Ofast for both versions—eliminating the bounds checking at compile-time: https://gcc.godbolt.org/z/qqWr1xjT8 https://gcc.godbolt.org/z/qqWr1xjT8
- jcelerier 5y ago
  > Part of the problem is that the multiply() function takes variable-size matrices as inputs so does real-life code ? I don't know about you but I pretty much never know the size of my data at compile time. > If it's declared as "static" again, real-life code calls math operations defined in other libraries, sometimes even proprietary.
  - titzer 5y ago
    In Java or other languages with bounds-checked arrays, you would typically just loop from 0 to the end of the array. In Java the JIT will analyze the loop, see that it is bounded by the length of the array, conclude all accesses are in-bounds and eliminate bounds checks. Virgil does this simple type of bounds check elimination as well in its static compiler, but its analysis is not quite as sophisticated as Java JITs.
  - nybble41 5y ago
    > I don't know about you but I pretty much never know the size of my data at compile time. Whole-program optimization (LTO) can deal with that. Also, Rust inlines across modules much more aggressively than C++ does, even without LTO, so optimization will be more effective and its bounds-checking won't have as much (if any) runtime overhead. Especially if you write your Rust code idiomatically, as others have already suggested. Your earlier Rust example was practically designed to inhibit any attempt at optimization. Simply iterating over a slice of the vector, rather than the indices, results in a much tighter inner loop as it only needs to check the bounds once. That being said, in this case I think it would be better to have fixed-size matrices (using const generic/template arguments) so that the bounds are encoded in the types and known to the compiler locally without relying on whole-program optimization.