7 ms·

Memory Copy Hunting

136 points by polyrand 3y ago

packetlost 3y ago
Man, I want to work at TigerBeetle so bad. So much cool stuff comes out of that company, exactly the type of stuff that I love thinking about and working on. On a semi-related note, if you want to look into compiler backends/IRs, there's QBE[0], which is far simpler than LLVM IR, but gets most of the point across [0]: https://c9x.me/compile/ https://c9x.me/compile/
loeg 3y ago
> One particular issue we fixed a couple of times in TigerBeetle is replacing by-value with by-pointer loops: I don't know about other tools and places, but one nice thing about working at Facebook is the internal Infer linter tool[1] is generally good about producing warnings for "this copy could be a ref instead"[2] (in the majority C++ codebase) at code review time, without manually combing the LLVM IR for memcpys. (Internally, Infer is using several handwritten analyses on C++ AST.) Reading further, it seems like they are essentially looking for the pattern where a memcpy call is generated with a large constant size parameter at compile time. Things of this nature should be somewhat easy to write a static analyzer pass for, if you've got an existing AST/SSA level framework. I believe there is already an Infer pass for this for C++, but it might be a different internal analyzer. [1]: https://fbinfer.com/ https://fbinfer.com/ [2]: https://github.com/facebook/infer/blob/main/infer/documentation/issues/PULSE_UNNECESSARY_COPY.md https://github.com/facebook/infer/blob/main/infer/documentat... (and related warnings, e.g., https://github.com/facebook/infer/blob/main/infer/documentation/issues/PULSE_CONST_REFABLE.md https://github.com/facebook/infer/blob/main/infer/documentat... )
- matklad 3y ago
  Yup! Ideally, you want to do this analysis on compiler IR, _before_ it gets lowered to LLVM IR. But to do that in a sustainable way, you need a quasi-stable internal IR format. Zig is rather new, and, while the compiler is a delight to hack on, there are no stable extension interfaces, and the code itself is very much not settled yet. So that's the main thing we get out of LLVM IR here is relative stability. You can quickly hack something together, and be reasonably sure that you won't have to spend a lot of time upgrading the infra with every compiler upgrade. LLVM IR of course is not absolutely stable, but it is stable enough, and way more stable than compiler internals at the moment.
  - k4st 3y ago
    At Trail of Bits, we've been working on this type of IR for C and C++ code [1]. We operate as a kind of Clang middle end, taking in a Clang AST, and spitting LLVM IR that is Clang-compatible out the other end. In this middle area, we progressively lower from a high-level MLIR dialect down to LLVM. [1] https://github.com/trailofbits/vast https://github.com/trailofbits/vast
    - JonChesterfield 3y ago
      There's been a longstanding wish to do things like inject a std::vector::reserve ahead of a loop that appends to a vector. Difficult to do once you've lowered the standard library to pointer arithmetic on structs. Clang emitting a MLIR dialect that preserves a lot of C++ semantic information before translation to IR would be a big deal in the LLVM pipeline.
  - yxhuvud 3y ago
    It would be nice if llvm provided some sort of IR linter that looks for common issues and list the biggest offenders in a set of IR.
    - deleted 3y ago
      [deleted]
    - JonChesterfield 3y ago
      Better to add said common issues to instcombine with a test case instead. But if you wanted tooling to look for misuse of your library API or similar, that can be done (and has been, at least out of tree).
- nemetroid 3y ago
  Clang-tidy has similar checks, e.g.: https://clang.llvm.org/extra/clang-tidy/checks/performance/for-range-copy.html https://clang.llvm.org/extra/clang-tidy/checks/performance/f... https://clang.llvm.org/extra/clang-tidy/checks/performance/unnecessary-value-param.html https://clang.llvm.org/extra/clang-tidy/checks/performance/u... https://clang.llvm.org/extra/clang-tidy/checks/performance/unnecessary-copy-initialization.html https://clang.llvm.org/extra/clang-tidy/checks/performance/u...
  - loeg 3y ago
    Thanks! Clang-tidy is another tool we use on diffs at Facebook.
  - ot 3y ago
    Clang-tidy only supports AST-based matchers, you get type resolution but you still can only match simple patterns that only need local reasoning. Infer does whole-program analysis, so it can for example detect whether it is safe to move an object instead of copying it, because nothing touches it afterwards.
- jeffbee 3y ago
  If the copies are expensive, they will show up in profiles. If you have a hot constructor that may be an opportunity to avoid a copy. If the copy is not present in the profiles then it was not worth worrying about.
  - openasocket 3y ago
    That’s probably the best advice for most use cases. However, there are times where you can’t necessarily do profiling. Consider an application that’s used in a lot of different contexts with varying workloads, like a database. It’s not possible to test all the different ways the system could be stressed, and the profiles could vary wildly. For example, at my job we have a series of functions in our codebase that should never, ever allocate. It doesn’t register as an issue on our profiles or stress tests, but we know that it’s theoretically possible that if they allocated it could cause certain weird performance issues. Rather than hope that one of our customers never unlocks the magic confluence of events that triggers this behavior, we just make sure those functions don’t allocate in our unit tests and rule out that failure condition completely. A bit paranoid yeah, but every now and then the paranoia is justified.
    - jeffbee 3y ago
      You'd have a different perspective when writing a backend system that only runs in the author's own datacenter. Then the author can have total confidence in the coverage of the profiles. There are examples of effective fleet-wide profiling on customer systems but I agree they are the exception and I also agree that profiling will not necessary catch black swan events.
JonChesterfield 3y ago
This would be a bad thing. It's taking code written in terms of value semantics, copying stuff around, and replacing it with more efficient code that avoids the copy. Doing that by improving the compiler is a win. Doing it by changing the source to be easier to compile is a loss. You're trading readability for performance when instead you should fix the compiler and get both.
- loeg 3y ago
  Disagree. Using reference (pointer) syntax explicitly to avoid relying on a non-deterministic compiler optimization doesn't decrease readability. It is extremely naive to assume that a heuristic-guided compiler optimization will always work or that you never need to write your code explicitly in a system that aims to be high-performance, like Tiger Beetle. Also, some of the optimizations they are hunting are implicit and surprising. Probably not something a new compiler optimization is going to automatically fix.
  - mhh__ 3y ago
    Compilers in general aren't always perfect so if you really genuinely care about copying that much you should be inspecting and profiling the binary they output e.g. unless you have some truly massive value types (at which point my eyebrows would be raised anyway) being copied, the cost is probably going to be in the same ballpark as some other compiler-fuckups too
    - loeg 3y ago
      > Compilers in general aren't always perfect Right. > so if you really genuinely care about copying that much you should be inspecting and profiling the binary they output Sure, but manual inspection is burdensome and unreliable. Are you advocating against just use the language-level constructs (pointers/references) that guarantee a copy isn't performed?
    - OfferFun6595 3y ago
      True, not all companies have a perfect data to be relied upon. Some of them are old and redundant
muizelaar 3y ago
I've also written something like this: https://github.com/jrmuizel/memcpy-find https://github.com/jrmuizel/memcpy-find It uses debug info to get a full stack including inline information which is especially helpful when running on Rust code.
vient 3y ago
> shaves off 300 bytes from the release binary I wonder if it should be "kilobytes", 300 bytes are nothing considering that fs block size is usually 4KB.
deleted 3y ago
[deleted]
eatonphil 3y ago
By the way, if you're in the Amsterdam area next week, almost the whole TigerBeetle team will be there on Monday/Tuesday. We'll be hosting a happy hour on Tuesday August 1st at 5pm. If you'd like to join, RSVP below and you're invited! Among others, some friends from the Zig communities will be coming through, and a DuckDB developer or two may be there. :) https://tigerbeetle.com/amsterdam23/ https://tigerbeetle.com/amsterdam23/
- deleted 3y ago
  [deleted]
smarx007 3y ago
A bit off-topic, but would be good to read what TigerBeetle folks think of the tech behind the recently released FedNow.
AndyKelley 3y ago
Related: this pull request that was merged last night: https://github.com/ziglang/zig/pull/16558 https://github.com/ziglang/zig/pull/16558 Currently only enabled for debug builds of the compiler, but there's talk there about making it a more general purpose tool for finding where the costly generic function instantations are.

136 points by polyrand 3y ago

Man, I want to work at TigerBeetle so bad. So much cool stuff comes out of that company, exactly the type of stuff that I love thinking about and working on. On a semi-related note, if you want to look into compiler backends/IRs, there's QBE[0], which is far simpler than LLVM IR, but gets most of the point across [0]: https://c9x.me/compile/ https://c9x.me/compile/

loeg 3y ago

> One particular issue we fixed a couple of times in TigerBeetle is replacing by-value with by-pointer loops: I don't know about other tools and places, but one nice thing about working at Facebook is the internal Infer linter tool[1] is generally good about producing warnings for "this copy could be a ref instead"[2] (in the majority C++ codebase) at code review time, without manually combing the LLVM IR for memcpys. (Internally, Infer is using several handwritten analyses on C++ AST.) Reading further, it seems like they are essentially looking for the pattern where a memcpy call is generated with a large constant size parameter at compile time. Things of this nature should be somewhat easy to write a static analyzer pass for, if you've got an existing AST/SSA level framework. I believe there is already an Infer pass for this for C++, but it might be a different internal analyzer. [1]: https://fbinfer.com/ https://fbinfer.com/ [2]: https://github.com/facebook/infer/blob/main/infer/documentation/issues/PULSE_UNNECESSARY_COPY.md https://github.com/facebook/infer/blob/main/infer/documentat... (and related warnings, e.g., https://github.com/facebook/infer/blob/main/infer/documentation/issues/PULSE_CONST_REFABLE.md https://github.com/facebook/infer/blob/main/infer/documentat... )

matklad 3y ago
Yup! Ideally, you want to do this analysis on compiler IR, _before_ it gets lowered to LLVM IR. But to do that in a sustainable way, you need a quasi-stable internal IR format. Zig is rather new, and, while the compiler is a delight to hack on, there are no stable extension interfaces, and the code itself is very much not settled yet. So that's the main thing we get out of LLVM IR here is relative stability. You can quickly hack something together, and be reasonably sure that you won't have to spend a lot of time upgrading the infra with every compiler upgrade. LLVM IR of course is not absolutely stable, but it is stable enough, and way more stable than compiler internals at the moment.
- k4st 3y ago
  At Trail of Bits, we've been working on this type of IR for C and C++ code [1]. We operate as a kind of Clang middle end, taking in a Clang AST, and spitting LLVM IR that is Clang-compatible out the other end. In this middle area, we progressively lower from a high-level MLIR dialect down to LLVM. [1] https://github.com/trailofbits/vast https://github.com/trailofbits/vast
  - JonChesterfield 3y ago
    There's been a longstanding wish to do things like inject a std::vector::reserve ahead of a loop that appends to a vector. Difficult to do once you've lowered the standard library to pointer arithmetic on structs. Clang emitting a MLIR dialect that preserves a lot of C++ semantic information before translation to IR would be a big deal in the LLVM pipeline.
- yxhuvud 3y ago
  It would be nice if llvm provided some sort of IR linter that looks for common issues and list the biggest offenders in a set of IR.
  - deleted 3y ago
    [deleted]
  - JonChesterfield 3y ago
    Better to add said common issues to instcombine with a test case instead. But if you wanted tooling to look for misuse of your library API or similar, that can be done (and has been, at least out of tree).
nemetroid 3y ago
Clang-tidy has similar checks, e.g.: https://clang.llvm.org/extra/clang-tidy/checks/performance/for-range-copy.html https://clang.llvm.org/extra/clang-tidy/checks/performance/f... https://clang.llvm.org/extra/clang-tidy/checks/performance/unnecessary-value-param.html https://clang.llvm.org/extra/clang-tidy/checks/performance/u... https://clang.llvm.org/extra/clang-tidy/checks/performance/unnecessary-copy-initialization.html https://clang.llvm.org/extra/clang-tidy/checks/performance/u...
- loeg 3y ago
  Thanks! Clang-tidy is another tool we use on diffs at Facebook.
- ot 3y ago
  Clang-tidy only supports AST-based matchers, you get type resolution but you still can only match simple patterns that only need local reasoning. Infer does whole-program analysis, so it can for example detect whether it is safe to move an object instead of copying it, because nothing touches it afterwards.
jeffbee 3y ago
If the copies are expensive, they will show up in profiles. If you have a hot constructor that may be an opportunity to avoid a copy. If the copy is not present in the profiles then it was not worth worrying about.
- openasocket 3y ago
  That’s probably the best advice for most use cases. However, there are times where you can’t necessarily do profiling. Consider an application that’s used in a lot of different contexts with varying workloads, like a database. It’s not possible to test all the different ways the system could be stressed, and the profiles could vary wildly. For example, at my job we have a series of functions in our codebase that should never, ever allocate. It doesn’t register as an issue on our profiles or stress tests, but we know that it’s theoretically possible that if they allocated it could cause certain weird performance issues. Rather than hope that one of our customers never unlocks the magic confluence of events that triggers this behavior, we just make sure those functions don’t allocate in our unit tests and rule out that failure condition completely. A bit paranoid yeah, but every now and then the paranoia is justified.
  - jeffbee 3y ago
    You'd have a different perspective when writing a backend system that only runs in the author's own datacenter. Then the author can have total confidence in the coverage of the profiles. There are examples of effective fleet-wide profiling on customer systems but I agree they are the exception and I also agree that profiling will not necessary catch black swan events.

JonChesterfield 3y ago

This would be a bad thing. It's taking code written in terms of value semantics, copying stuff around, and replacing it with more efficient code that avoids the copy. Doing that by improving the compiler is a win. Doing it by changing the source to be easier to compile is a loss. You're trading readability for performance when instead you should fix the compiler and get both.

loeg 3y ago
Disagree. Using reference (pointer) syntax explicitly to avoid relying on a non-deterministic compiler optimization doesn't decrease readability. It is extremely naive to assume that a heuristic-guided compiler optimization will always work or that you never need to write your code explicitly in a system that aims to be high-performance, like Tiger Beetle. Also, some of the optimizations they are hunting are implicit and surprising. Probably not something a new compiler optimization is going to automatically fix.
- mhh__ 3y ago
  Compilers in general aren't always perfect so if you really genuinely care about copying that much you should be inspecting and profiling the binary they output e.g. unless you have some truly massive value types (at which point my eyebrows would be raised anyway) being copied, the cost is probably going to be in the same ballpark as some other compiler-fuckups too
  - loeg 3y ago
    > Compilers in general aren't always perfect Right. > so if you really genuinely care about copying that much you should be inspecting and profiling the binary they output Sure, but manual inspection is burdensome and unreliable. Are you advocating against just use the language-level constructs (pointers/references) that guarantee a copy isn't performed?
  - OfferFun6595 3y ago
    True, not all companies have a perfect data to be relied upon. Some of them are old and redundant

muizelaar 3y ago

I've also written something like this: https://github.com/jrmuizel/memcpy-find https://github.com/jrmuizel/memcpy-find It uses debug info to get a full stack including inline information which is especially helpful when running on Rust code.

vient 3y ago

> shaves off 300 bytes from the release binary I wonder if it should be "kilobytes", 300 bytes are nothing considering that fs block size is usually 4KB.

deleted 3y ago

[deleted]

eatonphil 3y ago

By the way, if you're in the Amsterdam area next week, almost the whole TigerBeetle team will be there on Monday/Tuesday. We'll be hosting a happy hour on Tuesday August 1st at 5pm. If you'd like to join, RSVP below and you're invited! Among others, some friends from the Zig communities will be coming through, and a DuckDB developer or two may be there. :) https://tigerbeetle.com/amsterdam23/ https://tigerbeetle.com/amsterdam23/

deleted 3y ago
[deleted]

smarx007 3y ago

A bit off-topic, but would be good to read what TigerBeetle folks think of the tech behind the recently released FedNow.

AndyKelley 3y ago

Related: this pull request that was merged last night: https://github.com/ziglang/zig/pull/16558 https://github.com/ziglang/zig/pull/16558 Currently only enabled for debug builds of the compiler, but there's talk there about making it a more general purpose tool for finding where the costly generic function instantations are.