Memory Copy Hunting(tigerbeetle.com)

136 pointsby polyrand3 yıl önce40 comments

https://tigerbeetle.com/blog/2023-07-26-copy-hunting/

44 comments

loeg3 yıl önce

> 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/

[2]: https://github.com/facebook/infer/blob/main/infer/documentat... (and related warnings, e.g., https://github.com/facebook/infer/blob/main/infer/documentat... )

nemetroid3 yıl önce

Clang-tidy has similar checks, e.g.:

https://clang.llvm.org/extra/clang-tidy/checks/performance/f...

https://clang.llvm.org/extra/clang-tidy/checks/performance/u...

https://clang.llvm.org/extra/clang-tidy/checks/performance/u...

ot3 yıl önce

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.

loeg3 yıl önce

Thanks! Clang-tidy is another tool we use on diffs at Facebook.

matklad3 yıl önce

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.

k4st3 yıl önce

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

JonChesterfield3 yıl önce

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.

yxhuvud3 yıl önce

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.

JonChesterfield3 yıl önce

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).

[deleted]3 yıl önce

jeffbee3 yıl önce

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.

openasocket3 yıl önce

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.

jeffbee3 yıl önce

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.

AndyKelley3 yıl önce

Related: this pull request that was merged last night: 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.

packetlost3 yıl önce

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/

eatonphil3 yıl önce

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/

[deleted]3 yıl önce

muizelaar3 yıl önce

I've also written something like this: 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.

smarx0073 yıl önce

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

JonChesterfield3 yıl önce

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.

matklad3 yıl önce

Depends on the context! For close-to-the-human high level languages, you generally want to solve these things through optimizations. For close-to-the-cpu low-level languages, you rather want tools to express the desired behavior in the source code. That is, you need an ability to write code in a way that _guarantees_ that optimization triggers. Eg, you want explicit SIMD types rather than just loop auto-vectorization.

Zig is very much on the close-to-cpu side of the spectrum here. When it comes to copies, the current version of the language/compiler doesn't _yet_ provide the required guarantees with required ergonomics, but this is being actively worked on:

- https://github.com/ziglang/zig/issues/2765 - https://github.com/ziglang/zig/issues/12251 - https://github.com/ziglang/zig/issues/5973

In the meantime, you need to look one level below the source language to ensure that the runtime behavior of the code is what you want it to be.

JonChesterfield3 yıl önce

> Depends on the context!

Interesting distinction to draw. That's a pretty good definition for high level vs low level programming languages. Vector types and compiler intrinsics with an eye on the generated assembly are a good way to go for high performance subroutines. If you're willing to change the compiler back end to better serve the ISA, there's a decent chance you can emit exactly the machine code you wanted from somewhat convenient source code. edit: your post at https://matklad.github.io/2023/04/09/can-you-trust-a-compile... is great on this topic, thanks for the blog.

Where I disagree is the implication that higher level languages do not need a way to write code certain that an optimisation (transform?) will fire. All the constexpr clutter from C++ is an attempt to force optimisations to happen regardless of compiler (or compiler invocation, e.g. to say you want some map thing in .rodata in -O0 debug builds).

Transforms guaranteed by the language - whether vectorisation, monomorphising generics, garbage collection, constant folding - are inherently more useful things than heuristic optimisations where you hope for the best. I'm happy to see Zig is moving in that direction for memory copies and wish them good hunting with the aliasing analysis.

Hinted at in a sister comment, I think a missing lever in software dev is adding guaranteed-to-fire compiler transforms in application libraries. E.g. define some regex implementation along with optimisations that act on said regex implementation. Requires a sanely extensible compiler.

[deleted]3 yıl önce

loeg3 yıl önce

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.

JonChesterfield3 yıl önce

> ... avoid relying on a non-deterministic compiler optimization doesn't decrease readability. It is extremely naive to assume that a heuristic-guided ...

This is a post about crawling the compiler IR to find things the compiler missed so that the programmer can change their code to work around the compiler. Even if the crawl-the-IR is a heuristic, moving that into the compiler would mean exactly the cases that were reported are now fixed automatically.

Non-deterministic compilers are broken. Arguably by definition, but also by heuristic as a non-deterministic compiler is enough of a nightmare to debug and fix that it can be expected to grow more errors over time.

Heuristic compilers are very much a thing. Also sadly fragile optimisations are a thing, where minor changes to the application take it over some threshold and the change in output is larger than anticipated.

However, the plan of attack of "change the program until the compiler did what you hoped for" is itself a heuristic that future changes to program and compiler may upset. An alternative is to patch the compiler to do the right thing, and add a regression test to the compiler so that it will continue to do the right thing. That has better engineering properties in the large.

loeg3 yıl önce

Apologies for the confusion, but you've misread my comment and run with it. I don't think there's much here that's responsive to what I intended, so I'll elaborate a little:

> Non-deterministic compilers are broken.

I am not talking about non-determinism from run-to-run with identical sources and compiler version. I am talking about output variations between (1) different versions of the compiler, and (2) as the sources change slightly. Either of these things can easily nudge the heuristics a compiler uses in optimization into doing something different/worse.

JonChesterfield3 yıl önce

It's all good, we're talking past each other slightly. Thanks for the clarification on non-determinism. I think you're giving sensible advice for the world as it is, I'm speculating as to what the world should be.

Minor changes in compiler version and input source leading to widely varying output is a definite hazard. Especially when people change their code to make it run faster, or change the compiler to make some code run faster. That's one with no clear good solution.

anonymoushn3 yıl önce

Using the pointer syntax means "I want to mutate this" and not using it means "I don't need to mutate this." So it's unfortunate if readers cannot count on this meaning because the compiler is defective.

loeg3 yıl önce

Most languages have something like the ‘const’ keyword (or in Rust, eliding ‘mut’).

anonymoushn3 yıl önce

The post is about a specific language. The way that you write the loop without being able to mutate the elements in this language is like this:

  for (items) |item| {
  }

The way that you write the loop so that you can mutate the elements is like this:

  for (items) |*item| {
  }

A way that you could try writing the loop so that it's clear that the elements are not mutated, even though you are using the pointer syntax, is maybe like this:

  for (items) |*_item| {
    const item: *const @typeInfo(@TypeOf(_item)).Pointer.child = _item;
    // there's no "drop _item" so unfortunately _item remains in scope but we promise not to use it.
  }

I wasn't sure this would work, but it looks like you can also manage with this:

  const _items: []const @typeInfo(@TypeOf(items)).Pointer.child = items;
  for (_items) |*item| {
    // now item is of the correct type, even if items is a slice of mutable things.
  }

loeg3 yıl önce

If Zig does not have a |*const item| syntax, maybe adding it would be a good idea (and also satisfy your concern)? (Zig already has a concept of mutable and const pointers.)

For example, in C++ I would distinguish between mutating iteration and non-mutating iteration like this:

  for (const auto& item : collection) {} // non-mutating
  for (auto& item : collection) {} // mutating

jrockway3 yıl önce

> there's no "drop _item" so unfortunately _item remains in scope but we promise not to use it

This is actually a very intriguing programming language keyword. I feel like there are lots of cases where you don't want to split something into a separate function just to avoid being able to use a variable that was used previously, and these things often get refactored over time to the point where the not-to-be-used variable gets used unexpectedly.

mhh__3 yıl önce

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

loeg3 yıl önce

> 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?

OfferFun65953 yıl önce

True, not all companies have a perfect data to be relied upon. Some of them are old and redundant

tedunangst3 yıl önce

The year of the sufficiently smart compiler is always just over the horizon.

mhh__3 yıl önce

I think there's a deeper problem in that the program can't easily tell the compiler what to do - we have pragmas and so on but they're crap.

I remember a Jon Chesterfield pointing out to me that people mistake inlining to be solely about call-overhead and not specialization - you should be able to nudge the compiler which one you want if at all (the "don't do anything" case being more often desired than pass-authors might think, myself include)

masklinn3 yıl önce

> I remember a Jon Chesterfield pointing out to me that people mistake inlining to be solely about call-overhead and not specialization

I recall multiple mentions over the years that inlining is the most important optimisation because of how many further optimisations it unlocks. I guess having some experience with Rust helps there, as the inlining itself is only a small fraction of all the work required to achieve "zero-cost abstraction". It’s very much load-bearing, but it’s the start if the work, not the end.

mhh__3 yıl önce

Not particularly unique to rust

chlorion3 yıl önce

I don't think many languages other than rust and c++ use monomorphization extremely heavily.

Pretty much everything in rust is going to be using traits and c++ uses templates for most things as well.

Every time you use a trait or a template, the code is expanded for the specific instance, and this gives a lot of opportunity for inlining stuff.

A lot of other languages would not have the same opportunity to inline code when doing polymorphism stuff because they rely on dynamic dispatch or something similar that can't be inlined very well or at all.

So I'm not disagreeing with you at all but I think rust and c++ get to inline stuff a little more aggressively, but this is just my theory and may be incorrect!

JonChesterfield3 yıl önce

> I think there's a deeper problem in that the program can't easily tell the compiler what to do

Yes. We have divisions - application, language library, language implementation - which are broadly convenient but drop information on the boundaries. The implementation probably pattern matches on the library and the library will probably depends on quirks of the implementation (e.g. compiler intrinsics written for it), but the application is unlikely to be be able to extend the implementation. In cases where it can, there's a tendency to call it monkey patching and disapprove.

> people mistake inlining to be solely about call-overhead and not specialization

Yeah, that sounds like me. Inlining is an approximation to per-callsite specialisation which is easier to implement, where you pay for ease of compiler development with (machine) code duplication. attributes noinline and alwaysinline are relatively likely to exist, but specialise with respect to the third parameter is still on a wishlist.

This is in the ballpark of compilers could be better, and should be better, than the current state of the art.

saagarjha3 yıl önce

Well, at some point you need to deal with a compiler that isn’t fixed yet.

vient3 yıl önce

> 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]3 yıl önce