ActiveState Code

Recipe 229472: high-performance currying with instancemethod

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 
 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.

Discussion

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.

Comments

  1. 1. At 2:24 p.m. on 21 oct 2003, Chris Perkins said:

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

  2. 2. At 7 a.m. on 23 oct 2003, Wim Stolker said:

    Typo. In curry2:

    return func(args, *args)

    should be

    return func(arg, *args)

    I think.

  3. 3. At 3:43 p.m. on 24 oct 2003, Christopher Armstrong said:

    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 ;-)

  4. 4. At 8:03 a.m. on 27 oct 2003, Michael Hudson said:

    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 :-)

  5. 5. At 10:26 a.m. on 7 nov 2003, Anonymous said:

    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
  6. 6. At 7:24 p.m. on 6 dec 2003, Scott David Daniels said:

    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.

Sign in to comment