Beware: Rep spec on an enumeration type causes code explosion

Beware: Rep spec on an enumeration type causes code explosion

[Joe Gwinn]

We just ran into a real zinger with the Green Hills Ada95 compiler
(Solaris host, 68060 target, VxWorks 5.2 target OS), although it appears
that the issue may be common to all Ada95 compilers.  

The symptom at presentation was that the code was at least two orders of
magnitude too slow, although it did appear to work correctly, and didn't
crash.  This system is supposed to run at 64 Hz (with 50% CPU load), but
was barely making 4 Hz (at 96% CPU load) while doing a fraction of the
full workload, so we are at least a factor of 30 too slow, and more likely
a factor of 100 too slow.  As they say, this is a problem.  Projects have
died for less.

After the usual round of pointless finger-pointing (and helpful
suggestions that we recode the whole thing in C), we built an
interrupt-driven system execution profiler and used it to figure out what
the hell was going on.  

Basically, it was spending all of its time in VxWorks, because the Ada RTE
was calling on VxWorks at an astounding rate.  This was in turn due to two
things, the handling of enumeration types, and the registration and
deregistration of user-defined exception handlers at every turn.

Exception handlers.  We were declaring a number of exception handlers at
the beginning of each and every module, so every time the module was
entered, the context had to be saved, and every time the module was
exited, the context was popped off the exception stack and discarded,
regardless of if an exception was ever raised.  This was easily solved;
now, only tasks declare exception handlers, not modules.

Enumeration Types.  This is the zinger.  A 29-line Ada95 program expanded
into 1,090 lines of assembly code, a static expansion ratio of 38:1, not
the usual 3:1 or 4:1.  In this 1,090 lines of assembly, there were
multiple calls to the Ada RTE routine "_rts_holey_enumeration" (or the
like), which is reported to handle enumeration types that may contain gaps
in the mapping sequence, or whose base value (zero or one) isn't known at
compile time.  

At first, we though that the bloat was caused by the use of subranges of
enumeration types, but soon discovered that the real problem was caused by
the use of representation specifications on enumeration types, and that
use of subranges appears to be irrelevant.  

We have now removed the bulk of the rep specs on enumeration types, just
trusting for now that the compiler will always start enumerations at zero,
just like C/C++.  Ada95 does not specify the base value of an enumeration,
so compilers vary. We were using rep specs to govern the representation of
Ada records used to generate and understand messages exchanged with
display consoles coded in C++.  This idiom is used extensively.   For
portability, we will eventually change the code to remove all ungoverned
enumerations.


The code now runs something like ten times faster.  Fortunately, this one
wasn't too hard to fix.  Profiling and digging continues; we haven't heard
the last of performance problems.


Memory Management.  The Ada Runtime System makes extensive calls to the C
functions malloc() and free(), a cause for worry.  Variable-block
allocators such as malloc and free are generally unsuited for nonstop
heavy use, and will generally either leak memory or fragment their memory
pool, causing the application to run slower and slower until it eventually
jams.   The use of free() in a realtime system is generally forbidden;
it's OK to allocate a bunch of memory during startup, and explicitly
manage it yourself during operation, but it is not OK to use malloc and
free for realtime memory management.  The claim is that Wind River's
version of malloc/free is stable in realtime use.  It's hard to see how
this could be true.   This will need further research.  



Summary.  One wonders where the other beartraps are.  Some compiler gurus
seemed to know all about this one, long before we blundered into it, but
for some reason could not give timely advance warning.  It would have
saved considerable travail and fright, and deprived the just-do-it-in-C
crowd of a horror story.

In the early 1990s, when implementing a communications core in Ada83, we
had all manner of problems with similar beartraps.  You simply could not
tell from the manuals and books which idioms would blow up on you.  One
assumes that the compiler writers knew what they struggled with, but that
information was never published in a useable form, one assumes for PC
reasons.  The then solution was to try to stay in the Pascal subset of
Ada, and to read the generated assembly code to detect code explosions. 
Ugly, but effective.  Not that there was a practical alternative.  Even
so, we reimplemented the core three or four times before we achieved a
stable and reasonable Ada to assembly code expansion ratio.  

In communications cores, performance is very much the issue, so it was
possible to spend that kind of effort getting it just right.  Not all
projects can afford this.

The good news was that the resulting code ported to a new compiler without
provoking another code explosion, implying that the explosions were
properties of Ada83 the language, and were not due to the vagaries of 
design of this or that compiler.  (Generics did cause problems though.) 
As the descendant of Ada83, one would expect some of the same behaviour
from Ada95, plus the usual new-compiler and new-language teething effects.


Question.  Is there an Ada95 FAQ or the like, full of suitably dire
warnings?  I have seen very useful and widely used published books of such
things for C and C++, but have never seen anything like it for Ada95.  If
there isn't yet one, perhaps we should develop one, for our mutual
protection.  

I suppose that the writers of Ada95 compilers know where they struggled
with Ada95, as well as Ada83 before it.  If it was hard for them to write,
it will likely generate lots of code.


Joe Gwinn

Re: Beware: Rep spec on an enumeration type causes code explosion

[David Marshall]

gwinn@res.ray.com (Joe Gwinn) writes:

[interesting information on Ada95 code tuning snipped]

>We have now removed the bulk of the rep specs on enumeration types, just
>trusting for now that the compiler will always start enumerations at zero,
>just like C/C++.  Ada95 does not specify the base value of an enumeration,
>so compilers vary. We were using rep specs to govern the representation of
>Ada records used to generate and understand messages exchanged with
>display consoles coded in C++.  This idiom is used extensively.   For
>portability, we will eventually change the code to remove all ungoverned
>enumerations.

Just a moment!  Ada95 DOES represent the base value of the first
enumeral as zero, unless otherwise specified with an enumeration
representation clause.

RM95 3.5.1(7):

Each enumeration literal corresponds to a distinct value of the
enumeration type, and to a distinct position number.  The position
number of the value of the first listed enumeration literal is zero;
the position number of the value of each subsequent enumeration
literal is one more than that of its predecessor in the list.

RM95 13.4(8):

For nonboolean enumeration types, if the coding is not specified for
the type, then for each value of the type, the internal code shall be
equal to its position number.
-- 
Dave Marshall
dmarshal@netcom.com

Re: Beware: Rep spec on an enumeration type causes code explosion

[Robert Dewar]

Joe Gwinn said

<<Exception handlers.  We were declaring a number of exception handlers at
  the beginning of each and every module, so every time the module was
  entered, the context had to be saved, and every time the module was
  exited, the context was popped off the exception stack and discarded,
  regardless of if an exception was ever raised.  This was easily solved;
  now, only tasks declare exception handlers, not modules.>>


Just so it is clear, this is by no means a necessary consequence of the
Ada language (and indeed the situation with exceptions is essentially
identical in C++).

The issue is how exceptions are implemented. It is indeed much easier
to handle exceptions by doing context saves on entry to an exception
frame, and then popping them off. Particularly in tasking environments
(where the current task context must be accessed to determine where
to store the context), and on RISC machines (where saving the context
can mean saving dozens of registers), this can be a very expensive
approach. With GNAT, we even discovered that Sun, for no good reason
at all, was doing a system call as part of setjmp!

In the case of GNAT, we used to use the system setjmp/longjmp for this
purpose, but, particularly because of the idiotically inefficient design
of setjmp in Solaris, we replaced this with our own builtin setjmp that
is much more efficient, but that is still only relative.

Really what is intended and expected by the Ada design is a "zero cost"
approach where the declaration of exception handlers costs nothing, and
you pay a price only when an exception is raised. This is done by building
appropriate data tables, so that the exception handler can figure out how
to restore the context without having wasted time saving it.

Such zero cost exception handling approaches are not science fiction, rather
they are pretty standard in the Ada world. I assume that the new Aonix
Object Ada has zero cost EH (the reason I assume this is that the runtime
is based on the old Alsys technology, and I helped write the zero cost
exception handling for this old technology :-) I certainly know that
Verdix Ada 83 technology uses a zero cost approach.

The difficulty with the zero cost approach is that it tends to be highly
machine dependent, and that is one of the reasons that it is been difficult
to do in the GNAT environment, which is so committed to machine independent
approaches. 

Nevertheless we regard switching to a zero cost exception scheme in GNAT to
be our highest priority technical improvement to the system, and indeed it
happens to be exactly what I am working on right now (I am answering this
while waiting for a new version to build that incorporates some of the 
necessary changes). This will first be built for the SGI version (that's
because SGI is funding some of the technical work for this modification),
but will be propagated to other versions soon after.

The bottom line here is that this is something you need to beat up on your
vendor about! Some of our customers have complained loudly at this problem
in GNAT, and as usual, the technical direction of GNAT, like any other
commercial compiler, is quite sensitive to user needs :-) :-) We know at
least one customer who would like to switch from Verdix (Rational)
technology, but this one inefficiency is holding them up (that's an SGI
customer, and hopefully the problem will be resolved very shortly, and
they will be able to do the switch they would like to).

If you have a style of programming which requires very large numbers of
exception handlers, then this is one of the aspects of compiler performance
that you need to carefuly evaluate. It is most certainly an issue that
you need to be aware of when using a language like Ad or C++ that supports
exceptions.

Robert Dewar
Ada Core Technologies

Re: Beware: Rep spec on an enumeration type causes code explosion

[Robert Dewar]

Joe says

<<Memory Management.  The Ada Runtime System makes extensive calls to the C
  functions malloc() and free(), a cause for worry.  Variable-block
  allocators such as malloc and free are generally unsuited for nonstop
  heavy use, and will generally either leak memory or fragment their memory
  pool, causing the application to run slower and slower until it eventually
  jams.   The use of free() in a realtime system is generally forbidden;
  it's OK to allocate a bunch of memory during startup, and explicitly
  manage it yourself during operation, but it is not OK to use malloc and
  free for realtime memory management.  The claim is that Wind River's
  version of malloc/free is stable in realtime use.  It's hard to see how
  this could be true.   This will need further research.>>


The issue of implicit heap access is a critical one in any Ada technology.
This is *especially* true of embedded use. In the design of GNAT, we have
followed the general philosophy of minimizing implicit heap use. The only
times that the heap is used implicitly are the following:

1. Creation of tasks
2. Allocation of the secondary stack for tasks

We specifically do NOT use the heap for management of variant records.
Instead, we always allocate the maximum size where appropriate.

Note that an implementation (at least one that conforms to annex H) is
required to document where it uses the heap implicitly, see RM D.7:

8   No_Implicit_Heap_Allocations
                There are no operations that implicitly require heap storage
                allocation to be performed by the implementation.  The
                operations that implicitly require heap storage allocation
                are implementation defined.

Re: Beware: Rep spec on an enumeration type causes code explosion

[Robert Dewar]

Joe said

<<<<Enumeration Types.  This is the zinger.  A 29-line Ada95 program expanded
  into 1,090 lines of assembly code, a static expansion ratio of 38:1, not
  the usual 3:1 or 4:1.  In this 1,090 lines of assembly, there were
  multiple calls to the Ada RTE routine "_rts_holey_enumeration" (or the
  like), which is reported to handle enumeration types that may contain gaps
  in the mapping sequence, or whose base value (zero or one) isn't known at
  compile time.

  At first, we though that the bloat was caused by the use of subranges of
  enumeration types, but soon discovered that the real problem was caused by
  the use of representation specifications on enumeration types, and that
  use of subranges appears to be irrelevant.

  We have now removed the bulk of the rep specs on enumeration types, just
  trusting for now that the compiler will always start enumerations at zero,
  just like C/C++.  Ada95 does not specify the base value of an enumeration,
  so compilers vary. We were using rep specs to govern the representation of
  Ada records used to generate and understand messages exchanged with
  display consoles coded in C++.  This idiom is used extensively.   For
  portability, we will eventually change the code to remove all ungoverned
  enumerations.>>


There are two issues here. One is the use of a confirming enumeration
clause that specifies zero origin, and consecutive integers for the
representation. This should have ZERO effect on the generated code. If
it does not, then this is a clear inefficiency on the part of the
implementation that should be fixed. Certainly such a declaration
in GNAT has no effect whatsoever on the generated code.

On the other hand, it is totally unnecessary to give such a declaration
in Ada 95, since a compiler is *required* to use a zero based representation.
You can most certainly "trust" this. In fact I would be more inclined to
trust that a compiler would implement this correctly than that it would
get enumeration representation clauses right! The relevant statement in
the RM (easily found) is:

                         Implementation Requirements

8   For nonboolean enumeration types, if the coding is not specified for the
type, then for each value of the type, the internal code shall be equal to
its position number.


That's clear enough I think. So if you were putting in representation
clauses of this confirming type, they are obfuscatory and unnecessary
in any case, and should be removed whether or not they trigger compiler
madness.

As for enumeration types with holes, that's a different matter. There is
a fundamental extra processing requirement there for conversion from
position to representation values and back again for such opertions
as array indexing, and loop control. An Ada programmer should be
completely aware that if you use such an enumeration type for any
operation involving access to the pos value (e.g. array indexing,
loops, succ, pred), then you will pay a price. If you do NOT use
any of these operations, then the use of such enumeration types
should not introduce any significant overhead, although there may
be some space for tables. 

Measuring the expansion of a 29 line program may be completely bogus
here, because you may be looking at the base cost of the tables involved.

In the case of GNAT, all code for such enumeration types with holes is
generated by the compiler without reference to the runtime (this means
that such types are fully supported by the new GNORT tecnology, which is
GNAT with No RunTime, a version of GNAT for use in critical embedded
applications which require certification).

A very useful feature in GNAT is that you can understand a lot about 
expansion of your code by using the -gnatdg switch, which reconstructs
the expanded tree into Ada source. Let's look at it in action for
"holey" enumeration types:

Here is a little source program:

procedure h is
   type Enum is (A,B,C);
   for Enum use (1,5,10);

begin
   for J in Enum loop
      null;
   end;
end;

And the -gnatdg output (after correcting the silly syntax error of the
missing loop on the end loop :-) is:

procedure h is
   type enum is (a, b, c);
   for enum use (1, 5, 10);
      null;
      enumA : constant array (natural range 0 .. 2) of enum := (a, b, c);
      function _rep_to_pos (A : enum; F : boolean) return integer is
      begin
         case unsigned!(A) is
            when 1 =>
               return 0;
            when 5 =>
               return 1;
            when 10 =>
               return 2;
            when others =>
               if F then
                  [program_error]
               else
                  return -1;
               end if;
         end case;
      end _rep_to_pos;
   ]
   L_1 : label
begin
   L_1 : for jP in natural range 0 .. 2 loop
      declare
         j : constant enum := enumA (jP);
      begin
         null;
      end;
   end loop L_1;
   return;
end h;

You see here that a table is constructed for going from the pos value to
the rep value, and a function using a case statement for going in the
reverse direction. Obviously pos-to-rep is going to be much more efficient
than rep-to-pos, especially in the very sparse case.

The loop code generated by GNAT here is pretty nice, since as you see
it keeps a shadow of the pos value, and then computes the loop index
by using the fast pos-to-rep code. But you can't count on a compiler
doing that. The naive code would involve conversions in both directions
on each cycle of the loop.

For a more expensive use of this feature, let's look at arrays:

procedure h is
   type Enum is (A,B,C);
   for Enum use (1,5,10);
   type x is array (Enum) of Integer;
   v : x;
   e : enum := B;

begin
   v(e) := 2;
end;

There is actually a very important implementation dependent decision
to be made here, for which the RM gives no hint of a desirable decision,
or even a recognition that there *is* an implementation dependence here.
And that is whether to index the array by pos or rep values. To index
by pos values means that the array type x has size 12 bytes (assuming
4 byte integers), and to index by rep values, means that it has size
40 bytes (i.e. room for 10 integers with holes).

At first in GNAT, we chose the representation with holes, which is much
more efficient for indexing, but wastes space. However, we found that
Verdix had chosen to use the compact pos based representation, and so
we changed GNAT to match, since several of our large customers had
legacy Verdix code that depended on this assumption. This means that
indexing such an array requires the more expensive rep-to-pos conversion.
Let's look at the expanded code (the tables are the same of course)

th system.unsigned_types;

procedure h is
   type enum is (a, b, c);
   for enum use (1, 5, 10);
   type x is array (a .. c) of integer;
      null;
      enumA : constant array (natural range 0 .. 2) of enum := (a, b, c);
      function _rep_to_pos (A : enum; F : boolean) return integer is
      begin
         case unsigned!(A) is
            when 1 =>
               return 0;
            when 5 =>
               return 1;
            when 10 =>
               return 2;
            when others =>
               if F then
                  [program_error]
               else
                  return -1;
               end if;
         end case;
      end _rep_to_pos;
   ]
   freeze TxB []
   freeze x []
   v : x;
   e : enum := b;
begin
   xP!(v) (natural(_rep_to_pos (e, true))) := 2;
   return;
end h;

and there it is! The _rep_to_pos call that is needed to do the conversion.
The xP! here has to do with the fact that the underlying array at the
implementation level is different from the one in the source (since its
index type is integer range 0 .. 2), the ! is an unchecked conversion from
the source type to the implementation type. Like unchecked conversions in
general it does not generate code, it is required for type correctness of
the expanded tree.

The true parameter in the call tells the rep_to_pos routine what to do
with a bad value that falls in a hole. Normally this raises program error,
but there is one exception, namely the 'Valid attribute. We could generate
two tables, to avoid the extra parameter in the normal case. That's a 
trade off between time and space, and we decided that it is better
to have only one copy of that large case statement.

The -gnatdg switch is available on all versions of GNAT. The output is
Ada source with a few peculiar decorations (like the ! for unchecked
conversion above). For details on these decorations, you can look at the
text of the sprint.ads unit in the GNAT source distribution.

The -gnatdg switch was put in for compiler debugging, but it has proved
to be a very useful feature for programmers, to give them a better idea
of the consequences of the code they right, and to understand the code
that GNAT generates. We are thinking of elevating this switch to full
first-class citizenship instead of leaving it as a debugging switch.

Robert Dewar
Ada Core Technologies

Re: Beware: Rep spec on an enumeration type causes code explosion

[Robert Dewar]

<<Question.  Is there an Ada95 FAQ or the like, full of suitably dire
  warnings?  I have seen very useful and widely used published books of such
  things for C and C++, but have never seen anything like it for Ada95.  If
  there isn't yet one, perhaps we should develop one, for our mutual
  protection.>>


Although there are some general things that could be said, a lot of this
material is compiler dependent, so the place to go for such help and
information is most definitely your compiler vendor. We find that a lot
of our support work for GNAT involves working with our customers to help
them understand precisely the kind of issues that Joe raised in his post.

Robert Dewar
Ada Core Technologies

Re: Beware: Rep spec on an enumeration type causes code explosion

[Robert Dewar]

Joe said

<<I suppose that the writers of Ada95 compilers know where they struggled
with Ada95, as well as Ada83 before it.  If it was hard for them to write,
it will likely generate lots of code.
>>

Not necessarily, I don't see any real relationship between difficulty
of implementation and amount of code generated. For example, private
types remain one of the most difficult areas of Ada 95 to implement
correctly (Tuck once said that the hard parts of Ada 95 from an
implementors point of view all come from Ada 83 :-) Yet private types
of course generate no code at all in most cases.

Similarly, generics are very hard to get right, but this does not mean
that lots of unnecessary code is generated.

On the other hand, most (but not all) of the processing for enumeration
types with holes is quite straightforward, but surprised Joe with the
amount of code generated (actually that might not be quite fair, from the
sound of it, it could be the case that the compiler was in that case
generating more code than is justified).

Re: Beware: Rep spec on an enumeration type causes code explosion

[Tucker Taft]

Joe Gwinn (gwinn@res.ray.com) wrote:

: ...
: Exception handlers.  We were declaring a number of exception handlers at
: the beginning of each and every module, so every time the module was
: entered, the context had to be saved, and every time the module was
: exited, the context was popped off the exception stack and discarded,
: regardless of if an exception was ever raised.  This was easily solved;
: now, only tasks declare exception handlers, not modules.

I believe Green Hills is beginning to work on an implementation of
exceptions that uses a PC-indexed table rather than setjmp/longjmp.  
However, as Robert points out, using such a table is significantly more
machine-dependent, and generally requires coordination with the linker
and more complex out-of-line algorithms in the run-time.

As far as enumeration types, as others have pointed out, the Ada 95
standard requires that the internal codes for enumeration types are
contiguous and start at zero, so you are not in any danger if you leave
out your "confirming" representation clauses.  It would be nice if
our front end recognized "confirming" enumeration representation 
clauses, but as usual, there are many possible "optimizations" 
and this one never made it to the top of the list.
One might argue that this is not really an optimization, but 
it does require special code to recognize, and so represents
yet another "special case" that you have to decide the priority
of recognizing.

: ...
: Memory Management.  The Ada Runtime System makes extensive calls to the C
: functions malloc() and free(), a cause for worry.  

It might be interesting to identify where this is really happening.
Were these from calls in your source code to "new" and instances
of Unchecked_Deallocation, or were they "implicit"?

We have versions of our runtime which only use the heap "implicitly" 
for task control blocks (and these are recycled explicitly rather than 
using free) and for task stacks (and again, these are recycled rather
than using free).  So the only calls on "free" should be in response
to an explicit call on an instance of unchecked-deallocation.  Furthermore,
we also have our own implementation of malloc/free which uses 
"quick fit" rather than the traditional C "first fit."  This may
be the algorithm

: ...
: Joe Gwinn

--
-Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
Intermetrics, Inc.  Burlington, MA  USA

Re: Beware: Rep spec on an enumeration type causes code explosion

[Robert Dewar]

Tuck said

<<As far as enumeration types, as others have pointed out, the Ada 95
standard requires that the internal codes for enumeration types are
contiguous and start at zero, so you are not in any danger if you leave
out your "confirming" representation clauses.  It would be nice if
our front end recognized "confirming" enumeration representation
clauses, but as usual, there are many possible "optimizations"
and this one never made it to the top of the list.
One might argue that this is not really an optimization, but
it does require special code to recognize, and so represents
yet another "special case" that you have to decide the priority
of recognizing.
>>

We found pretty early on with GNAT that a *lot* of legacy code uses
these confirming representation clauses. This is not unreasonable. In
Ada 83 there is no guarantee that the default representation is zero
based and contiguous, and moreover the official definition of Standard
contains the following:

  for CHARACTER use  --  128 ASCII character set without holes
       (0, 1, 2, 3, 4, 5, ..., 125, 126, 127); 


which certainly creates the impression that it is good style to add
these confirming representation clauses. Indeed I would argue that it
is still good style to add them in Ada 95 as a way of documenting and
emphasizing that you are depending on the representation.

In any case, the fact is that a lot of code *does* contain this optimization,
which is why we are careful in GNAT to make the definition of "enumeration
with holes" be a situation in which the representation disagrees with the
pos for at least one literal, rather than the presence of an enumeration
representation clause. We have found that this optimization makes a critical
performance difference for more than one of our customers.

Robert Dewar
Ada Core Technologies

Re: Beware: Rep spec on an enumeration type causes code explosion

[Robert Dewar]

Tucker said

<<We have versions of our runtime which only use the heap "implicitly"
for task control blocks (and these are recycled explicitly rather than
using free) and for task stacks (and again, these are recycled rather
than using free).  So the only calls on "free" should be in response
to an explicit call on an instance of unchecked-deallocation.  Furthermore,
we also have our own implementation of malloc/free which uses
"quick fit" rather than the traditional C "first fit."  This may
be the algorithm
>>


A useful idea would be to have a specific overridable storage pool that
can be used for task stack creation, something like

for task'Task_Storage_Pool use storage pool

actually it seems like it would be perfectly reasonable to allow the
extension of the standard Storage_Pool attribute for this:

for task'Storage_Pool use ...

where task is a task object or task type???

Re: Beware: Rep spec on an enumeration type causes code explosion

[Matthew Heaney]

In article <dewar.881402942@merv>, dewar@merv.cs.nyu.edu (Robert Dewar) wrote:


>There is actually a very important implementation dependent decision
>to be made here, for which the RM gives no hint of a desirable decision,
>or even a recognition that there *is* an implementation dependence here.
>And that is whether to index the array by pos or rep values. To index
>by pos values means that the array type x has size 12 bytes (assuming
>4 byte integers), and to index by rep values, means that it has size
>40 bytes (i.e. room for 10 integers with holes).

The "recognition of an implementation dependence"  does appear in the Ada
83 Rationale.  Section 15.5, Enumeration Types with Noncontiguous
Representations, discusses the issues Robert alluded to in his post. 
Indeed, the implementation techniques Robert proffered are in there too.

Every Ada programmer should read the Ada 83 Rationale, as it provides lots
of cool insight into the language.

--------------------------------------------------------------------
Matthew Heaney
Software Development Consultant
<mailto:matthew_heaney@acm.org>
(818) 985-1271

Re: Beware: Rep spec on an enumeration type causes code explosion

[Ken Garlington]

Joe Gwinn wrote:
> 
> Question.  Is there an Ada95 FAQ or the like, full of suitably dire
> warnings?  I have seen very useful and widely used published books of such
> things for C and C++, but have never seen anything like it for Ada95.  If
> there isn't yet one, perhaps we should develop one, for our mutual
> protection.

Two sources of information come to mind:

1. For general "warnings" of this type, you may wish to try the Ada
Quality & Style Guide,
which is available from

   http://sw-eng.falls-church.va.us/AdaIC/

For example, using the handy search feature for "enumeration
representation", one finds the statement:

  "Only if absolutely necessary, use representation clauses to match
requirements of external devices."

2. Check with your compiler vendor for available tool-specific
documentation. TI/Tartan compilers, for example, come with a fairly good
section on writing for optimization, and include a list of bugs
(including those affecting optimization). If your vendor can't, or
won't, provide such information, and you really need it, then consider a
change of vendor!

Re: Beware: Rep spec on an enumeration type causes code explosion

[Kevin D. Heatwole]

In article <gwinn-0512972303070001@dh5055063.res.ray.com>,
gwinn@res.ray.com (Joe Gwinn) wrote:

>We just ran into a real zinger with the Green Hills Ada95 compiler
>(Solaris host, 68060 target, VxWorks 5.2 target OS), although it appears
>that the issue may be common to all Ada95 compilers.  

Sounds like the Green Hills compiler might just be a little green.  :-)

I wouldn't generalize your experiences to all Ada95 compilers though.  Some
are much more mature.  For example, the problem with entering/leaving
scopes with exception handlers causing setjmp/longjmp-like calls to be
performed is probably more related to Green Hills probably reusing their C
code generator with the Intermetrics Ada95 front-end.  Since C doesn't have
exception handlers, they probably just threw in the calls to setjmp/longjmp
since it was easier than trying to get the C code generator to support a
more table driven implementation for exceptions (so use of
exceptions/handlers don't incur any time penalty unless an exception is
actually raised).

Many of the Ada frontends that have been glued to backends that were
originally designed to support the C language have similar problems early
on (until the backend can be modified to support Ada features more
efficiently).  For example, I believe that the GNAT compiler had problems
implementing some overflow checks efficiently on some targets since the
backend (which hadn't been modified yet for Ada) didn't support easily
detecting overflow and turning this into an exception.
So, GNAT suppresses these checks by default and makes you ask for them.

Also, range checks can be inefficient on some hardware when using a C
oriented backend for the Ada compiler.  It is easy to implement these
checks using "if" statements in the backend and raise constraint_error if
the check fails.  On hardware, such as the PowerPC (which I work on
exclusively), it is much more efficient to implement range checks using
"trap" instructions that can be almost free (unless the trap is taken, then
the runtime needs to propagate the exception).

As for inefficient handling of enumeration types because of a rep spec, the
compiler should not revert to a slower implementation if the rep spec
doesn't add holes in the range of underlying values.  This is probably just
a sign of an immature compiler and this problem should be fixable by the
vendor if the vendor is responsive to its users needs.  It is a fact that
users need to be vocal in providing feedback to compiler vendors to get
them to address issues that are affecting their ability to deliver code
that meets application requirements.  If your vendor isn't responsive in
addressing your problems and working with you to be successful, you should
probably take your business elsewhere.  Ada compilers are very complex
beasts and no compiler is going to handle every Ada construct perfectly
with respect to minimal execution time, but compilers generally improve
with time and successful use (provided the vendor is committed to evolving
the implementation).

For the record, I work for an Ada95 compiler vendor (OC Systems) and I
would hope our users would feel that we are responsive to their
concerns/needs and that we would respond by doing whatever is reasonable to
make the user successful.  This sometimes involves short term workarounds
and some flexibility by the user in being open to solutions (not all
features in Ada have efficient implementations or not all compilers can be
adapted to implement a feature in a different way without adversely
affecting other parts of the implementation).   But, I believe that other
Ada vendors have similar goals in providing high quality Ada implementions
(especially those vendors that derive a significant portion of their
revenue from Ada sales/support).  Note that I have had no experience with
Green Hills products and do not know whether Joe's experience is typical.

Anyway, don't paint all Ada95 implementation with the same brush and not
all vendors provide the same level of support.

Kevin Heatwole
OC Systems, Inc.

Re: Beware: Rep spec on an enumeration type causes code explosion

[Corey Minyard]

gwinn@res.ray.com (Joe Gwinn) writes:
> 
> Memory Management.  The Ada Runtime System makes extensive calls to the C
> functions malloc() and free(), a cause for worry.  Variable-block
> allocators such as malloc and free are generally unsuited for nonstop
> heavy use, and will generally either leak memory or fragment their memory
> pool, causing the application to run slower and slower until it eventually
> jams.   The use of free() in a realtime system is generally forbidden;
> it's OK to allocate a bunch of memory during startup, and explicitly
> manage it yourself during operation, but it is not OK to use malloc and
> free for realtime memory management.  The claim is that Wind River's
> version of malloc/free is stable in realtime use.  It's hard to see how
> this could be true.   This will need further research.  
> 

Although this is not Ada related, I ran into this, too, when using C.
The VxWorks implementations of malloc() and free() are very bad, they
are slow and their speed decreases over use (we saw >100ms malloc
times on every call after a while!).

I ported GNU malloc, used the standard VxWorks calls to allocate a
block, and used that instead.  The times remained sub-millisecond even
after a long time.  Some people in VxWorks have the port, I suggest
you contact you VxWorks rep for it, since they have probably improved
it.

-- 
Corey Minyard               Internet:  minyard@acm.org
  Work: minyard@nortel.ca       UUCP:  minyard@wf-rch.cirr.com

Re: Beware: Rep spec on an enumeration type causes code explosion

[Larry Kilgallen]

In article <gwinn-0512972303070001@dh5055063.res.ray.com>, gwinn@res.ray.com (Joe Gwinn) writes:
> We just ran into a real zinger with the Green Hills Ada95 compiler
> (Solaris host, 68060 target, VxWorks 5.2 target OS), although it appears
> that the issue may be common to all Ada95 compilers.  

> Basically, it was spending all of its time in VxWorks, because the Ada RTE
> was calling on VxWorks at an astounding rate.  This was in turn due to two
> things, the handling of enumeration types, and the registration and
> deregistration of user-defined exception handlers at every turn.
> 
> Exception handlers.  We were declaring a number of exception handlers at
> the beginning of each and every module, so every time the module was
> entered, the context had to be saved, and every time the module was
> exited, the context was popped off the exception stack and discarded,
> regardless of if an exception was ever raised.

Isn't exception handling efficiency going to be related to the instruction
set of the machine and the calling convention of the operating system ?

VAX did this in hardware (well, microcode for some models) while Alpha
requires a slight bit more work by the compiler to set up the pointer to
the handler.  I know the VMS calling convention reasonably well, and I
have at least seen the Digital Unix one and don't remember it as being
too horrible.

Are compiler vendors really ignoring OS/hardware provided stack-based
exception handling conventions on machines that have them ?

Larry Kilgallen

Re: Beware: Rep spec on an enumeration type causes code explosion

[Robert Dewar]

Kevin said

<<Many of the Ada frontends that have been glued to backends that were
  originally designed to support the C language have similar problems early
  on (until the backend can be modified to support Ada features more
  efficiently).  For example, I believe that the GNAT compiler had problems
  implementing some overflow checks efficiently on some targets since the
  backend (which hadn't been modified yet for Ada) didn't support easily
  detecting overflow and turning this into an exception.
  So, GNAT suppresses these checks by default and makes you ask for them.>>

Actually I think that mis-diagnoses the situation. The trouble with checks
and exceptions is not the history of the code generators involved, but
rather the fundamental difficulty in dealing with these items efficiently
in a portable manner. One of the goals of both Greenhills and ACT is to
be able to easily port the technology to different architectures. This
is particularly true in the case of GNAT, where implementations for almost
all common architectures are available.

There are certainly some advantages in the OCS approach of concentrating on
a single processor with respect to these particular items. On the other hand,
good advice is always to actually test out compilers under conditions that
are realistic for you when it comes to performance. You will find results
that may well surprise you, and you certainly cannot assume that
concentrating on a single processor means better performance.

In the case of GNAT, we find overflow checks acceptably efficient in practice,
and improving their performance has not been a priority for any of our
customers (almost all of whom suppress checks for the final delivery if
performance is an issue anyway). There is no doubt they could be improved,
for example on the Power architecture, one can use the sticky bit, and
optimize checks over entire traces, using usual trace scheduling techniques,
but it is hard to believe that this would represent a useful expenditure
of effort.

On the other hand, efficient exception handling is definitely significant
for some users, especially for those who follow a style of putting an
exception handler in every subprogram :-) [yes, this is a style we have
seen!] So that we do see as a major priority, and as I mentioned, it is
the current work item in these parts!

Robert Dewar
Ada Core Technology

Re: Beware: Rep spec on an enumeration type causes code explosion

[Joe Gwinn]

In article <dewar.881405161@merv>, dewar@merv.cs.nyu.edu (Robert Dewar) wrote:

> <<Question.  Is there an Ada95 FAQ or the like, full of suitably dire
>   warnings?  I have seen very useful and widely used published books of such
>   things for C and C++, but have never seen anything like it for Ada95.  If
>   there isn't yet one, perhaps we should develop one, for our mutual
>   protection.>>
> 
> 
> Although there are some general things that could be said, a lot of this
> material is compiler dependent, so the place to go for such help and
> information is most definitely your compiler vendor. We find that a lot
> of our support work for GNAT involves working with our customers to help
> them understand precisely the kind of issues that Joe raised in his post.

Actually, I don't really care if some warnings are compiler dependent.  It
doesn't help the pain to know that it isn't universal.  

The C/C++ world is no different in this.  C++, a very complex language,is
known for its beartraps.

By and large, vendors (not just compiler vendors) don't seem to be
comfortable coming forth with sufficiently specific, pointed, and timely
warnings to allow the unwashed users to avoid blunders.  The rule seems to
just hope that the users will be lucky.  The larger the project, the less
lucky one is likely to be.  So, we will have to look to some other source
for our warnings.

What has in the past worked is lists of general issues and warnings,
without the naming of specific vendors, even though some issues may not be
universal, so at least we know under which rocks to look.  One way of
looking at this is that the list gives the relative size, weight, and
power of various idioms, so users have some idea what things cost.


Joe Gwinn

Re: Beware: Rep spec on an enumeration type causes code explosion

[Joe Gwinn]

In article <dewar.881405297@merv>, dewar@merv.cs.nyu.edu (Robert Dewar) wrote:

> Joe said
> 
> <<I suppose that the writers of Ada95 compilers know where they struggled
> with Ada95, as well as Ada83 before it.  If it was hard for them to write,
> it will likely generate lots of code.
> >>
> 
> Not necessarily, I don't see any real relationship between difficulty
> of implementation and amount of code generated. For example, private
> types remain one of the most difficult areas of Ada 95 to implement
> correctly (Tuck once said that the hard parts of Ada 95 from an
> implementors point of view all come from Ada 83 :-) Yet private types
> of course generate no code at all in most cases.
> 
> Similarly, generics are very hard to get right, but this does not mean
> that lots of unnecessary code is generated.
> 
> On the other hand, most (but not all) of the processing for enumeration
> types with holes is quite straightforward, but surprised Joe with the
> amount of code generated (actually that might not be quite fair, from the
> sound of it, it could be the case that the compiler was in that case
> generating more code than is justified).

I don't doubt that there are counterexamples, but still I bet that the
people who wrote the compilers have a pretty good idea which idioms are
likely to lead to code explosions, and which are not likely to explode,
and can tell us what the relative costs are likely to be.  I'm sure they
thought that part of the compiler quite ugly, for the gyrations they were
for one reason or another forced to perform.

Great precision is not required.  The point is to avoid project-killing
100:1 effects, not to trim 10% somewhere.

Joe Gwinn

Re: Beware: Rep spec on an enumeration type causes code explosion

[Joe Gwinn]

In article <EKrsrr.LD7.0.-s@inmet.camb.inmet.com>,
stt@houdini.camb.inmet.com (Tucker Taft) wrote:

> Joe Gwinn (gwinn@res.ray.com) wrote:
> 
> : ...
> : Exception handlers.  We were declaring a number of exception handlers at
> : the beginning of each and every module, so every time the module was
> : entered, the context had to be saved, and every time the module was
> : exited, the context was popped off the exception stack and discarded,
> : regardless of if an exception was ever raised.  This was easily solved;
> : now, only tasks declare exception handlers, not modules.
> 
> I believe Green Hills is beginning to work on an implementation of
> exceptions that uses a PC-indexed table rather than setjmp/longjmp.  
> However, as Robert points out, using such a table is significantly more
> machine-dependent, and generally requires coordination with the linker
> and more complex out-of-line algorithms in the run-time.

This sounds good, but I would guess that it won't arrive in time for the
current project.  

Probably two thirds of the high-end embedded realtime market will target
the PowerPC, so that's one place where some machine dependency may be
worthwhile.

 
> As far as enumeration types, as others have pointed out, the Ada 95
> standard requires that the internal codes for enumeration types are
> contiguous and start at zero, so you are not in any danger if you leave
> out your "confirming" representation clauses.  It would be nice if
> our front end recognized "confirming" enumeration representation 
> clauses, but as usual, there are many possible "optimizations" 
> and this one never made it to the top of the list.
> One might argue that this is not really an optimization, but 
> it does require special code to recognize, and so represents
> yet another "special case" that you have to decide the priority
> of recognizing.

The key issue was that we had no way of knowing the dire consequences of
this innocent looking bit of standard Ada, until we had gone a fair
distance down that wrong road.  One wonders what other surprises lay in
wait.

A number of folk have cited chapter and verse that enumerations do start
at zero if left alone.  This was not widely known, apparently, perhaps
because Ada83 didn't govern this.  


> : ...
> : Memory Management.  The Ada Runtime System makes extensive calls to the C
> : functions malloc() and free(), a cause for worry.  
> 
> It might be interesting to identify where this is really happening.
> Were these from calls in your source code to "new" and instances
> of Unchecked_Deallocation, or were they "implicit"?

They were implicit.  Our programmers are in fact forbidden to deallocate
using the Ada RTE, to avoid fragmentation etc.  The profiler caught no
miscreant applications.

Now that use of exception handlers and rep specs on enumerations have been
restricted, the calls to malloc and free dropped to near zero.  We will
trap and inspect all callers of free, so if any of our programmers are
using malloc/free, they will be caught.  

What to do about Ada RTE implicit use of malloc/free is quite another issue.

By the way, the issue is use of free, not malloc per se.  The applications
are allowed to allocate structures during startup, but they are not
allowed to use free.  They must instead keep the memory and manage it
themselves, using a simple and obviously fragmentation proof algorithm.


> We have versions of our runtime which only use the heap "implicitly" 
> for task control blocks (and these are recycled explicitly rather than 
> using free) and for task stacks (and again, these are recycled rather
> than using free).  So the only calls on "free" should be in response
> to an explicit call on an instance of unchecked-deallocation. 

This sounds good, but I don't know that it's draconian enough for embedded
realtime.  I don't know that I would give random users the choice of
versions.  As I said above, we forbid users to use deallocation (and thus
free).  Is that runtime set up so I can flip a compiler switch to catch
any users that didn't understand that they are not allowed to use
deallocate?


> ... Furthermore,
> we also have our own implementation of malloc/free which uses 
> "quick fit" rather than the traditional C "first fit."  This may
> be the algorithm

Quick-fit algorithms also can fragment; what's different is the spectrum
of request sizes needed to provoke trouble.  Actually, many quick-fit
algorithms generate worse fragmentation than the worst-fit algorithms. 
All the variable-length memory management algorithms have their advantages
and disadvantages, but the biggest disadvantage is that they are
inherently statistical in nature, so there is always a request spectrum
that will kill them.  

Historically, we have found that the only approach that always works, even
when the system is straining under the load, is a fixed-block allocator
offering three or four project-specific sizes of block.


Joe Gwinn

Re: Beware: Rep spec on an enumeration type causes code explosion

[Joe Gwinn]

In article <m267p2p27b.fsf@wf-rch.cirr.com>, Corey Minyard
<minyard@acm.org> wrote:

> gwinn@res.ray.com (Joe Gwinn) writes:
> > 
> > Memory Management.  The Ada Runtime System makes extensive calls to the C
> > functions malloc() and free(), a cause for worry.  Variable-block
> > allocators such as malloc and free are generally unsuited for nonstop
> > heavy use, and will generally either leak memory or fragment their memory
> > pool, causing the application to run slower and slower until it eventually
> > jams.   The use of free() in a realtime system is generally forbidden;
> > it's OK to allocate a bunch of memory during startup, and explicitly
> > manage it yourself during operation, but it is not OK to use malloc and
> > free for realtime memory management.  The claim is that Wind River's
> > version of malloc/free is stable in realtime use.  It's hard to see how
> > this could be true.   This will need further research.  
> > 
> 
> Although this is not Ada related, I ran into this, too, when using C.
> The VxWorks implementations of malloc() and free() are very bad, they
> are slow and their speed decreases over use (we saw >100ms malloc
> times on every call after a while!).
> 
> I ported GNU malloc, used the standard VxWorks calls to allocate a
> block, and used that instead.  The times remained sub-millisecond even
> after a long time.  Some people in VxWorks have the port, I suggest
> you contact you VxWorks rep for it, since they have probably improved
> it.

As I said in my reply to Tucker Taft, our experience is that only
fixed-block allocators work in embedded realtime, especially when the
system is heavily loaded.  Such allocators have constant performance,
right up to the point of pool exhaustion, and recover instantly when
someone returns some memory.  Variable block allocators as a class run
slower and slower as their pool approaches exhaustion; this is exactly the
wrong behaviour, as it makes worse the effects of the original overload.

Joe Gwinn

Re: Beware: Rep spec on an enumeration type causes code explosion

[Mats Weber]

Joe Gwinn wrote:

> Historically, we have found that the only approach that always works, even
> when the system is straining under the load, is a fixed-block allocator
> offering three or four project-specific sizes of block.

We have found that allocating only sizes that are powers of two works well.
You need very few lists of free blocks and the implementation is very simple.
If you want to waste less storage, you can also use powers of a smaller
number, e.g. 1.5.

Re: Beware: Rep spec on an enumeration type causes code explosion

[Matthew Heaney]

In article <EKxx9n.Ly1.0.-s@inmet.camb.inmet.com>,
stt@houdini.camb.inmet.com (Tucker Taft) wrote:


>So in retrospect, I believe enumeration representation 
>clauses in Ada are a mistake.  If a user wants to name 
>particular values, they should simply use named integer
>constants, or perhaps better, named private-type constants.  They can build 
>up various maps of their own if they want to translate to/from some kind
>of "holey" representation from/to a contiguous representation.

Hallelujah!  I've always thought the same thing.  If you want to read data
off an external interface, then just read it into an integer, and convert
it to an enumeration value yourself.  Look Ma, no validity problems!  And
no hidden inefficiencies.  And no compiler complexity.  And so on...

--------------------------------------------------------------------
Matthew Heaney
Software Development Consultant
<mailto:matthew_heaney@acm.org>
(818) 985-1271

Re: Beware: Rep spec on an enumeration type causes code explosion

[Jim Gleason]

Kevin D. Heatwole <heatwole@his.com> wrote in article
<heatwole-ya02408000R0612971125590001@news3.his.com>...
> 
> Sounds like the Green Hills compiler might just be a little green.  :-)
> 

The Green Hills Ada95 compiler was the first, and, to my knowledge, only,
compiler
to have completed ACVC 2.1 validations.  This validation included the
Systems
Programming Annex as well as the Real-Time Systems Annex.  The Green Hills
Ada95 compiler is a very mature implementation of Ada95.

I am a senior compiler developer at Green Hills Software.  Neither issue
that Joe Gwinn
ran into is a result of what Kevin refers to as the "reusing" or having
"glued" the Green
Hills "C code generator with the Intermetrics Ada95 front-end".  

The current 68K cross compiler implementation of exception handling in the
current
fashion has almost nothing to do with the code generator.  Rather, it is an
issue for the 
linker, Ada runtime system and, in some cases, the commercial target
operating 
system.  Another oversight by Kevin is the fact that the Green Hills
backend 
design is not limited to the C language.  Green Hills' backends/code
generators are 
designed to support Ada95, C, C++, Fortran and Pascal.  With this breadth
of 
language technology, there is nothing that hasn't been done or can't be
done with 
the Green Hills backends to fully support a highly optimizing Ada95
compiler.  As 
Tucker mentioned, we are currently developing a table-driven exception
handling 
scheme.

Like OC Systems, Green Hills is without question, sensitive to our
customers
concerns and needs.  Our primary goal is the success of our customer's
programs
and products.  To that end, we are always flexible and open to any
suggestions from
customers regarding the improvement of our Ada95 compilers and the
supporting 
software development tools.

Jim Gleason
Green Hills Software, Inc.

Re: Beware: Rep spec on an enumeration type causes code explosion

[Stanley R. Allen]

Joe Gwinn wrote:

> What has in the past worked is lists of general issues and warnings,
> without the naming of specific vendors, even though some issues may not be
> universal, so at least we know under which rocks to look.  One way of
> looking at this is that the list gives the relative size, weight, and
> power of various idioms, so users have some idea what things cost.

You need something like PIWG or ACES.

-- 
Stanley Allen
mailto:s_allen@hso.link.com

Re: Beware: Rep spec on an enumeration type causes code explosion

[Tucker Taft]

Joe Gwinn (gwinn@res.ray.com) wrote:
: In article <EKrsrr.LD7.0.-s@inmet.camb.inmet.com>,
: stt@houdini.camb.inmet.com (Tucker Taft) wrote:

: ...
: > As far as enumeration types, as others have pointed out, the Ada 95
: > standard requires that the internal codes for enumeration types are
: > contiguous and start at zero, so you are not in any danger if you leave
: > out your "confirming" representation clauses.  It would be nice if
: > our front end recognized "confirming" enumeration representation 
: > clauses, but as usual, there are many possible "optimizations" 
: > and this one never made it to the top of the list.
: > One might argue that this is not really an optimization, but 
: > it does require special code to recognize, and so represents
: > yet another "special case" that you have to decide the priority
: > of recognizing.

: The key issue was that we had no way of knowing the dire consequences of
: this innocent looking bit of standard Ada, until we had gone a fair
: distance down that wrong road.  

If you ask anyone who knows me well, you will know that I consider
the enumeration representation clause anything but "innocent looking" ;-).
For what it is worth, we will soon be releasing a new front end
that recognizes the special case of a confirming enumeration
representation clause.

[ASIDE:

Although the ability to specify the representation of an enumeration
type initially sounds perfectly reasonable, the fundamental problem is that
Ada also allows such "holey" enumeration types to be used as the
type for a for-loop index, an array index, an entry family index,
or the 'Succ/'Pred attributes.  This results in surprising implicit
inefficiencies, something that violates one of the general Ada 
language design principles.  Your enumeration rep clause simply reconfirmed
the default representation, but suppose it didn't?  You would be
stuck with the overhead you managed to eliminate by simply commenting
out the rep clause.  Of course, the compiler could recognize various
other specials cases, such as contiguous representation starting at
something other than zero, or evenly distributed "holey" representation
(e.g., even numbers only), or simply not "too" sparse, or ...  

Pretty soon handling these enumeration representation clauses
the way the "innocent" user would "expect" becomes a major artificial 
intelligence challenge.  During the Ada 9X design process, when we
found one of our new language ideas evoving into this kind of complex
AI pattern matching problem for the compiler, we knew we were on the
wrong track.  The user should be designing the algorithms, using
the basic primitives of the language.  The primitives shouldn't themselves
be at such a level that the compiler is effectively trying to take over
part of the programming problem.

Note that in C and C++, allowing the user to specify the values for
enumeration literals creates no similar problem, because there is
no operation that depends on the logical "position" of an enumeration
literal.  All semantics of enumeration values in C/C++ depends on the
underlying "code," not the position.  

So in retrospect, I believe enumeration representation 
clauses in Ada are a mistake.  If a user wants to name 
particular values, they should simply use named integer
constants, or perhaps better, named private-type constants.  They can build 
up various maps of their own if they want to translate to/from some kind
of "holey" representation from/to a contiguous representation.

END OF ASIDE]

: ... One wonders what other surprises lay in
: wait.

In general, the Ada language design philosophy eschewed "innocent"
looking features that were in fact expensive at run-time.
However, in the specific case of enumeration representation clauses,
this useful language design philosophy was not completely followed.
Other cases I know of are interactions between finalization, 
exception handling, and abort, where the combination of features
forces some or all of these three to incur more run-time overhead
than you might expect.

One "innocent" looking construct I once found was:

   (others => Default_Value(Segment))

used to initialize a segment of a load module to some default value.
This called the function Default_Value once for each byte of the
segment, and the segment was often 100K bytes or more.

: ...

: Joe Gwinn

--
-Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
Intermetrics, Inc.  Burlington, MA  USA

Re: Beware: Rep spec on an enumeration type causes code explosion

[Geert Bosch]

Joe Gwinn wrote:
 ``A number of folk have cited chapter and verse that enumerations
   do start at zero if left alone.  This was not widely known,
   apparently, perhaps because Ada83 didn't govern this.''

Strange conclusion!

I'd rather think those people know there is no reason to guess here
or to depend on vague recollections, as the RM is readily available.
Just look at the index or do a quick text search in the ASCII version. 
This may be a better way of spending time than going through all 
sources adding unnecessary representation clauses.

If you find that the problem isn't with the language but with
the implementation, you should have your compiler vendor fix it
and/or provide a good work-around until it is fixed. You should
expect better support from your vendor than a newsgroup like CLA!

Regards,
   Geert

Re: Beware: Rep spec on an enumeration type causes code explosion

[tmoran]

>By and large, vendors (not just compiler vendors) don't seem to be
>comfortable coming forth with sufficiently specific, pointed, and timely
>warnings to allow the unwashed users to avoid blunders.  The rule seems to
  The RR manual has a chapter "Limitations and Precautions" that addresses
at least some of the dangers.  I have no paper docs for either of my
other Ada compilers.

Re: Beware: Rep spec on an enumeration type causes code explosion

[Robert Dewar]

Joe Gwinn wrote:
 ``A number of folk have cited chapter and verse that enumerations
   do start at zero if left alone.  This was not widely known,
   apparently, perhaps because Ada83 didn't govern this.''

Well it is not easy to gauge what is or is not "widely known", or even what
such a phrase means. But I have never seen an Ada 83 compiler which did not
default to Pos value = representation value, and any other choice would be
strange indeed.

Yes, Ada 95 makes this explicit, but this is not a requirement that I would
expect to have any effect on implementations in practice, because no other
choice makes sense.

And certainly all the Ada programmers I have known were aware of this as
the natural and likely default!

Re: Beware: Rep spec on an enumeration type causes code explosion

[Robert Dewar]

Joe said

<<As I said in my reply to Tucker Taft, our experience is that only
fixed-block allocators work in embedded realtime, especially when the
system is heavily loaded.  Such allocators have constant performance,
right up to the point of pool exhaustion, and recover instantly when
someone returns some memory.  Variable block allocators as a class run
slower and slower as their pool approaches exhaustion; this is exactly the
wrong behaviour, as it makes worse the effects of the original overload.
>>

This is an over-generalization, there are algorithms known that provide
variable size allocation with constant performance. These algorithms are
the ones that should be used for real time performance.

Re: Beware: Rep spec on an enumeration type causes code explosion

[Robert Dewar]

Tuck said

<<Although the ability to specify the representation of an enumeration
  type initially sounds perfectly reasonable, the fundamental problem is that
  Ada also allows such "holey" enumeration types to be used as the
  type for a for-loop index, an array index, an entry family index,
  or the 'Succ/'Pred attributes.  This results in surprising implicit
  inefficiencies, something that violates one of the general Ada
  language design principles.>>

Well things are not as bad as all that, and should be better :-)

Loops need not generate significant inefficiency. Look back to the message
I sent earlier showing how GNAT handles these loops. The overhead is a single
indexed load per loop, not bad at all.

Array indexes should NOT be a problem, if we used the rep value as an index
instead of the pos value as an index. Unfortunately Verdix made what I think
was the wrong implementation choice here, and the Ada 95 RM gives no 
recommendation, so in the absence of any RM advice, we find ourselves
pushed to support Verdix compatibility, and thus introduce the unexpected
inefficiency.

To my mind, it would be better to index by default using the rep value, and
if you want to index by the pos value, do so explicitly!

Succ and Pred are indeed evil :-)

<<So in retrospect, I believe enumeration representation
  clauses in Ada are a mistake.  If a user wants to name
  So in retrospect, I believe enumeration representation
  clauses in Ada are a mistake.  If a user wants to name
  particular values, they should simply use named integer
  constants, or perhaps better, named private-type constants.  They can build
  up various maps of their own if they want to translate to/from some kind
  of "holey" representation from/to a contiguous representation.>>



No, I disagree, this is a useful feature that I have often found useful. You
only get the inefficiencies if you use the inefficient constructs, and it 
seems unreasonable to argue that a feature should be removed because someone
might use it inefficiently.

I would say that if I had my choice, I would ban the use of Succ and Pred,
and specify that array indexing was on the basis of pos values. That way
the (relatively) expensive Pos operation would only occur if the programmer
wrote it explicitly.

GNORT information ( Was Re: Beware: Rep spec on an enumeration type causes code explosion )

[Mark Bennison]

dewar@merv.cs.nyu.edu (Robert Dewar) wrote:
>In the case of GNAT, all code for such enumeration types with holes is
>generated by the compiler without reference to the runtime (this means
>that such types are fully supported by the new GNORT tecnology, which is
>GNAT with No RunTime, a version of GNAT for use in critical embedded
>applications which require certification).

Where can I find information on this GNORT stuff? I am currently involved in looking 
around for such a compiler ( we are currently considering Aonix's Raven but that is not 
yet available ). I have looked at both the GNAT and ACT europe web pages, checked the 
GNAT chat archives and performed an Alta Vista search which threw up nothing of 
relevance. Of course I may have missed something...

Thanks,

Mark.
-- 
Mark Bennison,           +-----------------------------------+
Technical Consultant,    | All opinions expressed are my own |
EASAMS Software Systems. +-----------------------------------+
"Death is a fickle hen, and random are her eggs" - Armando Iannucci

Re: Beware: Rep spec on an enumeration type causes code explosion

[Charles Hixson]

This may be so, and I'm not replying exactly to your point, but there
are many uses for disjoint ranges (e.g. [7..15, 23, 37, 128..255]), and
I think that THEY should be a part of the language.  (P.S.:  I am a
total novice at Ada, so maybe they already are, and I just haven't found
out about them).

Matthew Heaney wrote:
> 
> In article <EKxx9n.Ly1.0.-s@inmet.camb.inmet.com>,
> stt@houdini.camb.inmet.com (Tucker Taft) wrote:
> 
> >So in retrospect, I believe enumeration representation
> >clauses in Ada are a mistake.  If a user wants to name
> >particular values, they should simply use named integer
> >constants, or perhaps better, named private-type constants.  They can build
> >up various maps of their own if they want to translate to/from some kind
> >of "holey" representation from/to a contiguous representation.
> 
> Hallelujah!  I've always thought the same thing.  If you want to read data
> off an external interface, then just read it into an integer, and convert
> it to an enumeration value yourself.  Look Ma, no validity problems!  And
> no hidden inefficiencies.  And no compiler complexity.  And so on...
> 
> --------------------------------------------------------------------
> Matthew Heaney
> Software Development Consultant
> <mailto:matthew_heaney@acm.org>
> (818) 985-1271

-- 
Charles Hixson	charleshixson@earthling.net
(510) 464-7733	or chixso@mtc.dst.ca.us

Re: Beware: Rep spec on an enumeration type causes code explosion

[Jean-Pierre Rosen]

Tucker Taft wrote...
>So in retrospect, I believe enumeration representation
>clauses in Ada are a mistake.  If a user wants to name
>particular values, they should simply use named integer
>constants, or perhaps better, named private-type constants.  They can build
>up various maps of their own if they want to translate to/from some kind
>of "holey" representation from/to a contiguous representation.
>
An important issue is why is a representation clause necessary at all ?
In general, it is because of some interfaces to hardware or other
programming language. In this case, you can use an efficient representation
for internal use, and use a representation clause only for interfaces:

type Efficient_Enumeration is (...);
type External_Enumeration is new Efficient_Enumeration;
for External_Enumeration use (...);

You would convert to External_Enumeration (and incur some overhead) only
when needed.

Re: GNORT information ( Was Re: Beware: Rep spec on an enumeration type causes code explosion )

[Robert Dewar]

Mark asks

<<Where can I find information on this GNORT stuff? I am currently involved in loo
king
around for such a compiler ( we are currently considering Aonix's Raven but that
 is not
yet available ). I have looked at both the GNAT and ACT europe web pages, checke
d the
GNAT chat archives and performed an Alta Vista search which threw up nothing of
relevance. Of course I may have missed something...
>>

For information on the GNORT product, please contact our sales departments
at either sales@gnat.com or sales@act-europe.fr.

Robert Dewar
Ada Core Technologies

Re: Beware: Rep spec on an enumeration type causes code explosion

[Stephen Leake]

Tucker Taft wrote:
> 
> <discussion of holey rep clauses>
>
> So in retrospect, I believe enumeration representation
> clauses in Ada are a mistake.  If a user wants to name
> particular values, they should simply use named integer
> constants, or perhaps better, named private-type constants.  They can build
> up various maps of their own if they want to translate to/from some kind
> of "holey" representation from/to a contiguous representation.

I'm fairly sure that in most of the code I've written, if I supply a rep
clause for an enumeration type, I use it mainly as parameters to and
results from imported functions (Win32 comes to mind), but not as an
array index or with succ/pred. Often the results are used in case
statements. I guess this maps well to named private-type constants,
where the full type is simply an integer. However, it loses the
completeness check on case statements, which is always useful.

Maybe we could introduce a "bag" type (avoiding the highly overloaded
moniker "set"), which would not have pred/succ semantics, but would
provide completeness checks for case statements?

> --
> -Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
> Intermetrics, Inc.  Burlington, MA  USA

-- 
- Stephe

Re: Beware: Rep spec on an enumeration type causes code explosion

[Stanley R. Allen]

Tucker Taft wrote:

> 
> Although the ability to specify the representation of an enumeration
> type initially sounds perfectly reasonable, the fundamental problem is that
> Ada also allows such "holey" enumeration types to be used as the
> type for a for-loop index, an array index, an entry family index,
> or the 'Succ/'Pred attributes.  This results in surprising implicit
> inefficiencies, something that violates one of the general Ada
> language design principles.

I find it hard to believe that the efficiency of this
is *implictly* bad.  It seems like the use of holey enum
types for for-loop ranges, array-indexes, etc, would
always default to the use of positions; only placing
the enum value into a location should cause a table
look-up (one index redirection) for the actual value.

> 
> So in retrospect, I believe enumeration representation
> clauses in Ada are a mistake.  If a user wants to name
> particular values, they should simply use named integer
> constants, or perhaps better, named private-type constants.  They can build
> up various maps of their own if they want to translate to/from some kind
> of "holey" representation from/to a contiguous representation.
> 

But then you lose the 'Image function, 'Range, array
index, etc., which is why you wanted the Enum type to 
begin with!  (I understand that I can simulate some of
this.)

I'm not surprised to hear Tucker say this, however, since
he has complained publicly before that "those chapter 13
features end up being 50% of your compiler!"; I'm sure
compiler developers would like some relief from having to
expend so much effort on those aspects.

-- 
Stanley Allen
mailto:s_allen@hso.link.com

Re: Beware: Rep spec on an enumeration type causes code explosion

[Ken Garlington]

Tucker Taft wrote:
> [big snip]
> I believe enumeration representation
> clauses in Ada are a mistake.  If a user wants to name
> particular values, they should simply use named integer
> constants, or perhaps better, named private-type constants.  They can build
> up various maps of their own if they want to translate to/from some kind
> of "holey" representation from/to a contiguous representation.

One of the nice things about "holey" representations in Ada, when used
for
interfacing to external systems, is the use of 'Valid to check for valid
input
data in a very readable manner. However, I would convert the raw input
to a non-holey type after the check, using either a map or case
statement
(depending upon the compiler).

> One "innocent" looking construct I once found was:
> 
>    (others => Default_Value(Segment))
> 
> used to initialize a segment of a load module to some default value.
> This called the function Default_Value once for each byte of the
> segment, and the segment was often 100K bytes or more.

Assuming the function's library unit was marked Pure, then this could
(and probably should) have been optimized, right? In this case, isn't
this more of a compiler issue than a language issue?

> -Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
> Intermetrics, Inc.  Burlington, MA  USA

Re: Beware: Rep spec on an enumeration type causes code explosion

[Matthew Heaney]

In article <66po35$1a1$1@gte2.gte.net>, Rakesh Malhotra
<rakesh.malhotra@safetran.com> wrote:


>We work on safety critical projects.  And if we have a safety critical
>bit of code that defines and uses an enumeration then we use the rep
>clause to provide more than 1 bit separation between adjacent values in
>the enumeration.  That way if 1 bit got corrupted the value could not
>become some other legal value.
>
>Hence type SIGNAL_TYPE is (RED, GREEN);
>for SIGNAL_TYPE use (RED => 16#00#, GREEN => 16#03#);
>
>So if a signal was supposed to be RED, with just a 1 bit corruption it
>could never become GREEN.  Obviously we have these kinds of enum's and
>rep clauses all over the code space, and they are used in arrays to
>index etc etc.    An even worse example (from the coder's point of view)
>is that we create our own BOOLEAN_TYPE with states defined as TRUE_STATE
>and FALSE_STATE ; then give both true and false explicit values; and
>then test for those in "if" statements etc :)  Pretty horrible eh ?

This is a seriously wrong way to build safety-critical software.  As a
matter of fact, it's a wrong way to build *any* software.  You are quite
correct in pointing out that it is "pretty horrible."

As John Volan wisely pointed out, create holey types for use at the
EXTERNAL INTERFACE ONLY.  You should have an "interface object,"
implemented as a layered machine, to manage communication with each
external device.  The machine has three purposes: to read in the data from
the hardware, verify that the data received is valid, and then convert that
data from interface format to application format.
  
If you are using a holey type inside the application, ie not at the
interface layer only, then you are probably doing something wrong.  The
fact that you're using your own Boolean type does not bode well!

--------------------------------------------------------------------
Matthew Heaney
Software Development Consultant
<mailto:matthew_heaney@acm.org>
(818) 985-1271

Re: Beware: Rep spec on an enumeration type causes code explosion

[John G. Volan]

Ken Garlington wrote:
> 
> One of the nice things about "holey" representations in Ada, when used
> for
> interfacing to external systems, is the use of 'Valid to check for valid
> input
> data in a very readable manner. However, I would convert the raw input
> to a non-holey type after the check, using either a map or case
> statement
> (depending upon the compiler).

There is no need for anything so elaborate.  Just derive a holey
enumeration type from a contiguous enumeration type. Then you can simply
use ordinary Ada type-conversions, and the compiler will implicitly do
the mapping for you:

    with Ada.Text_IO;
    procedure Holey_Enum_Demo is
    
      type Contiguous_Type is (A, B, C, D, E);
      -- *no* rep spec!
    
      type Holey_Type is new Contiguous_Type;
      for Holey_Type use (A => 1, B => 2, C => 4, D => 8, E => 16);
    
      Contiguous : Contiguous_Type := A;
      Holey      : Holey_Type      := B;

    begin
    
      Contiguous := Contiguous_Type (Holey);
      -- implicitly does equivalent of 'Pos

      Holey      := Holey_Type (Contiguous);
      -- implicitly does equivalent of 'Val
    
    end Holey_Enum_Demo;

My feeling is that "holey" enumeration types (like other Chapter 13
features) should really only be used at the "edges" of a program,
wherever you're immediately reading from or writing to some external
system that is expecting a certain data format.  Contiguous enumeration
types should be used internally everywhere else in your program, for all
the efficiency reasons that have been ... enumerated :-) ... in this
thread. Luckily, Ada provides this convenient way of converting between
holey and contiguous representations.

-- 
Internet.Usenet.Put_Signature 
  (Name       => "John G. Volan",
   Employer   => "Raytheon/TI Advanced C3I Systems, San Jose, CA",
   Work_Email => "jvolan@ti.com",
   Home_Email => "johnvolan@sprintmail.com",
   Slogan     => "Ada95: World's *FIRST* International-Standard OOPL",
   Disclaimer => "My employer never defined these opinions, so using " & 
                 "them would be totally erroneous...or is that just "  &
                 "nondeterministic behavior now? :-) ");

Re: Beware: Rep spec on an enumeration type causes code explosion

[Rakesh Malhotra]

Tucker Taft wrote:
> 
> Joe Gwinn (gwinn@res.ray.com) wrote:
> : In article <EKrsrr.LD7.0.-s@inmet.camb.inmet.com>,
> [lots deleted]
> -Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
> Intermetrics, Inc.  Burlington, MA  USA

We work on safety critical projects.  And if we have a safety critical
bit of code that defines and uses an enumeration then we use the rep
clause to provide more than 1 bit separation between adjacent values in
the enumeration.  That way if 1 bit got corrupted the value could not
become some other legal value.

Hence type SIGNAL_TYPE is (RED, GREEN);
for SIGNAL_TYPE use (RED => 16#00#, GREEN => 16#03#);

So if a signal was supposed to be RED, with just a 1 bit corruption it
could never become GREEN.  Obviously we have these kinds of enum's and
rep clauses all over the code space, and they are used in arrays to
index etc etc.    An even worse example (from the coder's point of view)
is that we create our own BOOLEAN_TYPE with states defined as TRUE_STATE
and FALSE_STATE ; then give both true and false explicit values; and
then test for those in "if" statements etc :)  Pretty horrible eh ?

--
Rakesh.

Re: Beware: Rep spec on an enumeration type causes code explosion

[Ken Garlington]

John G. Volan wrote:
> 
> Ken Garlington wrote:
> >
> > One of the nice things about "holey" representations in Ada, when used
> > for
> > interfacing to external systems, is the use of 'Valid to check for valid
> > input
> > data in a very readable manner. However, I would convert the raw input
> > to a non-holey type after the check, using either a map or case
> > statement
> > (depending upon the compiler).
> 
> There is no need for anything so elaborate.  Just derive a holey
> enumeration type from a contiguous enumeration type. Then you can simply
> use ordinary Ada type-conversions, and the compiler will implicitly do
> the mapping for you:
> 
>     with Ada.Text_IO;
>     procedure Holey_Enum_Demo is
> 
>       type Contiguous_Type is (A, B, C, D, E);
>       -- *no* rep spec!
> 
>       type Holey_Type is new Contiguous_Type;
>       for Holey_Type use (A => 1, B => 2, C => 4, D => 8, E => 16);
> 
>       Contiguous : Contiguous_Type := A;
>       Holey      : Holey_Type      := B;
> 
>     begin
> 
>       Contiguous := Contiguous_Type (Holey);
>       -- implicitly does equivalent of 'Pos
> 
>       Holey      := Holey_Type (Contiguous);
>       -- implicitly does equivalent of 'Val
> 
>     end Holey_Enum_Demo;

This assumes Holey will always be one of A, B, C, D, E. What happens
when the underlying
I/O device returns a value of 6 for Holey?

> 
> My feeling is that "holey" enumeration types (like other Chapter 13
> features) should really only be used at the "edges" of a program,
> wherever you're immediately reading from or writing to some external
> system that is expecting a certain data format.  Contiguous enumeration
> types should be used internally everywhere else in your program, for all
> the efficiency reasons that have been ... enumerated :-) ... in this
> thread. Luckily, Ada provides this convenient way of converting between
> holey and contiguous representations.
> 
> --
> Internet.Usenet.Put_Signature
>   (Name       => "John G. Volan",
>    Employer   => "Raytheon/TI Advanced C3I Systems, San Jose, CA",
>    Work_Email => "jvolan@ti.com",
>    Home_Email => "johnvolan@sprintmail.com",
>    Slogan     => "Ada95: World's *FIRST* International-Standard OOPL",
>    Disclaimer => "My employer never defined these opinions, so using " &
>                  "them would be totally erroneous...or is that just "  &
>                  "nondeterministic behavior now? :-) ");

Re: Beware: Rep spec on an enumeration type causes code explosion

[Robert Dewar]

<<    I'll give you a good reason why getting too smart about rep clause
    implementation might be a Bad Thing. Suppose I implement an
    enumeral type with a "confirming" rep clause because I know I'm
    dealing with a real live hardware interface or message format and
    want to make it clear that the representation for this given
    enumeration is critical. I compile & run and my timing comes out a
    given way because your compiler was smart enough to detect that my
    representation was conveniently matching the positions. So far, so
    good. At a later date the hardware or message format changes to
    include some new bit patterns which create holes in the
    representation and now when I compile I get a significantly
    different implementation for the enumeration and a corresponding
    change in performance. This is a satisfactory definition of the
    technical term: "Bad Thing".

    Sometimes poor performance isn't as bad a Bad Thing as
    inconsistent performance can be.
>>

I don't buy this. A representation with holes is substantially and
fundamentally different from one that does not have holes. Your 
inconsistency problem would still arise if the original program had
not bothered with a rep clause on the grounds that it had no effect.
Surely you don't think all enumeration types should be made horribly
inefficient, just so that in case you add a rep clause with holes
your program does not slow down!

Re: Beware: Rep spec on an enumeration type causes code explosion

[Marin David Condic, 561.796.8997, M/S 731-96]

"Stanley R. Allen" <s_allen@HSO.LINK.COM> writes:
>Joe Gwinn wrote:
>
>> What has in the past worked is lists of general issues and warnings,
>> without the naming of specific vendors, even though some issues may not be
>> universal, so at least we know under which rocks to look.  One way of
>> looking at this is that the list gives the relative size, weight, and
>> power of various idioms, so users have some idea what things cost.
>
>You need something like PIWG or ACES.
>
    I think its important to note that, while it is a good idea to
    identify language features which may have implementation problems,
    that no other language definition that I know of does this now. No
    language I am aware of includes in its definition any assessment
    of the relative size/speed for a construct and I would suspect
    this would be extremely difficult to do because it would vary so
    much from one target to another.

    All languages have corner cases or difficult features which may be
    subject to inefficient or erroneous implementation. Ada does
    better than most at trying to make sure that no given feature is
    of necessity difficult to implement efficiently. Certainly things
    like the PIWG are very useful in benchmarking various features.
    I think Ada has done better than most in compiling statistics on
    performance issues for various implementations and making that
    information generally available. But it seems to me that it is
    inherently something that must be done at the implementation
    level - not at a language definition level.

    MDC

Marin David Condic, Senior Computer Engineer     Voice:     561.796.8997
Pratt & Whitney GESP, M/S 731-96, P.O.B. 109600  Fax:       561.796.4669
West Palm Beach, FL, 33410-9600                  Internet:  CONDICMA@PWFL.COM
===============================================================================
    Glendower: "I can call spirits from the vasty deep."
    Hotspur: "Why so can I, or so can any man; but will they come when
    you do call for them?"
        -- Shakespeare, "Henry IV"
===============================================================================

Re: Beware: Rep spec on an enumeration type causes code explosion

[Marin David Condic, 561.796.8997, M/S 731-96]

Tucker Taft <stt@HOUDINI.CAMB.INMET.COM> writes:
>language design principles.  Your enumeration rep clause simply reconfirmed
>the default representation, but suppose it didn't?  You would be
>stuck with the overhead you managed to eliminate by simply commenting
>out the rep clause.  Of course, the compiler could recognize various
>other specials cases, such as contiguous representation starting at
>something other than zero, or evenly distributed "holey" representation
>(e.g., even numbers only), or simply not "too" sparse, or ...
>
    I'll give you a good reason why getting too smart about rep clause
    implementation might be a Bad Thing. Suppose I implement an
    enumeral type with a "confirming" rep clause because I know I'm
    dealing with a real live hardware interface or message format and
    want to make it clear that the representation for this given
    enumeration is critical. I compile & run and my timing comes out a
    given way because your compiler was smart enough to detect that my
    representation was conveniently matching the positions. So far, so
    good. At a later date the hardware or message format changes to
    include some new bit patterns which create holes in the
    representation and now when I compile I get a significantly
    different implementation for the enumeration and a corresponding
    change in performance. This is a satisfactory definition of the
    technical term: "Bad Thing".

    Sometimes poor performance isn't as bad a Bad Thing as
    inconsistent performance can be.

    MDC

Marin David Condic, Senior Computer Engineer     Voice:     561.796.8997
Pratt & Whitney GESP, M/S 731-96, P.O.B. 109600  Fax:       561.796.4669
West Palm Beach, FL, 33410-9600                  Internet:  CONDICMA@PWFL.COM
===============================================================================
    Glendower: "I can call spirits from the vasty deep."
    Hotspur: "Why so can I, or so can any man; but will they come when
    you do call for them?"
        -- Shakespeare, "Henry IV"
===============================================================================

Re: Beware: Rep spec on an enumeration type causes code explosion

[Matthew Heaney]

In article <3490B7B1.711A@nospam.flash.net>,
Ken.Garlington@nospam.computer.org wrote:



>>       Contiguous := Contiguous_Type (Holey);
>>       -- implicitly does equivalent of 'Pos

>This assumes Holey will always be one of A, B, C, D, E. What happens
>when the underlying
>I/O device returns a value of 6 for Holey?

Of course, you must always check for validity prior to the conversion,

if Holey'Valid then
   Contiguous := Contiguous_Type (Holey);
else
   <handle error>
end if;

--------------------------------------------------------------------
Matthew Heaney
Software Development Consultant
<mailto:matthew_heaney@acm.org>
(818) 985-1271

Re: Beware: Rep spec on an enumeration type causes code explosion

[Alan E & Carmel J Brain]

John G. Volan wrote:

> There is no need for anything so elaborate.  Just derive a holey
> enumeration type from a contiguous enumeration type.

--->8--- 
> My feeling is that "holey" enumeration types (like other Chapter 13
> features) should really only be used at the "edges" of a program,
--->8---
>  Contiguous enumeration
> types should be used internally everywhere else in your program

Concur. Matches my own experience exactly. Although we didn't test to
see what the performance hit would have been if we'd have used the
rep type throughout. Any experimental data on this?

-- 
aebrain@dynamite.com.au     <> <>    How doth the little Crocodile
| Alan & Carmel Brain|      xxxxx       Improve his shining tail?
| Canberra Australia |  xxxxxHxHxxxxxx _MMMMMMMMM_MMMMMMMMM
 abrain@cs.adfa.oz.au  o OO*O^^^^O*OO o oo     oo oo     oo  
                    By pulling MAERKLIN Wagons, in 1/220 Scale

Re: Beware: Rep spec on an enumeration type causes code explosion

[Samuel Tardieu]

Matthew> If you are using a holey type inside the application, ie not
Matthew> at the interface layer only, then you are probably doing
Matthew> something wrong.  The fact that you're using your own Boolean
Matthew> type does not bode well!

This kind of code is horrible as he admits, but I don't think it is
wrong; they just consider the RAM as being an external device, thus
using a holey boolean type.

When they compare their own booleans to True_State and False_State,
the result is likely to be stored in a register only and never in RAM,
and registers are probably considered as "safe".

  Sam
-- 
Samuel Tardieu -- sam@ada.eu.org

Re: Beware: Rep spec on an enumeration type causes code explosion

[Robert Dewar]

Matthew Heaney says

<<This is a seriously wrong way to build safety-critical software.  As a
matter of fact, it's a wrong way to build *any* software.  You are quite
correct in pointing out that it is "pretty horrible."

As John Volan wisely pointed out, create holey types for use at the
EXTERNAL INTERFACE ONLY.  You should have an "interface object,"
implemented as a layered machine, to manage communication with each
external device.  The machine has three purposes: to read in the data from
the hardware, verify that the data received is valid, and then convert that
data from interface format to application format.
>>>

I strongly disagree. In fact this particular example, of Booleans that
differ by multiple bits, is one of the strong justifications in past
discussions of keeping holey enumeration types in the language. Note that
in this case it is in practice quite unusual to have loops through Boolean,
or arrays with a Boolean subscript, so typically there is ZERO overhead
in using this representation, and you get the one-bit-clobbered protection.

If you convert these boolean values to application format, you are introducing
an unnecessary lack of safety at the hardware level, namely a sensitivity to
undectable one-bit errors that does not exist with the non-standard
representation.

This is an entirely appropriate way to use this feature, and the language
was deliberately designed to facilitate this usage.

I see nothing 'pretty horrible' about this approach, and it is a commonly
used one. Brian Wichman has pointed this particular usage out on a number
of occasions and explained why it is important (indeed as I remember there
are contexts in which coding standards *require* this kind of approach,
and such standards make good sense to me!)

Robert Dewar

Re: Beware: Rep spec on an enumeration type causes code explosion

[Robert Dewar]

Alan says

<<Concur. Matches my own experience exactly. Although we didn't test to
see what the performance hit would have been if we'd have used the
rep type throughout. Any experimental data on this?
>>

The experimental data would be VERY sensitive both to the compiler 
implementation and the code used.

As long as the only operations are assignments and comparisons, the use
of holey enumeration types (let's call them HETS from now on) should
be completely without additional overhead.

Loops through HETS may or may not add significant overhead. I described
the GNAT approach which reduces the overhead to a single extra load on
each loop iteration. On the other hand, one would guess from Tuck's
repeated notes to watch out for the loop case that perhaps the Intermetrics
front end does not do this particular optimization [I really don't know
whether the optimization is worth while or not, I have no data that says
it is, this is NOT a GNAT decision that was customer driven, it is just
something that seemed reasonable to me at the time when I wrote the code :-)]

Arrays indexed by HETS may or may not take a hit depending on whether they
used the POS or representation values for indexing. Both GNAT and the
Intermetrics front ends (the only ones for which I know the story) started
by using the representation values, which is the time efficient choice. But
GNAT (and I believe Intermetrics as well) were forced to switch to the
POS choice, because legacy code, particularly Verdix code, requires this.
The use of POS values is space efficient, but can introduce a significant
time penalty.

Succ and Pred values are exceedingly likely to introduce significant
overhead, and I don't see any way around this that is general (but
see below).

Finally a case statment may involve a significant penalty because it could
involve a very sparse case.

Now: what exactly is this overhead we are worrying about. It is the effort
of converting a representation value to a POS value.

What GNAT does is generate a case statement, here is an example:

   type Enum is (A,B,C);
   for Enum use (1,5,10);

this causes the generation of a routine:

      function _rep_to_pos (A : enum; F : boolean) return integer is
      begin
         case unsigned!(A) is
            when 1 =>
               return 0;
            when 5 =>
               return 1;
            when 10 =>
               return 2;
            when others =>
               if F then
                  [program_error]
               else
                  return -1;
               end if;
         end case;
      end _rep_to_pos;

How efficient the case is depends on how sparse the case is, but in any
case the optimization considerations are those that apply in any case
to a case statement. In the case where the range is fairly compact, the
case will be a simple indexed jump which is not too bad.

A nice optimzation would be to replace _rep_to_pos by an array indexed
by the representation value in cases where the range is relatively compact
(that's on my list of things to do, but I don't know what the priority is).

I really don't know what other compilers do here! But I suspect this whole
area may be quite compiler dependent, so I suggest that you benchmark your
particular usage against the compilers you are considering using, advice
that always makes sense!

Robert Dewar
Ada Core Technologies

Re: Beware: Rep spec on an enumeration type causes code explosion

[Robert Dewar]

Sam said

<<This kind of code is horrible as he admits, but I don't think it is
wrong; they just consider the RAM as being an external device, thus
using a holey boolean type.
>>

If the horrible here refers to inefficiency, this is wrong, the use of a
derived Boolean type of this kind will have no efficiency impact on typical
code on most machines, well perhaps there could be one extra instruction in
a comparison on *some* machines.

Re: Beware: Rep spec on an enumeration type causes code explosion

[Rakesh Malhotra]

Matthew Heaney wrote:
> 
> In article <66po35$1a1$1@gte2.gte.net>, Rakesh Malhotra
> <rakesh.malhotra@safetran.com> wrote:
> 
>[snip]
> >
> >Hence type SIGNAL_TYPE is (RED, GREEN);
> >for SIGNAL_TYPE use (RED => 16#00#, GREEN => 16#03#);
> >[snip]
> >Pretty horrible eh ?
> 
> This is a seriously wrong way to build safety-critical software.  As a
> matter of fact, it's a wrong way to build *any* software.  You are quite
> correct in pointing out that it is "pretty horrible."

It may be a wrong way of building safe software but it (seems to be ?)
is not uncommon.  I know of and have worked in 3 different companies in
3 different countries who have chosen to implement their enumeration
types this way. And successfully.  1 project was in Pascal and 3 in Ada
and all did it the same way for enum types.

Just as an aside safety can be implemented on a project in many
different ways.  One of the best ways is to implement safety as high up
in the system as possible - so maybe one chooses a diverse or redundant
design.  However this tends to be expensive as one duplicates hardware.

So for cost reasons we had to implement safety at a fairly low level and
one of the areas is consideration of what would happen if an alpha
particle from the sun hit the RAM chip and corrupted your signal state
from RED to GREEN due to a 1 bit corruption.  Would you now turn your
signal GREEN ?

Obviously bit separation of enums is not the only thing we do, however
it is one of the tools in our cupboard.

--
Rakesh

Re: Beware: Rep spec on an enumeration type causes code explosion

[Joe Gwinn]

In article <EKxx9n.Ly1.0.-s@inmet.camb.inmet.com>,
stt@houdini.camb.inmet.com (Tucker Taft) wrote:

> Joe Gwinn (gwinn@res.ray.com) wrote:
> : In article <EKrsrr.LD7.0.-s@inmet.camb.inmet.com>,
> : stt@houdini.camb.inmet.com (Tucker Taft) wrote:
>
> : The key issue was that we had no way of knowing the dire consequences of
> : this innocent looking bit of standard Ada, until we had gone a fair
> : distance down that wrong road.  
> 
> If you ask anyone who knows me well, you will know that I consider
> the enumeration representation clause anything but "innocent looking" ;-).
> For what it is worth, we will soon be releasing a new front end
> that recognizes the special case of a confirming enumeration
> representation clause.

All for the good.  But, we will never know Ada as you have known her.


> [ASIDE:
> 
[snip]
> So in retrospect, I believe enumeration representation 
> clauses in Ada are a mistake.  If a user wants to name 
> particular values, they should simply use named integer
> constants, or perhaps better, named private-type constants.  They can build 
> up various maps of their own if they want to translate to/from some kind
> of "holey" representation from/to a contiguous representation.

I guess I would have to agree, because it's certainly too expensive for
realtime use.  We will invent some such solution as you suggest.


> END OF ASIDE]
> 
> : ... One wonders what other surprises lay in
> : wait.
> 
> In general, the Ada language design philosophy eschewed "innocent"
> looking features that were in fact expensive at run-time.
> However, in the specific case of enumeration representation clauses,
> this useful language design philosophy was not completely followed.
> Other cases I know of are interactions between finalization, 
> exception handling, and abort, where the combination of features
> forces some or all of these three to incur more run-time overhead
> than you might expect.
> 
> One "innocent" looking construct I once found was:
> 
>    (others => Default_Value(Segment))
> 
> used to initialize a segment of a load module to some default value.
> This called the function Default_Value once for each byte of the
> segment, and the segment was often 100K bytes or more.

Thanks for the pointers.  This is just the kind of information we need to
avoid further blunders.

Another one I knew of from before was tick-Image, which triggered
formatted conversion.  Text-IO also.  I have been forbidding the use of
formatted I/O in realtime from the 1970s, in fortran.  


Joe Gwinn

Re: Beware: Rep spec on an enumeration type causes code explosion

[Joe Gwinn]

In article <3490252D.6B550F17@ac3i.dseg.ti.com>, johnv@ac3i.dseg.ti.com wrote:

> Ken Garlington wrote:
[snip]
> My feeling is that "holey" enumeration types (like other Chapter 13
> features) should really only be used at the "edges" of a program,
> wherever you're immediately reading from or writing to some external
> system that is expecting a certain data format.  Contiguous enumeration
> types should be used internally everywhere else in your program, for all
> the efficiency reasons that have been ... enumerated :-) ... in this
> thread. Luckily, Ada provides this convenient way of converting between
> holey and contiguous representations.

I have to disagree somewhat.  We were using enumeration types as message
type IDs all over the place, not just at the edges.  For safety-critical
messages, the enumerations are not permitted to be numerically contiguous,
being required to differ in at least four bits from all other message type
integer codes.  This 4-bit requirement is intended to greatly reduce the
probability of message spoofing.  (I know this isn't by itself
sufficient.  This isn't the entire defense, only the part relevant to the
current issue.)


Joe Gwinn

Re: Beware: Rep spec on an enumeration type causes code explosion

[Ken Garlington]

Matthew Heaney wrote:
> 
> In article <3490B7B1.711A@nospam.flash.net>,
> Ken.Garlington@nospam.computer.org wrote:
> 
> >>       Contiguous := Contiguous_Type (Holey);
> >>       -- implicitly does equivalent of 'Pos
> 
> >This assumes Holey will always be one of A, B, C, D, E. What happens
> >when the underlying
> >I/O device returns a value of 6 for Holey?
> 
> Of course, you must always check for validity prior to the conversion,
> 
> if Holey'Valid then
>    Contiguous := Contiguous_Type (Holey);
> else
>    <handle error>
> end if;

which is the same as my original statement, to wit: "One of the nice
things about 'holey' representations in Ada, when used for interfacing
to external systems, is the use of 'Valid to check for valid input data
in a very readable manner. However, I would convert the raw input to a
non-holey type after the check, using either a map or case statement
(depending upon the compiler)."

A response to this statement was: "There is no need for anything so
elaborate." The corresponding code did the conversion without a
check, which prompted me to ask how validity was handled.

> --------------------------------------------------------------------
> Matthew Heaney
> Software Development Consultant
> <mailto:matthew_heaney@acm.org>
> (818) 985-1271

Re: Beware: Rep spec on an enumeration type causes code explosion

[Robert Dewar]

Joe said

<<I have to disagree somewhat.  We were using enumeration types as message
type IDs all over the place, not just at the edges.  For safety-critical
messages, the enumerations are not permitted to be numerically contiguous,
being required to differ in at least four bits from all other message type
integer codes.  This 4-bit requirement is intended to greatly reduce the
probability of message spoofing.  (I know this isn't by itself
sufficient.  This isn't the entire defense, only the part relevant to the
current issue.)
>>

As I said in previous messages, I consider this usage perfectly reasonable.
However, it is probably a good idea to consider that such non-contiguous
enumeration types should not be used in loops, array indexes, or succ and
pred.

Indeed a reasonable compromise on the language design issue (Tucker says
he would remove them completely) would have been to say that these 
operations (array indexing, looping, succ and pred) are not available
for enumeration types with enumeration representation clauses. You can
construct these effects if you like using Pos and Val, but then these
operations (with their attendant possible overhead) are explicit.

Re: Beware: Rep spec on an enumeration type causes code explosion

[Alan E & Carmel J Brain]

Rakesh Malhotra wrote:

> We work on safety critical projects.  And if we have a safety critical
> bit of code that defines and uses an enumeration then we use the rep
> clause to provide more than 1 bit separation between adjacent values in
> the enumeration.  That way if 1 bit got corrupted the value could not
> become some other legal value.

See if I understand you correctly: Thus you'd use 2#1100 and 2#0011 for
example, to avoid single-bit soft failures. Just don't choose 2#0000 and
2#1111 as many soft failures either latch high or latch low. Right?

Interesting, not seen this technique used before, but it makes sense in
some areas. And my vast ignorance is infinitesimally decreased,
thank-you.

Am I right in thinking that in the areas where such paranoia is
reasonable, the code could well look like:

SECTION_1
begin
  single statement, or at most a few
exception
  when (etc)
end SECTION_1;

SECTION_2
begin
  single statement, etc
exception
  when (etc)
end SECTION_2;

and repeat as nauseum.

Such code, where efficiency is not a major consideration :) might well
be appropriate in certain specialised areas. Just not in the general
case, even for safety-critical stuff.
-- 
aebrain@dynamite.com.au     <> <>    How doth the little Crocodile
| Alan & Carmel Brain|      xxxxx       Improve his shining tail?
| Canberra Australia |  xxxxxHxHxxxxxx _MMMMMMMMM_MMMMMMMMM
 abrain@cs.adfa.oz.au  o OO*O^^^^O*OO o oo     oo oo     oo  
                    By pulling MAERKLIN Wagons, in 1/220 Scale

Re: Beware: Rep spec on an enumeration type causes code explosion

[Robert Dewar]

Stanley said

<<I find it hard to believe that the efficiency of this
is *implictly* bad.  It seems like the use of holey enum
types for for-loop ranges, array-indexes, etc, would
always default to the use of positions; only placing
the enum value into a location should cause a table
look-up (one index redirection) for the actual value.>>

Well may be you find it hard to believe, but that does not make it false :-)

If you say a(i), where i is of the HET, then the representation of i is
what is stored, and indeed the normal expectation seems to be that the
array i will be indexed by the pos value, thus requiring a rep to pos
conversion, which is the potentially expensive one.

Of course if you say a(red) where red is an enuemration literal of the HET
then there is no additional overhead (or should not be).

Re: Beware: Rep spec on an enumeration type causes code explosion

[Robert Dewar]

Stephen says

<<I'm fairly sure that in most of the code I've written, if I supply a rep
clause for an enumeration type, I use it mainly as parameters to and
results from imported functions (Win32 comes to mind), but not as an
array index or with succ/pred. Often the results are used in case
statements. I guess this maps well to named private-type constants,
where the full type is simply an integer. However, it loses the
completeness check on case statements, which is always useful.
>>


Using case statements is reasonable, and should be reasonably efficient
if your compiler generally makes an effort to be reasonably efficient on
generting code for case statements. ertainly if the representation is
reasonbly compact (holes not too large), then the code should be efficient.

Re: Beware: Rep spec on an enumeration type causes code explosion

[Tucker Taft]

Robert Dewar (dewar@merv.cs.nyu.edu) wrote:

: ...
: I really don't know what other compilers do here! But I suspect this whole
: area may be quite compiler dependent, so I suggest that you benchmark your
: particular usage against the compilers you are considering using, advice
: that always makes sense!

This kind of statement is exactly what makes me feel the feature
should not have been in the language in the first place, or
as Robert suggested, the operations that might involve mapping
would be prohibited (though that means the enum. rep. clause has
more effect on semantics than is usually allowed).  Interestingly,
the Ravenskar real-time workshop proposed a restriction that essentially 
means "no potentially expensive holey-enum-type operations."

Of course all readers of this news thread will now be more careful in 
their use of the holey enum type feature.  However, my preference is for 
language features whose (reasonably) efficient implementation is 
essentially intuitively obvious, with all compilers 
doing essentially the same thing, and all programmers having an 
intuitive grasp of the overhead of various operations.  If you have
to start running examples through a compiler to learn how to properly
use a language feature on that particluar compiler, that is a bad 
sign...

Of course nifty optimizations are nice, but they should be incremental
improvements on something that is already acceptably fast.  If the
real-time correctness of your program begins to depend heavily on 
particular compiler-specific optimizations/transformations, then the 
"standard" language features are not what they should be.

Other examples where this principle was violated are with generics,
where some compilers macro-expand and others (partially or universally)
share, exceptions, where some compilers introduce an overhead on
entry to a handled-sequence-of-statements and others don't,
on finalization, where the declaration and cleanup overhead 
varies dramatically, on rendezvous, where some compilers have certain
special transformations and others don't, etc.

These differences can dramatically affect the "right" way to use the
language, and that means it really isn't a single language, but rather
a set of languages that happen to share syntax.  This is one case where
putting more implementation guidance into the manual might help establish
stronger norms.  One might even go so far as to include relative timing 
tests into the conformance tests, where operations are required to
take no more than some basic unit, such as the null procedure call time,
or take no more space than that given by some formula.

This is all pretty radical thinking, but for a real-time language, this
might make sense.  The "metrics" paragraphs in the Real-Time annex are
an attempt to push in this direction, where rather than saying something
felt to be "critical" had to be fast, we simply required a vendor to 
measure its performance.  The embarrassment factor would hopefully mean 
that they would spend the energy to make the given "critical" operation 
efficient.

: Robert Dewar
: Ada Core Technologies

--
-Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
Intermetrics, Inc.  Burlington, MA  USA

Re: Beware: Rep spec on an enumeration type causes code explosion

[Robert Dewar]

Joe says

<<I guess I would have to agree, because it's certainly too expensive for
realtime use.  We will invent some such solution as you suggest.
>>


No, that's wrong. If you do nothing but assignments and comparisons, there
is no overhead in the use of enumeration types with holes. If you index
compact arrays, or worse, do Succ or Pred, then you should have an
implementation model which tells you immediately that there is extra
overhead. This should not be a mystery.

Similarly, how could you possibly be surprised that x'Image(a) causes
a formatted conversion, THAT IS WHAT IMAGE IS ABOUT. There is no resaon
to forbid this. If you need the function of Image, you should use it, if
not you should not. I must say I find the comment on Image *very* odd!

Re: Beware: Rep spec on an enumeration type causes code explosion

[Joe Gwinn]

In article <dewar.882235092@merv>, dewar@merv.cs.nyu.edu (Robert Dewar) wrote:

> Joe says
> 
> <<I guess I would have to agree, because it's certainly too expensive for
> realtime use.  We will invent some such solution as you suggest.>>
> 
> No, that's wrong. If you do nothing but assignments and comparisons, there
> is no overhead in the use of enumeration types with holes. If you index
> compact arrays, or worse, do Succ or Pred, then you should have an
> implementation model which tells you immediately that there is extra
> overhead. This should not be a mystery.

I was talking about rep specs on enumeration types.

 
> Similarly, how could you possibly be surprised that x'Image(a) causes
> a formatted conversion, THAT IS WHAT IMAGE IS ABOUT. There is no resaon
> to forbid this. If you need the function of Image, you should use it, if
> not you should not. I must say I find the comment on Image *very* odd!

Umm, the point was that many programmers were not aware of the runtime
cost of tick-Image, not that tick-Image was inherently bad.  I had the
same problem with fortran programmers wanting to use encode in realtime
programs.  I recall getting an argument when I forbade the use of encode
in the late 1970s; it turned out that the core issue was that some of the
programmers didn't recall how to write a binary<->decimal conversion
routine, but were afraid to admit it.  A few pages copied from Knuth
solved the problem.  In those days, most of the embedded realtime
programmers were retread hardware engineers who learned to program by
reading the language and computer manuals.

So, the core issue comes down to having some kind of idea of what various
language features and idioms cost in memory and CPU time at runtime.  This
issue is relevant to all languages, especially complex and capable ones
such as Ada95 and C++.  Simpler langauges, such as fortran and C, seemed
to have fewer surprises.  It certainly makes sense that this should be so.


Joe Gwinn

Re: Beware: Rep spec on an enumeration type causes code explosion

[John G. Volan]

Ken Garlington wrote:

> A response to this statement was: "There is no need for anything so
> elaborate." The corresponding code did the conversion without a
> check, which prompted me to ask how validity was handled.

Sorry, let me clarify: I wasn't commenting on the need to use 'Valid, of
course that is quite necessary. What I was getting at was that you
seemed to imply that the "holey" type ought to be something other than
an enumeration type, let's say an integer type; and that the programmer
should write some elaborate function involving perhaps a case statement
to do a mapping between valid integer values and the target enumeration
type.  All I was trying to show was that Ada's built-in type conversion
facility can "automagically" supply this mapping, if you simply derive a
"holey" enumeration type from a parent "contiguous" enumeration type.

-- 
------------------------------------------------------------------------
Internet.Usenet.Put_Signature 
  (Name       => "John G. Volan",
   Employer   => "Raytheon/TI Advanced C3I Systems, San Jose, CA",
   Work_Email => "jvolan@ti.com",
   Home_Email => "johnvolan@sprintmail.com",
   Slogan     => "Ada95: World's *FIRST* International-Standard OOPL",
   Disclaimer => "My employer never defined these opinions, so using " & 
                 "them would be totally erroneous...or is that just "  &
                 "nondeterministic behavior now? :-) ");
------------------------------------------------------------------------

Re: Beware: Rep spec on an enumeration type causes code explosion

[John G. Volan]

Joe Gwinn wrote:
> 
> I have to disagree somewhat.  We were using enumeration types as message
> type IDs all over the place, not just at the edges.  For safety-critical
> messages, the enumerations are not permitted to be numerically contiguous,
> being required to differ in at least four bits from all other message type
> integer codes.  This 4-bit requirement is intended to greatly reduce the
> probability of message spoofing.  (I know this isn't by itself
> sufficient.  This isn't the entire defense, only the part relevant to the
> current issue.)

I don't see how this requirement conflicts with the idiom I sketched
before (derive a "holey" enumeration type from a parent "contiguous"
enumeration type, and rely on Ada type conversions to provide the
necessary mapping).  Your program only needs to deal with these "secure"
but "holey" message id bit patterns at its edges, where it receives and
unpacks input messages (whose provenance may be questionable) and where
it must pack up and transmit output messages (and establish their
provenance). But once you've checked your input messages against
whatever security measures you've established (including among other
things 'Valid-ating their "holey" message id's) there is hardly any
reason for your program to continue using the "holey" representation
internally. Particularly if you proceed to use message id's in a lot of
for-loops and array-indexes and other such enumerated-type operations
that threaten to "blow up" if the type is "holey". If you simply
type-convert the "holey" external versions of your message id's into 
"contiguous" internal versions, right at the point of input, then you
incur the cost of the expensive mapping just once, rather than
repeatedly throughout your program.  The nice thing about this is that
you don't have to give up on using your nice enumeration literals -- you
only have to give up the *representation*.

-- 
Internet.Usenet.Put_Signature 
  (Name       => "John G. Volan",
   Employer   => "Raytheon/TI Advanced C3I Systems, San Jose, CA",
   Work_Email => "jvolan@ti.com",
   Home_Email => "johnvolan@sprintmail.com",
   Slogan     => "Ada95: World's *FIRST* International-Standard OOPL",
   Disclaimer => "My employer never defined these opinions, so using " & 
                 "them would be totally erroneous...or is that just "  &
                 "nondeterministic behavior now? :-) ");

Re: Beware: Rep spec on an enumeration type causes code explosion

[Brian Rogoff]

On Mon, 15 Dec 1997, Tucker Taft wrote:
> <snip>
> 
> Other examples where this principle was violated are with generics,
> where some compilers macro-expand and others (partially or universally)
> share, exceptions, where some compilers introduce an overhead on

I haven't seen any descriptions of the compiler techniqes used to do 
partial sharing of generic instantiations. Any references available?

-- Brian

Re: Beware: Rep spec on an enumeration type causes code explosion

[Robert Dewar]

Joe said

<<I guess I ould have to agree, because it's certainly too expensive for
  realtime use.  We will invent some such solution as you suggest.>>

Robert replied

<<No, that's wrong. If you do nothing but assignments and comparisons, there
  is no overhead in the use of enumeration types with holes. If you index
  compact arrays, or worse, do Succ or Pred, then you should have an
  implementation model which tells you immediately that there is extra
  overhead. This should not be a mystery.>>

Joe replied

<<I was talking about rep specs on enumeration types.>>

RObert says

SO WAS I!! That's the point! First I assume you mean an enumeration
representation clause when you say "rep spec on enumeration type" (the
term rep spec, despite popular impressions to the contrary, is not
an Ada technical term!)

The whole point of my comment is that enumeration representation clauses
add ZERO overhead if the only operations are assignments and comparisons.
If your experience leads you to avoid HET's even in this case, you are
overreacting from not understanding the situation clearly.

<<Umm, the point was that many programmers were not aware of the runtime
  cost of tick-Image, not that tick-Image was inherently bad.  I had the
  same problem with fortran programmers wanting to use encode in realtime
  programs.  I recall getting an argument when I forbade the use of encode
  in the late 1970s; it turned out that the core issue was that some of the
  programmers didn't recall how to write a binary<->decimal conversion
  routine, but were afraid to admit it.  A few pages copied from Knuth
  solved the problem.  In those days, most of the embedded realtime
  programmers were retread hardware engineers who learned to program by
  reading the language and computer manuals.>>

Any programmer who does not realize that 'Image involves runtime overhead
lacks very fundamental knowledge about the computing model that underlies
the program. Yes, I understnd that retrodden hardware engineers, physicists,
etc, might conceivably have misunderstandings that are this fundamental,
or more properly, gaps in their knowledge that are this fundamental. That
is *exactly* why I emphasize the importance of having some people on a
project who are competent programmers!

Re: Beware: Rep spec on an enumeration type causes code explosion

[Joe Gwinn]

In article <3496D55F.1312429E@ac3i.dseg.ti.com>, johnv@ac3i.dseg.ti.com wrote:

> Joe Gwinn wrote:
> > 
> > I have to disagree somewhat.  We were using enumeration types as message
> > type IDs all over the place, not just at the edges.  For safety-critical
> > messages, the enumerations are not permitted to be numerically contiguous,
> > being required to differ in at least four bits from all other message type
> > integer codes.  This 4-bit requirement is intended to greatly reduce the
> > probability of message spoofing.  (I know this isn't by itself
> > sufficient.  This isn't the entire defense, only the part relevant to the
> > current issue.)
> 
> I don't see how this requirement conflicts with the idiom I sketched
> before (derive a "holey" enumeration type from a parent "contiguous"
> enumeration type, and rely on Ada type conversions to provide the
> necessary mapping).  Your program only needs to deal with these "secure"
> but "holey" message id bit patterns at its edges, where it receives and
> unpacks input messages (whose provenance may be questionable) and where
> it must pack up and transmit output messages (and establish their
> provenance). But once you've checked your input messages against
> whatever security measures you've established (including among other
> things 'Valid-ating their "holey" message id's) there is hardly any
> reason for your program to continue using the "holey" representation
> internally. Particularly if you proceed to use message id's in a lot of
> for-loops and array-indexes and other such enumerated-type operations
> that threaten to "blow up" if the type is "holey". If you simply
> type-convert the "holey" external versions of your message id's into 
> "contiguous" internal versions, right at the point of input, then you
> incur the cost of the expensive mapping just once, rather than
> repeatedly throughout your program.  The nice thing about this is that
> you don't have to give up on using your nice enumeration literals -- you
> only have to give up the *representation*.

Well, it depends on where one chooses to put the boundaries between safe
and unsafe.  Because we choose not to attempt safety validation of VxWorks
and the various COTS communications systems, an impossible task, every
VxWorks task stands alone, so safety critical messages between tasks must
have message type IDs differing in at least 4 bits.  I think this meets
the definition of holey; in fact, it's more hole than anything else, by
design.  

So, can one convert to a compact enumeration within those tasks, defining
the "edges" to be the task boundaries?  Not really, both by common sense
and by a specific contractual safety requirement.  Enumeration types
within the task are still implemented using physical memory, there being
no other way, and thus have no more divine protection from bitflips and
other forms of spoofing then they do outside the tasks.  

There is no physical task boundary; tasks are just an illusion created by
VxWorks for the benefit of programmers.  So, the four-bit rule must be
universal.

Note that in VxWorks (as in most embedded realtime operating systems),
there is no memory protection barrier separating tasks from one another,
and there never has been, even in the most safety-critical of systems. 
Safety is a product of overall system architecture and design, and cannot
be permitted to depend on any one feature or component.

Because of the need to talk to entities written in languages other than
Ada95, or in Ada95 but compiled and linked at a different time perhaps
using a different compiler and compiler version, the specific enumeration
mapping must be explicitly nailed down, with no discretion left to any of
the various compilers.  This was the reason for the rep specs.  Now that
the rep specs are gone, some other equivalent method will be needed.  The
holes are absolutely required and thus will remain.  Something else will
be forced to give.


Joe Gwinn

Re: Beware: Rep spec on an enumeration type causes code explosion

[Ken Garlington]

John G. Volan wrote:
> 
> Ken Garlington wrote:
> 
> > A response to this statement was: "There is no need for anything so
> > elaborate." The corresponding code did the conversion without a
> > check, which prompted me to ask how validity was handled.
> 
> Sorry, let me clarify: I wasn't commenting on the need to use 'Valid, of
> course that is quite necessary. What I was getting at was that you
> seemed to imply that the "holey" type ought to be something other than
> an enumeration type, let's say an integer type;

No, I was assuming a conversion between a holey to non-holey enumeration
type;

> and that the programmer
> should write some elaborate function involving perhaps a case statement
> to do a mapping between valid integer values and the target enumeration
> type.  

Maybe (although it shouldn't be that elaborate). I have seen cases where
using a case statement is slightly more efficient than using the
built-in
type conversion (as well as the opposite). Given the expected use to
convert
I/O, small optimizations in this area can be important. Of course, the
choice is compiler dependent.

> All I was trying to show was that Ada's built-in type conversion
> facility can "automagically" supply this mapping, if you simply derive a
> "holey" enumeration type from a parent "contiguous" enumeration type.
> 
> --
> ------------------------------------------------------------------------
> Internet.Usenet.Put_Signature
>   (Name       => "John G. Volan",
>    Employer   => "Raytheon/TI Advanced C3I Systems, San Jose, CA",
>    Work_Email => "jvolan@ti.com",
>    Home_Email => "johnvolan@sprintmail.com",
>    Slogan     => "Ada95: World's *FIRST* International-Standard OOPL",
>    Disclaimer => "My employer never defined these opinions, so using " &
>                  "them would be totally erroneous...or is that just "  &
>                  "nondeterministic behavior now? :-) ");
> ------------------------------------------------------------------------

Re: Beware: Rep spec on an enumeration type causes code explosion

[Ken Garlington]

John G. Volan wrote:
> 
> Joe Gwinn wrote:
> >
> > I have to disagree somewhat.  We were using enumeration types as message
> > type IDs all over the place, not just at the edges.  For safety-critical
> > messages, the enumerations are not permitted to be numerically contiguous,
> > being required to differ in at least four bits from all other message type
> > integer codes.  This 4-bit requirement is intended to greatly reduce the
> > probability of message spoofing.  (I know this isn't by itself
> > sufficient.  This isn't the entire defense, only the part relevant to the
> > current issue.)
> 
> I don't see how this requirement conflicts with the idiom I sketched
> before (derive a "holey" enumeration type from a parent "contiguous"
> enumeration type, and rely on Ada type conversions to provide the
> necessary mapping).  Your program only needs to deal with these "secure"
> but "holey" message id bit patterns at its edges, where it receives and
> unpacks input messages (whose provenance may be questionable) and where
> it must pack up and transmit output messages (and establish their
> provenance). 

In Wichmann's paper, the use of "holey" booleans was to catch local
memory
faults, so this technique is not necessarily limited to "edges".

Of course, is it worth protecting this use of local memory, but not all
the
others? I'm skeptical...

Re: Beware: Rep spec on an enumeration type causes code explosion

[John G. Volan]

Joe Gwinn wrote:
> 
> In article <3496D55F.1312429E@ac3i.dseg.ti.com>, johnv@ac3i.dseg.ti.com wrote:
> 
> > I don't see how this requirement conflicts with the idiom I sketched
> > before (derive a "holey" enumeration type from a parent "contiguous"
> > enumeration type, and rely on Ada type conversions to provide the
> > necessary mapping).  Your program only needs to deal with these "secure"
> > but "holey" message id bit patterns at its edges, where it receives and
> > unpacks input messages (whose provenance may be questionable) and where
> > it must pack up and transmit output messages (and establish their
> > provenance)...[snip]
> 
> Well, it depends on where one chooses to put the boundaries between safe
> and unsafe.  Because we choose not to attempt safety validation of VxWorks
> and the various COTS communications systems, an impossible task, every
> VxWorks task stands alone, so safety critical messages between tasks must
> have message type IDs differing in at least 4 bits.  I think this meets
> the definition of holey; in fact, it's more hole than anything else, by
> design.
> 
> So, can one convert to a compact enumeration within those tasks, defining
> the "edges" to be the task boundaries?  

Sure, why not?

> Not really, both by common sense

"Common sense"?  If common sense has anything to do with this, I'm
afraid you aren't very convincing in showing the connection...

> and by a specific contractual safety requirement.  Enumeration types
> within the task are still implemented using physical memory, there being
> no other way, and thus have no more divine protection from bitflips and
> other forms of spoofing then they do outside the tasks.

There must be some limit to this paranoia, else we degenerate into
infinite regress!  I can understand being paranoid about flipped bits in
messages coming in over a network connection, where the communication
line may be held suspect, but to worry about a bit flipping in a
variable in memory while it is being used within a single task on a
single host processor is surely beyond the pale.  One may as well outlaw
the use of standard 2's-complement integers and floats for representing
critical physical quantities, on the grounds that a single bit flip
could suddenly double a quantity, or worse yet, change its sign! We
would also have to preclude the use of standard CPU models with
instruction sets that aren't sufficiently "holey", on the grounds that a
single bit flip could suddently turn, say, a LOAD instruction into a
STORE instruction!

Even putting that aside, let's asume that there is some compelling
reason to keep using a "holey" representation even within a single task
(and let's also assume that your comments are not simply a troll). Then,
as you say:

[snip, fast-forward to the end]

> The
> holes are absolutely required and thus will remain.  Something else will
> be forced to give.

... Of course: You must give up some efficiency.  If one cannot trust an
enumerated value to remain intact from one executable statement to the
next, then one is forced to constantly check and re-check it to make
sure it hasn't gone bad.  Each iteration through a for-loop, each index
into an array, and so forth, must pay the cost of mapping the
representation to the position number (raising Constraint_Error if the
represented value is not 'Valid). In short, you incur the "blow up"
which you previously complained about.  You cannot have it both ways:
You can get speed or you can get safety, but not both at once.

At any rate, what does this have to say about the suitability of an Ada
enumeration type as an abstraction for a "holey" set of bit-patterns? 
If you choose some other data abstraction to implement the bit-patterns,
you will get the same sort of performance, but you will have to do some
programming work to implement the very same mapping operations that the
Ada compiler already provides for a holey enumeration type. Seems like
wrong-headedness leading to wasted effort...

> Because of the need to talk to entities written in languages other than
> Ada95, or in Ada95 but compiled and linked at a different time perhaps
> using a different compiler and compiler version, the specific enumeration
> mapping must be explicitly nailed down, with no discretion left to any of
> the various compilers.  This was the reason for the rep specs.  Now that
> the rep specs are gone, some other equivalent method will be needed.  

Huh? What do you mean?  Last time I checked, rep specs were very much
alive and well in Ada95!  Or do you simply mean that your project has
chosen to give up on using rep specs for some incomprehensible reason
... ? :-)

-- 
Internet.Usenet.Put_Signature 
  (Name       => "John G. Volan",
   Employer   => "Raytheon/TI Advanced C3I Systems, San Jose, CA",
   Work_Email => "jvolan@ti.com",
   Home_Email => "johnvolan@sprintmail.com",
   Slogan     => "Ada95: World's *FIRST* International-Standard OOPL",
   Disclaimer => "My employer never defined these opinions, so using " & 
                 "them would be totally erroneous...or is that just "  &
                 "nondeterministic behavior now? :-) ");

Re: Beware: Rep spec on an enumeration type causes code explosion

[Joe Gwinn]

In article <34989D6B.402AE2A7@ac3i.dseg.ti.com>, johnv@ac3i.dseg.ti.com wrote:

> Joe Gwinn wrote:
> > 
> > In article <3496D55F.1312429E@ac3i.dseg.ti.com>,
johnv@ac3i.dseg.ti.com wrote:
> > 
> > > I don't see how this requirement conflicts with the idiom I sketched
> > > before (derive a "holey" enumeration type from a parent "contiguous"
> > > enumeration type, and rely on Ada type conversions to provide the
> > > necessary mapping).  Your program only needs to deal with these "secure"
> > > but "holey" message id bit patterns at its edges, where it receives and
> > > unpacks input messages (whose provenance may be questionable) and where
> > > it must pack up and transmit output messages (and establish their
> > > provenance)...[snip]
> > 
> > Well, it depends on where one chooses to put the boundaries between safe
> > and unsafe.  Because we choose not to attempt safety validation of VxWorks
> > and the various COTS communications systems, an impossible task, every
> > VxWorks task stands alone, so safety critical messages between tasks must
> > have message type IDs differing in at least 4 bits.  I think this meets
> > the definition of holey; in fact, it's more hole than anything else, by
> > design.
> > 
> > So, can one convert to a compact enumeration within those tasks, defining
> > the "edges" to be the task boundaries?  
> 
> Sure, why not?
> 
> > Not really, both by common sense
> 
> "Common sense"?  If common sense has anything to do with this, I'm
> afraid you aren't very convincing in showing the connection...

The common sense is that nothing has divine protection, as discussed later
in the original posting.


> > and by a specific contractual safety requirement.  Enumeration types
> > within the task are still implemented using physical memory, there being
> > no other way, and thus have no more divine protection from bitflips and
> > other forms of spoofing then they do outside the tasks.
> 
> There must be some limit to this paranoia, else we degenerate into
> infinite regress!  I can understand being paranoid about flipped bits in
> messages coming in over a network connection, where the communication
> line may be held suspect, but to worry about a bit flipping in a
> variable in memory while it is being used within a single task on a
> single host processor is surely beyond the pale.  

The greatest fear is that some other bit of software will scribble on our
precious data structures.  This applies across the board, not just to
messages.  And, in some applications, bitflips are physically possible, a
consequence of using semiconductor RAM, which can have bits flipped by
stray cosmic rays and alpha particles from the ceramic used to make the IC
package.  In satellites, there is plenty of natural radiation, so bitflips
(and worse) are actually fairly common.


> ... One may as well outlaw
> the use of standard 2's-complement integers and floats for representing
> critical physical quantities, on the grounds that a single bit flip
> could suddenly double a quantity, or worse yet, change its sign! 

I hate to tell you this, but in some applications we do exactly this, as a
guard against (transient) errors in the CPU's arithmetic logic.  No
hardware is perfect.  Actually, we do all arithmetic twice in the same CPU
but by somewhat different mathematical paths, and compare the results. 
Paranoia is proportional to the product of risk and consequence.


> ... We
> would also have to preclude the use of standard CPU models with
> instruction sets that aren't sufficiently "holey", on the grounds that a
> single bit flip could suddently turn, say, a LOAD instruction into a
> STORE instruction!

We haven't gone quite that far; the parallel paths and compare is
sufficient, and standard hardware is so much cheaper than special
hardwware that we would instead use multiple CPUs in lockstep and compare
their outputs.  This is called triple modular redundancy, and is widely
used in fly-by-wire systems, for instance.

It all depends on what threats one is countering.


> Even putting that aside, let's asume that there is some compelling
> reason to keep using a "holey" representation even within a single task
> (and let's also assume that your comments are not simply a troll). Then,
> as you say:
> 
> [snip, fast-forward to the end]
> 
> > The
> > holes are absolutely required and thus will remain.  Something else will
> > be forced to give.
> 
> ... Of course: You must give up some efficiency.  If one cannot trust an
> enumerated value to remain intact from one executable statement to the
> next, then one is forced to constantly check and re-check it to make
> sure it hasn't gone bad.  Each iteration through a for-loop, each index
> into an array, and so forth, must pay the cost of mapping the
> representation to the position number (raising Constraint_Error if the
> represented value is not 'Valid). In short, you incur the "blow up"
> which you previously complained about.  You cannot have it both ways:
> You can get speed or you can get safety, but not both at once.

Yes, it's more costly to support a sparse enumeration mapping, but I don't
think that it needs to be a factor of 100 to 1000 more expensive.  At
worst, one could use a standard-issue hash table to hold the mapping
pairs; this approach has constant overhead regardless of the nature of the
holes, and could be less than 10 times more expensive.

Also, we have drifted off the point a bit.  The reason for the rep specs
on an enumeration type was to permit interchange of data between systems
not all in the same language or even compiler; the bits must be pinned
down or every time somebody gets a new version, the system will collapse. 
The presence or absence of holes in the enumeration, though important, is
an independent issue.

 
> At any rate, what does this have to say about the suitability of an Ada
> enumeration type as an abstraction for a "holey" set of bit-patterns? 
> If you choose some other data abstraction to implement the bit-patterns,
> you will get the same sort of performance, but you will have to do some
> programming work to implement the very same mapping operations that the
> Ada compiler already provides for a holey enumeration type. Seems like
> wrong-headedness leading to wasted effort...

I don't agree.  Users have an intrinsic advantage over compiler writers in
that users know just what they are trying to do, and so can build a
mechanism that answers that need and that need alone, while compiler
writers are forced to cover entire spaces of possible needs.  

Specifically, we can implement the hash table ourselves, or even choose to
spend lots of memory on a large but mostly empty lookup table.  Compiler
writers cannot use such limited solutions because they are pulled too many
ways by too many users.

For the record, I once ran an 6-person compiler group whose main mission
was Fortran 77 and K&R C for some computers we then made, so I've been
poked with both ends of this stick.  

 
> > Because of the need to talk to entities written in languages other than
> > Ada95, or in Ada95 but compiled and linked at a different time perhaps
> > using a different compiler and compiler version, the specific enumeration
> > mapping must be explicitly nailed down, with no discretion left to any of
> > the various compilers.  This was the reason for the rep specs.  Now that
> > the rep specs are gone, some other equivalent method will be needed.  
> 
> Huh? What do you mean?  Last time I checked, rep specs were very much
> alive and well in Ada95!  Or do you simply mean that your project has
> chosen to give up on using rep specs for some incomprehensible reason
> ... ? :-)

Whoa!  What we have given up on are rep specs on enumeration types, not
rep specs in general.   

And, we find a 100:1 to 1000:1 performance hit to be simply intolerable,
not just incomprehensible.  It's all too comprehensible; projects have
died for less. 

Joe Gwinn