Welcome, guest | Sign In | My Account | Store | Cart

high-performance currying with instancemethod (Python recipe) by Alex Martelli
ActiveState Code (http://code.activestate.com/recipes/229472/)

instancemethod provides a way to perform currying such that the curried function runs much faster than one produced by closure (the second-fastest way). [Currying is explained and covered in detail in other recipes]

Python, 18 lines
Download
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
# Consider this code in module a.py:
import new
def curry1(func, arg):
    return new.instancemethod(func, arg, object)
def curry2(func, arg):
    def curried(*args): return func(args, *args)
    return curried
def f(a, b, c): return a, b, c
g1=curry1(f, 23)
g2=curry2(f, 23)
# g1 and g2 have the same behavior.  But NOT the same performance...:
#[alex@lancelot ba]$ timeit.py -c -s'import a' 'a.g1(45,67)'
# 1000000 loops, best of 3: 1.37 usec per loop
#[alex@lancelot ba]$ timeit.py -c -s'import a' 'a.g2(45,67)'
# 100000 loops, best of 3: 2.4 usec per loop
# curry1-produced g1 is faster enough than curry2-produced g2 to make
# this worth keeping in mind for curried functions that must be run
# as part of a program's performance bottleneck.

Currying is an important technique to build callables on the fly and is well covered in other recipes. If the callables need to be used in a performance bottleneck, the specific advantage of currying via new.instancemethod is speed of the resulting callable: it avoids nesting an extra Python function call, which may be important. In the above little benchmark, for example, a microsecond per call was saved.

Tags: algorithms

6 comments

Chris Perkins 20 years, 6 months ago  # | flag

Caveat. Neat trick, but be careful - it won't work if arg is None.

Wim Stolker 20 years, 6 months ago  # | flag

Typo. In curry2:

return func(args, *args)

should be

return func(arg, *args)

I think.

Christopher Armstrong 20 years, 6 months ago  # | flag

partial application. Very cool! I have been thinking about doing a C implementation of this partial application for a long time; this will hold me off for the time being :-) I still might, though, if I ever find a need for applying partially to keyword arguments or ordered arguments other than the first one.

It's a neat hack, I just hope python-dev doesn't decide to break it ;-)

Michael Hudson 20 years, 6 months ago  # | flag

an old bytecodehack is probably faster still. If you still have 1.5.2 lying around somewhere, you could look at bytecodehacks.xapply. It works by rewriting the bytecode of a function with 'LOAD_FAST n' for small n into an appropriate LOAD_CONST.

It was also by far the hairiest code I'd ever written at the time :-)

joshhoyt 20 years, 6 months ago  # | flag

Binding multiple arguments. For binding a single argument, new.function has the same performance as new.instancemethod, and it can be used to bind arbitrarily many arguments with equal performance:

import new

def curry1(func, *args):
    return new.function(func.func_code, func.func_globals, argdefs=args)

def curry2(func, *args):
    if not len(args): return func

    arg = args[0]
    curried = new.instancemethod(func, arg)
    return curry2(curried, *args[1:])

def curry3(func, *args):
    def curried(*args2):
    args2 = args + args2
    return func(*args2)
    return curried

def f(a, b, c):
    return a, b, c

g1 = curry1(f, 23, 45)
g2 = curry2(f, 23, 45)
g3 = curry3(f, 23, 45)

# oat (josh) ~$ python timeit.py -c -s'import curry' 'curry.g1(67)'
# 1000000 loops, best of 3: 0.97 usec per loop
# oat (josh) ~$ python timeit.py -c -s'import curry' 'curry.g2(67)'
# 1000000 loops, best of 3: 1.4 usec per loop
# oat (josh) ~$ python timeit.py -c -s'import curry' 'curry.g3(67)'
# 100000 loops, best of 3: 2.1 usec per loop
Scott David Daniels 20 years, 5 months ago  # | flag

I might be dense, but ... I might be dense, but, using 2.3.2 on Win2K SP4+:

    def triple(a, b, c): return (a, b, c)

    curry1(triple, 1) (2, 3)
--> (2,3,1)
    curry1(triple, 1,2,3) (4, 5)
--> (4,5,3)
    curry1(max, 1)(2)
---> Failure: curry1 doesn't work on builtin_function_or_method.
     (nor type, nor ...)  Seems to be user-defined functions.