4 ms·

Virgil doesn't use frame pointers. If you don't have dynamic stack allocation, the frame of a given function has a fixed size can be found with a simple (binary

by titzer 3y ago

Virgil doesn't use frame pointers. If you don't have dynamic stack allocation, the frame of a given function has a fixed size can be found with a simple (binary-search) table lookup. Virgil's technique uses an additional page-indexed range that further restricts the lookup to be a few comparisons on average (O(log(# retpoints per page)). It combines the unwind info with stackmaps for GC. It takes very little space. The main driver is in (https://github.com/titzer/virgil/blob/master/rt/native/NativeStackWalker.v3); https://github.com/titzer/virgil/blob/master/rt/native/Nativ... the rest of the code in the directory implements the decoding of metadata. I think frame pointers only make sense if frames are dynamically-sized (i.e. have stack allocation of data). Otherwise it seems weird to me that a dynamic mechanism is used when a static mechanism would suffice; mostly because no one agreed on an ABI for the metadata encoding, or an unwind routine. I believe the 1-2% measurement number. That's in the same ballpark as pervasive checks for array bounds checks. It's weird that the odd debugging and profiling task gets special pleading for a 1% cost but adding a layer of security gets the finger. Very bizarre priorities.

moonchild 3y ago
You can add bounds checks to c, but that costs a hell of a lot more than 1-2%. C++ has them off by default for std::vector because c++ is designed by and for the utterly insane. Other than that, I can't off the top of my head think of a language that doesn't have them.
- shrimp_emoji 3y ago
  > C++ has them off by default for std::vector because c++ is designed by and for the utterly insane. And for those who value performance and don't want to pay the cost of "a lot more than 1-2%" ;p
  - moonchild 3y ago
    std::vector falls into the category of things that are easy to bounds check, st the cost, even under today's primitive compilers, is low. It's direct pointer accesses—which are common in c but not in c++ or most other languages—that are hard to and therefore cost more to bounds check.
    - shrimp_emoji 3y ago
      That's assuming you're keeping no metadata about your C array(s) that you're bounds-checking, which would be very slow indeed. :o You'd be traversing pointers until you hit a tombstone value or something. But would anyone do this in performance-chasing code? Cuz, otherwise, with metadata to support your bounds checks, you're doing the same thing that I assume std::vector is doing: asking your array metadata about whether something's in bounds. And that's extra cycles, which can add up depending on what you're doing! Btw, in my experience, std::vector is fast. Insanely fast. "I don't understand how it can be so fast", "barely distinguishable from raw arrays in C" fast. Not doing bounds checking is probably part of that, though far from the whole story.
  - pjmlp 3y ago
    std::regexp, std::map, fronzen ABI.... apparently the value for performance is relative at WG21.
  - UncleMeat 3y ago
    The data I've seen for turning on bounds checks in std::vector shows overhead considerably lower than 1-2%.
- chlorion 3y ago
  The bounds safety C compiler extension research by Apple has measured the runtime impact of adding bounds checking to C and it is not a lot more than 1-2% in almost all cases. Even in microbenchmarks its often around 5%. The impact on media encoding and decoding was around 1-2% and the overall power use on the device did not change. https://www.youtube.com/watch?v=RK9bfrsMdAM https://www.youtube.com/watch?v=RK9bfrsMdAM https://llvm.org/devmtg/2023-05/slides/TechnicalTalks-May11/01-Na-fbounds-safety.pdf https://llvm.org/devmtg/2023-05/slides/TechnicalTalks-May11/... It's a myth that bounds checking has extraordinary performance costs and cannot be enabled without slowing everything to a halt. Maybe this was the case 10 years ago or 20 years ago or something, but not today.

by titzer 3y ago

moonchild 3y ago

You can add bounds checks to c, but that costs a hell of a lot more than 1-2%. C++ has them off by default for std::vector because c++ is designed by and for the utterly insane. Other than that, I can't off the top of my head think of a language that doesn't have them.

shrimp_emoji 3y ago
> C++ has them off by default for std::vector because c++ is designed by and for the utterly insane. And for those who value performance and don't want to pay the cost of "a lot more than 1-2%" ;p
- moonchild 3y ago
  std::vector falls into the category of things that are easy to bounds check, st the cost, even under today's primitive compilers, is low. It's direct pointer accesses—which are common in c but not in c++ or most other languages—that are hard to and therefore cost more to bounds check.
  - shrimp_emoji 3y ago
    That's assuming you're keeping no metadata about your C array(s) that you're bounds-checking, which would be very slow indeed. :o You'd be traversing pointers until you hit a tombstone value or something. But would anyone do this in performance-chasing code? Cuz, otherwise, with metadata to support your bounds checks, you're doing the same thing that I assume std::vector is doing: asking your array metadata about whether something's in bounds. And that's extra cycles, which can add up depending on what you're doing! Btw, in my experience, std::vector is fast. Insanely fast. "I don't understand how it can be so fast", "barely distinguishable from raw arrays in C" fast. Not doing bounds checking is probably part of that, though far from the whole story.
- pjmlp 3y ago
  std::regexp, std::map, fronzen ABI.... apparently the value for performance is relative at WG21.
- UncleMeat 3y ago
  The data I've seen for turning on bounds checks in std::vector shows overhead considerably lower than 1-2%.
chlorion 3y ago
The bounds safety C compiler extension research by Apple has measured the runtime impact of adding bounds checking to C and it is not a lot more than 1-2% in almost all cases. Even in microbenchmarks its often around 5%. The impact on media encoding and decoding was around 1-2% and the overall power use on the device did not change. https://www.youtube.com/watch?v=RK9bfrsMdAM https://www.youtube.com/watch?v=RK9bfrsMdAM https://llvm.org/devmtg/2023-05/slides/TechnicalTalks-May11/01-Na-fbounds-safety.pdf https://llvm.org/devmtg/2023-05/slides/TechnicalTalks-May11/... It's a myth that bounds checking has extraordinary performance costs and cannot be enabled without slowing everything to a halt. Maybe this was the case 10 years ago or 20 years ago or something, but not today.