7 ms·

Always amuses me that it's current year and people think about turning off checks, even when they're pretty much free in modern* (since 1993 Pentium, which got

by Jach 4y ago

Always amuses me that it's current year and people think about turning off checks, even when they're pretty much free in modern* (since 1993 Pentium, which got like 80% accuracy with its primitive branch prediction?) CPUs... "Around Easter 1961, a course on ALGOL 60 was offered … After the ALGOL course in Brighton, Roger Cook was driving me and my colleagues back to London when he suddenly asked, "Instead of designing a new language, why don't we just implement ALGOL60?" We all instantly agreed--in retrospect, a very lucky decision for me. But we knew we did not have the skill or experience at that time to implement the whole language, so I was commissioned to design a modest subset. In that design I adopted certain basic principles which I believe to be as valid today as they were then. "(1) The first principle was security: The principle that every syntactically incorrect program should be rejected by the compiler and that every syntactically correct program should give a result or an error message that was predictable and comprehensible in terms of the source language program itself. Thus no core dumps should ever be necessary. It was logically impossible for any source language program to cause the computer to run wild, either at compile time or at run time. A consequence of this principle is that every occurrence of every subscript of every subscripted variable was on every occasion checked at run time against both the upper and the lower declared bounds of the array. 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." -Tony Hoare, 1980 Turing Award Lecture (https://www.cs.fsu.edu/~engelen/courses/COP4610/hoare.pdf https://www.cs.fsu.edu/~engelen/courses/COP4610/hoare.pdf)

titzer 4y ago
> 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. Here we are, 42 years later, and bounds checks are still not the default in some languages. Because performance, or something. And our computers are literally 1000x as fast as they were in 1980. So instead of paying 2% in bounds checks and getting a merge 980x faster, we get 2-3x more CVEs, costing the economy billions upon billions of dollars a year.
- nine_k 4y ago
  Removing bounds checks is a stark example of a premature optimization. You can remove bounds checks when you can prove that the index won't ever get out of bounds; this is possible in many cases, such as iteration with known bounds.
  - 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.
dataangel 4y ago
They’re nowhere near free. Branch prediction table has finite entries, instruction cache has finite size, autovectorizing is broken by bounds checks, inlining (the most important optimization) doesn’t trigger if functions are too big because of the added bounds checking code, etc. This is just not great benchmarking — no effort to control for noise.
- deleted 4y ago
  [deleted]
- dahfizz 4y ago
  > autovectorizing is broken by bounds checks This is the big one. You pay a 50% penalty for actual CPU bound, iteration heavy code with bounds checking enabled. https://github.com/matklad/bounds-check-cost https://github.com/matklad/bounds-check-cost
  - camkego 4y ago
    This should be the article. Running this with 1.65 on an Intel 12400 gets a nearly 4x speedup when bounds checking is not needed. Just wow. Bounds checking avoidance is important when it becomes a significant chunk of your hot-path.
  - zozbot234 4y ago
    The proper way of addressing that is to manually hoist bound checks out of "hot" loops. Not just remove them altogether.
- moloch-hai 4y ago
  For real programs, you should demand that the compiler hoist such checks out of the loop, which may then be vectorized the usual way. If the compiler can't do that by itself, a library should do it. The real issue is whether the information about the true size of the memory region involved is available at the point where it is needed. This may come down to how good the language is at capturing desired semantics in a library. Rust still has a long way to go to catch up with C++ on this axis, and C++ is not waiting around. Rust claims responsibility for enforcing safety in the compiler, with libraries using "unsafe" to delegate some of that to themselves. Users then trust the compiler and libraries to get it right. In C++, the compiler provides base semantics while libraries take up the whole responsibility for safety. Users can trust libraries similarly as in Rust, to similar effect. Modern C++ code typically does no visible operations with pointers at all, and most often does not index directly in arrays, preferring range notation, as in Rust, achieving correctness by construction. A correct program is implicitly a safe program.
fear91 4y ago
I have removed signed-integer based values bounds checking in a compiler once and before I noticed, I got a nice 3.8% performance gain in a large diverse benchmarking suite. While not expensive, bounds checks are certainly not free.
- kelnos 4y ago
  And that's the thing, really. Sure, they're not free, but they're pretty cheap. In a project like OpenSSL, if C had bounds checking, it should be enabled, all the time. Sure, disable it for some random bit of custom high-perf software where you really need to eke out the last few percent of performance. But for 99% of everything else, leave the bounds checking turned on.
  - netr0ute 4y ago
    I don't know, because if you're writing programs for things like IoT or embedded, then you're dealing with nothing but wimpy little low power processors where removing a bounds check gives you huge increases. Then, it makes no sense to have checks by default if you're going to get rid of them anyway.
    - skyde 4y ago
      if it’s a 4% gain. then it’s the same 4% game no matter if running on a big fast cpu or a 8bit micro controller. right?
      - bluecalm 4y ago
        It isn't because those microcontrollers are not that smart about branch prediction and instruction ordering so the penalty is often bigger. Same with reordering - might not matter that much on a big modern CPU but may matter way more on a device with a micro cache and very slow division for example.
    - Gibbon1 4y ago
      I'll just point out that a wimpy low power processor that costs less than a buck has as much processing power as a 486. And the amount of processing tends to be on small amounts of data in short bursts. Big problem as I see it is compiler writers using C++ with it's completely broken language and compilation model. Of course they think speed is the only important metric because C++ compilers compiling C++ compilers is very very slow. And they're dealing with trusted data 100% of the time and not the guys desperately trying to patch a zero day vulnerability at 2am.
userbinator 4y ago
If you want to experience what using a "safe" language looks like, complete with bounds checking amongst other things, there's the JavaScript ecosystem. ...which has evolved its own, much worse, horrors instead. Before that, there was Java. Do not want.

by Jach 4y ago

titzer 4y ago

> 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. Here we are, 42 years later, and bounds checks are still not the default in some languages. Because performance, or something. And our computers are literally 1000x as fast as they were in 1980. So instead of paying 2% in bounds checks and getting a merge 980x faster, we get 2-3x more CVEs, costing the economy billions upon billions of dollars a year.

nine_k 4y ago
Removing bounds checks is a stark example of a premature optimization. You can remove bounds checks when you can prove that the index won't ever get out of bounds; this is possible in many cases, such as iteration with known bounds.
- 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.

dataangel 4y ago

They’re nowhere near free. Branch prediction table has finite entries, instruction cache has finite size, autovectorizing is broken by bounds checks, inlining (the most important optimization) doesn’t trigger if functions are too big because of the added bounds checking code, etc. This is just not great benchmarking — no effort to control for noise.

deleted 4y ago
[deleted]
dahfizz 4y ago
> autovectorizing is broken by bounds checks This is the big one. You pay a 50% penalty for actual CPU bound, iteration heavy code with bounds checking enabled. https://github.com/matklad/bounds-check-cost https://github.com/matklad/bounds-check-cost
- camkego 4y ago
  This should be the article. Running this with 1.65 on an Intel 12400 gets a nearly 4x speedup when bounds checking is not needed. Just wow. Bounds checking avoidance is important when it becomes a significant chunk of your hot-path.
- zozbot234 4y ago
  The proper way of addressing that is to manually hoist bound checks out of "hot" loops. Not just remove them altogether.
moloch-hai 4y ago
For real programs, you should demand that the compiler hoist such checks out of the loop, which may then be vectorized the usual way. If the compiler can't do that by itself, a library should do it. The real issue is whether the information about the true size of the memory region involved is available at the point where it is needed. This may come down to how good the language is at capturing desired semantics in a library. Rust still has a long way to go to catch up with C++ on this axis, and C++ is not waiting around. Rust claims responsibility for enforcing safety in the compiler, with libraries using "unsafe" to delegate some of that to themselves. Users then trust the compiler and libraries to get it right. In C++, the compiler provides base semantics while libraries take up the whole responsibility for safety. Users can trust libraries similarly as in Rust, to similar effect. Modern C++ code typically does no visible operations with pointers at all, and most often does not index directly in arrays, preferring range notation, as in Rust, achieving correctness by construction. A correct program is implicitly a safe program.

fear91 4y ago

I have removed signed-integer based values bounds checking in a compiler once and before I noticed, I got a nice 3.8% performance gain in a large diverse benchmarking suite. While not expensive, bounds checks are certainly not free.

kelnos 4y ago
And that's the thing, really. Sure, they're not free, but they're pretty cheap. In a project like OpenSSL, if C had bounds checking, it should be enabled, all the time. Sure, disable it for some random bit of custom high-perf software where you really need to eke out the last few percent of performance. But for 99% of everything else, leave the bounds checking turned on.
- netr0ute 4y ago
  I don't know, because if you're writing programs for things like IoT or embedded, then you're dealing with nothing but wimpy little low power processors where removing a bounds check gives you huge increases. Then, it makes no sense to have checks by default if you're going to get rid of them anyway.
  - skyde 4y ago
    if it’s a 4% gain. then it’s the same 4% game no matter if running on a big fast cpu or a 8bit micro controller. right?
    - bluecalm 4y ago
      It isn't because those microcontrollers are not that smart about branch prediction and instruction ordering so the penalty is often bigger. Same with reordering - might not matter that much on a big modern CPU but may matter way more on a device with a micro cache and very slow division for example.
  - Gibbon1 4y ago
    I'll just point out that a wimpy low power processor that costs less than a buck has as much processing power as a 486. And the amount of processing tends to be on small amounts of data in short bursts. Big problem as I see it is compiler writers using C++ with it's completely broken language and compilation model. Of course they think speed is the only important metric because C++ compilers compiling C++ compilers is very very slow. And they're dealing with trusted data 100% of the time and not the guys desperately trying to patch a zero day vulnerability at 2am.

userbinator 4y ago

If you want to experience what using a "safe" language looks like, complete with bounds checking amongst other things, there's the JavaScript ecosystem. ...which has evolved its own, much worse, horrors instead. Before that, there was Java. Do not want.