3 ms·

What if a compiler were to only allow an array access when it can prove that it's in bounds? Wherever it can't you'd have to wrap the array access in an if, or

What if a compiler were to only allow an array access when it can prove that it's in bounds? Wherever it can't you'd have to wrap the array access in an if, or otherwise refactor your code to help the compiler. Then you'd have no panicking at least and more predictable performance.

jackmott 4y ago
tylerhou 4y ago
With bounds checking by default, even if a compiler can't statically prove that an index is in bounds, if the index in practice is always in bounds, the compiler inlines the check/branch into the calling function, and you're not starved of branch prediction resources, the check will be "free" because the branch will always be predicted as taken.
constantcrying 4y ago
>What if a compiler were to only allow an array access when it can prove that it's in bounds? Even very good static analysis tools have a hard time doing this. In a language like C++ this would effectively mean that very few index operations can be done naively and compile times are significantly increased. Performance is likely reduced as well over the trivial alternative of using a safe array.
glittershark 4y ago
there's a cheeky link to idris's vector type in the second paragraph: https://www.idris-lang.org/docs/idris2/current/base_docs/docs/Data.Vect.html https://www.idris-lang.org/docs/idris2/current/base_docs/doc... which accomplishes just that
est31 4y ago
Rust has a tool for that, it's iterators. It is only limited however.
- dathinab 4y ago
  also `slice.get()` will return on option and using a range check manually before an index will normally optimize the internal bounds check away
nigeltao 4y ago
That's how WUFFS (Wrangling Untrusted File Formats Safely) works: https://github.com/google/wuffs#what-does-compile-time-checking-look-like https://github.com/google/wuffs#what-does-compile-time-check...
- LoganDark 4y ago
  WUFFS is awesome. It won't even let you add two ints without proving they cannot overflow

jackmott 4y ago

tylerhou 4y ago

With bounds checking by default, even if a compiler can't statically prove that an index is in bounds, if the index in practice is always in bounds, the compiler inlines the check/branch into the calling function, and you're not starved of branch prediction resources, the check will be "free" because the branch will always be predicted as taken.

constantcrying 4y ago

>What if a compiler were to only allow an array access when it can prove that it's in bounds? Even very good static analysis tools have a hard time doing this. In a language like C++ this would effectively mean that very few index operations can be done naively and compile times are significantly increased. Performance is likely reduced as well over the trivial alternative of using a safe array.

glittershark 4y ago

there's a cheeky link to idris's vector type in the second paragraph: https://www.idris-lang.org/docs/idris2/current/base_docs/docs/Data.Vect.html https://www.idris-lang.org/docs/idris2/current/base_docs/doc... which accomplishes just that

est31 4y ago

Rust has a tool for that, it's iterators. It is only limited however.

dathinab 4y ago
also `slice.get()` will return on option and using a range check manually before an index will normally optimize the internal bounds check away

nigeltao 4y ago

That's how WUFFS (Wrangling Untrusted File Formats Safely) works: https://github.com/google/wuffs#what-does-compile-time-checking-look-like https://github.com/google/wuffs#what-does-compile-time-check...

LoganDark 4y ago
WUFFS is awesome. It won't even let you add two ints without proving they cannot overflow