473,322 Members | 1,259 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

Optimizing multiple dispatch

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.
Jul 18 '05 #1
15 1758
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 methodForSelector in Objective-C.

--
Brian Gough

Network Theory Ltd,
Publishing the Python Manuals --- http://www.network-theory.co.uk/
Jul 18 '05 #2
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(object)
extern object PyTuple_New(int)
extern int PyTuple_GET_SIZE(object)
extern void *PyObject_Type(void*)
extern void PyTuple_SET_ITEM(object, int, void*)
extern void *PyTuple_GET_ITEM(object, int)

def maptype(i):
if not PyTuple_Check(i): raise TypeError
cdef int l
cdef int j
l = PyTuple_GET_SIZE(i)
o = PyTuple_New(l)
for j from 0 <= j < l:
PyTuple_SET_ITEM(o, j, PyObject_Type(PyTuple_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)

iD8DBQFAvy2pJd01MZaTXX0RAvgPAJ9+smiDH0o+bo5rwwsOri 1hl7jtIQCeKCXR
BE8bms1T8IJduTWe7+ivEwQ=
=Xtuc
-----END PGP SIGNATURE-----

Jul 18 '05 #3
[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.
Jul 18 '05 #4
Jeff Epler <je****@unpythonic.net> writes:
Avoding map() may help:
tuple([type(a) for a in args])
Nonononononooooo! :-)
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.
Jul 18 '05 #5
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.
Jul 18 '05 #6
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 ****
Jul 18 '05 #7
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.

Jul 18 '05 #8
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****@unpythonic.net> writes:
Avoding map() may help:
tuple([type(a) for a in args])


Nonononononooooo! :-)

[...]
... 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)

iD8DBQFAv0QgJd01MZaTXX0RAmwoAJ920fACmXQR0UWd03BMQy bUuKWEOwCfWDPB
Yc059n1wXFyym54rUNFnctg=
=2YRY
-----END PGP SIGNATURE-----

Jul 18 '05 #9
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
Jul 18 '05 #10
Jeff Epler <je****@unpythonic.net> wrote in message news:<ma*************************************@pyth on.org>...
Avoding map() may help:
tuple([type(a) for a in args]) [snip]
... hmm, map is faster than listcomp. my mistake!


Rule of thumb: listcomp is only faster than map if it avoids an extra
function call. So, for example, "[ x+1 for x in xs ]" is probably
faster than "map(lambda x:x+1,xs)".

But, since this particular use doesn't avoid a function call, the map
is faster.
--
CARL BANKS
Jul 18 '05 #11
Jacek Generowicz <ja**************@cern.ch> wrote in message news:<ty*************@pcepsft001.cern.ch>...
Jeff Epler <je****@unpythonic.net> writes:
[... 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.


Because not all C is the same. For example, to execute something like
"type(m)", Python has to construct a tuple for the arguments, and call
the type object with it. The type object new function has some
special casing (to get the behavior of the old type function) and
argument checks and stuff in it.

OTOH, PyObject_Type is probably a macro defined like this:
#define PyObject_Type(_obj) (_obj->ob_type)

So, even though type(m) is "coded in C already", it's not really fast
C.
--
CARL BANKS
Jul 18 '05 #12
Heiko Wundram <he*****@ceosg.de> writes:
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...
Well, I still find writing pure Python/C-API to be a pain.
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 ;)


I probably write suboptimal code too ... probably more suboptimal than
Pyrex :-)
Jul 18 '05 #13
Jeff Epler <je****@unpythonic.net> writes:
No message about optimization should be without one downright wrong
suggestion.


Ain't dat da truth!
Jul 18 '05 #14
In your Multimethods, is the number of args fixed and known at the time
you first call Multimethod(), or do you need to be able to support dispatching
based on the number as well as the type of the arguments?

If the former, your __init__ method can take an n_args_to_dispatch argument,
and use this to create a function that collects the types. For the two arg
case shown here,
lambda args: (type(args[0]), type(args[1]))

I suppose you would save more if type_collector1(), type_collector2(), etc.
were written in C.

You could save even more if __call__ took an explict signature that you
didn't have to access from a tuple. This isn't an option for a general purpose
Multmethod, but might be ok in your domain-specific situation. Or you could have
classes Multimethod1, Multimethod2, etc.
Timer('tuple(map(type, (1, 2)))').timeit() 5.4792276672034177 Timer('(lambda args: (type(args[0]), type(args[1])))((1, 2))').timeit() 3.246841148805288 Timer('(lambda a, b: (type(a), type(b)))(1, 2)').timeit()
2.6581895185003077
Jacek Generowicz wrote: 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.


Jul 18 '05 #15
Howard Stearns <ho************@charter.net> writes:
In your Multimethods, is the number of args fixed and known at the time
you first call Multimethod(), or do you need to be able to support dispatching
based on the number as well as the type of the arguments?


These multimethods are proxies for C++ functions, so the number of
arguments is variable.

Thanks for your ideas though: it surprised me to see just how much
those timings differ.
Jul 18 '05 #16

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

0
by: Hung Jung Lu | last post by:
Hi, I try win32com.client.Dispatch('InternetExplorer.Application'), and it returns an instance of the running IE object. If there are multiple instances of IE running, how can I make sure I get...
31
by: Chris S. | last post by:
Is there a purpose for using trailing and leading double underscores for built-in method names? My impression was that underscores are supposed to imply some sort of pseudo-privatization, but would...
4
by: Leslaw Bieniasz | last post by:
Cracow, 20.09.2004 Hello, I need to implement a library containing a hierarchy of classes together with some binary operations on objects. To fix attention, let me assume that it is a...
8
by: J. Black | last post by:
Hello everyone - I've been developing an incident tracking and reporting system for an emergency services outfit that I work with part time. It's going well, except for one fly in the ointment....
6
by: G.Ashok | last post by:
Hi, Does anybody know how Multiple polymorphism can be done in VB.NET or DOT doesn't support it? Is there any third party extensions available like for Java to do this? Regards, ....Ashok...
1
by: vinoraja | last post by:
There are a number of reasons we don't implement Multiple Implementation Inheritance directly. (As you know, we support Multiple Interface Inheritance). However, I should point out that it's...
60
by: Shawnk | last post by:
Some Sr. colleges and I have had an on going discussion relative to when and if C# will ever support 'true' multiple inheritance. Relevant to this, I wanted to query the C# community (the...
3
by: tyler.schlosser | last post by:
Hi there, I am trying to launch a program called AmiBroker using the command: AB = win32com.client.Dispatch("Broker.Application") However, I have a dual-core CPU and would like to launch two...
3
by: Tigera | last post by:
Greetings, I too have succumbed to the perhaps foolish urge to write a video game, and I have been struggling with the implementation of multiple dispatch. I read through "More Effective C++"...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.