Re: C/C++ programmer giving Ada95 a chance -- writing an emulator.

[Robert Dewar <dewar@gnat.com>]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 3509 bytes --]

In article <8c7j8c$plf$1@wanadoo.fr>,
  "Jean-Pierre Rosen" <rosen.adalog@wanadoo.fr> wrote:
>
> jross <rem.jross@rem.codemecca.com> a �crit dans le message :
> 38e7e951.8384503@news.shreve.net...
> >
> > I was making the assumption that a case statement would
> > compile to evaluate every case until finding a match --
> > hence, not efficient.

> > Several years ago, I am sure this would have been the case

Completely wrong, the switch or case statement from the earliest
days (it is after all in Algol-60, Fortran, C etc in some form
or other) has always been associated with the idea of a jump
table, and all computers have always had instruction sets
suitable for this kind of generation.

It is always surprising when people make these kind of
assumptions -- why not look at the generated code to find
out what kind of machine language is being generated.

It is not unreasonable to write high level code without worrying
too much about low level code efficiency.

It is better to know enough about code generation to have a
reasonable idea of how the compiler generates code.

The worst thing is to worry about what kind of machine language
is being generated and not know the answer, this can lead you
very much astray.

> (no pun
> > intended).  However, now that I think about it, a compiler
these days
> > should be intelligent enough to create an indexed jump table
where all
> > (or most all) consecutive values are provided and create
efficient
> > execution code.

Generally most compilers do indeed do far more than just
generate a simple jump table.

If the jump table is sparse, then it is reasonable to break
it up into ranges, with specific tests on the ranges. These
tests are often arranged into a binary search tree to minimize
run time tests. GCC has done this kind of optimization for a
long time.

If the set of values is really sparse, a hash table is a
reasonable choice, especially given that a perfect hash
function can be computed at compile time. BCPL compilers
had this optimization quite early (in the 60's I would guess).

> As a point of information, when I was working on Ada/Ed (some
> years ago now), I had in my office a PhD thesis on "efficient
> code generation techniques for case statements". There was
> literally a dozen of techniques possible, depending on how the
> values were split over the whole range...

Indeed there are many techniques and it is quite reasonable to
study them formally. I saw a much more recent thesis on the same
topic (the consideration is made more difficult by paging and
icache considerations on modern processors).

> Moral: NEVER make assumptions about the way code is generated,
> unless you REALLY know what's happening in the compiler (which
> in practice means, you are part of the compiler team!)

That's a bit extreme, but I know what you mean. In particular
the whole Realia COBOL team knew the compiler very well and
what it generated, and that was one of the reasons this
compiler is so fast (it compiles high quality run-time code
for COBOL at a very high speed -- well over 100,000 lines a
minute on a 25MHz 386, I have no idea how it does on a
gigahertz Pentium, should be several million lines a minute :-)

By the way, the -gnatG option in GNAT is quite useful for
finding out what code the compiler is generating at a macro
level. It is also a very useful verification tool (see also
the asociated -gnatD option).

Robert Dewar
Ada Core Technologies



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