Rust's Vec indexing is bound-checked by default. Just something like this is abysmal for performance (but pretty good for consultants who get called to fix stuff afterwards, so, like, keep them coming!):
> 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.
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).
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.
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.
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.
> 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 !
A compiler can do loop versioning for that. And they do. Hotspot C2 (and Graal, too) does a ton of loop optimizations, partitioning the index space into in-bounds and potentially out-of-bounds ranges, unrolling loops, peeling the first iteration off a loop, generating code before a loop to dispatch to a customized version if everything will be in bounds.
When a compiler is doing that sophisticated of loop transforms, you are not measuring the cost of bounds checks anymore, you are measuring a whole host of other things. And sometimes if a loop is just a little different, the results can be disastrously bad or miraculously good. Which is why microbenchmarking is so fraught with peril. A microbenchmark might be written assuming a simple model of the computation and then a sophisticated compiler with analyses never dreamed of comes along and completely reorganizes the code. And it cuts both ways; a C++ compiler might do some unrolling, fusion, tiling, vectorization, software pipelining or interchange on your loops and suddenly you aren't measuring bounds check cost anymore, but loop optimization heuristics that have been perturbed by their presence. You end up studying second-order effects and not realizing it. And it keeps running away from you the more you try to study it.
>> 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
We are always comparing suboptimal programs. No compiler is producing optimal code, otherwise they would dead-code eliminate everything not explicitly intertwined into program output, statically evaluate half of our microbenchmarks, and replace them with table lookups.
You're going down a linear algebra rabbit hole trying to come up with a result that paints bounds checks in the worst possible light. If this is the real problem you have, maybe your linear algebra kernels would be better off just using pointers, or you could even try Fortran or handwritten assembly instead, if it is so important. Unsafe by default is bad IMHO. For real programs bounds checks really don't matter that much. Where this thread is going is all about loop optimizers, and they don't really get a chance to go nuts on most code, so I think we're way off in the weeds.
Note that Rust has unchecked index, you just have to explicitly ask for that if you want it. You can even - if you just insist on writing cursed code - which it seems jcelerier is, write your own type in which the index is always unchecked and it is Undefined Behaviour when you inevitably make a mistake. Just implement std::ops::Index and if you also want to mutate these probably invalid indices, std::ops::IndexMut and in your implementation say you're unsafe and just don't bother doing bounds checks.
You can shoot yourself in the foot with Rust, it's just that you need to explicitly point a loaded gun at your foot and pull the trigger, whereas C++ feels like any excuse to shoot you in the foot is just too tempting to ignore even if you were trying pretty hard not to have that happen.
C++ devs that actually care about security the same way as titzer, do turn on the security checks that are disabled by default, thus you can have a same experience.
Example, on Visual Studio define _ITERATOR_DEBUG_LEVEL to 1, enable /analize as part of the build.
While not Rust like, it is already much better than not caring.
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.
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:
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.
> 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.
> 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.
This is pretty much word-for-word what I've seen in other similar disagreements. Rust Skeptic transcribes their solution from its original programming language into Rust line by line, producing something nobody using Rust would actually write. They find that Rust performs poorly. Rust Proponent writes it the way you'd expect someone who actually knows Rust to write it, and performance meets or exceeds the original. Sometimes they even catch a few bugs.
Yes, if you don't know Rust, and you think it's just a weird re-skin of C++ that can be gsub'd from one to another, you're going to have a bad time. If you're an expert in C++ and have never written Rust, you probably aren't going to beat your finely-tuned C++ program with a ten minute Rust translation. But someone with a year of experience in Rust is probably going to be able to rewrite it in half an hour and come within spitting distance of the thing you've optimized by hand over the course of a few years.
I've written Rust for half a decade and I'm not sure I've ever actually explicitly indexed into a Vec or slice in production code. If I needed to, and it was in a hot loop, and it wasn't a fixed-size array whose size is known at compile time... there's always `get_unchecked()` which is functionally identical to indexing into a C++ vec without `at`.
etc ... which is in general code from science papers written in pseudocode which is ported at 2AM by tired astrophysics or DSP masters students to have something to show to their advisor. You can have whatever abstraction you want but they won't be used because the point is not to write rust or C++ or anything but to get some pseudo-MATLABish thing to run ASAP, and that won't have anything that looks like range / span, only arrays being indexed raw.
If you were using std::vector::at (the proper way), you'd have bounds checking as well. One should only direct index if they really know that they are inside the bounds. And in Rust, there's std::vec::Vec::get_unchecked: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.get...
Yeah I agree using vector::at is a common and fairly bad anti-pattern.
So long as you make sure your program is correct you never need to worry about indices being out of bounds. Requiring bounds checking is a sign you need to eliminate the errors in your software.
This makes me wonder, why are people writing software with errors in it in the first place? Even master programmers seem to be too lazy and careless to remove the errors from their software. What gives?
That is why I write all my code in Pascal, where you can enable bound checking for []
Enable it for a debug build, and you an be sure there are no overflows of any kind, and when it runs the program has pretty much no errors at all. Disable it for the release build, and it runs as fast as if it was written in C
Here is a honest answer. The problem is frankly unsolvable thanks to the halting problem. It's impossible to determine in general whether a program is going to reach a certain state except by testing all potential inputs and even that is only going to give you an approximate answer. If it were possible we would have written a program that solves the problem through static analysis.
Idiomatic Rust here would use something like this, not that in this case it makes them performance identical, but it is more representative of real Rust code, and is slightly smaller https://rust.godbolt.org/z/brh6heEKE
EDIT: lol don’t write code five minuets after waking, the reply to this has far better code
(EDIT: incidentally, I was also curious about a non-extern function, but the compiler is seeing through all of my attempts to call a native Rust function with an opaque body here...)
That being said this code will also be a no-op instead of... something worse, if the vector is empty, so, they're not directly comparable, but they weren't really in the first place, as you mention, so...
>but pretty good for consultants who get called to fix stuff afterwards, so, like, keep them coming!):
I'm confused. Doesn't that apply to the C cowboy way of doing things? You introduce security vulnerability after vulnerability and then lots of people have to hire expert security consultants all the time. Your snark just makes no sense to me. Fixing an ArrayOutOfBoundsException in Java is something even a novice programmer with less than a year experience can do. No expensive consultant needed.
The Java vulnerabilities aren't even in the same class as C. They are usually quite dumb shit like class loading remote class files using obsolete features that nobody even remembers (log4shell). It's like setting up ssh with a default password (raspberry pi). It happens but it's rare because of the sheer amount of "incompetence" required that it requires lightning to strike twice.
Sometimes they're called auditors. Or "formal audits" because people think if they call something "formal" it's somehow different from not being "formal".
I mean, I know that this is a business that exists, what I mean is that I get called regularly for fixing performance things, but have never heard of any request for security - or met security consultants during my jobs. However I know of a few cases where people would sell members of their extended family in a heartbeat for a % more oomph.
And look, putting a limit that the compiler and guarantee once outside the critical loop eliminates it. You're already using unsafe. If you really want to shoot yourself in the foot with this nonsense you can use a get unchecked or an unchecked assumption
The point is to have some code that exhibits what happens when a bound check is needed. You can also do
for(double v : std::span(vec).subspan(1)) { }
in C++ and that will be safe and not need a bound check except an user-provided one at the creation of the span (-1 for C++ here :-)) - and also not matter at all regarding the bound checks problem which will occur as soon as you don't just iterate linearly which is extremely common in the kind of problems that end up showing at the top of the profiler and the whole point of this conversation.
- Rust: https://rust.godbolt.org/z/GK8WY599o
- CPP: https://gcc.godbolt.org/z/qvxzKfv8q