New gf dispatcher for d2c 
Author Message
 New gf dispatcher for d2c

So last week there was some talk about dispatching generic functions
and how d2c could stand some improvement in that regard, and I brought
up the algorithm described in "Efficient Predicate and Multimethod
Dispatching" by Craig Chambers and Weimin Chen. Essentially, they
describe a way to do multimethod dispatching efficiently by building a
decision tree that will let you quickly figure out which method to
to actually run.

Perhaps foolishly, I said I'd try to implement this algorithm for
d2c. Currently, I have a scratch implementation of the dispatch-tree
building algorithm. I'm calling it a scratch version because it's and
untested, unoptimized, undocumented, undebugged version written mainly
to help me figure out a) how the algorithm works, and b) how to
program in Dylan. It's the first nontrivial piece of Dylan code I've
written -- I will no doubt have to rewrite the whole thing from
scratch before it's fit for submission to the Gwydion maintainers.

But in the meantime, if you are interested in seeing what this
algorithm looks like in Dylan, you can find it at:

  http://www.*-*-*.com/

Note that this is just the dispatch tree, and would theoretically get
called each time add-method() is. This *doesn't* include the code to
actually handle a generic function call. Mostly, I'm just posting this
to get some critiques on my Dylan programming style.

BTW, is dylan-hackers back up yet?

Neel



Fri, 01 Feb 2002 03:00:00 GMT  
 New gf dispatcher for d2c

Quote:

> So last week there was some talk about dispatching generic functions
> and how d2c could stand some improvement in that regard, and I brought
> up the algorithm described in "Efficient Predicate and Multimethod
> Dispatching" by Craig Chambers and Weimin Chen. Essentially, they
> describe a way to do multimethod dispatching efficiently by building a
> decision tree that will let you quickly figure out which method to
> to actually run.

Have you looked at build-discriminator-tree in
src/d2c/compiler/convert/deffunc.dylan?

I'm not sure how smart it is, or even whether it's used much, but it's
certainly building a decision tree.

-- Bruce

p.s. the code looks fine to me at first glance.  This is intruiging:

if (element(#(method-set . formal-positions), #f))
   let node = memo[#(method-set . formal-positions)];

What, exactly, is the first line trying to do?  IS that supposed to be:

if (element(memo, #(method-set . formal-positions), #f))

If so, you may need to use a "value table", not a "table" i.e. one which
tests using = not ==.

-- Bruce



Fri, 01 Feb 2002 03:00:00 GMT  
 New gf dispatcher for d2c

Quote:

> So last week there was some talk about dispatching generic functions
> and how d2c could stand some improvement in that regard, and I brought
> up the algorithm described in "Efficient Predicate and Multimethod
> Dispatching" by Craig Chambers and Weimin Chen. Essentially, they
> describe a way to do multimethod dispatching efficiently by building a
> decision tree that will let you quickly figure out which method to
> to actually run.

While I very much appreciate your efforts, I have the feeling that the
dispatch table based algorithm described in

http://www.acm.org/pubs/citations/journals/toplas/1998-20-1/p116-duja...

performs better, since it essentially does one table lookup per
argument. Of course this is modulo unions (which should be quite easy
to implement) and singletons (which require special treatment).

Andreas

--
"We show that all proposed quantum bit commitment schemes are insecure because
the sender, Alice, can almost always cheat successfully by using an
Einstein-Podolsky-Rosen type of attack and delaying her measurement until she
opens her commitment." ( http://xxx.lanl.gov/abs/quant-ph/9603004 )



Fri, 01 Feb 2002 03:00:00 GMT  
 New gf dispatcher for d2c

Quote:

>> So last week there was some talk about dispatching generic functions
>> and how d2c could stand some improvement in that regard, and I brought
>> up the algorithm described in "Efficient Predicate and Multimethod
>> Dispatching" by Craig Chambers and Weimin Chen.

>While I very much appreciate your efforts, I have the feeling that the
>dispatch table based algorithm described in

>http://www.acm.org/pubs/citations/journals/toplas/1998-20-1/p116-duja...

>performs better, since it essentially does one table lookup per
>argument. Of course this is modulo unions (which should be quite easy
>to implement) and singletons (which require special treatment).

I suspect that the only way to tell is to implement both; the number
of methods in the typical generic function will frequently be small
enough that big-O analysis isn't going to be very revealing.

For example, the Chambers algorithm can use binary or linear search in
the nodes of the dispatch tree, which while either O(ln n) or O(n),
might turn out to be faster in practice than an O(1) hash-table when
the number of methods is small to medium, or if we have some profile
information about which methods are most likely to be invoked. Worse
still, the behavior of the two algorithms could be radically different
for large and small programs, because if everything is cache-miss-free
that radically changes the cost of memory accesses. :(

Anyway, I would be happy to implement both and compare them on some
real system like d2c, except for one problem: I'm not an ACM member,
so I can't download the Dujardin paper from the URL you gave. If it's
legal to do so, I'd appreciate it if you could email me a copy of the
paper. I'm going to have some free time next week, and I could take a
stab at it then.

Neel



Sat, 02 Feb 2002 03:00:00 GMT  
 New gf dispatcher for d2c

Quote:

>Have you looked at build-discriminator-tree in
>src/d2c/compiler/convert/deffunc.dylan?

>I'm not sure how smart it is, or even whether it's used much, but it's
>certainly building a decision tree.

No, I didn't even know it existed. But it does look like it's doing
something very very similar. I can't tell for certain yet, because
it's a single 3-page-long function which will take me a while to grok.

Quote:
>Is that supposed to be:

>if (element(memo, #(method-set . formal-positions), #f))

>If so, you may need to use a "value table", not a "table" i.e. one which
>tests using = not ==.

Yes, you are right on both counts.

Incidentally, programming in Dylan is a weird experience: I keep
*wanting* to see parentheses around every body, and every time I
modify a binding with an assignment, I feel guilty for using mutable
state. It's a lot like programming in Scheme, only doing all the bad
things we were always supposed to avoid. :)

Neel



Sat, 02 Feb 2002 03:00:00 GMT  
 New gf dispatcher for d2c

Quote:


> >Have you looked at build-discriminator-tree in
> >src/d2c/compiler/convert/deffunc.dylan?

> >I'm not sure how smart it is, or even whether it's used much, but it's
> >certainly building a decision tree.

> No, I didn't even know it existed. But it does look like it's doing
> something very very similar. I can't tell for certain yet, because
> it's a single 3-page-long function which will take me a while to grok.

Yeah.  Which is why I hadn't got to deciphering it.  And there are a bunch
of related functions in the same place, such as discriminator-possible?
that need to be groked at the same time.

Looking at the output of d2c, I *have* seen discriminator functions
generated and used, but far less often that I would have expected -- the
default GF dispatch function is used virtually all the time.

I don't know for sure, but I suspect that discriminator-possible? is being
too strict.

Just one of the many things I've seen while browsing through the code, but
haven't gotten to looking at yet...

Quote:
> Incidentally, programming in Dylan is a weird experience: I keep
> *wanting* to see parentheses around every body, and every time I
> modify a binding with an assignment, I feel guilty for using mutable
> state. It's a lot like programming in Scheme, only doing all the bad
> things we were always supposed to avoid. :)

Well, modifying local bindings is no biggie as the compiler converts it to
SSA form immediately anyway, creating new variables as necessary.  And
then the C compiler does graph-colouring and maps all those generated
variables back into a few registers...

Slot bindings are a different matter, but since objects are by definition
bundles of mutable state it's hard to avoid... :-)

-- Bruce



Sat, 02 Feb 2002 03:00:00 GMT  
 New gf dispatcher for d2c

Quote:


> > ... I brought up the algorithm described in "Efficient Predicate
> > and Multimethod Dispatching" ...
> ...

> p.s. the code looks fine to me at first glance.  This is intruiging:

> if (element(#(method-set . formal-positions), #f))
>    let node = memo[#(method-set . formal-positions)];

BTW, that "dotted list" expression isn't DRM-conformant Dylan, because
"#()" can only contain literals.  You want to use

  pair(method-set, formal-positions)

if you want this to be portable.

Quote:
> What, exactly, is the first line trying to do?  IS that supposed to be:

> if (element(memo, #(method-set . formal-positions), #f))

> If so, you may need to use a "value table", not a "table" i.e. one
> which tests using = not ==.

If you don't need to compare the components of your index (method-set
and formal-positions) with \=, a more alternative approach would be to
have layered <object-table>s, so the above call would become more like

  let positions-table = element(memo, method-set, default: #f);
  let node
    = positions-table
      & element(postions-table, formal-positions, default: #f);
  when (node)
    // ...
  end;

It should be easy enough to wrap up this notion into some kind of
<explicit-key-array> class and, by renaming "aref[-setter]" on
import and defining your own version, you could use the "foo[x, y]"
syntax :-)  Haven't tried that, though.



Sat, 02 Feb 2002 03:00:00 GMT  
 
 [ 7 post ] 

 Relevant Pages 

1. New Release of mac-d2c

2. Op-code dispatcher

3. Extend/Embed Python Method table Dispatcher

4. SICStus, global constraint dispatcher

5. GF/ST on VW2.52 question

6. d2c string-to-integer error

7. bugs in d2c ratio.dylan

8. d2c string-to-integer problem

9. Second beta release of d2c CodeWarrior plugin available

10. First beta release of d2c CodeWarrior plugin available

11. First alpha release of d2c CodeWarrior plugin available

12. Second alpha release of d2c CodeWarrior plugin available

 

 
Powered by phpBB® Forum Software