[Vm-dev] (Rescued) Re: Copy Down to avoid Looking Up
nabble.42 at klix.ch
nabble.42 at klix.ch
Fri Mar 19 11:08:49 UTC 2021
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
More information about the Vm-dev
mailing list