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.9 required=5.0 tests=BAYES_00 autolearn=unavailable autolearn_force=no version=3.4.4 Path: eternal-september.org!reader01.eternal-september.org!feeder.eternal-september.org!aioe.org!.POSTED!not-for-mail From: "Dmitry A. Kazakov" Newsgroups: comp.lang.ada Subject: Re: class wide iterable (and indexable) Date: Sun, 6 Jan 2019 10:43:40 +0100 Organization: Aioe.org NNTP Server Message-ID: References: <2a6929c5-72fa-4d84-953a-44ea4597ab38@googlegroups.com> <69ee6a46-237c-49d7-b17a-db7a549ba00a@googlegroups.com> NNTP-Posting-Host: i065DRYuysvTI4qVnaNkyg.user.gioia.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Complaints-To: abuse@aioe.org User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.4.0 Content-Language: en-US X-Notice: Filtered by postfilter v. 0.8.3 Xref: reader01.eternal-september.org comp.lang.ada:55210 Date: 2019-01-06T10:43:40+01:00 List-Id: On 2019-01-05 21:46, Shark8 wrote: > On Saturday, January 5, 2019 at 2:21:55 AM UTC-7, Randy Brukardt wrote: >> "Dmitry A. Kazakov" wrote in message >> ... >>> In real programs dispatch is rare, thus there is no overhead. >> >> This is probably true, but then interfaces are even more useless (they >> provide nothing that could possibly be of value other than dispatch!). >> >>> I don't know which overhead Randy meant, though. Maybe, space overhead? >>> That is not nearly close to what generics produce in GNAT... >> >> Dispatching is very expensive for interfaces, in that some form of search is >> needed. (Note: I have no idea how GNAT implements them exactly.) It might be >> possible to do some sort of link-time assignment of interface identifiers >> and link-time tag construction to avoid some of that cost (at the cost of a >> lot of space), but that would be such a complex and unusual project >> (conventional linkers don't support anything like that) that I've always >> considered it impraactical. > > There are some optimizations that can be done, these three papers show some interesting methods for resolving/optimizing dynamic-calls: > > http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.53.1099&rep=rep1&type=pdf > http://web.cs.ucla.edu/~palsberg/tba/papers/dean-grove-chambers-ecoop95.pdf > https://scholarworks.umass.edu/cgi/viewcontent.cgi?article=1008&context=cs_faculty_pubs > > IIUC, the techniques also work in the presence of full-multi dispatch. I skimmed these papers briefly and have an impression that they solve problems resolved in Ada 95 long ago. The problem Randy meant is different. You have a type tag and a primitive operation's ID. Out of these two you must get the operation body entry point (dispatch). With single inheritance we can use the tag as a pointer to the array indexed by the ID (the dispatch table). The ID can be made dense index because all primitive operations are known and added sequentially. You simply increment it for each newly declared primitive operation. With multiple inheritance this does not work anymore for the interfaces. When an interface type is declared, you don't know which types will use it and thus you cannot assign the IDs to its operations so that they will land into unique slots in all dispatching tables of all future descendants. Thus by interfaces you have to use (Tag, ID) in some sort of hash table or binary search or whatever, which is less efficient than simple indexing. A linker could "densify" the IDs later when all dispatching tables are settled, but that would also require the dynamic loader to be able to do this as well in the case of relocated libraries. Since both lingered in the Stone Age under Windows and Linux, that will not happen. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de