4 ms·

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 i

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.
        titzer 5y ago
        No worries. It's too late for me to edit it now, though, but I meant vectorizing="compiler introduces SIMD".
    - jcelerier 5y ago
      > We are, after all, not even doing experiments with Rust vectors, they are very close to C++ ones, down to the stack unwinding to report the panic in case of bound error if I'm not mistaken. > That's just even more confounding variables. No they are not. We are trying to see how much bound checks costs. If you compare between suboptimal programs the comparison is meaningless (or rather not interesting to anyone) - the starting point has to be the absolute best performance that it is possible to get, and add the worst-case bound-checking (I'm happy for you if you never have to worry about the worst case though!) > Bounds checks are literally just a couple machine instructions, and often eliminated by the compiler anyway please provide a source for this ? sure, if you use spans as other commenters mentioned, that moves the checking at the span creation time but that only works for the simplest cases where you are going to access linearily - and I would say that it's a library feature rather than a compiler one. for(double v : vec) { } // or any sub-span you can take from it in C++ also does not need bound-checks by design but this kind of construct also utterly does not matter for so HPC workloads. I can look into my pdfs folders and bring out dozens of papers where the core algorithms all use funky non-linear indexing schemes where you cannot just iterate a range (algorithms based on accessing i, i-1, i+1, or accessing i and N-i, or accessing even / odd values, etc etc) - how would you implement an FFT for instance ? This is the code that matters !
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.

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.
        titzer 5y ago
        No worries. It's too late for me to edit it now, though, but I meant vectorizing="compiler introduces SIMD".
  - jcelerier 5y ago
    > We are, after all, not even doing experiments with Rust vectors, they are very close to C++ ones, down to the stack unwinding to report the panic in case of bound error if I'm not mistaken. > That's just even more confounding variables. No they are not. We are trying to see how much bound checks costs. If you compare between suboptimal programs the comparison is meaningless (or rather not interesting to anyone) - the starting point has to be the absolute best performance that it is possible to get, and add the worst-case bound-checking (I'm happy for you if you never have to worry about the worst case though!) > Bounds checks are literally just a couple machine instructions, and often eliminated by the compiler anyway please provide a source for this ? sure, if you use spans as other commenters mentioned, that moves the checking at the span creation time but that only works for the simplest cases where you are going to access linearily - and I would say that it's a library feature rather than a compiler one. for(double v : vec) { } // or any sub-span you can take from it in C++ also does not need bound-checks by design but this kind of construct also utterly does not matter for so HPC workloads. I can look into my pdfs folders and bring out dozens of papers where the core algorithms all use funky non-linear indexing schemes where you cannot just iterate a range (algorithms based on accessing i, i-1, i+1, or accessing i and N-i, or accessing even / odd values, etc etc) - how would you implement an FFT for instance ? This is the code that matters !

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.