Re: Code size of Ada ? was Re: Ada95 Strengths/Weaknesses.

[Robert Dewar <robert_dewar@my-deja.com>]

In article
<Pine.A41.3.96-heb-2.07.990930154826.68392B-100000@pluto.mscc.hu
ji.ac.il>,
  Ehud Lamm <mslamm@mscc.huji.ac.il> wrote:
> On Thu, 30 Sep 1999, Robert Dewar wrote:
>
> |Now of course if you use high level constructs in Ada that
have
> |no analogy in C, you will pay a price. But that's always the
> |case, programming at a higher semantic level almost always
> |(not always, but almost) costs in space and time (if you
don't
> |like this, you can always write in machine language and save
> |lots of time and space over high level languages like C :-)
> |
>
> I'd like to respond to this, even though it is a little off
topic, even
> for this roving thread. I think the "almost always" claim is
an
> overstatement - as I am sure Robert knows.
> Today's processors (esp. RISC, superscalar, bredictive
brancing etc.) have
> many features that make writing good machine code for them
quite hard.

First, we are a bit confusing two issues here.

1. The issue of high level semantic features (e.g. finalization,
garbage collection, dynamic dispatching, slice assignments, etc)
compared with writing low level equivalents but still at the
C or low level Ada level.

2. The issue of machine language vs low level stuff, an issue
which I am quite happy to comment on, but which has nothing at
all to do with issue 1, which is what I *was* talking about.

> Good optimizing compilers, many times, outperform all but the
> most expert of programmers.

People often say this, particularly those in the compiler field,
but in my experience it is just plain wrong. There are many
people who can write VERY tight assembly language which
outperforms anything compilers can generate.

The last time I was challenged on this, I gave as an example
my program DASC for doing syntax checking on full Ada 83. This
program is 12K bytes long and runs at several million lines a
minute on a 25MHz 386 (I have no idea how fast it runs on a
modern PC, I have not run it recently.

Furthermore, the 12K is quite deceptive, since this program
gives reasonable error messages, and half that space is used
to hold error message text.

A student of Paul Hilfinger's spent some time analyzing this
program to find out why any reasonable attempt to duplicate its
function in C was far bigger and far slower. The resulting
paper was called "Galactic Optimization" as I remember, but
I don't think it was ever published.

Just today in my class on beginning 386 assembly language, we
looked at code for a silly C function to add two integers. With
perfectly straightforward assembler code we beat the best C
compiler by a factor of 3. Why? Because the C compiler was
crippled by adhering to an idiotic design for the calling
sequence, whereas our assembler routine could use a sensible
tailored calling sequence suitable for that particular
procedure.

I am certainly not advocating programming in assembly language.
Far from it, in fact I think most people should not be allowed
to attempt this under any circumstances given the junk I have
seen.

But this idea that optimizing compilers can do as well as
competent assembler programmers, though a common one, is to
me urban myth, not backed up by any careful studies. One often
quoted figure is Bill Wolf's study showing that assembler was
only 11% (or was it 7%) faster than Bliss. I asked him about
this one day. Turns out what they did was take a program in
Bliss, generate the assembler, and then ask a student to
improve the assembler language. Hopeless methodology! One
of the most striking things about writing in machine language
is that the detailed low level instruction set design often
dictates the data structures at a high level.

An example:

THe Alsys storage allocator for the x86 (I don't know if it is
still in use for Object Ada or not) was written by me in x86
assembly language.

The critical data structure was a word whose format was

  x yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy

(where x was a bit showing if a block was in use, and yyyy
 was the length of the block in bytes divided by 2).

This was chosen because a single shift instruction could

a) double the value of yyyyy
b) remove x from the word
c) place x in a flag where it could easily be used

Yes, it might be that a compiler with good local optimization
(like gcc) could retrieve this kind of code if you specified
the same data structure by elaborate pattern matching on a
sequence of code saying something like

    siz = 2 * size_word.yyy;
    if size_word.x then ...

but the point is that unless you are thinking at this ferocious
low level, you would not come up with the data structure in the
first place. In particular, I would choose a totally different
data structure on the MIPS chip.

> Now surely, a programmer who fails to use the right
> compiler switches will also fail to produce good machine code
by hand.
> Hand tuning machine code is hard. The abstraction mechanisms
of HLL help
> you think more clearly about the actuall problem to be solved
- getting to
> a better algorithm

Yes, of course, it is much harder work to use good algorithms
in a lower level environment, and that is indeed an important
effect, but for a competent assembler programmer this is not
an issue, it just means you have to work harder. Certainly
programming in assembly language is no excuse for using poor
algorithms.

 - and with the aid of a good compiler, tend to produce
> better results.

Please justify this with actual data.

> (Not to mention all the other benefiets: less bugs, easier
maint. etc.)

Yes, yes, yes, of course, no argument here. No one is arguing
that things should be done at a lower level, not at all. I
just take issue with the idea that we are not paying a price
for it.

Look we all know that programs these days are massively
oversized. Remember the days when 10 people could share
a 128K PDP-11 doing C compilations and edits under Unix,
and get quite reasonable response time. Seems unthinkable
now, right ...

> In most cases I've seen sending someone to code in machine
language (or
> let's be more realistic - Assembly language)

well of course from a programming point of view assembly
language = machine language, no one programs in absolute,
so when we talk about programming in machine language, we
mean asm.

, won't bring faster programs
> - UNLESS that person has a verey good knowledge of how things
really work in the first place.

Of course you need to be a skilled assembly language programmer
to take advantage. The above statement is a bit like saying that
a Cessna pilot may not be able to make the New York to San Fran
run any faster in an F15 unless he has a very good knowledge
of how to fly an F15 ...

> I had a student once, who always insisted on using shift (in
his C code)
> instead of multiplication, when multiplying by two. I'll let
you guess
> which C code produced faster object code

I trust they were identical, or something is sadly wrong

, what optimization did (not to
> mention some funny run time checks I saw on one compiler...).

Something must have been sadly wrong ...

 The only way
> to convince him that (a) a negligable speed increase is not
worth the
> obsufication and that (b) there isn't any speed increase
anyway was to
> examine the assembly listing from the compiler.

This really has nothing at all to do with the point I was
making.

> Alas a week later he had a new clever idea.
> I have a feeling he will never "get it."

You were really emphasizing the wrong thing to him. The issue
is not whether or not it speeded things up, by far the more
important point is that abstraction is more important than
efficiency in almost all cases.

> I wouldn't bet on Assembly, unless knowing the exact problem
> and programmer invovled.

I agree with the above statement. I still agree with it for
any possible substitution of language, methodology, tools etc
for the word Assembly in the above statement.

It seems like your whole post was about assembler, but that
makes it an odd non-sequitur, my post was nothing at all to
do with the issue of high level languages vs assembly language.



Sent via Deja.com http://www.deja.com/
Before you buy.