Hacker News Reader

> I'm sure vectors of ints is quite common. I wish C++ could share that generated object code (not the instantiated template at compile-time). [...] I wish the compiler could aggressively look for and link to instances that have the same binary representation - even if they have disparate type information.

Today your wish comes true, because this is something that compilers do and have done for a very long time. Redundant definitions of templated functions which didn't get inlined always get dropped at link time. VC++ and the Gold linker also have a feature called "Identical COMDAT Folding" which will agreesively merge functions with different names but identical bodies, which can merge distinct template instantiations in the case where the concrete type doesn't effect the compiled representation.

extern templates are orthogonal to this whole thing; they're purely a compile speed optimization and have no effect on the end binary after linking.

> Redundant definitions of templated functions which didn't get inlined always get dropped at link time.

I wonder how many things aren't aggressively inlined in C++..

---

Are you saying `extern template` is used like a `#pragma once` just for the template? I thought it had a greater effect on linking. :(

My concern is that even if the generated object code for std::vector<int> and a binary-compatible type like std::vector<something> are deduplicated in your codebase, that same object code for that specialized type of vector probably exist in several different programs throughout my system. (as an example)

That is implementation specific behavior and changes even between versions of the same compiler.

Has it should be, actually. Freezing inlining algorithms in a language specification hinders future optimization algorithms.

Chandler Carruth has done quite a few interesting talks how the clang inliner works.

I'm not sure what purpose your desire would serve, or even if it makes sense. For example, this is a contradiction: "I wish the compiler could aggressively look for and link to instances that have the same binary representation - even if they have disparate type information."

The generated object code for thing<int> and thing<double> are likely to not be identical, except for where the types are manipulated. Because thing<int> and thing<double> generate entirely different classes, they can actually be radically different. First, C++'s resolution rules allow them to be actually different C++ code. But even if it reuses the C++ code, because that code then goes through the optimization phases, what comes out the other side may not have the kind of trivial relationship you're thinking of.

I don't think this is unique to C++; it should be true of any language that has non-type erased generics that generates native code. I'm thinking of Haskell, OCaml and Rust - but if people who know those languages and compiler chain better think I'm wrong, please speak up.

Personally, I find C++'s templates to be extremely useful and powerful. I also think they are demonstrably not as nearly as hackish as the C preprocessor, as evidenced by the fact that they actually have knowledge of types. The C preprocessor is just textual substitution, while C++'s templates are far, far from that.

To the best of my knowledge, (GHC) Haskell and OCaml don't need to monomorphize parametrically polymorphic code, because they use a uniform representation for most objects. Some features of these languages, like GADTs and polymorphic recursion, are difficult to reconcile with monomorphization anyway.

On the other hand, Rust generics are monomorphized at compile time, which is closer to how C++ templates work. (The most important difference is that Rust generics are type-checked at definition time, rather than instantiation time.) Another language implementation that uses compile-time monomorphization is MLton, a whole-program Standard ML compiler.

Ideally, the language should offer the programmer two kinds of polymorphism: (0) second-class, which is less expressive but easier to type-check and more amenable to optimization, (1) first-class, with the opposite tradeoff.

I mean to say, the compiler might see std::vector<a> and std::vector<b> as strictly separate types, but at their base/binary might be code that is identical (effectively std::vector<int>). I am imagining that the compiler would generate code for both, and not see the opportunity to deduplicate identical object code. Again, I suspect I am naive here.

I think you're saying that a and b are actually typedefs to the same type. Yes, in that case I believe C++ compilers are smart enough to share code.

If `a` and `b` are typedefs to the same type, then `foo<a>` and `foo<b>` are literally the same type, so sharing code isn't a matter of compilers being “smart” - it's a matter of respecting C++'s semantics.

I think GP is talking about something different. Let's say you have two completely unrelated types `a` and `b`, but, for whatever reason, `foo<a>` and `foo<b>` happen to compile to exactly the same machine code. (For a concrete example, say `a` and `b` have the same size and alignment requirements, and say `foo` is `std::vector::reserve`.) Then either the compiler or the linker can “merge” the duplicated code for `foo<a>` and `foo<b>`.

That is not what I'm saying.

Example: You can have 2 struct types that each only contain an int with the same member name. They would [likely] have the same binary representation. You could then create 2 vector types specialized for each struct type. The code for both vectors would handle the data in the same way - but the compiler would view the vector types as _STRICTLY_ separate types.

I do not think this code would be uniquely shared - the compiler would generate code for both vector types.

Now I get what you're saying. I think it's possible for a C++ compiler to be smart about this. But why is this such a big deal to you? Have you seen it become an issue in projects you've worked on?

Full disclosure: I have not had a problem with this.

It's just a theory I have that this is low-hanging fruit to reduce C++ binary size.

You're less likely to define the same structure and methods of a type in exactly the same way as someone else in C because we don't have the STL (ofc). So it's probably a worse issue in C having a hundred different implementations of a linked list or some array type across your system in each program.

I just think there's an opportunity to aggressively dedupe object code for "representation-identical" types in C++.

We've had optimizing C++ compilers for a long time - decades. I think it's safe to assume that the low-hanging fruit was picked a long time ago.

Forgive me here if I'm being argumentative, but I think we're both speculating.

Someone further up the chain mentioned this sort of deduplication might be done by the linker, but the code for the duplicated type would still exist in the binary before linking.. An old but probably negligible complaint about C++ is that it creates larger binaries than if one were writing C. I think this is something overlooked because C++ has a focus on type strictness - perhaps the linker has a better way of seeing through abstractions..

I've identified where I think a problem lies.. now I just have to find proof it :3

Unrelated: I wonder if identical libraries that exist in separate filesystem trees (like in Docker) are deduped in memory, or if it's done by inode.

I'm not an expert on this in any way either, but I think template instantiations end up as 'weak symbols' in object files, so when you link multiple objects together that contain the same template instantiations, you only end up with one of them in the final object file.

This of course means that compile times are a bit longer, as a given template may be instantiated by the compiler many times, but in terms of run-time and final object size it should be optimal.

I think this behaviour also makes more sense when you think about inlining -- a lot of template code is actually doing something quite simple under the hood, so by having the compiler instantiate your template each time, you potentially allow it to inline the code qithout relying on a LTO, which may not have been feasible when this whole mess was designed.

The linker can consolidate binary-identical functions if you really want, although generally linkers limit themselves to string consolidation.

"Defined ABI" is something of a problem, as C++ is required to work on a variety of current and future hardware platforms, with disparate calling conventions and the like.

Monkeypatching is not something I understand how or why one would attempt in C++, but there's always the option of building yourself a C-style collection of function pointers and swapping them out at runtime. Or, may God have mercy on your soul, Windows COM.

Templates are C++'s metaprogramming feature. Without them there would have to be another means of implementing generics. The syntax is often ugly and occasionally bananas, but they're one of the things that make C++ what it is.

Templates are actually much more advanced, in several ways, than C-style preprocessor macros. Maybe this was the part where you would "sound like English isn't your first language" though? etc etc...

I understand that templates offer several protections over the problematic macros one would write in C, but I do not believe templates are the right way to write for generic behavior.

what would you design then? (That can be done statically)