| |||||||||||||
PausesPausesPosted Jun 23, 2010 13:10 UTC (Wed) by nix (subscriber, #2304)In reply to: Pauses by i3839 Parent article: The Managed Runtime Initiative
In my experience most memory is used when linking, not when compilingThe only reason you think that is because GCC runs several garbage collections when compiling even a small file. And your assumption about being able to throw away whole intermediate steps at once -- that's how GCC used to work when it kept everything in obstacks. It's often correct, but if it's wrong only in part you have to keep a lot around because you have no way to tell which bits you're using and which you're not. (actually, to be maximally pedantic it's almost never correct because most passes annotate or shuffle some tree somewhere: if it did nothing all the time it would be a pretty useless pass.) But it seems you don't get it. I know GCC already has a GC: I'm using it as a counterexample to your claim that GC is unnecessary because you can always simplify your datastructures. You cannot always do that (although you often can and it should be the first thing you try, if practicable), and doing it by hand (i.e. explicitly triggering GC cycles) is often impractical too. Managing (or rather mismanaging) object lifetime is the part of memory management that is most likely to cause bugs in C programs (less so in C++); GC largely eliminates that as a cause of bugs.
(Log in to post comments)
Pauses Posted Jun 25, 2010 14:57 UTC (Fri) by i3839 (guest, #31386) [Link]
> (actually, to be maximally pedantic it's almost never correct because
> most passes annotate or shuffle some tree somewhere: if it did nothing > all the time it would be a pretty useless pass.)
That's why I was talking about compilation stages, not optimisation
I'm also sure that GCC does not use hundreds of megabytes to keep
I'd rather have GCC spend its time on using 10 times the memory for
> But it seems you don't get it. I know GCC already has a GC: I'm using it
No, I don't get it. You brought GCC as an example of something that people
> Managing (or rather mismanaging) object lifetime is the part of memory
In my experience memory leaks almost never happen and when they do
Pauses Posted Jun 27, 2010 17:05 UTC (Sun) by nix (subscriber, #2304) [Link] That's why I was talking about compilation stages, not optimisation stages.There is no meaningful distinction, after parsing, between translation and optimization. There are only compilers that optimize more, and compilers that optimize less. I'm also sure that GCC does not use hundreds of megabytes to keep very complex graphs in memory.You're hilariously wrong. (Seriously, what do you think it's doing with the gigabytes of space it can sometimes use? Playing electronic tic-tac-toe? Of course it's holding graphs, and other things some of which it indeed can never throw away e.g. hordes of decl nodes for all the declarations in all the header files it's parsed...) I'd rather have GCC spend its time on using 10 times the memory for compiling small files fast than waste time on reducing memory usage by running slower and not really achieving it anyway.You'd say that until you tried to compile something and it failed because you ran out of memory, or it started taking a thousand times longer than otherwise because you were pushed into swap. Also, the more we reduce memory usage, the better our (still quite awful) cache utilization becomes. You seem to assume that GCC would use a lot more memory if it didn't use GC. I think it's rather that GC doesn't improve the situation.No. If it never garbage collected and didn't free(), as you suggested, it would use incredibly much more memory (many times more than it does now). As for what would happen if it was designed without GC, well, we have actual evidence of that because pre-3.0 it did indeed have no GC, and used manual memory management for everything, with explicit lifetimes. Maintaining the object lifetimes was a nightmare and there were countless bugs raised due to SEGVs caused by something being freed when it shouldn't. In my experience memory leaks almost never happen and when they do happen they're easily fixed.That's true until you have to manage complex data structures. It's also only true if your memory leak (or, worse, double-free) isn't tied up with an API bug somewhere and not fixable without changing the API. I've seen that too and it was a nightmare to fix (we had to change every caller and there were hundreds, ick, never again). GC may be more inefficient than manual memory management (theoretically this is not true, but I've never heard of a situation where that theory is turned to practice) and is surely not right for every situation, but it wipes out all these problems at a stroke. And to be honest if asked if I'd rather have a program that ran more slowly but used GC or a program that didn't work I'd surely pick the former.
Pauses Posted Jul 4, 2010 17:14 UTC (Sun) by i3839 (guest, #31386) [Link]
Yes, but compilers don't grab the whole source and optimise everything at
once, at least not generally, though they can do that. So it's fine if they use a bit more memory when compiling one unit, the only moment when the whole program has to be in memory is when linking.
Considering that optimising is a computationally expensive process which
What the hell is gcc doing to achieve this? Making hundreds of copies of
In a dark past I compiled the whole system on a slow, crappy computer with
But yeah, if you have a huge body of code with crappy internal APIs then
Pauses Posted Jul 7, 2010 15:56 UTC (Wed) by nix (subscriber, #2304) [Link] Yes, but compilers don't grab the whole source and optimise everything at once, at least not generally, though they can do that. So it's fine if they use a bit more memory when compiling one unit, the only moment when the whole program has to be in memory is when linking.Well, -flto does exactly that. In any case, grabbing one translation unit and optimizing it can easily use hundreds of megabytes of memory, and without doing garbage collections (i.e. never freeing storage) would easily use many gigabytes. Considering that optimising is a computationally expensive process which grows much more than O(n) if the working set increases by n, I'm really surprised that memory usage is a limiting factor at all, and that compile time hasn't gone through the roof before this became a problem.Well, compile time having gone through the roof is a perennial complaint about GCC, and its L2 cache utilization is pretty awful. What the hell is gcc doing to achieve this? Making hundreds of copies of all the nodes every time it modifies them? (I know you can trade memory usage for time with certain algorithms, but is gcc actually doing that?)No, but it has a lot of optimization passes, several IRs, and it does a lot of work. Also, headers are large these days: decl nodes alone can use hundreds of megabytes, and recent work to reduce the size of decl nodes has reduced the memory consumption of the compiler considerably. You might find the -fmem-report flag interesting. (Note that reuse of tree nodes is a classic example of a time where GC is very useful, because all of a sudden that object's lifetime must be extended, and telling the entity that originally allocated it is likely to be unpleasant.) In a dark past I compiled the whole system on a slow, crappy computer with 128 MB of RAM (bloody Gentoo, but Archlinux had no i586 binaries), and I'm pretty sure it was totally limited by CPU speed. Took a whole day, but it got to the end. What code makes gcc use hundreds of megabytes of memory in your experience?Virtually anything in C++. Anything more than a few thousand lines long in C. It's downright commonplace. It's pretty common to see GCC using >500Mb, and I've seen it using gigabytes before now. If you run several compilations in parallel, you'll need even more... But yeah, if you have a huge body of code with crappy internal APIs then GC is probably a very good idea. Using explicit memory allocation for short lived objects plainly sucks, GC is better for that.That's exactly the class of allocations for which obstacks are good and GC can often be forgone. When you have long-lived allocations in a complex webwork in elaborate interconnected graphs, then is when GC becomes essential. And GCC has elaborate interconnected graphs up the wazoo. The quality of internal APIs is mostly irrelevant here: it's the nature of the data structures that matters. The case where it's really because of "complex data structures" is a rare case indeed.I find that about 5% of the programs I write start to get complex enough data structures that memory management becomes a serious burden. I think it depends on the class of program, really. If you mostly write little scripting things or financial add-up-these-numbers programs, then, no, complex data structures will be uncommon. If you're hacking on the inside of a database server or a compiler, then they'll be common.
Pauses Posted Jul 8, 2010 14:36 UTC (Thu) by etienne (subscriber, #25256) [Link]
> Note that reuse of tree nodes is a classic example of a time where GC is
> very useful, because all of a sudden that object's lifetime must be > extended, and telling the entity that originally allocated it is likely > to be unpleasant.
I am not a specialist of GC, but I wonder if the usual malloc/free interface is wrong, and if we should use something like malloc/memlock/free.
Pauses Posted Jul 8, 2010 14:52 UTC (Thu) by nye (guest, #51576) [Link]
>Basically, the function which create the data allocates it, all functions using the data memlock() it, and every function calls free() when it finishes using that data. Free() decrements a counter and frees the memory when the counter reaches zero.
How would this be different from any other form of reference counting, with its attendant problems?
Pauses Posted Jul 9, 2010 16:22 UTC (Fri) by nix (subscriber, #2304) [Link]
Straight reference counting works if you can tell who the 'users' are, and if the data structures are fairly simple. But we can't really ask everyone touching a graph to walk the entire graph and all its data structures and increment, then decrement, all its reference counts (that would be much more cache-unfriendly and unpleasant to maintain than what is done now); and because nodes are often shared between graphs we can't have one giant reference count across the whole graph... and if the reference-count-freer walks the graph and only frees if all connected entities are at refcount zero, you might as well drop the reference count, because what you've got there is a garbage collector. :)
Pauses Posted Jul 14, 2010 14:23 UTC (Wed) by i3839 (guest, #31386) [Link]
-flto enables link time optimisation, which is IMHO something slightly
different, and earlier (current?) implementation has a reputation of being slow. I was thinking more about -combine -fwhole-program. As far as I know link time optimisation is about doing further optimisations before the real linking.
-fmem-report flag is indeed interesting. On my current project, which
So assuming C++ is ten times worse, and the code ten times bigger, then
> That's exactly the class of allocations for which obstacks are good and
With crappy APIs/design you can't allocate objects on the stack, but are
The problem of elaborate interconnected graphs is that it's hard to end
Pauses Posted Jul 15, 2010 17:06 UTC (Thu) by nix (subscriber, #2304) [Link]
Link-time optimization works by having the compilation phases drive the compilation to the GIMPLE tree stage, then writing it out and having the link stage invoke the compiler again (via collect2, or via a linker plugin: the latter is preferable because then you can run it over the contents of .a archives as well) to read in all the GIMPLE trees and optimize them. At that stage you've got all the trees written out by all the compilation phases in memory at once. And a good few optimizations will, unless bounded explicitly, start using up crazy amounts of memory when hit with large programs all at once. (Of course they *are* bounded explicitly. At least all of them that anyone noticed are.)
-combine -fwhole-program has a similar memory hit, for similar reasons.
C++ is a good bit worse memory-wise than C, mostly because the headers make C headers look like child's toys: they have a lot of definitions in them and a large number of very complex declarations. I've known compiling *single C++ files* to eat a couple of gigabytes before (although, admittedly, those were exceptional, things like large yacc parsers compiled with C++: mysql's SQL parser is a good example).
Pauses Posted Sep 6, 2010 20:22 UTC (Mon) by Blaisorblade (guest, #25465) [Link]
> That's why I was talking about compilation stages, not optimisation
stages. > I don't think you can free any significant amount of memory between the latter ones, because you never know what may be needed in the future.
Well, if no pointer exists to an object, there's no way somebody can use it. It seems you don't know what you're talking about.
> Even if you just replace multiple nodes with fewer ones you can't save much memory because of fragmentation
Fragmentation only exists in languages which don't support GC well (i.e., C). GC have been able to fix that for ages. Whether we have decent heuristics for handling it without using too much CPUs is an open issue, when that's a problem choosing the GC algorithm among the implemented ones is the best solution.
|
|||||||||||||