Saturday, October 8, 2011

Caring by Sharing: Header Hero


Compile times get worse over time, that is the second law of C++ programming dynamics. There are many small day-to-day changes that each exacerbate the problem slightly: The project grows. New header files get included. Clever templates get written. And so on. There are comparatively few forces that work in the other direction. Once an #include has been added, it stays.

The only exception is when some hero steps up, says Enough! and starts to crunch down on those header files. It is thankless menial work that offers few rewards, save the knowledge that you are contributing to the public good.

Today, I want to give something back to these unsung heroes, so I’ve made a small tool to make their drudgery a bit less... drudgery-ish? It is called Header Hero:


To run Header Hero you specify the directories where your .cpp files can be found as well as the directories to search for included headers. The program scans your .h and .cpp files to find all the include links. It presents the result in a summarized report that shows you what the worst headers are. You can think of it as a header file profiler.

You don’t need to specify all your include directories, but only the ones you have specified will be scanned.

I’ve focused on making the tool fast by caching as much information as possible and using a simple parser that just looks for #include patterns rather than running the real C preprocessor. The downside is that if you are using any fancy preprocessor tricks, they will most likely be missed. On the other hand, the tool can scan a huge project in seconds. And after the initial scan, new scans can be done in a fraction of that time.

The program produces a report that looks something like this:


At the top are some statistics, such as the total number of files and lines in the project. Total Parsed counts how many lines that would actually be parsed in a full recompile of the project. So, a header that is included by several .cpp files adds to that number every time. The Blowup Factor are the last two items divided. It specifies how many times, on average, each line gets parsed. A value of 35 means that on average, each line in our project is parsed 35 times. That seems quite a lot.

Below the summary are a list of the header files sorted by how many lines they contributed to the Total Parsed number. In other words, the size of that file multiplied by the number of times it was included.

Looking at the sample report above, it seems pretty reasonable. At the top we find big templated collection classes (map, set, string, vector) that have big header files and are used in a lot of places. Math (matrix4x4, vector3) and utility (critical_section, file_system) files also end up high on the list.

But when you dig into it, there are also things that seem a bit fishy. Set<T> is not a very popular collection class. Sets are used less than maps, and HashSet is usually preferable to Set. Why does it end up so high on the list? What is shader.h doing there? That seems too specialized to end up so high. And file_system.h? There shouldn’t be that much code that directly accesses the file system, only the resource loader needs to do that.

To answer those questions, you can click on any file in the report to get a detailed view of its relations:


In the middle we find the file we are looking at. To the left are the files that directly include it. The number after each file name specifies how many files that directly or indirectly include that file. To the right are the files included by the file. The numbers are all the files directly or indirectly included by those files. You can double click on any file name in the view to refocus on it.

Here we clearly see that the main culprit is data_compiler.h. It includes set.h and is in turn included by 316 other files. To fix the compile times we can make data_compiler.h not include set.h or we can try to reduce the number of files that include data_compiler.h (that number also seems high). If we also fix scene_graph.h we can really make a difference.

Breaking dependencies is a whole topic in itself, especially when it comes to templates and inlined code. Here are some quick tips though:

1) Predeclare the structs and classes that you use instead of including the header file. Don’t forget that you can predeclare templates and typedefs as well as regular classes:

class MyClass;
typedef int Id;
template <class T> class Vector;

2) Predeclared types can only be used as pointers and references. You can’t have a member variable of a type whose actual size is unknown. So you may have to change your member variables to pointers in order to get rid of the header dependency. You can also use the pimpl idiom, if you can live with the extra indirection and lack of inlining.

3) Switching from in-place variables to pointers can lead to bad memory access patterns. One way of fixing that is to placement new the object directly into a raw memory buffer.

// a.h

class B;

class A {
    A();
    B *_b;
    static const int SIZE_OF_B = 20;
    char _b_storage[SIZE_OF_B];
};

// a.cpp

#include ”b.h”

A::A()
{
    XASSERT(sizeof(B) == SIZE_OF_B);
    _b = new (_b_storage) B();
}

With this technique, you get the data for B stored inside A, without having to include the b.h header in a.h. But the code isn’t exactly easy to read, so you should only use this in desperate situations.

4) For files with small type definitions, but lots of inlined methods (e.g., matrix4x4.h), a good strategy is to split the file, so you have just the type in one file and all the methods in the other. Header files can then include just the type definition, while .cpp files pull in the whole shebang.

Using these techniques you can get rid of the header dependencies one by one, until you are back at reasonable compile times. Since a rescan takes just a fraction of a second it is easy to see how your changes affect the compile time. Just make sure you have your integration test running, it is easy to break build configurations when you are fiddling around with the headers.

Here is the result of about a day and a half of header optimization in our code base:


From 6 million to 4.3 million lines, that’s not too shabby. We can now do a complete rebuild in 37 seconds on a reasonably modern machine. With this tool we can hopefully keep that number.

You can download the C# source code here. Feel free to do whatever you like with it:

43 comments:

  1. Interesting tool, thanks.
    But FYI after a very simple test I've just made where I commented few #include lines to sse the changes, it seems that those lines are still taken into account, at least for the right column of the detailed view (while it also seems that stats like blowup factor are correctly updated).

    ReplyDelete
  2. Yes, Header Hero's simple parser doesn't understand comments, so delete the lines completely instead of commenting them out.

    Commenting out code is
    bad form anyway ;)

    ReplyDelete
  3. Great stuff. A few things it doesn't handle the way I'd expect:

    Firstly, if there's a header and one .cpp file that includes it, that header seems to be counted twice.

    Generally, a header file will have include guards around it so will only be parsed once per translation unit. So you should really be only counting, for each header file, how many different .cpp files it is transitively included by.

    Of course, neither are showstoppers. I'm looking forward to trying this out!

    ReplyDelete
  4. Yes, I assume include guards and only count the files once per translation units. If you see a file doubly counted, there must be something else going on. I'll investigate.

    ReplyDelete
  5. I tested it. Made a small project with just one header and one .cpp file and the count was correct. If you have something where it counts badly, perhaps you can zip it up and send it to me.

    ReplyDelete
  6. small suggestion. Dont expect "#include". A lot of boost and others use 'pretty printing' in includes. So something like
    string line = inputLine.Trim();
    if (line.StartsWith("#") && line.Contains("include"))
    will show blowup not 35 but 67 :)

    And to be useful the thing probably should read build system instructions for sources/includes - when company starts to separate 'common' libs the src/include filesystem locations start to become quite hairy.

    ReplyDelete
  7. Ah, right! I'll add some better #include-parsing.

    I don't think I'll add project parsing though. That's too messy, with different build systems, configurations, etc.

    ReplyDelete
  8. Thx, it's a simple great tool. I am also a game dev and it can be really boring to wait for a build.

    I did a clean up few month ago on our engin by using PIMPL idiom and cleaning includes at hand, but without your tools it's much more easier to find some little miss.

    Do you know the D language? That make me dream of instantaneous build.

    What is your machine because I build this (i7 2600 under Visual Studio 2010) in 54seconds :
    Files: 419
    Total Lines: 79 102
    Total Parsed: 1 732 757
    Blowup Factor: 21,91

    Those numbers are without standard headers.

    ReplyDelete
  9. Yes, it's crazy that we even have to deal with this stuff. We are still paying the price for the fact that 60's computers couldn't fit both a compiler and a linker in main memory. In modern languages such as D and Go, this isn't even a problem.

    The numbers are from an i7 with lots of memory, compiler set to use all cores. But I don't think you can compare across projects... there are many other things that could affect compile time then the raw line count, such as amount of templates, etc.

    ReplyDelete
  10. I just can suppose our engine is much more simple as yours. We only realize some adventure games ports. We are just adding some real 3D features for a new kind of game, but there is no dynamics, all scenes are precalculated.

    VS 2010 Compiler use all core of our CPU, mine have 4 and 8Go of RAM, but I think your right it's hard to compare without a real analyse of code and compiler work around.

    ReplyDelete
  11. I've wanted to write this tool for a while now, but haven't had the time. Here's what I would do different.

    Flame graphs!!!

    http://www.brendangregg.com/flamegraphs.html

    I think a flame graph visualization would make it easier to find the intermediate include that is dragging in tons of unwanted stuff. You could get good visualization results even if your tool just emitted an .svg that could then be opened in a browser.

    ReplyDelete
  12. I liked your post and I am waiting for your new update.if you are an obsessive gamer also check this out
    Johnny Silverhand Vest

    ReplyDelete
  13. African Mango Seed Extract Market is often combined with other ingredients such as green tea and marketed as a fat-burning supplement. Because of the weight-loss properties associated with the seed extract, along with the rising fears about health problems such as obesity, the market for African mango seed extract is expected to be further propelled forward. The industry is also being driven by the rising demand for foods made from natural ingredients.

    ReplyDelete
  14. Chlorine is a greenish-yellow gas. It has a pungent, suffocating odour. It is slightly soluble in water. It liquefies at -35C.

    Chlorine Production

    ReplyDelete
  15. Are you looking for stylish, trendy, comfortable, easy to carry, best quality jackets and coats? But find it difficult to get one with all your demands? Not anymore! Buy premium quality, super stylish attires at hiltonsky.

    ReplyDelete
  16. We produce high quality trendy products, available at our website christmas apparel at the best possible prices. Buy your favorite jackets and coats to look stylish and classy like your favorite celebrities.

    ReplyDelete
  17. Indulge in the quality and style you have never experienced before! pink ladies jacket brings you the most trendy and stylish product line this season. Visit pink ladies jacket and grab your favorite superstar attires!

    ReplyDelete
  18. This comment has been removed by the author.

    ReplyDelete
  19. Great Article. You have beautifully articulated it. Readers revisit only if they found something useful. Oujeer - Men Vest

    ReplyDelete
  20. The PhD students need to do low maintenance occupations to monetarily uphold their families and accordingly have an extremely brief time frame to provide for their examinations and dissertation writing service is such an extensive undertaking that no understudy can do it in one go.

    ReplyDelete
  21. Pretty good post. I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog posts. Any way I'll be subscribing to your feed and I hope you post again soon. Grease Trap Cleaning Houston TX Big thanks for the useful info.

    ReplyDelete
  22. Your Pet Planet - Treat animals with care, it's only fair
    Great Article! I appreciate your effort. Well done and thank you.
    Best Regards:
    Your Pet Planet

    ReplyDelete
  23. It's great to have you here. I really like the colours and theme.
    Is this your website? I'd like to start working on my project as soon as possible.
    If you don't mind, I was curious to know where you got this or what theme you're using.
    Thank you..
    Final Cut Pro X Ios Mac Torrents Full Download

    ReplyDelete
  24. Really Good Work Done By You...However, stopping by with great quality writing, it's hard to see any good blog today.
    CRACKPEDIA
    Nsauditor Network Security Auditor Crack
    Crack Softwares Free Download

    ReplyDelete
  25. Delite Cleaning Services is Australia’s fastest growing Commercial cleaning Company that provides steady work for thousands of people throughout Australia. The work is what you do in your own home every day. The only difference is you get paid for it!

    ReplyDelete
  26. I adore your websites way of raising the awareness on your readers. ลิงค์รับทรัพย์

    ReplyDelete
  27. Thank you very much. Thank you for sharing this wonderful article with us.
    https://softhound.net/idm-crack-download/

    ReplyDelete
  28. This is a great post. Thank you.
    https://windowsactivators.org/internet-download-manager-crack/

    ReplyDelete
  29. what a best type of article which is really great, thanks for sharing the most beautiful post of the blog with useful information which is really amazing. Scott Callum

    ReplyDelete
  30. What a fantastic article; thank you for giving the most beautiful blog post with important information; it's truly awesome.top gun jacket

    ReplyDelete
  31. Wow! Great blog, I really liked your post. Keep Posting. We provide the technical support for the email related issues like how to Recover Spectrum Email Password

    ReplyDelete
  32. We offer a wide variety of used cars with hundreds of choices, while holding zero interest rates on our new and used car loans. Car Dealers Mississauga

    ReplyDelete
  33. It's wonderful to see that some people can still craft an outstanding post! Not only is your blog helpful, but it's also really imaginative. I looked over and thought about what you said. Seeing your article makes me happy. Pelle Pelle Jacket

    ReplyDelete
  34. Truly awesome! for the best type of site sharing beautiful post with best information that I had learned properly. Atty Pete

    ReplyDelete
  35. what a best type of article that I really appreciated, sharing best info update that looks very impressive. click here to view

    ReplyDelete
  36. It's wonderful to see that some people can still write excellent posts! Your blog is not only informative, but also very creative. I looked over and considered what you said. I'm delighted to see your article.Tom Cruise Outfit

    ReplyDelete
  37. JSM offers Premium and affordable Luxury Limo Services in Toronto. We offer services for weddings, proms, corporate, and special events. JSM Black Limousine easily handles your event transportation demands and less celebratory logistics, such as any last-minute errands or special-needs transportation for your wedding guests.
    Limo service hamilton
    limo services toronto

    ReplyDelete
  38. SEO Content Writing Very welled explained. Great Pro Tips! Thank you very much for taking the time to make this great video. I found it extremely helpful.

    ReplyDelete
  39. I feel extremely cheerful to have seen your post. I found the most beautiful and fascinating one. The Batman Bomber Jacket

    ReplyDelete