[HN Gopher] Memory Copy Hunting
___________________________________________________________________
Memory Copy Hunting
Author : polyrand
Score : 103 points
Date : 2023-07-26 12:16 UTC (10 hours ago)
(HTM) web link (tigerbeetle.com)
(TXT) w3m dump (tigerbeetle.com)
| [deleted]
| loeg wrote:
| > 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... )
| matklad wrote:
| 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.
| yxhuvud wrote:
| 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.
| JonChesterfield wrote:
| 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]
| k4st wrote:
| 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
| JonChesterfield wrote:
| 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.
| jeffbee wrote:
| 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 wrote:
| 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 wrote:
| 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.
| nemetroid wrote:
| 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...
| ot wrote:
| 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.
| loeg wrote:
| Thanks! Clang-tidy is another tool we use on diffs at
| Facebook.
| JonChesterfield wrote:
| 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.
| matklad wrote:
| 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.
| JonChesterfield wrote:
| > 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.
| tedunangst wrote:
| The year of the sufficiently smart compiler is always just over
| the horizon.
| mhh__ wrote:
| 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)
| JonChesterfield wrote:
| > 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.
| masklinn wrote:
| > 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__ wrote:
| Not particularly unique to rust
| loeg wrote:
| 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.
| anonymoushn wrote:
| 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.
| loeg wrote:
| Most languages have something like the 'const' keyword (or
| in Rust, eliding 'mut').
| anonymoushn wrote:
| 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.
| }
| loeg wrote:
| 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
| jrockway wrote:
| > 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__ wrote:
| 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 wrote:
| > 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?
| JonChesterfield wrote:
| > ... 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.
| muizelaar wrote:
| 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.
| smarx007 wrote:
| A bit off-topic, but would be good to read what TigerBeetle folks
| think of the tech behind the recently released FedNow.
| vient wrote:
| > 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.
| eatonphil wrote:
| 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]
| packetlost wrote:
| 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/
___________________________________________________________________
(page generated 2023-07-26 23:01 UTC)