Hacker News new | past | comments | ask | show | jobs | submit login
Diving into GCC Internals (gcc-newbies-guide.readthedocs.io)
212 points by penguin_booze on June 13, 2022 | hide | past | favorite | 53 comments



If anyone wants to make an easy but useful improvement to GCC, might I suggest: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=58770

Summary: headers that use pragma once are tracked using a list resulting in slow uniqueness checks. The performance fix is to use a hash table.


Wait. So gcc uses a linked list? OK, but why? If the whole point of #pragma once is to replace include guards, why would they use something as inefficient as a linked list (O(n^2) for this situation[a]) for that, but something quicker for include guards? That’s nonsense!

And then for each .c/.cpp file, the compiler has to do the whole rigamarole all over again because modules are too new for everyone to use.

[a]: or worse when you have a full project!


Basic CS fail.

Most translation units have maybe 100 header files or fewer. While a hash map might be O(1) (O(n^2) worst case) and a linked list O(n^2), the overhead of every insertion into a hash map is significantly greater than into a linked list. If you have such a tiny n, a linked list is almost always more time- and space-efficient. Switching to a more inappropriate data structure is more likely to negatively impact the performance of your toolchain.

Of course the best answer is to make the change and collect measurements before and after using a spectrum of data sets, then compare. Don't let me stop you. But remember for that small a number of items bubble sort is usually the fastest, most efficient algorithm. Also remember that looking up a header name at preprocessor time, no matter how slow, will likely not show up on your profile graph when you turn on the optimizer.


Regardless of what’s better, my comment was more about how they have a profiled and optimized method for include guards, but threw it all away for #pragma once. If performance doesn’t matter because the optimizer is worse, then why’d they optimize include guards?

My whole point is that something is not adding up with gcc’s implementation. It’s a fail on the authors’ parts, not mine.


I’m pretty sure I read something on HN the other day that showed that a linked list is almost always a bad choice, even for small values, due to memory locality issues.


> Unfortunately, there are very few developers working on the preprocessor and very few users of "#pragma once", so this will likely have very low priority unless one of those users takes the lead to fix it.

    $ cd 
    $ rg --stats 'pragma once' -g '*.{h,hpp}?'
    45406 matches
frustrating


The generated switch statements for large sparse lists should be generated to hash tables, perfect tables even. A not so trivial task.


Off topic, but TIL pragma once isn't part of the standard. I was wondering why clang-tidy didn't have a check for it...


C 11 standard, 6.10.6 "Pragma directive"

A preprocessing directive of the form

    `#pragma pp-tokens_opt new-line`
where the preprocessing token STDC does not immediately follow pragma in the directive (prior to any macro replacement) causes the implementation to behave in an implementation-defined manner. ...

Pragma directives are only part of the C standard if followed by STDC. The ISO C++ standard does not require any pragmas to be supported at all, though most compilers will support at least the ones required by C even in C++ mode.


#pragma once isn't needed for GCC anyway. It recognizes include guards and doesn't reparse headers that have already been processed.


That’s not an argument; every major C compiler recognizes include guards, and every standards compliment C compiler supports them. The whole point of #pragma once is so you don’t have to use them and worry if you have naming collisions.

The issue is that gcc uses a horribly performant method of handling #pragma once when it’s nothing more than a fancy include guard. Clearly they have some quick and optimized way of seeing if a file was #ifdef include guarded, but they created a whole other system based on linked lists for #pragma once.


I teach a C++ class, and I can assure you that one of the most frequent errors I see in students' codes is to copy-and-paste a header file into another and modify it instead of writing a new one from scratch (beats me why they think this is efficient), forgetting to change the name of the include guard or only modifying the #ifdef part but not the #define part.

Since a few years I teach them only to use #pragma once, and the problem has disappeared.


> the problem has disappeared.

No, it did not.

You have empirically found a wonderful way to teach your students that their errors are their responsibility, and you are wilfully giving it up and sort of spoiling them.

Extrapolating a bit, you are helping them join the idiots who complain about undefined behaviour while proudly showing their horribly wrong code.


Yes, it did. The problem has literally disappeared.

I believe that I can teach more interesting ways to catch and prevent errors than that stuff. I find that #ifdef/#define errors are boring and not interesting. The #ifdef/#define errors are due to the archaic way to literally include C/C++ files one into another. By following your reasoning, one would «spoil» their own students and making them «idiots» just by using a language with a proper module system (Rust, Python, Pascal, Ada, Nim…).

Moreover, suggesting to use "#pragma once" means to teach them that you can use the features of the language at your advantage. It is silly to use X if it is error prone when there is Y that is simpler and prevents you from doing that kind of error. I am teaching them that it is worth to dig in the specification of your language and check for possible alternatives of doing X.

I'll give you a hint. Please should stop teaching your students how to write Makefiles just because you want to let them know that a tab at the beginning of a line is different than eight spaces, seriously. Make them learn CMake and use the time in your class to teach more useful stuff about dependencies, feature discoverability, etc. Your students will be eternally grateful.


I'm not advocating for keeping pragma once a secret: just let them use the historical way once, fall into the beginner error, and let them notice how dangerous copy/paste can be.


In the absence of an IDE to manage include guards, they are pointless busywork that make refactoring harder. The future solution would be C++ modules, but in absence of that pragma once is a lifesaver.


It's not needed for any compiler. People use it because it's a whole lot nicer to write.


Gosh, I really wish GCC had more/better documentation. Especially big picture stuff. E.g., I would like to know what register allocation algorithms it uses (and how certain details are handled), but looking at that code I noped out...


It uses something they call IRA and LRA on the RTL representation. But bottom line is: it's graph colouring.

https://gcc.gnu.org/onlinedocs/gccint/RTL-passes.html

There's really quite a lot of documentation and published papers when you actually look:

https://github.com/gcc-mirror/gcc/blob/751f306688508b08842d0...


LLVM: Lots of documentation for frontend authors, not so much for backend stuff.

GCC: Lots of documentation for backend authors, actively made difficult to being used for frontends for many years (although things have improved dramatically)


How have things evolved for LLVM backend authors? Has it improved too?


You can read GCC Summit presentations for things like that. The register allocator is called IRA/LRA. It used to have a ball of mud called reload that isn’t worth understanding because it doesn’t make much sense.

GCC’s code style is strange because the original authors wanted to make it look like Lisp for some reason.


Err I always thought it looked strange because it was in C with classes before or after some holy war.

While gcc (and in general compiler) plugins are some of the most interesting tech enablers (be it for fuzzing,, static analysis, or runtime checks injection) 'People competently maintaining gcc plugins' (a sect I'm not a part anymore, thank dog) are amongst the most patient, devoted, unsung angels of this world.


It’s in C++ now. The weird spacing and functions ending in _p are Lispisms.

It’s also garbage collected so it’s still not “normal” C++ but neither is LLVM.

Not sure about the plugin API, but C++ is basically impossible to use with plugins because it’s so hard to keep ABI contracts, so it might not have changed.


Well you basically have to compile the plugins against your gcc's headers anyway, and they're gpl by default (same as wireshark dissectors iirc). No the pain is all the churn on gcc internals and in plugin APIs over the years. You basically become an ifdef monkey and end up testing myriads of gcc versions...


Isn’t the compiler the one who makes the ABI contract?

And I’ve seen _p and friends all over the place usually to differentiate between a pointer and, umm, not pointer. I thought it was a C++ism to be honest.


C++ has things like the fragile base class problem meaning you can accidentally break it easily. There's issues with throwing exceptions across different libraries on some platforms (maybe just Windows?) but I forget the reason why.

p is short for predicate.


Fragile base class problem affects all languages that offer some kind of inheritance, not only C++.


You are of course correct in a broad sense.

However, when the discussion already mentions "ABI contracts", they're probably referring specifically to the "fragile binary interface problem" (especially regarding member field access), which does not affect all languages that offer inheritance.

As the Wikipedia article mentions, this more specific problem is (confusingly) often referred to just as the "fragile base class problem".

https://en.wikipedia.org/wiki/Fragile_binary_interface_probl...


It still affects all compiled languages that offer inheritance, and OOP ABIs like COM.


Maybe I'm still misunderstanding you, but (modern) Objective-C is an example of a compiled language without the fragile base class ABI problem.

(It pays for this with extra indirection at runtime, of course: ivar accesses must first look up their runtime-resolved offset.)


Maybe the lispism are Stallman's legacy. He is a great lisp proponent after all.


This might be less true now, but for a long time gcc's code was terrible and undocumented on purpose. rms wanted it that way, to make it harder for it to be forked or EEE'd by corporations.

Whether that was a good plan is up for debate, but there you go.


People say that dmd's backend is terrible and undocumented, but I don't know what they're talking about:

https://github.com/dlang/dmd/tree/master/src/dmd/backend


> I would like to know what register allocation algorithms it uses

I'm wondering why you'd like to know. If it is just for your curiosity, that's very good. If you want to participate in the compiler development effort, hat tip!

But if you are thinking about tuning your code to such an internal detail, please don't! Coding to an implementation, rather than an interface, is never a good idea.


One thing I've heard about even modern compilers is that they don't really release memory during compilation, as it's faster just to use the memory and release it all when the process exits. How true is that?


It is true that that is of course faster. However, clang and GCC, both do release memory since with modern C++ software projects, it can take huge amounts of ram to compile them.

https://dmalcolm.fedorapeople.org/gcc/newbies-guide/memory-m...


> It is true that that is of course faster.

Is it? What do you base that on?

I would guess that this hypothesis was true at one time, but is no longer, due to relative memory latencies increasing that mean that the resulting lack of locality becomes a very big problem.

I think this is empirically support by for example this research result, where epsilon collectors are not the highest throughput.

https://users.cecs.anu.edu.au/~steveb/pubs/papers/lbo-ispass...


The nix programming language's interpreter deliberately has no memory garbage collector based on this argument.

This decision does force a few other architectural decisions, and as a result has led to a few firey debates.

Most nix users are surprised to learn that nix has no GC. It's unfortunately hard to search for details about this since nix uses the phrase "garbage collection" to describe something it does to the filesystem, rather than memory.


Gives me PTSD to my operating systems class in university. Once upon a time I knew how a linker actually worked under the hood, but those days are long gone.


GCC really needs to get it's act together if it wants to not die. Basic things like onboarding and spectating on other people's code being reviewed is pretty hard to do from a mailing list.

GCC is already basically non-existent in academic research now, although the inner essentials of the compiler are still pretty damn good and is the benchmark for open source compilers, the stuff around the outside is suffering.


Pretty interesting history behind the current status quo. Looks like GCC deliberately resisted an interoperable design in an attempt to exclude proprietary code integration. It's only natural that interoperable alternatives would emerge and threaten its dominance.

https://lwn.net/Articles/582697/

> GCC's developers have actively resisted allowing it to be modularized in a way that would allow GCC's internal representation of a program to be read and used by proprietary compilation tools or optimizers.

Learning about this changed the way I looked at all GNU software.

> Basic things like onboarding and spectating on other people's code being reviewed is pretty hard to do from a mailing list.

Participation is even harder. I made some mistakes when I tried to reply to people on the GPG mailing list because I didn't really understand how mailing lists worked. Thankfully a person made a bug report on the issue tracker.

I still don't fully understand how they work. Many times I thought twice before getting involved in projects because I don't want to risk accidentally emailing people directly instead of the list thread again.


> Pretty interesting history behind the current status quo. Looks like GCC deliberately resisted an interoperable design in an attempt to exclude proprietary code integration. It's only natural that interoperable alternatives would emerge and threaten its dominance.

This hasn't been true for at least 10, maybe 15 years.

Mailing list development is very traditional; it's what git was initially designed around, with `format-patch` and `am` commands. People moving to Github and PRs is a generational shift thing, like using TikTok.


Stallmann was still putting up this fight until at least a couple of years ago. Maybe a critical mass of people finally told him to fuck off, but if that happened it was within the past 6-8 years.


Doesn't really matter what he wants if he's not on the GCC steering committee.

Though I know someone who was fired from being GNU libtool maintainer by Stallman because he developed on a Mac.


>> GCC's developers have actively resisted allowing it to be modularized [...] > > Learning about this changed the way I looked at all GNU software.

It means that you had not yet understood the principle behind free software. I'm not defending Stallman's choice, but it is coherent with the philosophy that gave us FSF and GNU.


I understand the principles behind free software. I also understand those principles ultimately undermined the most important free software project ever created.


> actively resisted allowing it to be modularized

and this is exactly the place where LLVM shines.


As policies for academics to own intellectual property and form companies, the license also has come into play. The license also has influenced corporate choices and advocacy for toolchain projects. Documentation and actively encouraging new developers is important, but not the only impact on the project.


[flagged]


I don't know what the sarcasm is helping. Somebody's working on documenting it and they're not done yet, and they're documenting that too.


Yeah, I'm being salty, but at the same gcc is notoriously unapproachable while also struggling to pull in new blood. Considering the long, but sporadic update history [1] of this documentation, I am not optimistic about this effort turning it around. Seems more likely to become yet another one of the out of date or incomplete tutorials lying around [2]. GCC's own contribution docs [3] cop to the fact that most new contributors are doing paid work on behalf of chip and system designers, so for GCC's sake I hope it remains the must have compiler for new chips because that seems to be its main source of fresh blood at this point. This blog post [4] from a GCC and autotools developer popped up on here a month ago, and while it doesn't address GCC, if you squint I think you can apply most of the criticisms to GCC as well.

[1] https://github.com/davidmalcolm/gcc-newbies-guide/commits/ma...

[2] https://gcc.gnu.org/wiki/GettingStarted

[3] https://gcc.gnu.org/contributewhy.html

[4] https://www.owlfolio.org/development/autoconf-swot/


Yeah, I'm being salty

You've hit upon a reliable way to turn that kind of comment into a good comment which is to imagine the grumpcomment getting downvoted, flagged, complained about or mod-scolded, writing a defense of the grumpcomment and then just posting that, instead of the original comment. Works every time way more than 60% of the time.


It'll lose that too as more and more low-level software is written in LLVM-backed languages.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: