Optimizing multiple dispatch

[Jacek Generowicz]

I have a multiple disptacher which, conceptually, looks something like
this:

class Multimethod:

def __init__(self):
self.methods = {}

def __call__(self, *args):
return self.methods[tuple(map(type, args))](*args)

def add_method(self , method, *types):
self.methods[types] = method

foo = Multimethod()

def fooii(a, b):
print "We got two ints"

def foosb(a, b):
print "We got a string and a bar"

class bar(object): pass

foo.add_method( fooii, int, int)
foo.add_method( foosb, str, bar)

foo(1,2)
foo("a string", bar())

My actual code looks nothing like this[*], because it contains a
number of optimizations, and addresses some domain-specific
considerations which are not relevant in this context; but the code
shown should highlight the salient points.

Profiling suggests that "tuple(map(type , args))" is taking a
significant proportion of time in certain critical loops.

Do you have any suggestions about how to make in run faster? (Either
by optimizing "tuple(map(type , args)", or by using a completely
different organization for the whole thing. There is almost certainly
no point in addressing any other implementation detail[*] of what is
shown here, as it is likely to be absent from my real code.)

[*] For example, there is no __call__ in my implementation; it's
implementeted as a closure.

[Brian Gough]

Jacek Generowicz <ja************ **@cern.ch> writes:

Profiling suggests that "tuple(map(type , args))" is taking a
significant proportion of time in certain critical loops.
Do you have any suggestions about how to make in run faster? (Either
by optimizing "tuple(map(type , args)", or by using a completely
different organization for the whole thing.

If the arguments inside the loop have fixed types, then maybe you
could have a method to get the reference to the function (once)
outside the loop.

This would be like methodForSelect or in Objective-C.

--
Brian Gough

Network Theory Ltd,
Publishing the Python Manuals --- http://www.network-theory.co.uk/

[Jeff Epler]

Avoding map() may help:
tuple([type(a) for a in args])
Using generator expressions (aren't they in 2.4?) might or might not
help:
tuple(type(a) for a in args)

You could write a small extension to perform this operation without all
the Python function calls.

cdef extern from "Python.h":
extern int PyTuple_Check(o bject)
extern object PyTuple_New(int )
extern int PyTuple_GET_SIZ E(object)
extern void *PyObject_Type( void*)
extern void PyTuple_SET_ITE M(object, int, void*)
extern void *PyTuple_GET_IT EM(object, int)

def maptype(i):
if not PyTuple_Check(i ): raise TypeError
cdef int l
cdef int j
l = PyTuple_GET_SIZ E(i)
o = PyTuple_New(l)
for j from 0 <= j < l:
PyTuple_SET_ITE M(o, j, PyObject_Type(P yTuple_GET_ITEM (i, j)))
return o

print maptype.maptype (("", 0, 0.0, 0L, str, int, type))

(<type 'str'>, <type 'int'>, <type 'float'>, <type 'long'>, <type 'type'>, <type 'type'>, <type 'type'>)

$ timeit -s 's = ("", 0, 0.0, 0L, str, int, type); from maptype import maptype' 'maptype(s)'
100000 loops, best of 3: 2.41 usec per loop
$ timeit -s 's = ("", 0, 0.0, 0L, str, int, type)' -s 'def maptype(s): return tuple([type(i) for i in s])' 'maptype(s)'
10000 loops, best of 3: 25.3 usec per loop
$ timeit -s 's = ("", 0, 0.0, 0L, str, int, type)' -s 'def maptype(s): return tuple(map(type, s))' 'maptype(s)'
100000 loops, best of 3: 17 usec per loop

... hmm, map is faster than listcomp. my mistake!

Jeff

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iD8DBQFAvy2pJd0 1MZaTXX0RAvgPAJ 9+smiDH0o+bo5rw wsOri1hl7jtIQCe KCXR
BE8bms1T8IJduTW e7+ivEwQ=
=Xtuc
-----END PGP SIGNATURE-----

[Jacek Generowicz]

[Hi, Brian, fancy meeting you here !]

Brian Gough <bj*@network-theory.co.uk> writes:

If the arguments inside the loop have fixed types, then maybe you
could have a method to get the reference to the function (once)
outside the loop.

Yup, we do that already ... it gives us more than a factor of 2
improvement in a particular politically important benchmark.

But, this must remain an option open to the user, and there is still a
need to make the thing go faster without pre-selection.

[Jacek Generowicz]

Jeff Epler <je****@unpytho nic.net> writes:

Avoding map() may help:
tuple([type(a) for a in args])
Nonononononoooo o! :-)
You could write a small extension to perform this operation without all
the Python function calls.

[... Pyrex ...] 100000 loops, best of 3: 2.41 usec per loop [... List comprehension ...] 10000 loops, best of 3: 25.3 usec per loop [... map ...] 100000 loops, best of 3: 17 usec per loop
(I'm pretty sure that should be 10**5 loops in the list comp case)

Hmm, ok, the extension seems to be significantly faster. This
surprises me, because everything that executes in
"tuple(map(type ,args))" is coded in C already, so I don't see where
the gain is coming from.

I've never got around to trying Pyrex ... and I won't be allowed to
depend on it formally. Would it be feasible to use Pyrex to generate
the extension source code and paste[*] that into my extension module?
IOW, is there a run-time dependence on Pyrex?
<ASIDE>
... hmm, map is faster than listcomp. my mistake!

:-)

I've asked for optimization advice a few times here, and usually the
responses include "replace map with a list comprehension" ... and yet
the map is always faster. I wonder where people get this idea that map
is slow ... until this started happening I had always assumed that
"everyone" knows that the map/reduce/filter family are the fastest
Python looping constructs.

</ASIDE>
[*] Ugh, I shudder at the thought, putting the products of code
generators into CVS really goes against my fundamental principles.

[Jacek Generowicz]

Jacek Generowicz <ja************ **@cern.ch> writes:

Hmm, ok, the extension seems to be significantly faster. This
surprises me, because everything that executes in
"tuple(map(type ,args))" is coded in C already, so I don't see where
the gain is coming from.

Forgot to mention: your map and list comp versions included an
unnecessary call to a pure Python function (maptype). The extension
you proposed would replace an inlined "tuple(map(type , args))", so we
don't get hit by pure Python function call overhead at that point[*].

Still, eliminating that overhead knocks off only one third of the
time, while your extension was better by a factor of 7 ... so there's
still a factor of 4.5ish to be had by coding it as an extension
(sorry, I don't have Pyrex, so I can't show the time):

-s 's = ("", 0, 0.0, 0L, str, int, type)' -s 'def maptype(s): return tuple(map(type, s))' 'maptype(s)'
100000 loops, best of 3: 4.73 usec per loop
-s 's = ("", 0, 0.0, 0L, str, int, type)' 'tuple(map(type , s))'
100000 loops, best of 3: 4.46 usec per loop
[*] There is a pure Python function call overhead I would like to
eliminate by recoding in C, but it concerns a closure (which Pyrex
doesn't allow, IIRC), and that seems a bit tricky to do.

[Jacek Generowicz]

Jacek Generowicz <ja************ **@cern.ch> writes:

(I'm pretty sure that should be 10**5 loops in the list comp case)

I'm sorry, ignore that, I was talking out of my ****

[Heiko Wundram]

Am Donnerstag, 3. Juni 2004 16:55 schrieb Jacek Generowicz:

[*] Ugh, I shudder at the thought, putting the products of code
generators into CVS really goes against my fundamental principles.

Writing this module by hand shouldn't be much harder than writing it using
Pyrex. The Python/C-API is very clean, and there's good documentation in the
Python Documentation section on Python.org...

I guess you could squeeze out another 0.1 usecs by writing it by hand, because
Pyrex sometimes generates suboptimal C code, on another note ;)

Heiko.

[Jeff Epler]

Pyrex is just a translator, there's no dependency on a Pyrex library or
include file when you actually want to compile the generated .c

On Thu, Jun 03, 2004 at 04:55:19PM +0200, Jacek Generowicz wrote:

Jeff Epler <je****@unpytho nic.net> writes:

Avoding map() may help:
tuple([type(a) for a in args])

Nonononononoooo o! :-)

[...]

... hmm, map is faster than listcomp. my mistake!

:-)

I've asked for optimization advice a few times here, and usually the
responses include "replace map with a list comprehension" ... and yet
the map is always faster. I wonder where people get this idea that map
is slow ... until this started happening I had always assumed that
"everyone" knows that the map/reduce/filter family are the fastest
Python looping constructs.

No message about optimization should be without one downright wrong
suggestion.

The common wisdom about listcomp speed may apply when the body doesn't
include a function call, but the map version would include a lambda:
$ timeit 'map(lambda x:x+1, range(100))'
1000 loops, best of 3: 230 usec per loop
$ timeit '[x+1 for x in range(100)]'
10000 loops, best of 3: 156 usec per loop
Jeff

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iD8DBQFAv0QgJd0 1MZaTXX0RAmwoAJ 920fACmXQR0UWd0 3BMQybUuKWEOwCf WDPB
Yc059n1wXFyym54 rUNFnctg=
=2YRY
-----END PGP SIGNATURE-----

[David Bolen]

Jacek Generowicz <ja************ **@cern.ch> writes:

I've never got around to trying Pyrex ... and I won't be allowed to
depend on it formally. Would it be feasible to use Pyrex to generate
the extension source code and paste[*] that into my extension module?
IOW, is there a run-time dependence on Pyrex?

Probably not even necessary - doing the same operation directly in
your extension module with straight C code shouldn't be much work (the
example Pyrex code posted is largely just a set of calls tov the
Python API anyway already). About the only thing that can't be
written directly in C is probably the "raise TypeError" part, but for
that you can just set the error and return NULL from the function, I
believe.

-- David