[Vm-dev] (Rescued) Re: Copy Down to avoid Looking Up

[ken.dickey at whidbey.com]

HI Gerald,

Thanks for the feedback.

I am aware of Virtual Function Tables, Sparse Array index compression, 
lots of strategies for Dynamic Dispatch, many I have used to implement 
various object systems.

One can arrange the hash/ID of selectors, classes, and method tables.

I am looking for something which is space compact, simple to explain, 
runtime efficient, supports dynamic updates, and "fails softly" (an 
"imperfect hash" still works in a Dictionary).  Also, deals with 
polymorphism and super and does not require an expensive #isSubclassOf: 
test.

My thought with "Copy Down" is that while loading a bunch of code, one 
can build simple method dictionaries, then apply a #deepRehash after the 
load.  This could be done to affected method dictionaries each time a 
method is accepted during development as UI's (i.e. users) are slow.

The #deepRehash for each method dictionary could use simple trials to 
generate a compact table/array and set the hash for a method Dictionary 
so that (<selector> hash) <logical-op> (<mtable> hash>) finds the 
<selector>'s method without collisions.

The #deepRehash only requires local knowledge (all used selectors are 
known), not a global analysis to renumber classes or selectors.

Perfect hash would be something competitive, speed wise, with PICs but 
does not require cache management or inline code changes.  With lookup 
in only one table/dict one does not need to traverse the class hierarchy 
on a miss, because lookup never misses (DNU in every table which is 
answer on not found -- separate lookup if invoker wants nil instead).

A bit of work to craft hashfun creation, but seems worthwhile.  And an 
interesting problem to work on. :)

The idea seems simple enough that I suspect someone has looked at this 
strategy.

If this is a really bad idea, I don't have to spend any more thing 
thinking about it or worse, actually doing something.  ;^)

Thanks again,
-KenD


On 2021-03-18 07:25, nabble.42 at klix.ch wrote:
> Hi Ken,
> 
> I am by no means a VM expert, but this idea can
> be enhanced further:
> 
> Let's generate consecutive
> numbers for all the symbols used as message selectors then this
> "perfect hash" degenerates
> to an array with pointers to the compiled
> method. Let's also ignore
> -- for the sake of simplicity --
> symbols that are garbage collected;
> the holes occurring can simply be filled
> by some sort "free-list-algorithm.
> 
> Now you have something the C++ programmer knows
> really well: A virtual function table.
> 
> I have no clue whether those VFTs will help.
> 
> 
> Just my 0.01€.
> 
> 
> Best Regards,
> 
> Gerald