Re: Languages don't matter. A mathematical refutation

["Randy Brukardt" <randy@rrsoftware.com>]

"Paul Rubin" <no.email@nospam.invalid> wrote in message 
news:878ue3ff6y.fsf@jester.gateway.sonic.net...
> "Randy Brukardt" <randy@rrsoftware.com> writes:
>>> GC doesn't use that much of the runtime of typical programs
>> Given that there is no such thing as a "typical program" when it comes to
>> memory management, that's a meaningless statement.
>
> Take all the actively used programs out there and sort by decreasing
> percentage of their runtime used by GC.  Throw away the top and bottom
> 10% as outliers and call the other 80% typical.  That seems meaningful
> to me.
>
>>> in GC'd languages, and the cpu overhead can be made quite small
>> And this isn't remotely the major expense,
>
> So what is the major expense, and how often should anyone care about it?

Tracing, as I discussed below.

>>> There is no allocation overhead (just bump a pointer)
>> And this is bogus. Either items are collected in place, which means that 
>> you
>> have to allocate from fragmented memory (a lot of more expensive than
>> "bumping a pointer" - that was the cause of the issues we had with our
>> compiler back in the day), or they're compacted somehow.
>
> Yes, the idea is to use a copying collector, which compacts, so
> allocation is just bumping a pointer.  I don't claim that the
> copying/compaction phase has no overhead.  But, it is not too bad in
> practice, for most applications in which GC is usable at all.
>
>> And compaction is very expensive,
>
> Maybe your info is out of date.  Modern gc's use generational copying,
> so during most collections, only recently created data gets copied,
> which isn't very much data.

That's a fantasy for many programs. And for the ones that it isn't, subpools 
work just as well.

> There are also larger collections when
> everything gets copied and that takes longer, but it's less frequent.

Of course. But those are the only ones that actually do anything. And it's 
that overhead (plus the excessive tracing overhead) that matter.

> The aggregate overhead isn't too much.  There's tons of heavily used
> code out there using GC these days, e.g. Gmail is written in Java unless
> I'm mistaken.  They wouldn't have done that if GC was unaffordable.

They did it because it allowed them to use trained apes to program. :-)

Let me be clear here: Ada is used by programmers that want to get their 
programs right *and* need native code performance (performance might mean 
space or mean speed). That means that we're typically worrying about the 
last 25%. GC sucks up that last 25%.

"Most programmers", OTOH, don't care about correctness (well, more 
accurately, their management doesn't care, because bugs allow them to sell 
subscriptions and other products [why is anti-virus needed, for instance? An 
unwillingness to adopt simple rules to prevent the running of foreign code, 
mostly caused by programming in languages like C that don't check bounds.] 
And often they don't care about performance, either, concentrating on 
time-to-market and other issues.

These people are not (IMHO, I know David B. would disagree) ever going to be 
Ada users. While there would be some benefit in faster time-to-market if one 
spends less time debugging, and Ada development is more reproducible for 
that reason, the up-front costs of actually designing your code will be too 
much a time sink for such users to buy into. Unfortunate, but reality.

That's what I call "trained ape" programming. It's so easy, anyone can do 
it, so anyone does, and we get the mounds of crapware out there that barely 
works and steals your identity at the same time. Bah-humbug. ;-)

>> simply because copying things around for no reason is expensive. (Ada
>> 2012 has to add access-in-place operations to the Ada Containers
>> specifically to eliminate that overhead.)
>
> That sounds like you're talking about copying in the application and not
> in the GC.  The access frequency could be far higher in the app,
> increasing the copying costs.

Copying (of anything) is unnecessary overhead. If the programmer put it 
there, that's their problem. OTOH, if the implementation puts it there, it's 
a problem for all programmers, and that's a real problem. Remember again 
that I'm trying to get the fastest/smallest possible code to implement the 
programmer's algorithm. Any implementation overhead that can be eliminated 
should be eliminated, because that's overhead that the programmer can do 
nothing about.

>> Our compiler uses a lot of pointers; most of them act as handles and
>> aren't actually dereferenced in the majority of the code, but they do
>> get passed around a lot. That means a lot of copies of pointers, so
>> lots of data structures to trace.
>
> You trace from each pointer just once, either by setting a mark bit in
> the object in the case of a mark-sweep collector, or by overwriting the
> pointed-to object with a forwarding pointer in the case of a copying
> collector.  So the number of objects matters much more than the number
> of pointers.

That makes no sense to me whatsoever. The whole point of tracing is to 
determine what is reachable (since GC cleans up objects that are no longer 
reachable). There's two ways to do that; one is to retrace everything that 
exists (based on some algorithm to avoid retracing stuff that hasn't 
changed), alternatively, one can somehow determine when pointers are 
destroyed and update data structures based on that. In the first case (which 
seems to be what you are talking about), you have to revisit every pointer 
variable that might have been changed (which is pretty much all of them) 
with some frequency in order to determine what they're pointing at. Pointer 
constants are rare in Ada (primarily, just formal parameters); everything 
else is a variable.

And of course, a "forwarding pointer" is just an extra level of indirection. 
There is an old saying in the compiler world that any problem can be solved 
with a level of indirection. The problem is, that such a level of 
indirection costs quite a bit, as much as 10% for frequently accessed 
objects. And of course in native code, once that indirection is in place, it 
will stay there forever (one could use a thunk instead to make the 
indirection conditional, but that would be even more expensive, because of 
cache effects).

> Anyway, look at it like this.  If your compiler was written 30 years ago
> and ran at tolerable speed then, it's 1000x faster now because of
> advances in hardware.  Even if using GC would have slowed it down by 2x,
> it's still 500x faster than before.

Our compiler was barely usable 30 years ago; the only thing that made it 
useful was that everybody was in the same boat. (On the order of 5 minutes 
per compilation unit.) There were many things that we could not do because 
of lack of CPU power. The current version is faster by a lot, but it still 
can take minutes per compilation unit (although most units are much faster). 
There's still a lot of stuff that could be done that most users would not 
tolerate the wait for. I'm not remotely interested in wasting a decent 
amount of time on a mechanism that is not needed for most real-world Ada 
code (not to mention a compiler). People who don't know better (or don't 
care) may come to a different conclusion. They're probably not trying to 
integrate proof into the compiler. :-)

                                      Randy.