[HN Gopher] Ask HN: What is it about compiling that is so time-c...
___________________________________________________________________
Ask HN: What is it about compiling that is so time-consuming?
20 years ago, the "cool kids" (aka the egocentric dorks who wanted
to be thought of as "special") would brag about installing Gentoo
from source, or something similar, and how the kernel had _only_
taken 3 days to compile now that they had a gig of RAM instead of
384 megs Even today, a not-insignificant number of
projects/tools/etc are distributed as _source_ , and you have to
build it locally ... sometimes taking hours Other tools (eg
Apache) are distributed both as binaries or source, and you can run
the "out of the box" edition, or 'tweak' it a little compiling
yourself...but again - it takes _forever_ to get up and running
(and heaven help you when an update comes out) What is it about
compilation that is so time-consuming? Fundamentally, it's a
[relatively-simple] translation from one language to another - with
most compiled languages having been around for a long time Surely
compiling locally shouldn't be so astronomically time-
consuming...should it?
Author : warrenm
Score : 23 points
Date : 2023-01-30 17:50 UTC (5 hours ago)
| [deleted]
| jvalencia wrote:
| It's about efficiency. Obviously something like python is real
| time. Even typescript to javascript can be fairly quick (a la
| esbuild). However, once we start talking about moving bits around
| using compiler optimizations, things slow down a lot. This is
| because there are a lot of steps to going through every bit of
| assembly to reorganize the code into a machine optimized state.
| Some quick Google searches get you gory details:
| https://gcc.gnu.org/onlinedocs/gccint/Tree-SSA.html#Tree-SSA
| JonChesterfield wrote:
| The languages are usually quite different to one another, the
| user expects some extensive semantic checking with error
| messages, then the majority of the time should be spent in code
| optimisation so that the resulting program runs faster.
|
| Some languages (I suppose language pairs from source to target)
| compile dramatically faster than others.
| malux85 wrote:
| Most of the time you don't need to compile yourself - which is
| why OS package managers exist.
|
| But sometimes it's advantageous - E.g. it's possible for a
| compiler to take advantage of special CPU instructions that that
| are present on your CPU but cannot be guaranteed are present
| everywhere - resulting in a faster binary. In some special but
| relatively rare edge cases (e.g. numerical computing /
| simulations) these speed ups can be significant.
|
| But there's heaps of room for improvement, E.g. most compilations
| have steps that are embarrassingly parallel - so make has an
| option "-j" that allows you to use multiple CPU cores - this
| significantly speeds up the compilation of numpy, the trouble is,
| it also increases memory consumption quite a bit, so make cannot
| change its default to use all cores as it would OOM a lot of
| existing build systems.
|
| What what I have seen the vast majority (like > 90%) of automated
| build systems don't take advantage of multi core compiles, so
| that's why they are dreadfully slow by default. Pythons
| subsystems are guilty of this, which is why building matplotlib,
| numpy, scipy, etc from source is very very slow
| mike_hearn wrote:
| There are fast compilers. Go is an example. Delphi was another
| very fast compiler.
|
| AOT compilers that are slow, are slow because they spend a lot of
| time optimizing code that isn't particularly important (but they
| have no way to know that).
|
| A good way to see this is by taking a large-ish Java program that
| does the same thing as a large-ish C++ or Rust program, and
| comparing the compile times. The Java program will compile much
| faster, but runtime performance will be roughly comparable post-
| warmup (unless the program is very sensitive to memory locality,
| as Java doesn't currently have value types). The reason is that
| the Java -> bytecode compilation is very simple and involves
| almost no optimization work, and then the rest of the compile is
| done at runtime, but it's all profile guided so only the parts of
| the app that actually benefit from optimization get it.
| AussieWog93 wrote:
| >Delphi was another very fast compiler.
|
| My old manager used to love this language. Apparently back in
| the late 90s he was compiling serious pieces of software in a
| few seconds.
|
| The first demo app he compiled finished so quickly he thought
| something had actually gone wrong.
| mikewarot wrote:
| Lazarus/Free Pascal includes its own sources, and takes about 3
| minutes to rebuild everything, if I recall correctly.
|
| It's single pass recursive descent compiler, with no macros.
|
| It doesn't have separate header files, and auto-manages
| dependencies, so there isn't a need for make. Units get
| compiled once, no matter how often they are used.
| brundolf wrote:
| > because they spend a lot of time optimizing code that isn't
| particularly important
|
| This is a pretty loaded and weird thing to say. You're right
| that optimization accounts for a major chunk of the time, but
| compilers are often slow while optimizing code that is
| important
| ender341341 wrote:
| I think they're saying that for the vast majority of code it
| doesn't matter to optimize as the actual time to run the code
| is trivial compared to waiting on network calls and the like.
| brundolf wrote:
| I've never seen any evidence (or even anecdotes, until now)
| saying this is true. It could be, who knows, but it's a
| weird thing to assert out of the blue in this kind of
| conversation, especially when just "doing optimizations
| [important or not] is a major contributor" is widely-
| accepted as true and is enough to answer the OP's question
| madethissoicou wrote:
| one issue in c/c++ is that each compilation unit (i.e. cpp file)
| includes tons of headers which in turn include tons more headers.
| so it's like an O(n^2) kind of growth where n is source size.
| obvs you can do better if you're careful about dependencies
| yetihehe wrote:
| Compound that with inability to cache those headers between
| different compilation units because each time you include a
| header, it can behave differently thanks to preprocessor
| definitions, but you can't really make dependency of those
| definitions because even changing order of header inclusion can
| make difference to those definitions.
| canucker2016 wrote:
| ...which is why sane, large projects use precompiled headers
| (PCH).
|
| C (and later C++) compilers have used precompiled headers
| since at least the late 80s.
|
| PCH speeds up compilation and roots out (hopefully, the few)
| cases where precompiled headers fail.
|
| But C/C++ wasn't designed for a world where tens/hundreds of
| programmers build an app measured in the tens/hundreds of
| megabytes.
| bjourne wrote:
| It's time consuming because the compiler tries to optimize the
| code. A compiler that doesn't try to optimize can be amazingly
| fast like Python's compiler or like how Go's compiler used to be.
| Neither attempted many optimizations.
|
| Compiler optimizations are time consuming because they are trying
| to find solutions to NP-hard problems. Since solving NP-hard
| problems optimally is intractable compilers use heuristics. So
| the more optimization the user asks for the more time consuming
| heuristics are executed. One such problem is register allocation.
| Your CPU has a finite number of registers that should be used for
| an almost infinite number of variables. Figuring out a good
| register allocation is very difficult.
|
| It also gets more difficult because modern compilers are
| optimizing larger contexts. Rust, C++, and other languages with
| functional features rely heavily on function inlining. So a
| function you write that is five lines may internally be expanded
| by the compiler to hundreds of lines.
| retrac wrote:
| > NP-hard
|
| I wrote a toy compiler once as an educational project. I
| accidentally invented super-optimization, too. Felt so clever
| for a whole hour or so. It was guaranteed to produce the
| optimal program that can be represented in the intermediate
| representation I used. Unfortunately, this only works for
| programs with up to six operations with current hardware; more
| than about ten would require more RAM than can fit in the
| universe.
|
| Finding shortcuts to prune down that problem is the black art
| of practical optimization.
| JCWasmx86 wrote:
| You have more complex programming languages like Rust/Swift that
| take comparably ages to compile compared with C due e.g. all the
| extra code that is generated and that has to be optimized by LLVM
| (This one is quite slow AFAIK, too).
|
| C++ has its template instantiations with the same problem.
|
| Another aspect is how much more the compilers optimize, compared
| to the "early" days, modern compilers can often beat human
| programmers at optimizing assembly in a reasonable time and can
| do a lot more complex optimizations. In addition to that, you can
| couple it e.g. with linker optimizations like LTO/BOLT and you
| have even longer build times.
|
| I think another factor is the more and more dominant static
| linking model (Rust/Go/Swift). If I compile e.g. my program with
| the swift stdlib statically linked, it takes around 15 seconds
| for an incremental build, while using a dynamically linked stdlib
| it takes around 6 seconds. Sure it is just one benchmark, but
| static linking nearly everything won't have no impact.
| [deleted]
| WorldMaker wrote:
| A simple, fundamental reason that hasn't shifted in 20 years and
| in some ways has only grown worse as our collective hard drives
| have grown increasingly larger versus RAM size: File I/O.
| Compilers eat a lot of files and produce a number of more files,
| sometimes with several passes of intermediate files along the
| way.
|
| You could have the most efficient possible compiler and it still
| has to read N files and output X binary objects back to disk.
| Those will always be bottlenecks that are sometimes extremely
| visible in wall clock time (even on the fastest SSDs sometimes,
| once you account also for OS paging and caching and background
| processing like anti-virus tools and other security audits).
| robertelder wrote:
| I spent a fair amount of time working on building my own from-
| scratch C compiler that I no longer work on anymore:
|
| https://recc.robertelder.org/
|
| One of the reasons that I stopped working on it was because of
| how slow it became, so I might be able to contribute to answering
| your question.
|
| Initially, when the compiler was simpler, it was actually much
| faster. I was able to do some meaningful proof of concept demos
| with it like compiling a small microkernel, and compiling most of
| its own source code. Of course, the natural thing to do is to
| make it so that could cross-compile itself and run in the
| browser, and that's where it became terribly slow, which required
| more code to optimize, and the new code that was added to make it
| faster in the long term made it much slower in the short term.
|
| To start with, if you think of a simple piece of code like this:
| if ( 1 ) { putc('a'); }
|
| This is only a 23 byte character program, so why should it be
| slow to compile? Well, the first stage of parsing this program
| involves tokenization. In this short program, I count 16
| different 'tokens' (including the whitespace). If you want to
| have even the simplest data structure to describe one of your
| 'tokens', that only contains a single pointer to an offset in the
| program, then you will need to consume 16 pointers just for the
| tokens. On a 64 bit machine, you'll have 8 byte pointers, and 16
| * 8 = 128 bytes, just for the pointers into the byte array of the
| program! And we haven't even started talking about the memory
| overhead of all the other things you'll need to describe about
| these tokens in your token object.
|
| So, now we already have a memory overhead that is more than 5
| times as big as the program, but we also have to build the parse
| tree, control flow graphs, linker objects etc. and you also have
| to pull in a mess of header files, bloated libraries etc. If
| you're wasteful with memory in the compiler, you can easily run
| out of memory from compiling a few megabytes of source code.
| Being more intelligent with memory management requires copying
| memory around a lot, which also adds to the latency.
|
| So, now you need to think about optimizing your memory use, and
| do 'smarter' things that trade memory usage for CPU. Plus, you're
| likely to also start needing free/delete a lot from heap memory
| which is a system call and therefore slower than a call within
| your program. By the time you implement all this 'optimization',
| you compiler has become an incredibly complicated and bloated
| system that requires even more code to optimize all the
| opportunities for improvement.
| dangets wrote:
| A major contributor can be memory access patterns. Traversing
| trees and pointers not adjacent in memory can result in a
| noticeable performance drag. Andrew Kelley gave an interesting
| talk about performance wins in the Zig compiler here
| https://media.handmade-seattle.com/practical-data-oriented-d... ,
| but the same idea is broadly applicable.
___________________________________________________________________
(page generated 2023-01-30 23:02 UTC)