Arc Forumnew | comments | leaders | submitlogin
2 points by stefano 5981 days ago | link | parent

> Still, I wonder - how does CLOS implement this?

I think that for every method with the same name an hash table indexed on the types of the argument is created, and when the method is called, a lookup is made on the table.

> Hmm. I've been trying to grok through dynamic dispatching speedup techniques - the Sun Self papers are pretty good, Sun's index doesn't have the papers themselves but you can ask Google for them.

I've found those papers in the past (a few weeks ago), but I've never found the will to read them, they are written for people already in the compilers' world and I'm still learning the basics about compilers. BTW, a good type inferencer + a good function inliner could solve the problem, but I wouldn't know even where to start to implement them :(.



2 points by almkglor 5980 days ago | link

The gist of the papers are mostly this:

Use a "Polymorphic Inline Cache" (PIC). Basically if a piece of code could call several different methods, we figure out which one it is, then we create a copy of the calling function which does the type checking at the top and specialize all method calls to that type:

  (defm method ((t n my-type))
    (my-type::method n))
  (defm method ((t n your-type))
    (your-type::method n))
  (defm other-meth ((t n my-type))
    (my-type::other-meth n))
  (defm other-meth ((t n your-type))
    (your-type::other-meth n))

  (def general-function (n)
    (+ (method n) (other-meth n)))

  (general-function (your-type-creator 42))
  ===>
    (do
      (def general-function (n)
        (if (isa n 'your-type)
          (+ (your-type::method n) (your-type::other-meth n))
          (+ (method n) (other-meth n))))
      (general-function (your-type-creator 42)))
Everything else in the papers that go beyond the PIC is mostly about debugging and making the PIC lazy.

Edit:

Okay, I've been thinking. Basically the call* table is about specializing on 'apply, and we might think of 'defcall as:

  (defcall type (val . params)
    (code))
  ==>
  (defm apply ((t val type) . params)
    (code))
Could we possibly generalize this at the language level and make a PIC, say in arc2c/SNAP?

-----

1 point by stefano 5980 days ago | link

To do the optimization when we see

  (general-function (your-type-creator 42))
we need a type inferencer to discover the return type of your-type-creator. The cache should also be able to change. For example I could write:

(general-function (your-type-creator 42))

(set your-type-creator another-type-creator)

(general-function (your-type-creator 42))

Now the optimization doesn't work if the cache doesn't change. This seems a rare case, though, and it's useless to optimize rare cases.

-----

1 point by almkglor 5979 days ago | link

Actually we don't: general-function is actually defined this way:

  (with (PIC (table) ;init empty table
         num-calls 0
         orig-fn
         (fn (n)
           (+ (method n) (other-meth n))))
    (def general-function (n)
      ((aif
         ; don't infer type: just look at the runtime type
         (PIC:type n)
            it
         (is optimization-trigger-level** (++ num-calls))
            (do (= num-calls 0)
                (= (PIC:type n)
                   (optimize* orig-fn (type n))))
            orig-fn)
        n)))
Basically s/type inference/just look at it directly/

-----