Re: there is a subtle problem doing: mySlot := obj getSlot(slotname)

On 2011-11-08, at 11:39 AM, Kevin Edwards wrote:

> On 11/8/2011 8:11 AM, Jeremy Tregunna wrote:
> 
>> On 2011-11-08, at 7:41 AM, Mildred Ki'Lya wrote:
>>> If this isn't mentioned somewhere, it should be. That said, perhaps it's time we figured out a long term solution to this problem which doesn't affect performance quite as much as my Slot object idea did (impacted the runtime by approximately 35% of additional overhead).
>>> 
>>> That's not an easy solution ... For a long time (before I knew about Self and Io), i tried to design a language that had methods as first-class objects. I never really succeeded.
>> 
>> Believe me, I know. Before I had the Slot idea, it was Jan-Paul Bultmann being super annoyed with this problem that it finally became more than a minor annoyance for me (and I've written a plethora of Io code since 2003, perhaps I just got used to it). Which is why the Slot object/meta idea came about. We talked for about 2 days figuring out solutions, and this is the one that we agreed was workable.
> 
> Hey, I remember this discussion!... or maybe one like it a long while ago.  It's neat that you actually implemented it!  Did Slot localize get, set, del, etc., too?  This could entail big changes.

I forgot about it until you just brought it up. Ahhh memories. :)

> I'm curious how you implemented it.  Did you put an indirection bit in PHashRecord?  You could probably twiddle some low bits of 'v' if you didn't want to waste space in exchange for a little extra time on each lookup.
> 
> Ah, from more recent messages, it looks like you implemented it in Ruby which might explain the inefficiency.  Maybe the JIT you're working on can optimize it at some point.

TL;DL Detail algorithms and performance metrics of Acute's bootstrap, and how I implemented metas.

Right, it's implemented in Ruby in the Acute throw-away bootstrap interpreter (what I'm now calling a prototype, since I have to reimplement it given a change in other priorities). But basically how it's implemented is simply like this:

In Acute, I have objects which are effectively nothing more than a hash table. This makes lookup effectively a bit less efficient because it looks up in the slot table using a sort of "default fallback" lookup mechanism, and if it finds a lookup slot, calls it. Let's just assume there's no customized lookup behaviour. This returns a "Slot" object (a meta). This object contains a data pointer, which points at the object, and is itself, a first class object. There is a potential dependency problem here if you aren't careful.

In any event, lookup returns that meta. Perform invokes lookup like it does in Io, and perform looks very much the same. Has a bunch of contexts passed to it, message, etc. Instead of checking the activatable bit on the object though, we check it on the slot that was returned from lookup. If the activatable bit is set, we lookup an activate slot on it, if we have one, and call it. Otherwise, we return the data in the meta if we found it, or lookup forward, call it and repeat our process for each proto. Very likely not the most efficient algorithm, but it was the one that immediately came to mind, so it's what I used. We didn't need this in the ruby bootstrap, but I chose to implement it because it would let us build a real complex system (Io itself) using metas and see how it impacts the w
 hole system.

As such, one lookup on an activatable object is guaranteed to perform at least 4 lookups, versus 2 in Io, in the average case however, it'll generate 9 lookups. As such, I fully expected Acute's performance to be at best half of what Io does.

What I mean by on average it'll take 9 lookups, this assumes a very shallow lookup tree. For instance:

A := Object clone do(
  foo := method(...)
)
A foo

In this case, I'm not counting the lookups that would need to be done to get the receiver of a message, I'm assuming you have it by that point. So let's break it down:

1. The "foo" message is passed to perform, it finds its name. Calls lookup passing it that name.
2. Lookup looks for a lookup method on the receiver, if it finds one, it calls it.
3. Lookup finds the "foo" slot on A, and returns its meta
4. Back in perform, we now check if the meta is activatable, and if it is, we look for an "activate" slot in the receiver
5. If we don't find it, we look for its protos hierarchy, and iterate it (internally no message sends to iterate)
6. Since "foo" is a method which directly descends from Block, we ask it's evaluator to evaluate our message, repeating steps 1 through 4, then continuing onto step 7
7. We find the activate slot, have its meta, and now check if it's activatable, and call it.

Now this assumes non-complex hierarchies, and protos lists that are shallow (1 item). The more complex your hierarchies get, the longer message lookup will take. This holds true for Io as well, but it's not as bad.

Performance characteristics for looping 10 million times, yielded 2.15 million sends per second on Steve's C Io implementation, and 512 thousand sends per second on my Ruby Io implementation. I expected it to be slower given the extra message sending overhead.

I ultimately opted to remove them, and figure out how much we'd boost lookup performance, and found a 25% improvement in performance of the evaluator.

Regards,

Jeremy Tregunna