3 ms·

Over a library used by billions of people a lot of times a day, those bounds checks add up to a lot of wasted time and energy if you don't strictly need them.

Over a library used by billions of people a lot of times a day, those bounds checks add up to a lot of wasted time and energy if you don't strictly need them. If this is a common function in the webp library, this function is probably called something like a trillion times a day.

kevincox 3y ago
They aren't wasted if they are preventing security vulnerabilities. I also wouldn't be surprised if patching, rebuilding and distributing this fixed version of libwebp to all of these devices would be comparable to the extra cost of decoding.
- pclmulqdq 3y ago
  "Preventing security vulnerabilities" is not an unadulturated good (the most secure computer does nothing but checking to make sure it hasn't been breached), and any bounds check that does not actively prevent an intrusion is wasted from a value perspective. Your intuition about the cost of a patch vs the extra instructions in the hot path to check bounds everywhere is also very much wrong: the cost of a patch (which is also amortized among many fixes) is not even close. The hot path adds up when you call it a lot.
  - saagarjha 3y ago
    The most secure computer does nothing, because checking if it has been breached is attack surface.
ctz 3y ago
I think your intuition on the cost of not-taken bounds check branches is off, especially in the context of devices that spend most of their resources browsing the web, running radios, powering screen backlights. I bet any holistic measurement could not tell the difference.
- kps 3y ago
  > … resources browsing the web, running radios That's the whole point of webp, though.
- pclmulqdq 3y ago
  Not-taken branches and filling your superscalar slots with extra instructions costs 0 time, but they still cost energy.
aidenn0 3y ago
The past 40+ years of CS research has created a huge number of tools for reducing the costs of memory safety. Some of these made it into Rust, but others are sitting in (often abandoned) academic projects. It is an abject failure of industry that we are still parsing untrusted input in languages like C. WebP gets a slight pass because the code is so old; WebP is at least partly based on code from On2 that extends back at least until the early '00s. Rewriting working code is always going to be lower priority than writing new code (and it's not always a safety win either; being deployed for 10 years gets you an awful lot of real-world testing!). But look at implementations for newer image formats and you see more of the same; C and C++ with the token java implementation that won't get used outside of the JVM.
- pclmulqdq 3y ago
  C and C++ are often used because at the optimization level that these sorts of libraries use, Rust makes tradeoffs that do not work out to 0 overhead. I would personally suggest that Google et al invest in figuring out how to make "formally-verified C" a more widely adopted language for libraries that are truly security-critical.
  - pjmlp 3y ago
    People should learn to use profilers, not even C and C++ do zero overhead versus writing in pure Assembly. Maybe WEBP should have been written in Assembly, all the speed and I bet quite safe. /s
  - namibj 3y ago
    C safe enough to use for parsing untrusted input like this needs to be either formally verified to be safe (not to be correct, at least it's it's the canonical implementation), or written in an intrinsically memory-safe way which humans can fully reason about the safety of. And at that latter point it's slower than Rust. (Not too mention that Rust's awareness of memory lifetimes enables substantial optimizations beyond plain C code that quite often result in faster code at the same level of effort.)
chlorion 3y ago
Apple has actually measured the impact of adding bounds checking to commonly used libraries including media libraries and found no impact on overall power use. Audio and video encoding libraries took around a 1% performance impact. https://llvm.org/devmtg/2023-05/slides/TechnicalTalks-May11/01-Na-fbounds-safety.pdf https://llvm.org/devmtg/2023-05/slides/TechnicalTalks-May11/... I don't think there is any evidence to support that bounds checking causes any significant increase in power consumption, and measurements currently available such as shown above show minimal runtime performance impact. Bounds checking is the perfect situation for branch predictors, 99.9% of the time the branch is predicted correctly, and when it's not it doesn't matter because you're probably aborting the program! There's also the point that you can opt out of bounds checking as-needed on hot loops if you really need to. There is no technological reason to not use bounds checking as the default mode of operation today.
- pjmlp 3y ago
  There is no technological reason to not use bounds checking as the default mode of operation since ALGOL exists. My favourite quote, C.A.R Hoare's "The 1980 ACM Turing Award Lecture" "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." -- https://www.labouseur.com/projects/codeReckon/papers/The-Emperors-Old-Clothes.pdf https://www.labouseur.com/projects/codeReckon/papers/The-Emp...

kevincox 3y ago

They aren't wasted if they are preventing security vulnerabilities. I also wouldn't be surprised if patching, rebuilding and distributing this fixed version of libwebp to all of these devices would be comparable to the extra cost of decoding.

pclmulqdq 3y ago
"Preventing security vulnerabilities" is not an unadulturated good (the most secure computer does nothing but checking to make sure it hasn't been breached), and any bounds check that does not actively prevent an intrusion is wasted from a value perspective. Your intuition about the cost of a patch vs the extra instructions in the hot path to check bounds everywhere is also very much wrong: the cost of a patch (which is also amortized among many fixes) is not even close. The hot path adds up when you call it a lot.
- saagarjha 3y ago
  The most secure computer does nothing, because checking if it has been breached is attack surface.

ctz 3y ago

I think your intuition on the cost of not-taken bounds check branches is off, especially in the context of devices that spend most of their resources browsing the web, running radios, powering screen backlights. I bet any holistic measurement could not tell the difference.

kps 3y ago
> … resources browsing the web, running radios That's the whole point of webp, though.
pclmulqdq 3y ago
Not-taken branches and filling your superscalar slots with extra instructions costs 0 time, but they still cost energy.

aidenn0 3y ago

The past 40+ years of CS research has created a huge number of tools for reducing the costs of memory safety. Some of these made it into Rust, but others are sitting in (often abandoned) academic projects. It is an abject failure of industry that we are still parsing untrusted input in languages like C. WebP gets a slight pass because the code is so old; WebP is at least partly based on code from On2 that extends back at least until the early '00s. Rewriting working code is always going to be lower priority than writing new code (and it's not always a safety win either; being deployed for 10 years gets you an awful lot of real-world testing!). But look at implementations for newer image formats and you see more of the same; C and C++ with the token java implementation that won't get used outside of the JVM.

pclmulqdq 3y ago
C and C++ are often used because at the optimization level that these sorts of libraries use, Rust makes tradeoffs that do not work out to 0 overhead. I would personally suggest that Google et al invest in figuring out how to make "formally-verified C" a more widely adopted language for libraries that are truly security-critical.
- pjmlp 3y ago
  People should learn to use profilers, not even C and C++ do zero overhead versus writing in pure Assembly. Maybe WEBP should have been written in Assembly, all the speed and I bet quite safe. /s
- namibj 3y ago
  C safe enough to use for parsing untrusted input like this needs to be either formally verified to be safe (not to be correct, at least it's it's the canonical implementation), or written in an intrinsically memory-safe way which humans can fully reason about the safety of. And at that latter point it's slower than Rust. (Not too mention that Rust's awareness of memory lifetimes enables substantial optimizations beyond plain C code that quite often result in faster code at the same level of effort.)

chlorion 3y ago

Apple has actually measured the impact of adding bounds checking to commonly used libraries including media libraries and found no impact on overall power use. Audio and video encoding libraries took around a 1% performance impact. https://llvm.org/devmtg/2023-05/slides/TechnicalTalks-May11/01-Na-fbounds-safety.pdf https://llvm.org/devmtg/2023-05/slides/TechnicalTalks-May11/... I don't think there is any evidence to support that bounds checking causes any significant increase in power consumption, and measurements currently available such as shown above show minimal runtime performance impact. Bounds checking is the perfect situation for branch predictors, 99.9% of the time the branch is predicted correctly, and when it's not it doesn't matter because you're probably aborting the program! There's also the point that you can opt out of bounds checking as-needed on hot loops if you really need to. There is no technological reason to not use bounds checking as the default mode of operation today.

pjmlp 3y ago
There is no technological reason to not use bounds checking as the default mode of operation since ALGOL exists. My favourite quote, C.A.R Hoare's "The 1980 ACM Turing Award Lecture" "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." -- https://www.labouseur.com/projects/codeReckon/papers/The-Emperors-Old-Clothes.pdf https://www.labouseur.com/projects/codeReckon/papers/The-Emp...