Re: class wide iterable (and indexable)

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

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