From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,ca9eef4d5e2078ea X-Google-Attributes: gid103376,public From: dewar@merv.cs.nyu.edu (Robert Dewar) Subject: Re: Beware: Rep spec on an enumeration type causes code explosion Date: 1997/12/12 Message-ID: #1/1 X-Deja-AN: 297609751 References: <348F3DFC.10DB@nospam.flash.net> <3490252D.6B550F17@ac3i.dseg.ti.com> <34921C4D.4B0D@dynamite.com.au> X-Complaints-To: usenet@news.nyu.edu X-Trace: news.nyu.edu 881950145 29280 (None) 128.122.140.58 Organization: New York University Newsgroups: comp.lang.ada Date: 1997-12-12T00:00:00+00:00 List-Id: Alan says <> 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