Re: Languages don't matter. A mathematical refutation

[Paul Rubin <no.email@nospam.invalid>]

"Randy Brukardt" <randy@rrsoftware.com> writes:
> 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%.

Hmm, ok, but that's a very narrow niche of programs in my experience.
Non real-time programs where the last 25% matters.  If it's realtime, GC
is off the table and there's no decision to make.  For something like a
compiler, people use GCC all day long despite other compilers being 10x
faster, so I'd say the 25% isn't of consequence.  So why wouldn't I use
GC in a compiler if it was going to make my job easier?

> "Most programmers", OTOH, don't care about correctness ...  These
> people are not (IMHO, I know David B. would disagree) ever going to be
> Ada users.

I'd say in non-critical but real-time or memory-constrained applications
(think of consumer electronics typically programmed in C), correctness
at the level of high-end formal verification is not an
issue--conventional QA testing results in products that meet customer
expectations.  Yet Ada is enough of a productivity win to make it
attractive over C.  If correctness is critical then that makes Ada's
advantage even bigger.

In non-real-time applications critically needing what I call
denotational correctness (is that the right term?  It means the program
must never deliver a wrong answer, compilers being an archetypal
example), I probably want GC unless I can't stand that 25% performance
hit.  I compile code all the time and I'd like a 2x or 5x or 20x faster
compiler, but 25% faster is a yawner.
>
> That's what I call "trained ape" programming. It's so easy, anyone can
> do it, so anyone does,

If GC gives those trained apes such a boost that their output competes
with your experts, just imagine how much better your experts would be if
they used it too.

> Copying (of anything) is unnecessary overhead. 

There's a huge difference between an application copying something out
of an Ada container 1e5 or 1e6 times a second, and a GC copying it once
or twice a second.  

>> You trace from each pointer just once, either by setting a mark bit...
> That makes no sense to me whatsoever. The whole point of tracing is to 
> determine what is reachable 

I just mean you trace from an object to all the other objects reachable
from it, then you set a bit in the object marking it as already having
been traced.  Then the next time you find a pointer to the object, you
see that the bit is set, and you don't have to trace it again.

> And of course, a "forwarding pointer" is just an extra level of indirection. 

The forwarding pointer only exists during GC.  It means you've copied
the object from the old place to the new place, so as you copy other
objects that contained the old address, you update them to point to the
new address.

> Our compiler was barely usable 30 years ago.... (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). 

OK, so let's say a little under 2 minutes per CU on the average (single
threaded compilation).  Your customer's program has 2000 CU's and he
wants to compile it and run regression tests every night, so he wants
the compilation to complete in 2 hours.  His build farm uses commodity
4-core Intel CPU's so he needs 8 compilation servers.  Your competitor's
programmers are about equal to yours, and his compiler does about the
same thing, but he chose to use GC, so his compiler is 25% slower, which
means the customer needs 10 servers instead of 8.  So the customer will
pay more for your compiler--but not much, since x86 servers are cheap.
Your costs are mostly from programmer salaries developing the compiler.
Did your competitor's productivity gains from GC let him underbid you by
enough that the customer chooses him?  If yes, maybe you ought to
reconsider GC.

That is actually a pretty extreme case.  A real such customer is more
likely to say there's no difference between a 2 hour nightly compilation
and a 2.5 hour one.  Programs where the last 25% matters are the ones
where the program runs on hundreds of servers 24/7.  Those programs
exist, but they're not that common.  The economics of computing have
changed so that programmer time is more valuable than machine time by a
far larger ratio than before.  There is no longer a company timesharing
system doing the compilations, whose depreciation and operation cost is
equivalent to several full time salaries.  With cloud computing, if you
occasionally need 100 servers for something, you can spin them up with
an API, pay a few cents per hour per server til you've completed your
task, then spin them back down.

> People who don't know better... are probably not trying to integrate
> proof into the compiler. :-)

What exactly is your compiler doing?  The compilers I know of with
serious proof automation use external SMT solvers.  Admittedly these
tend to be written in C++ ;-)