LCA: Lessons from 30 years of Sendmail [LWN.net]

LCA: Lessons from 30 years of Sendmail

Posted Feb 5, 2011 13:55 UTC (Sat) by mpr22 (subscriber, #60784)
In reply to: LCA: Lessons from 30 years of Sendmail by cmccabe
Parent article: LCA: Lessons from 30 years of Sendmail

This means that compilation times for C++ projects tend to be O(n^n), where n = number of files.

Nice piece of hilariously ridiculous hyperbole there. A 1000-file C++ project - even one composed by the Stupidest Imaginable Programmer - does not take 1000¹⁰⁰⁰ times as long to compile as a one-file project.

O(m * n), where m = number of source files and n = number of ubiquitously included header files, is rather closer to the mark.

(Log in to post comments)

LCA: Lessons from 30 years of Sendmail

Posted Feb 8, 2011 0:37 UTC (Tue) by cmccabe (guest, #60281) [Link]

First of all, big-O is the worst-case upper bound, not the average case.

> O(m * n), where m = number of source files and n = number of ubiquitously
> included header files, is rather closer to the mark.

Header files tend to include other header files. This is a consequence of one of the other design features of C++, the fact that the definition of a class cannot be spread across multiple files.

So you often see stuff like this:
> #include "private_helper.h"
>
> class MyClass {
> ...
> private:
> PrivateHelper myPrivateHelper;
> };

PrivateHelper is not be part of the public API of the class (hopefully), but even so, it will require you to include private_helper.h. That class itself might have its own private helpers... and so it goes, on and on.

What's that, you say? I can use the pImpl idiom? Sure, if I can live with reduced performance and more boilerplate code to initialize and destroy the pImpl. Sigh.

It would be interesting to graph, say, WebKit compilation times as a function of the number of files. I really doubt it's anywhere close to linear.

LCA: Lessons from 30 years of Sendmail

Posted Feb 8, 2011 9:13 UTC (Tue) by mpr22 (subscriber, #60784) [Link]

A worst-case upper bound that will never be hit even by insane usage is of purely academic interest - particularly in this discussion, since the feature that permits the O(nⁿ) worst case in C++ is also present in C.

Now, I'll happily admit that real-world incremental recompilation times are worse for C++ than C - but the worst-case upper bound is a red herring there.