4 ms·

Isn't this a job for the compiler? The default would be to have boundary checking, but if the compiler can prove that the index is always in range it can drop

by femto 4y ago

Isn't this a job for the compiler? The default would be to have boundary checking, but if the compiler can prove that the index is always in range it can drop the boundary check. From the user's perspective, the boundary check is always there. Most vector operations would have provable boundaries. Edit: Based on the benchmark code linked to in dahfizz 's comment, it seems that Rust does the above for vectors, but there are situations where the bounds can't be proved, so boundary checking can't be removed. How common is this case in practice?

moloch-hai 4y ago
To omit the check, the compiler would need to know that the loop range matches or subtends the array bound. That is commonly easy for built-in arrays, uncommonly for user-defined types. Most types are user-defined. We trust the library author to get it right, despite (in Rust) wrapping accesses in "unsafe" or (in C++) not. Compilers are not particularly better at everything than library authors.
- titzer 4y ago
  > would need to know that the loop range matches or subtends the array bound Some compilers have pretty sophisticated analyses aimed at just that: determining affine relations to statically bound indexed accesses. Failing that, some compilers will resort to loop versioning, generating two versions of the loop and then partitioning the iteration space into the definitely-in-bounds range from possibly-out-of-bounds range, then selecting which portions of which loop to execute by prefixing both with dynamic checks. Couple all of that with peeling and unrolling, and bounds checks start disappearing and getting amortized away.
  - moloch-hai 4y ago
    Libraries can do this too, in many cases more reliably.
    - titzer 4y ago
      Unless libraries are receiving a copy of the meta representation of the program and running integer equality relations over the dataflow chains, then no, not really.
      - moloch-hai 4y ago
        Yet, really. The library author has certain knowledge of what the library is meant to achieve, where the compiler is obliged to guess according to whatever tea leaves it can find to descry. In particular, the library author knows that the container won't be changing size over the duration of the loop, something the compiler would have difficulty proving.
        MaxBarraclough 4y ago
        > The library author has certain knowledge of what the library is meant to achieve What's special about libraries? Every programmer has such knowledge, and every programmer writes buggy code.
        moloch-hai 4y ago
        What's special about compilers, then? Compilers are code, and therefore, as you say, buggy. Library authors know things about what their code is meant to be doing that compilers cannot deduce, so cannot act on. But the library author can. A library, according to how heavily it is used, benefits from more thorough testing than generic application code gets.
        MaxBarraclough 4y ago
        You're right that compilers tend to have bugs, but in practice, compiler bugs are rarely the cause of software issues. The same cannot be said of libraries. Major SSL/TLS libraries for instance tend to be written in C, and all of them have had memory-safety bugs. > Library authors know things about what their code is meant to be doing that compilers cannot deduce, so cannot act on. But the library author can. I don't see your point here. > A library, according to how heavily it is used, benefits from more thorough testing than generic application code gets This doesn't generalise. There's plenty of very widely used application-specific code, and there's plenty of little used library code. Also, widespread use does not imply a high level of scrutiny, even if we're talking only about Free and Open Source software. Anyway, that's all a sidetrack. The benefits of memory-safe languages aren't up for debate, even for well-scrutinised codebases. We continue to suffer a stream of serious security vulnerabilities arising from memory-safety issues in code written in unsafe languages. The go-to example is Chromium, where 70% of serious security issues are due to memory safety. [0] [0] https://www.chromium.org/Home/chromium-security/memory-safety/ https://www.chromium.org/Home/chromium-security/memory-safet...

by femto 4y ago

moloch-hai 4y ago

To omit the check, the compiler would need to know that the loop range matches or subtends the array bound. That is commonly easy for built-in arrays, uncommonly for user-defined types. Most types are user-defined. We trust the library author to get it right, despite (in Rust) wrapping accesses in "unsafe" or (in C++) not. Compilers are not particularly better at everything than library authors.

titzer 4y ago
> would need to know that the loop range matches or subtends the array bound Some compilers have pretty sophisticated analyses aimed at just that: determining affine relations to statically bound indexed accesses. Failing that, some compilers will resort to loop versioning, generating two versions of the loop and then partitioning the iteration space into the definitely-in-bounds range from possibly-out-of-bounds range, then selecting which portions of which loop to execute by prefixing both with dynamic checks. Couple all of that with peeling and unrolling, and bounds checks start disappearing and getting amortized away.
- moloch-hai 4y ago
  Libraries can do this too, in many cases more reliably.
  - titzer 4y ago
    Unless libraries are receiving a copy of the meta representation of the program and running integer equality relations over the dataflow chains, then no, not really.
    - moloch-hai 4y ago
      Yet, really. The library author has certain knowledge of what the library is meant to achieve, where the compiler is obliged to guess according to whatever tea leaves it can find to descry. In particular, the library author knows that the container won't be changing size over the duration of the loop, something the compiler would have difficulty proving.
      - MaxBarraclough 4y ago
        > The library author has certain knowledge of what the library is meant to achieve What's special about libraries? Every programmer has such knowledge, and every programmer writes buggy code.
        moloch-hai 4y ago
        What's special about compilers, then? Compilers are code, and therefore, as you say, buggy. Library authors know things about what their code is meant to be doing that compilers cannot deduce, so cannot act on. But the library author can. A library, according to how heavily it is used, benefits from more thorough testing than generic application code gets.
        MaxBarraclough 4y ago
        You're right that compilers tend to have bugs, but in practice, compiler bugs are rarely the cause of software issues. The same cannot be said of libraries. Major SSL/TLS libraries for instance tend to be written in C, and all of them have had memory-safety bugs. > Library authors know things about what their code is meant to be doing that compilers cannot deduce, so cannot act on. But the library author can. I don't see your point here. > A library, according to how heavily it is used, benefits from more thorough testing than generic application code gets This doesn't generalise. There's plenty of very widely used application-specific code, and there's plenty of little used library code. Also, widespread use does not imply a high level of scrutiny, even if we're talking only about Free and Open Source software. Anyway, that's all a sidetrack. The benefits of memory-safe languages aren't up for debate, even for well-scrutinised codebases. We continue to suffer a stream of serious security vulnerabilities arising from memory-safety issues in code written in unsafe languages. The go-to example is Chromium, where 70% of serious security issues are due to memory safety. [0] [0] https://www.chromium.org/Home/chromium-security/memory-safety/ https://www.chromium.org/Home/chromium-security/memory-safet...