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

[nabble.42 at klix.ch]

Hi Ken,

... see below ...
On 2021-03-18 16:28, ken.dickey at whidbey.com wrote:
> 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.
I suspected that you know better than me.
I just explained the train of thought I follow
when I muse about that problem. It always
ends with: "Now you reinvented the wheel
aka. VFTs"
> 
> 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.
I have a hunch that something like
(in pseudo-smalltalk):

receiver class
	caseOf: {
		[ Class1 ] -> [<send directly>]
		[ Class2 ] -> [ ... ] }
	otherwise: [
		<just do the normal thing > ]

will translate to byte code that executes quickly on an interpreter an 
can easily be
(translated|jitted) to fast machine code.
AFIR branch prediction for the resulting
chain of jumps was much better than for
indirect calls. I don't know if this
is still the case with modern processors.
Maybe Elliot can enlighten me here.

I also imagine that this can be done
easily with Sista.

> 
> 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).
> 
How big do these tables get?

> 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
Again just my sundry thoughts.


Best Regards,

Gerald