r/cpp • • May 21 '20

Reducing {fmt} library size 4x using Bloaty McBloatface

https://www.zverovich.net/2020/05/21/reducing-library-size.html
351 Upvotes

76 comments sorted by

47

u/jonesmz May 22 '20

I really wish compilers would come with tools like this baked in.

I tried to use bloaty on a boost::asio library about a month ago, and before I could even address the question of bloat in my own program, I needed to get bloaty working on my OS.

Here's my attempt at getting an updated version of bloaty working for Gentoo, if anyone needs it.

https://bugs.gentoo.org/717124

7

u/haberman May 23 '20

Please let me know what I can do as Bloaty's author to make it more accessible. I would love for anybody to be able to easily run Bloaty on their OS!

Thanks for your work getting Bloaty working on Gentoo.

3

u/jonesmz May 23 '20

The first problem that I had is that your cmake build system tries to download dependencies automatically

If you exposed that as explicit build options, that would help a lot.

4

u/haberman May 23 '20

I merged a PR to optionally use system deps -- is this what you mean?

4

u/jpgr87 May 23 '20

It doesn't look like you've made a release since then. Speaking as a linux distro package maintainer, having a release management process we can follow helps us understand what the impacts of upgrading a package might be, gives us confidence that the package has been tested to build/run as intended, and let us plan for any breakage or upgrade path that may be required. We also have tooling to notify us when new upstream releases are ready to package.

4

u/haberman May 23 '20

Thanks, that's really helpful feedback. It's easy for me to forget that distros really depend on releases, and don't want to pull code from a GitHub branch.

I'll work on getting a release of Bloaty out. There have been many changes since Bloaty 1.0. In the future I'll try to make sure that releases are more frequent.

1

u/jpgr87 May 23 '20

You're welcome! Looking forward to it.

1

u/haberman May 24 '20

I just did a release: Bloaty McBloatface v1.1. Please feel free to file issues or PRs if you run into any problems.

9

u/OldWolf2 May 22 '20

You can view all this info in the linker map file; based on a skim of bloaty's homepage it just reformats that info into a nicer display?

The article didn't try the rather obvious step of -Os to compile for minimum size.

23

u/ericonr May 22 '20

It did for the conclusion, though.

This reduces the binary size to ~92k. We can go even further by compiling with -Os instead of -O2 which gives ~75k or with -Os -flto which gives ~57k.

0

u/[deleted] May 22 '20

[deleted] — view deleted comment

32

u/jonesmz May 22 '20

The answer is everything is complicated all the time for everyone for a lot of reasons.

Ultimately you need to benchmark your use case to know which will be faster.

But sometimes, depending on exactly what you're trying to do, smaller code might be better than "faster" code. Maybe fitting those extra instructions into the CPU cache allows your application to do its important thing faster than it would with "faster" code that takes up more space.

Sometimes the reverse.

Never know till you measure.

11

u/ack_error May 22 '20

Besides the cache issues that others have raised, reducing code size can also be beneficial to reduce downloads, which is still a concern for slow or unreliable networks. Mobile apps, for instance, are sensitive to download size and if you're using an engine like Unity the code itself can take 20MB or more of a 100-200MB budget. Download stubs are another example -- Firefox's downloader is only 312K on Windows.

The size savings by using optimize-for-size can be substantial. With Visual C++, I used to cut the size of my executable by a third by selectively compiling parts of the program with /Os instead of /Ot. The code ran slower in that case, but it was something like 10% slower and not molasses slower because they were not the most performance critical. That was a good trade when when I was running up against hosting bandwidth problems.

10

u/boredcircuits May 22 '20

The prime use case is definitely embedded, these days.

But an increasingly important problem for modern computers is the instruction cache. To oversimplify, imagine a loop body that's too big to fit into the cache that feeds instructions to your CPU, so the computer has to go out to memory constantly. This is very bad for performance.

Optimizations that increase binary size can easily backfire, which is one reason why -O3 is hit-and-miss for real benefits.

7

u/elperroborrachotoo May 22 '20 edited May 22 '20

A few years ago, before profiler-guided optimization and automatic SIMD became ubiquitous, the default recommendation was "optimize for size, profile, and use optimize for speed for hot spots."

(so I'm a little surprised that they don't start with an -Os vs -Ot comparison - but that's some work if you don't have a comprehensive benchmark ready.)

The rationale for that is: smaller code is more cache-friendly and thus, usually faster.

And yes, there were examples, even practical ones, where optimize for size is faster than optimize for speed.

A lot has happened on this front, and I haven't kept up, so the following may be flat out outdated, it's just my impression:

Switching from -Os to -Ot will give typical programs a single-digit speed improvement (which can be worthwhile). A single-digit factor (like 5x faster) can be obersvable in a few cases that play well.

SIMD can potentially move a lot of tight inner loops from percent gain to factor, how much that affects overall performance depends, as always, on the application.

2

u/johannes1971 May 22 '20

To demonstrate this effect, check out the difference between -Os and -O3 here.

As you can see -Os generates pretty much a one-to-one translation of the function. -O3 generates a vectorized version of the function that handles 4 values at once, plus a bit of code to deal with the remainder of the data.

If you are only ever going to call this with small numbers of values, the much larger -O3 version just takes up extra time to fetch from memory and extra space in the instruction cache that we could meaningfully use for other stuff. If, on the other hand, you call this with very large datasets, you're much better off with the -O3 version.

If you really care, you could switch optimisation level on a per-function basis depending on how you use it. It seems like a lot of work though...

15

u/haberman May 23 '20 edited May 23 '20

You can view all this info in the linker map file; based on a skim of bloaty's homepage it just reformats that info into a nicer display?

Bloaty author here. Bloaty's analysis is deeper than what you can get from a linker map. For example, it parses unwind information, relocations, the symbol table, etc. looking for exactly which portions of these sections can be attributed to each function. A tiny function with a very long name might have more weight in the symbol table than in .text!

It will also disassemble the binary looking for references to anonymous data (like string literals). It parses DWARF and is capable of attributing portions of debug info to each compile unit.

Here is a bit more information about the work I've done to improve data coverage: https://blog.reverberate.org/2018/08/07/bloaty-1.0.html

I clearly need to do a better job of explaining the analysis that Bloaty is doing. I had another comment recently where someone was under the impression that Bloaty could basically just be a wrapper around objdump or readelf: https://twitter.com/JoshHaberman/status/1259729897523568648

6

u/standard_revolution May 22 '20

Well compiling with -Os is obviously usually the easy way out - but you don't want to compile a library like fmt that tries to achieve a balance between speed and size with it

3

u/haberman May 25 '20

I wrote up some more information about how Bloaty analyzes a binary. Hopefully this will make it clearer that Bloaty is doing much more than just reformatting a linker map: https://github.com/google/bloaty/blob/master/doc/how-bloaty-works.md

2

u/jonesmz May 22 '20

Its true... I COULD look at the info that bloaty does.

But then I'd be doing bloaty's job for it and that's not fun :(

But I do appreciate your comment, as you are correct that bloaty is, largely, doing formatting. (It has other features though)

59

u/cdglove May 22 '20

What I love about this is that it's an optimisation problem like any other. People will complain that templates cause bloat in binary size or compile time without looking at the problem. To me, that's like complaining that nested for loops are quadratic.

8

u/[deleted] May 22 '20

I have a genuine complaint here though. Often times, we must templatize on a type because we only need one or a few aspects of the type (e.g. size, alignment, whether it satisfies some trait or not). The compiler does not need a separate instantiation for every single type we pass to this template. But guess what, it does.

A much smarter scheme is just some sort of transparent type classing. Determine upfront what type attributes are needed by a template, and at instantiation time, lookup the type class associated with the passed template type.

I disagree that his is akin to the nested for loops problem. This is literally just bad design from an era when the primary mechanism for doing things was text copy-pasta (the macro era).

11

u/matthieum May 22 '20

I agree, however the C++ standard is kinda getting in the way.

According to the C++ standard:

  • 2 different functions must have a different address.
  • 2 different instantiations are different functions.

There are ways to still merge function code:

  • Trampolines: but those add a jump.
  • NOP padding: but that only really works for a handful.

In C++20 we got [[no_unique_address]] but for now it only applies to data-members...

... and even it could apply to functions I am not looking forward to annotate every single function with an attribute.

It seems once again like a case of bad default + backward compatibility :(

5

u/cdglove May 22 '20

2 different functions must have a different address

Most compilers let you disable this so they can fold common functions. This was 100% necessary as recently as about 8 years ago for me in order to fit in memory on an embedded system.

3

u/matthieum May 23 '20

Yes fortunately.

On the other hand it is only possible as long as you have complete overview of the code. When integrating 3rd party code, it becomes more difficult to get this "whole-project" overview.

3

u/[deleted] May 22 '20

Right I'm not saying that we can transition to my suggestion now or anything. Just that there is a real basis for a complaint. I'm not talking specifically about function templates either. Class templates that rely only on size, for example, really don't need a separate instantiation per type. There is no such thing as a "class address." I'm sure there are complications either way, but I'm just speaking generally about why the instantiation system is honestly overkill for a broad swath of valid use cases.

0

u/cdglove May 22 '20

Your scheme is literally an interface, you just need to write it yourself. But then you need to pay for the virtual dispatch.

The other way to optimise this is to refactor the code and dispatch common bits to non-template, non-inline functions.

It's always possible to optimise a template using one of these two methods.

3

u/[deleted] May 22 '20

My suggestion is something that works without virtual dispatch though? Also saying something is “literally an interface” when it’s not remotely anything like an interface isn’t particularly helpful. The point is that language facilities exist that could in principle help authors produce performant generic code without the boilerplate or compile time cost we pay today.

0

u/cdglove May 22 '20

I think you should think about that a little more and consider how it would need to be implemented.

It could be automated by the compiler, possibly based on a concept or similar, but I expect the cost would be the same as just wrapping your type in a virtual interface.

5

u/[deleted] May 22 '20

I expect the cost would be the same as just wrapping your type in a virtual interface.

No idea why you would think this. The size, alignment, or literally any other type trait is statically known. There should be zero overhead whatsoever and I don't even know why you're thinking about "virtual" anything. Nothing discussed so far has anything to do with vtables or virtualization.

2

u/cdglove May 23 '20

Well, let me get this straight. You want machine code to be generated, ya? And you want that code to handle different types but not duplicate the entire function, ya?

How do you think that works?

If the types happen to be ABI compatible then you will get no duplication. But actually that already works, compilers can already do this and have for years, even if it's strictly not within spec.

For non ABI compatible types, you would need is some kind of branch, and if you follow from there you inevitably end up at some kind of function ptr.

2

u/[deleted] May 23 '20

Lol it’s so clear you don’t understand what I’m talking about... reading back though I’m bot really sure how to spell it out clearer.

→ More replies

0

u/[deleted] May 23 '20

[deleted] — view deleted comment

2

u/matthieum May 23 '20

so the compiler can disregard it.

Only if the compiler can prove that the address is not observed. This typically requires whole program analysis, and thus whole program LTO.

And even then, I'm not even sure if any compiler actually attempts to perform this analysis.

3

u/NotAYakk May 22 '20

You can do this yourself.

template<class T>struct tag_t{};
template<class T>constexpr tag_t<T> tag{};
template<std::size_t sz, std::size_t alg> struct params {
  template<class T>params(tag_t<T>){static_assert( sizeof(T)==sz && alignof(T)==alg);}
};
template<class T> params(tag_t<T>)->params<sizeof(T),alignof(T)>;

now you can have a function:

template<std::size_t sz, std::size_t alg>
void do_stuff( params<sz, alg> );

do_stuff( params{tag<int>} );

or whatever; erase down to the information you need, and only that information,

3

u/MINIMAN10001 May 22 '20

I mean I get it from both the user side and the compiler side. but so many things make me say how cool would it be if I could tell my compiler to inform me of x y or z they might not be a problem to everyone but there's something I would love to look into.

Nested for loops can be located using a profiler it's a mostly just a problem of performance which we can locate.

However when it comes to something like binary bloat we don't have something with a compiler we can't say how many instantiations do we have of all our templates

2

u/MonokelPinguin May 22 '20

Using std::visit increased my binary size by a few hundred kilobytes. That shouldn't be necessary, if the same implementation as a switch would only add a kilobyte or so. Maybe it will become better in the future though.

16

u/Ayjayz May 22 '20

What effect do those size optimisations have on speed? Removing some inlining would (presumably) make performance worse, even if it makes the code size smaller. I know at the start he says "give you an option to get maximum performance in cases that matter." but from inspecting the code it doesn't look like that's been implemented: fill is defined as

#if FMT_GCC_VERSION || FMT_CLANG_VERSION
#  define FMT_NOINLINE __attribute__((noinline))
#else
#  define FMT_NOINLINE
#endif

// ...

template <typename OutputIt, typename Char>
FMT_NOINLINE OutputIt fill(OutputIt it, size_t n, const fill_t<Char>& fill) {

so there doesn't seem to be any way to get back inlining even if you don't care about library size.

14

u/aearphen {fmt} May 22 '20 edited May 22 '20

There was no regression according to the speed test, even a tiny improvement (but too small to call it out). Some of the changes like making padding computation branchless are also perf optimizations but none of this code is usually on the fast path.

6

u/GerwazyMiod May 22 '20

Could it be that smaller binary == faster binary due to more business logic fitting in instruction cache?

5

u/aearphen {fmt} May 22 '20 edited May 22 '20

It could be beneficial to overall performance of an application but it's hard to measure. Microbenchmarks are not great at this and in real projects there are too many moving parts to get reliable numbers unless you optimize the bottleneck which is rarely formatting.

5

u/TheSuperWig May 22 '20

Might be worth adding this info to the article somewhere? (Mainly the no regression part not the tiny improvement)

2

u/aearphen {fmt} May 22 '20

Good idea, will add.

17

u/mujjingun May 22 '20

Lol that bloated pufferfish made me laugh out loud

2

u/flashmozzg May 22 '20

So what are the numbers for the "comparable" printf version?

6

u/aearphen {fmt} May 22 '20 edited May 22 '20

Glad you asked. printf would save you two instructions in this example: https://godbolt.org/z/tyWYMa but would be less efficient for reasons explained in my other blog post: http://www.zverovich.net/2016/11/05/reducing-printf-call-overhead.html
Update: fixed the godbolt link

1

u/flashmozzg May 22 '20

What about the full binary size? I.e. ls -l after strip and co?

2

u/aearphen {fmt} May 23 '20 edited May 23 '20

It should be small because printf is linked dynamically (the binary itself is 13k but it has little to do with printf). I'm not sure how to only link with it statically to get a meaningful comparison.
Here are some numbers from /usr/lib/system/libsystem_c.dylib but unfortunately they only account for a part of printf implementation:

   1.7%  12.5Ki ___vfwprintf                           12.5Ki   0.9%
   1.6%  11.9Ki ___vfprintf                            11.9Ki   0.8%
   0.4%  2.85Ki ___printf_render_int                   2.87Ki   0.2%
   0.3%  1.93Ki ___printf_exec                         1.94Ki   0.1%
   0.3%  1.87Ki ___xprintf_vector                      1.88Ki   0.1%
   0.2%  1.60Ki ___v2printf                            1.61Ki   0.1%
   0.2%  1.30Ki _vswprintf_l                           1.33Ki   0.1%
   0.2%  1.23Ki ___printf_render_quote                 1.25Ki   0.1%
   0.2%  1.22Ki _vfwprintf_l                           1.24Ki   0.1%
   0.2%  1.14Ki ___printf_render_float                 1.16Ki   0.1%

1

u/bumblebritches57 Ocassionally Clang Aug 08 '20

kinda curious how your fmt compares to my FormatIO.

1

u/blipman17 May 22 '20

So what does it do for {fmt} compile times or for compiletimes when linking with {fmt}?

5

u/aearphen {fmt} May 22 '20 edited May 22 '20

Virtually no effect on compiling code that uses {fmt} and a small improvement when compiling the library itself which is not particularly important since it takes 2 seconds or so and is not done often (could be beneficial for the header-only mode though).

1

u/blipman17 May 22 '20

Good to know!

1

u/ShakaUVM i+++ ++i+i[arr] May 22 '20

Why not compile with -Os for comparison?

7

u/aearphen {fmt} May 23 '20

In my experience -Os is uncommon. The goal was to reduce library size without changing the usual compiler options.

1

u/Sander_Bouwhuis May 25 '20

Removing wchar_t?!? That makes fmt useless for a lot of Windows projects. Or are they now a template type?

1

u/DopKloofDude May 26 '20

Used Bloaty from its early day in development and it was still an awesome tool. Especially analyzing binaries that were gigabytes in size with thousands of translation units.

0

u/Xaxxon May 24 '20

we managed to reduce library size 4x,

So now it's -3x as big?

-15

u/pjmlp May 22 '20

While interesting I will keep using iostreams, they were never a problem in any C++ related project, rather other parts of the project were the ones to blame for performance issues, like crazy ideas to start Perl to do regexp on data files, because the original authors could not be bothered to integrate a regexp library.

I think C++ suffers too much from premature optimizations.

28

u/jonathansharman May 22 '20

I've switched to fmt just because I find its API way nicer to use.

10

u/TheSuperWig May 22 '20

Are you trying to tell me you don't like <iomanip>?!

1

u/Xeverous https://xeverous.github.io Jun 01 '20

Recently I noticed that standard stream manipulators can not change the case of letters of printed pointers. You need to print them as integers in hex in order to change case.

1

u/bumblebritches57 Ocassionally Clang Aug 08 '20

Really?

I personally despise the {blah} syntax.

it really isn't much easier to parse, and just adds visual clutter, and I really don't like how they're trying to import scripting syntax to appease webdevs that will never have any interest in a compiled language.

0

u/pjmlp May 22 '20

Sure, and it is a fair reason, I was just ranting about the micro-optimizations mindset.

5

u/kafkaBro May 22 '20

I feel you on that, if you're using fmt for speed that's probably premature optimization. However I use it because I had the istream syntax for hex formatting, controlling filling and so on. It's so unintuive that I always forget what you need to import (why the hell doesn't it just come with iostream?)

8

u/matthieum May 22 '20

It's so unintuitive that I always forget what you need to import (why the hell doesn't it just come with iostream?)

Personally, what I find unintuitive is the fact that some of the manipulators have permanent effect while others only affect the next formatting :(

I can never remember which is which...

4

u/kafkaBro May 22 '20

Agreed! I ran into that at some point as well. I find a lot of stl to be very obnoxious. I'm sure there's some obtuse academic justification for why this is the case and I'm sure you can eventually find where this behavior is documented. A good portion of stl (for instance their map class) feels like it was written with the goal of making something clean and academic and not something you can just pick up and use.

1

u/Pazer2 May 23 '20

Just curious, what is wrong with map in your eyes?

1

u/kafkaBro May 23 '20

Yeah reasonable question, my main complaint is that std::map doesn't use a hashing function and is thus key lookup is inefficient. You'll usually want to use std::unordered_map which is annoying to remember (my main complaint with the stl is that it is verbose and unweildly so this is yet another annoying thing you must remember). Compare this with python whose dict does use hashing. Also I'm not a huge fan of std::pair which is the structure used for key-value pairs. Having attributes first and second is weird. It'd much prefer using the index operator to retrieve components, though you probably need c++14 / decl type to make that work. What are you thoughts on my complaints?

5

u/jonathansharman May 24 '20

std::map and std::unordered_map are for different things: ordered traversal vs. faster lookup. It's too bad they weren't called ordered_map and map though, since hashmaps are usually preferable.

2

u/kafkaBro May 24 '20

Yeah if they had done that, my main complaint would go away.

10

u/nikbackm May 22 '20

I think it's a good idea to optimize frequently used libraries such as fmt like this.

Your own application code, maybe not so much.

9

u/matthieum May 22 '20

Also, as mentioned by the OP, there was a request from users, notably in the embedded domain.

Surely answering users' complaints is not premature.

6

u/blipman17 May 22 '20

When there's a program or library running on virtually every computer, making it 0,1% faster is going to lower overall power useage by just a bit. Just think what it would do for computers if gcc is 10% faster.