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

[dewar@merv.cs.nyu.edu (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