> Some “managed” programming languages do automatic, compulsory range checks on array accesses, and invoke some kind of error condition if the array access is out of bounds.
Not some. All languages besides C and its direct descendent (not counting Forth and Assembly here).
Other system programming languages, even older than C used to do it.
As Hoare so elegantly described at his Turing award speech, regarding Algol compilers:
"Many years later we asked our customers whether they wished
us to provide an option to switch off these checks in the interests of efficiency on production runs. Unanimously, they urged us not to--they already knew how frequently subscript errors occur on production runs where failure to detect them could be disastrous. I note with fear and horror that even in 1980, language designers and users have not learned this lesson. In any respectable branch of engineering, failure to observe such elementary precautions
would have long been against the law."
Optimizing bounds checks in compilers is very important for performance, and, as the article points out, often the bounds checks can be completely optimized out. This was done in at least one Pascal compiler in the 1980s, but the technology has been lost. Now it's needed in Go and Rust.
The article extends range checking for compilers to handle the case where the index variable wraps around due to arithmetic overflow, as intended behavior. This is neat, but isn't a real problem.
LLVM is already capable of eliminating bounds checks and Rust is designed to avoid straight array indexing anyway. I have repeatedly asked the Servo developers if they've ever had to think about bounds checking and the answer is that it's not shown up even once in performance profiles.
Much like the noise over the loss of O(1) string indexing, worries about automatic bounds checks seem to be nothing more than developers clutching their pearls over antiquated best practices that amount to premature optimization at best.
" I have repeatedly asked the Servo developers if they've ever had to think about bounds checking and the answer is that it's not shown up even once in performance profiles."
That's because the problem they're solving isn't array-oriented. Try running LINPACK benchmarks, matrix multiplies, etc.
(Annoyingly, both Go and Rust lack first-class multidimensional arrays. Arrays of arrays are not the same thing.)
I.e. like C++'s eigen or Python's numpy? I'm sure that Rust and Go can take the same approach: implement it in libraries. E.g. https://github.com/bluss/rust-ndarray is a Rust library for it.
I'm sure you'll be sad that this takes `unsafe` to do performantly, but embedding it in the language is no different (the burden of proof just switches from "is this code safe" to "is the code that this code generates safe", and the latter is a harder question).
Not only does that crate use unsafe code, it exports unsafe operations:
unsafe fn uchk_at<'a>(&'a self, index: D) -> &'a A
Perform unchecked array indexing.
Return a reference to the element at index.
Note: only unchecked for non-debug builds of ndarray.
There's no subscript checking optimization for the operations there at all. If you use the safe "at" operation, you get back a "Some" or "None". Here's the basic operation of subscripting:
/// Return a reference to the element at **index**, or return **None**
/// if the index is out of bounds.
pub fn at<'a>(&'a self, index: D) -> Option<&'a A> {
self.dim.stride_offset_checked(&self.strides, &index)
.map(|offset| unsafe {
to_ref(self.ptr.offset(offset) as *const _)
})
}
"I don't see why exposing unsafe operations is problematic: the crate's user still has to explicitly decide to use them if desired."
Duh. The fact that someone felt it necessary to expose unsafe array access to the user indicates that the checking optimization has an overhead problem.
I struggle to believe that subscript checking can be automatically removed in arbitrary code in any language (at least, not without full dependent typing), e.g. it seems pretty hard to make guarantees about something like x[y[i]] with arbitrary y.
I don't understand why you are so insistent that the technology has been lost, e.g. it's been pointed out to you before that LLVM can do optimisations in this vein via its IRCE pass[1] and I believe there are other passes that touch on these sort of things (and I'm sure that GCC isn't bad at it either).
That's for the easy case of iterating through an array sequentially. Of course, in languages with only 1D arrays, most of the hard cases don't come up. The classic is a matrix multiply, where you're progressing through one array on one axis and a second array on the other axis using the same index variable.
It's still fundamentally the same "shape" of iteration:
some_operation(x[i,j], y[j,i])
has checks essentially looking like:
if (i < min(x.n, y.m) && j < min(x.m, y.n)) {
// do things
} else {
out_of_bounds()
}
and moving each of those outside their respective loops should work with IRCE-style optimisations.
E.g. -O3 with clang 3.5.0 and gcc 4.9.2 leave only one comparison (out of 4) in the inner loop the following implementation of transpose (I've tried to make it mirror what the "obvious" implementation in a high-level language would do, i.e. bounds check accesses to y and then separately bounds check them to x, but the precise details don't seem to make much difference):
#include<stdlib.h>
void transpose(float * restrict x, size_t xn, size_t xm,
const float * restrict y, size_t yn, size_t ym) {
size_t i, j;
if (xn != ym || xm != yn) {
abort();
}
for (i = 0; i < yn; i++) {
for (j = 0; j < ym; j++) {
float tmp;
if (i < yn && j < ym) {
tmp = y[ym * i + j];
} else {
abort();
}
if (i < xm && j < xn) {
x[xm * j + i] = tmp;
} else {
abort();
}
}
}
}
And, if I use clang 3.7 and run the LLVM output through `opt-3.7 -irce -O3` (since IRCE isn't enabled in clang by default), then the inner loop has no bounds checks and is even unrolled once:
In any case, naive code in this manner is not a good way to write high-performance code for modern CPUs: iterating with large strides (i.e. b > 1, per the article's notation) is a bad memory access pattern for caches, and optimising memory accesses has a much larger impact than bounds checking. Point is: it's a bit of a strawman to talk about performance with such an example since these naive algorithms just aren't good enough if performance matters.
Not some. All languages besides C and its direct descendent (not counting Forth and Assembly here).
Other system programming languages, even older than C used to do it.
As Hoare so elegantly described at his Turing award speech, regarding Algol compilers:
"Many years later we asked our customers whether they wished us to provide an option to switch off these checks in the interests of efficiency on production runs. Unanimously, they urged us not to--they already knew how frequently subscript errors occur on production runs where failure to detect them could be disastrous. I note with fear and horror that even in 1980, language designers and users have not learned this lesson. In any respectable branch of engineering, failure to observe such elementary precautions would have long been against the law."