Replace array bounds checking with modulo?

[pepp]

I don’t find the code that messy. And it is fine to opt-in for unsafe code if performance is really needed as long as it spans reasonable amount of code.

The thing is that the current behaviour should fit to majority of use-cases. And it is the safest behaviour possible. Your proposed wrap-around vector (using modulo) is memory safe but it will lead to silent error quite often. I believe that it would be regression for majority of use-cases for vectors because it is almost everytime more valuable to have correct code than extremely good performing code.

Moreover, you can create your own vector type that does modulo and uses unsafe_gets but provides memory safe interface. Only you have to avoid using slices of such vector.

[crispweed]

Anyone else have any thoughts on this? I was thinking that there are most likely faster ways than modulo to force to a non-power of 2 range, e.g. with things like compare and conditional move (but that all starts to get processor specific pretty quickly). Also, while I quite like the idea of this kind of behaviour actually being the defined behaviour of a language (!), it could also just be something that could be turned on for release builds if desired, by compile flag…

[arcto]

Rust aims to be safe, concurrent, and fast. Your proposal fails to adhere to the first goal.

It’s that simple really. The modulo is not safe. Allowing corrupt state in the program must certainly be a niche situation, not applicable to general case. If you have a situation where this is acceptable, go right ahead and create your own vector type that does this. For general usage, and for inclusion into the language, this is totally out of the question.

[arcto]

Look. If you know that your index will stay within bounds you can use the unsafe accessors that don’t do any bounds-checking at all. This is even faster than the modulo-trick or what have you.

[glaebhoerl]

Although I strongly disagree with it, Rust’s current philosophy in many cases seems to be that memory safety is paramount, but program correctness is dispensable. Using modulo instead of bounds checking would preserve memory safety, but not correctness. In that sense it would be highly consistent with (and analogous to) Rust’s current choice that integer overflow wraps around, which is nearly always wrong, but is fast and doesn’t compromise memory safety. (That is if modulo is faster than bounds checking - a benchmark would be nice.)

(All I’m saying is that there is at least a reasonable argument in favor of this proposal. But my strong preference would be to go in the opposite direction: keep the existing bounds checking and add optional overflow checks as well.)

[arielb1]

@glaebhoerl

Rust wraps on integer overflow because integer arithmetic is pure (up to UB) in all common languages (can you even find 1 counterexample?), trying not to break that almost-universal trend (and because immutability is important in Rust).

On the other hand, raising some exception on OOB access is quite common.

[Gankro]

Divide by zero is frequently quite impure. Raises exceptions or sets an error flag.

[comex]

That may be one reason for wrapping on integer overflow, but the issue has been discussed thoroughly on the mailing list in the past - it was lack of performance of overflow traps (especially where they inhibit optimization) that seemed to ruin what was otherwise a strongly desired feature.

(Also, pure up to UB isn’t really pure. It still means that evaluating the wrong expression can, and sometimes will, cause the rest of the program to work incorrectly.)

[cgaebel]

How much faster is an idiv compared to a branch?

According to www.agner.org/optimize/instruction_tables.pdf , IDIV on Haswell has a latency of 39-103 cycles. That sounds a lot more painful than a well-predicted branch.

I would only use such an optimization with arrays with power-of-two size, so that I can mask instead of divide. But in that case, I wouldn’t want such an optimization built into the language. I’d write a wrapper myself.

[crispweed]

Modulo operator is just one example, and yes this could be quite expensive, so modulo operator is probably not the best suggestion.

Another example that satisfies the same goals (certain type of safety guarantee + good performance) could be something like forcing out of range indices to zero. I’m not an expert on assembly, and this is platform dependant, but it seems like this could come down to something like a compare and then conditional move.

There’s a comment about bounds checking in this thread on reddit, btw:

Rust 0.12.0 vs C++ [Computer Language Benchmarks Game] • r/rust

And I’m not sure that the cost of checking just comes down to a single conditional. I think I saw comments somewhere else to the effect that there is also an issue with stack frame requirements (or something like that) due to the fact that bounds checking failure may need to be reported somehow…

[Gankro]

What do these proposals do when you index into an empty slice?

[cgaebel]

The cost in the not-out-of-bounds case is the same for both failing and clamping to 0, since the failure code will never be run.

It costs in terms of executable size and compile time, though, since the compiler needs to generate more code for failure than it does for clamp-to-zero. But honestly this is more the fault of failure not calling abort than the current bounds-checking strategy being sub-par.

[bfops]

If you don’t want the safety and correctness that comes with real bounds-checking, don’t use it. It seems silly to invent different kinds of bounds-checking that still add overhead and that kill correctness. Just index the pointer directly if that’s what you want.

[crispweed]

The possibility for empty slices complicate the situation, and throw a bit of a spanner in the works.

The worst case is indexed writes to potentially empty slices, I guess, but I’m thinking that indexed reads and writes could be treated differently. If there is a way to speed up indexed reads only, but not writes, then that would still seem pretty worthwhile.

But indexed reads from potentially empty slices is still a tricky case.

Maybe it would be possible to require all arrays to hold an extra sentinel value, and then just read off the end of the slice. (Messier, but can still provide meaningful memory safety guarantees.)

In some situations it would be ok to read from some global zero filled memory space, I guess, since, in some situations, zero filled memory can work as valid default object initialisation. (I’m thinking about C# structs, for example.)

I don’t know enough about rust, to know whether any of this is actually workable, though…

[crispweed]

Or treat empty slices differently.

Most extreme would be to disallow empty slices completely. But that would be very annoying, of course, because it would add the need for special case checks in a bunch of places where no special case checks were previously required.

Or, extend the type system to include some extra information which can be used to compile differently (without bounds checking). e.g. Allow me to specify for some slice type that the slice is not permitted to be empty.

[crispweed]

The cost in the not-out-of-bounds case is the same for both failing and clamping to 0, since the failure code will never be run.

I’m assuming that it will be possible to do clamping without a branch on at least some architectures, e.g. with conditional move on x86 and x64, and that this should then be faster. I don’t have any proof of concept, however, or benchmark, to show this in practice…

[crispweed]

Some relevant benchmarking here: http://danluu.com/integer-overflow/ (AMD64)

He compares estimated and measured performance costs for branch on integer overflow, so this seems quite similar to a lot of branch on range bound exceeded cases, but with the difference that branch on range bound exceeded will also need:

• a cmp instruction, and
• the bound to be brought in from memory, or use up a register

It seems like the branch on overflow basically gets set up to be correctly predicted for the not overflowing case, and I guess the same is likely to happen for branch on range bound exceeded.

My take away (for the branch on overflow case, at least), is that the theoretical cost of this is really not so bad. The actual cost can be very significant, but it seems like this is something that should be fixed at the level of the compiler…

[crispweed]

Another interesting blog post on this subject:

http://bluishcoder.co.nz/2013/05/07/ranged-integer-types-and-bounds-checking.html

This kind of system with ranges actually coded into types statically is what I would need to be able to code something like PathEngine both memory safely and efficiently, I think…

[John_Nagle]

If there’s a performance problem with subscript checking, that should be looked into. If you write that inner loop in a straightforward way, is the compiler missing an optimization? Could the subscript check be hoisted out of the loop.

That code looks like something transliterated from C. Would a redesign help?

[system]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.