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=2.1 required=5.0 tests=BAYES_00,INVALID_MSGID, MSGID_RANDY,PP_MIME_FAKE_ASCII_TEXT autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII X-Google-Thread: 103376,1ea19776e3073a96 X-Google-Attributes: gid103376,public From: Robert Dewar Subject: Re: C/C++ programmer giving Ada95 a chance -- writing an emulator. Date: 2000/04/02 Message-ID: <8c80ms$jnk$1@nnrp1.deja.com>#1/1 X-Deja-AN: 605698465 References: <38e148e2.5089627@news.shreve.net> <38E2E979.3D1A95DE@research.canon.com.au> <38e7e951.8384503@news.shreve.net> <8c7j8c$plf$1@wanadoo.fr> X-Http-Proxy: 1.0 x21.deja.com:80 (Squid/1.1.22) for client 205.232.38.14 Organization: Deja.com - Before you buy. X-Article-Creation-Date: Sun Apr 02 17:40:46 2000 GMT X-MyDeja-Info: XMYDJUIDrobert_dewar Newsgroups: comp.lang.ada X-Http-User-Agent: Mozilla/4.61 [en] (OS/2; I) Date: 2000-04-02T00:00:00+00:00 List-Id: In article <8c7j8c$plf$1@wanadoo.fr>, "Jean-Pierre Rosen" wrote: > > jross a �crit dans le message : > 38e7e951.8384503@news.shreve.net... > > > > I was making the assumption that a case statement would > > compile to evaluate every case until finding a match -- > > hence, not efficient. > > Several years ago, I am sure this would have been the case Completely wrong, the switch or case statement from the earliest days (it is after all in Algol-60, Fortran, C etc in some form or other) has always been associated with the idea of a jump table, and all computers have always had instruction sets suitable for this kind of generation. It is always surprising when people make these kind of assumptions -- why not look at the generated code to find out what kind of machine language is being generated. It is not unreasonable to write high level code without worrying too much about low level code efficiency. It is better to know enough about code generation to have a reasonable idea of how the compiler generates code. The worst thing is to worry about what kind of machine language is being generated and not know the answer, this can lead you very much astray. > (no pun > > intended). However, now that I think about it, a compiler these days > > should be intelligent enough to create an indexed jump table where all > > (or most all) consecutive values are provided and create efficient > > execution code. Generally most compilers do indeed do far more than just generate a simple jump table. If the jump table is sparse, then it is reasonable to break it up into ranges, with specific tests on the ranges. These tests are often arranged into a binary search tree to minimize run time tests. GCC has done this kind of optimization for a long time. If the set of values is really sparse, a hash table is a reasonable choice, especially given that a perfect hash function can be computed at compile time. BCPL compilers had this optimization quite early (in the 60's I would guess). > As a point of information, when I was working on Ada/Ed (some > years ago now), I had in my office a PhD thesis on "efficient > code generation techniques for case statements". There was > literally a dozen of techniques possible, depending on how the > values were split over the whole range... Indeed there are many techniques and it is quite reasonable to study them formally. I saw a much more recent thesis on the same topic (the consideration is made more difficult by paging and icache considerations on modern processors). > Moral: NEVER make assumptions about the way code is generated, > unless you REALLY know what's happening in the compiler (which > in practice means, you are part of the compiler team!) That's a bit extreme, but I know what you mean. In particular the whole Realia COBOL team knew the compiler very well and what it generated, and that was one of the reasons this compiler is so fast (it compiles high quality run-time code for COBOL at a very high speed -- well over 100,000 lines a minute on a 25MHz 386, I have no idea how it does on a gigahertz Pentium, should be several million lines a minute :-) By the way, the -gnatG option in GNAT is quite useful for finding out what code the compiler is generating at a macro level. It is also a very useful verification tool (see also the asociated -gnatD option). Robert Dewar Ada Core Technologies Sent via Deja.com http://www.deja.com/ Before you buy.