Honey, I shrunk {fmt}: bringing binary size to 14k and ditching the C++ runtime

https://vitaut.net/posts/2024/binary-size/

by karagenit • 2 years ago

244 128 2 years ago

magnio• 2 years ago

All the formatting in {fmt} is locale-independent by default (which breaks with the C++’s tradition of having wrong defaults)

Chuckles

tialaramex3• 2 years ago

It's really more of a committee thing - so we wouldn't necessarily expect fmt, a third party library, to have wrong defaults.

Astoundingly, when this was standardised (as std::format for C++ 20) the committee didn't add back this mistake (which is present in numerous other parts of the standard). Which does give small hope for the proposers who plead with the committee to not make things unnecessarily worse in order to make C++ "consistent".

formerly_proven2• 2 years ago

I'm filing a Defect Report about std::format disrespecting locale as we speak.

ape4• 2 years ago

You can pass in a locale as a parameter. (Of course this doesn't fix the default)

h4ck_th3_pl4n3t• 2 years ago

It's kind of mindblowing to see how much code floating point formatting needs.

The linked dragonbox [1] project is also worth a read. Pretty optimized for the least used branches.

[1] https://github.com/jk-jeon/dragonbox

mananaysiempre2• 2 years ago

It's kind of mindblowing to see how much code floating point formatting needs.

If you want it to be fast. The baseline implementation isn’t terrible[1,2] even if it is still ultimately an implementation of arbitrary-precision arithmetic.

[1] https://research.swtch.com/ftoa

[2] https://go.dev/src/strconv/ftoa.go

vitaut5• 2 years ago

If I interpret the numbers correctly it is of the order of ~1000 times slower than modern algorithms such as Dragonbox.

vitaut5• 2 years ago

{fmt} has an optional implementation of the old Dragon4 algorithm that is smaller in terms of code size but not as fast.

ziml772• 2 years ago

I learned how much floating point formatting needs when I was doing work with Zig recently.

Usually the Zig compiler can generate binaries smaller than MSVC because it doesn't link in a bunch of useless junk from the C Runtime (on Windows, Zig has no dependency on the C runtime). But this time the binary seemed to be much larger than I've seen Zig generate before and it didn't make sense based on how little the tool was actually doing. Dropping it into Binary Ninja revealed that the majority of the code was there to support floating point formatting. So I changed the code to cast the floating point number to an integer before printing it out. That change resulted in a binary that was down at the size I had been expecting.

delta_p_delta_x2• 2 years ago

Usually the Zig compiler can generate binaries smaller than MSVC because it doesn't link in a bunch of useless junk from the C Runtime (on Windows, Zig has no dependency on the C runtime)

MSVC defaults to linking against the UCRT, just like how Clang and GCC on Linux default to linking against the system libc. This is to provide a reasonably useful C environment as a sane default.

If you don't want UCRT under MSVC, supply `/MT /NODEFAULTLIB /ENTRY:<function-name>` in the command-line invocation (or in the Visual Studio MSBuild options).

It is perfectly possible to build a Win32-only binary that is fully self-contained and only around 1 KiB.

jk-jeon2• 2 years ago

https://github.com/jk-jeon/dragonbox/discussions/57#discussi...

We have been doing some experiment on optimizing for size, and currently it can be reduced to ~3k on 8-bit AVR. It only contains impl/table for single-precision binary32, and double-precision requires quite more, but at the same time much of the bloat is due to how limited AVR is. On platforms like x64 it should be much smaller.

You can certainly say 3k is still huge though.

franga2000• 2 years ago

I'm guessing the majority of use-cases limit the number of decimal points that are printed, I wonder if it would be more efficient to multiply by the number of decimals, convert to int, itoa() and insert the decimal point where it belongs...

jk-jeon2• 2 years ago

Not sure what you mean by decimal points. Did you mean the number of decimal digits to be printed in total, or the number of digits after the decimal dot, or something else?

In any case, what Dragonbox and other modern floating-point formatting algorithms do is already roughly what you describe: they compute the integer consisting of digits to be printed, and then print those digits, except:

- Dragonbox and some of other algorithms have totally different requirements than `printf`. The user does not request the precision, rather the algorithm determines the number of digits to print. So `1.2` is printed as `1.2` and `1.199999999999` is printed as `1.199999999999`. You can read about the exact requirements in the Readme page of Dragonbox.

- The core of modern floating-point formatting algorithms is on how to compute the needed multiplication by a power of 10 without needing to do it by the plain bignum arithmetic (which is incredibly slow). Note that a `float` (assuming it's IEEE-754 binary32) instance can be as large as 2^100 or as small as 2^-100. It's nontrivial to deal with these numbers without incorporating bignum arithmetic, and even if you just give up avoiding it, bignum arithmetic itself is quite nontrivial in terms of the code size it requires.

londons_explore6• 2 years ago

I kinda hoped a formatting library designed to be small and able to print strings, and ints ought to be ~50 bytes...

strings are ~4 instructions (test for null terminator, output character, branch back two).

Ints are ~20 instructions. Check if negative and if so output '-' and invert. Put 1000000000 into R1. divide input by R1, saving remainder. add ASCII '0' to result. Output character. Divide R1 by 10. put remainder into input. Loop unless R1=0.

Floats aren't used by many programs so shouldn't be compiled unless needed. Same with hex and pointers and leading zeros etc.

I can assure you that when writing code for microcontrollers with 2 kilobytes of code space, we don't include a 14 kilobyte string formatting library...

vient• 2 years ago

It is a featureful formatting library, not simply a library for slow printing of ints and strings without any modifiers. You can't create a library which is full of features, fast, and small simultaneously.

jstimpfle3• 2 years ago

You'd hope the unused stuff gets stripped out but I don't know much about this topic so not going to argue.

jstimpfle3• 2 years ago

Curious what space space you work in? What kind of devices, what are they used for?

londons_explore6• 2 years ago

Not me but a friend. Things like making electronics for singing birthday cards and toys that make noise.

But there are plenty of other similar things - like making the code that determines the flashing pattern of a bicycle light or flashlight. Or the code that does the countdown timer on a microwave. Or the code that makes the 'ding' sound on a non-smart doorbell. Or the code that makes a hotel safe open when the right combination is entered. Or the code that measures the battery voltage on a USB battery bank and puts 1-4 indicator LED's on so you know how full it is.

You don't tend to hear about it because the design of most of this stuff doesn't happen in the USA anymore - the software devs are now in China for all except high-end stuff.

IshKebab4• 2 years ago

It isn't designed to be small; it's designed to be a fully featured string formatting library with size as an important secondary goal.

If you want something that has to be microscopic at the cost of not supporting basic features there are definitely better options.

I can assure you that when writing code for microcontrollers with 2 kilobytes of code space, we don't include a 14 kilobyte string formatting library...

No shit. If you only have 2kB (unlikely these days) don't use this. Fortunately the vast majority of modern microcontrollers have way more than that. E.g. esp32 starts at 1MB. Perfectly reasonable to use a 14kB formatting library there.

londons_explore6• 2 years ago

When you're designing something that sells for a dollar to retailers, eg. a birthday card that sings, your boss won't let you spend more than about 5 cents on the microcontroller, and probably wants you to spend 1-2 cents if you can.

Narishma• 2 years ago

esp32 starts at 1MB

Which models? The most I've ever seen on an ESP32 is 512KB of SRAM.

maccard3• 2 years ago

What do you use instead?

Iostream is… far bigger than this, for example.

Sharlin• 2 years ago

I presume the sort of custom routines that GP described?

londons_explore6• 2 years ago

most platforms come with their own libraries for this, which are usually a mix of hand coded assembly and C. You #include the whole library/sdk, but the linker strips out all bits you don't use.

Even then, if you read the disassembled code, you can usually find within a few minutes looking some stupid/unused/inefficient code - so you could totally do a better job if you wrote the assembly by hand, but it would take much more time (especially since most of these architectures tend to have very irregular instruction sets)

criddell• 2 years ago

If you only have 2 kB of code space, you would likely be doing custom routines in assembly that do exactly what you need and nothing more.

secondcoming• 2 years ago

Would someone writing code for a 2Kb microcontroller even be using full-fledged C++, or just C With Classes?

londons_explore6• 2 years ago

It's still full fledged C++, you just don't use many of the features, and the compiler leaves out all of the associated code.

Pretty easy to accidentally use some iostream and accidentally pull in loads of code you didn't want though.

formerly_proven2• 2 years ago

avrlibc's small variant of printf (which still has a ton of features) is like 600 bytes.

jeroenhd2• 2 years ago

I don't think the requirements for your specific programming niche should influence the language like that. Your requirements are valid, but they should be served by a bottom of the barrel microcontroller compiler rather than the language spec.

MobiusHorizons2• 2 years ago

It’s relevant because the author mentions microcontrollers as the reason for focusing on binary size.

sixfiveotwo10• 2 years ago

I can assure you that when writing code for microcontrollers with 2 kilobytes of code space, we don't include a 14 kilobyte string formatting library...

I'm pretty sure you wouldn't use C++ in that situation anyway, so I don't really see your point.

usrnm• 2 years ago

If you get rid of the runtime, which most compilers allow you to do, C++ is just as suitable for this task as C. Not as good as hand-rolled assembly, but usable

ta9882• 2 years ago

You can use c++ yes and a lot of people do. You just keep the exceptions, stdlib and runtime in general at the door.

aseipp• 2 years ago

The design of any library for a microcontroller and an "equivalent" for general end user application is going to be different in pretty much every major design point. I'm not sure how this is any more relevant to fmt than it is just general complaining out in the open.

The code for an algorithm like Dragonbox or Dragon4 alone is already blowing your size budget, so the "optional" stuff doesn't really matter. And that's 1 of like 20 features people want.

ska• 2 years ago

Sure, but there are also microcontrollers with a lot more space. This probably won’t ever usefully target the small ones, but that doesn’t mean it isn’t useful in the space at all.

fsckboy• 2 years ago

I can assure you that when writing code for microcontrollers with 2 kilobytes of code space, we don't include a 14 kilobyte string formatting library...

then the thing to do is publish the libraries you do use, right, then document what formatting features they support? then other people might discover more and clever ways to pack more features in than you thought of

otherwise, I don't get your point.

dinkumthinkum• 2 years ago

What? I mean, you realize that fmtlib is much more complicated than that, right? What you are describing is something very basic, primitive by comparison. I’m also puzzled why you think floats are not used by many programs, that’s kind of mind-boggling. I get that you wouldn’t load it on a microcontroller but you wouldn’t do that with the standard library either.

progmetaldev2• 2 years ago

As someone coming into this programming space, is it common to be running a debugger that can read the float, as opposed to someone brand new to the space printing out a value for debugging. Not specifically comments like yours, but in general the assumption that others should know their tools as strongly as those profess in limited environment spaces, makes it seem that this is a space only for those with a high level of knowledge. That is absolutely not a knock on your knowledge or ability if that is just how things are, I'm sure there are specific areas of computing that require a vast knowledge of how things work without having a library to debug your issues into the way a simple print statement works. I have worked in limited environments, so I am curious specifically about a microcontroller environment like londons_explore specified.

I learned to program in Atari 8-bit systems, and know there are limitations on what you can output. londons_explore had a completely valid comment. I was just looking for a perspective for developers getting involved in microcontroller environments, and how they could best debug their code. We all know that a debugger is better than a "print" statement, but not always the fastest, especially with logic. If my answer is just "debugging", and there isn't another, that satisfies me. I am always looking for unique ways developers solve problems in ANY environment, because I would enjoy being able to work in any environment that's best for the solution being provided. I guess I have been blessed with environments where the client is willing to pay for something higher-level than what is actually required.

I enjoy all aspects of development across devices, so I hope nobody took my comment as a challenge, it absolutely was not.

jcelerier2• 2 years ago

strings are ~4 instructions (test for null terminator, output character, branch back two).

that's C strings. You also need to handle (size, data) strings like std::string_view

For the record, here's what fmt allows (from the docs):

    fmt::print(fmt::emphasis::bold | fg(fmt::color::red)
             , "Elapsed time: {0:.2f} seconds", 1.23);
    fmt::print("Elapsed time: {0:.2f} seconds"
             , fmt::styled(1.23, fmt::fg(fmt::color::green)  fmt::bg(fmt::color::blue)));
 
    fmt::print("{}", fmt::join(std::vector<int>{1, 2, 3}, ", "));

    fmt::print("strftime-like format: {:%H:%M:%S}\n", 3h + 15min + 30s);

you really think you can replicate that in 50 bytes?

pzmarzly• 2 years ago

However, since it may be used elsewhere, a better solution is to replace the default allocator with one that uses malloc and free instead of new and delete.

C++ noob here, but is libc++'s default allocator (I mean, the default implementation of new and delete) actually doing something different than calling libc's malloc and free under the hood? If so, why?

murderfs• 2 years ago

No, modulo the aligned allocation overloads, but applications are allowed to override the default standard library operator new with their own, even on platforms that don't have an equivalent to ELF symbol interposition.

masklinn2• 2 years ago

That doesn't really explain where the dependency on the C++ runtime come from tho, as far as I know the dependency chain is std::allocator -> operator new -> malloc, but from the post the replacement only strips out the `operator new`.

Notably I thought the issue would be the throwing of `std::bad_alloc`, but the new version still implements std::allocator, and throws bad_alloc.

And so I assume the issue is that the global `operator new` is concrete (it just takes the size of the allocation), thus you need to link to the C++ runtime just to get that function? In which case you might be able to get the same gains by redefining the global `operator new` and `operator delete`, without touching the allocator.

Alternatively, you might be able to statically link the C++ runtime and have DCE take care of the rest.

pjmlp8• 2 years ago

ISO C++ doesn't require new and delete default implementations to call down into malloc()/free().

Many implementations do it, only because it is already there and thus it is easy just to reach for them.

1000100_1000101• 2 years ago

Not the strongest on C++ myself, but the new[] will attempt to run constructors on each element after calling the new operator to get the RAM. The delete[] will attempt to run destructors for each element before calling operator delete[] to free the RAM.

In order for delete[] to work, C++ must track the allocation size somewhere. This could be co-located with the allocation (at ptr - sizeof(size_t) for example), or it could be in some other structure. Using another structure lowers the odds of it getting trampled if/when something writes to memory beyond an object, but comes with a lookup cost, and code to handle this new structure.

I'm sure proper C++ libraries are doing even more, but you already get the idea, new and delete are not the same as malloc and free.

OskarS• 2 years ago

In order for delete[] to work, C++ must track the allocation size somewhere.

That is super-interesting, I had never considered this, but you're absolutely right. I am now incredibly curious how the standard library implementations do this. I've heard normal malloc() sometimes colocates data in similar ways, I wonder if C++ then "doubles up" on that metadata. Or maybe the standard library has it's own entirely custom allocator that doesn't use malloc() at all? I can't imagine that's true, because you'd want to be able to swap system allocators with e.g. LD_PRELOAD (especially for Valgrind and stuff). They could also just be tracking it "to the side" in some hash table or something, but that seems bad for performance.

bangaladore• 2 years ago

realloc is the same, as the old memory needs to be copied to the new memory.

progmetaldev2• 2 years ago

Isn't it also possible for other logic to run in a destructor, such as freeing pointers to external resources? Doesn't this cause (at the very least) the possibility for more advanced logic to be run beyond freeing the object's own memory?

janos95• 2 years ago

The main point of replacing it with malloc is that new will throw std::bal_alloc so using it requires linking against the c++ runtime.

pjmlp8• 2 years ago

Only if not using nothrow placement new syntax.

neonsunset• 2 years ago

It's always fmt. Incredibly funny that this exact problem now happens in .NET. If you touch enough numeric (esp. fp and decimal) formatting/parsing bits, linker ends up rooting a lot of floating point and BigInt related code, bloating binary size.

pjmlp8• 2 years ago

Still looking forward for the Delphi like experience with Native AOT, thankfully getting better.

msephton• 2 years ago

Very enjoyable. I love these sort of thinking outside the box optimisations.

a1o2• 2 years ago

Considering that a C program with an empty main function is 6kB on this system, {fmt} now adds less than 10kB to the binary.

Interesting, I've never done this test!

JonChesterfield• 2 years ago

It varies widely with whether the C library is dynamically or statically linked and with how the application (and C library) were built. And on which C library it is. Also a little on whether you're using elf or some other container.

ptspts• 2 years ago

Shameless plug: printf(Hello, World!\n"); is possible with an executable size of 1008 bytes, including libc with output buffering: https://github.com/pts/minilibc686

Please note that a direct comparison would be apples-to-oranges though.

jart• 2 years ago

That's because the compiler turns it into fputs

rty322• 2 years ago

Maybe I am slow, it took me a while to realize the "14k" in the title refers to "14kB"

hrydgard• 2 years ago

What else would it possibly mean?

k is very common shorthand for kB, at least historically.

Rygian• 2 years ago

14000 lines of assembler?

Honey, I shrunk {fmt}: bringing binary size to 14k and ditching the C++ runtime

Related Stories