are python lambdas implemented differently from standard functions?

Question

While trying to write an answer for another SO question something really peculiar happened.

I basically came up with a one liner gcd and said it maybe slower because of recursion
gcd = lambda a,b : a if not b else gcd(b, a % b)

heres a simple test:

assert gcd(10, 3) == 1 and gcd(21, 7) == 7 and gcd(100, 1000) == 100

here are some benchmarks:

timeit.Timer('gcd(2**2048, 2**2048+123)', setup = 'from fractions import gcd').repeat(3, 100)
# [0.0022919178009033203, 0.0016410350799560547, 0.0016489028930664062]
timeit.Timer('gcd(2**2048, 2**2048+123)', setup = 'gcd = lambda a,b : a if not b else gcd(b, a % b)').repeat(3, 100)
# [0.0020480155944824219, 0.0016460418701171875, 0.0014090538024902344]

Well thats interesting I expected to be much slower but the timings are fairly close, ? maybe importing the module is the issue ...

>>> setup = '''
... def gcd(a, b):
...     """Calculate the Greatest Common Divisor of a and b.
... 
...     Unless b==0, the result will have the same sign as b (so that when
...     b is divided by it, the result comes out positive).
...     """
...     while b:
...         a, b = b, a%b
...     return a
... '''
>>> timeit.Timer('gcd(2**2048, 2**2048+123)', setup = setup).repeat(3, 100)
[0.0015637874603271484, 0.0014810562133789062, 0.0014750957489013672]

nope still fairly close timings ok lets try larger values.

timeit.Timer('gcd(2**9048, 2**248212)', setup = 'gcd = lambda a,b : a if not b else gcd(b, a % b)').repeat(3, 100) [2.866894006729126, 2.8396279811859131, 2.8353509902954102]
[2.866894006729126, 2.8396279811859131, 2.8353509902954102]
timeit.Timer('gcd(2**9048, 2**248212)', setup = setup).repeat(3, 100)
[2.8533108234405518, 2.8411397933959961, 2.8430981636047363]

interesting I wonder whats going on?
I always assumed recursion was slower because of the overhead of calling a function, are lambdas the exception? and why I haven't reach my recursion limit?
If implemented using def I hit it right away, if I increase the recursion depth to something like 10**9 I actually get a segmentation fault probably a stack overflow ...

Update

>>> setup = '''
... import sys
... sys.setrecursionlimit(10**6)
... 
... def gcd(a, b):
...     return a if not b else gcd(b, a % b)
... '''
>>> 
>>> timeit.Timer('gcd(2**9048, 2**248212)', setup = 'gcd = lambda a,b:a if not b else gcd(b, a%b)').repeat(3, 100)
[3.0647969245910645, 3.0081429481506348, 2.9654929637908936]
>>> timeit.Timer('gcd(2**9048, 2**248212)', setup = 'from fractions import gcd').repeat(3,   100)
[3.0753359794616699, 2.97499680519104, 3.0096950531005859]
>>> timeit.Timer('gcd(2**9048, 2**248212)', setup = setup).repeat(3, 100)
[3.0334799289703369, 2.9955930709838867, 2.9726388454437256]
>>>

even more puzzling ...

I think it's most likely that the Python interpretter is optimising your lambda expression into a loop *for you* (much in the same way that a typical Lisp implementation will optimize recursive tail calls). However this would be an implementation detail of CPython, not necessarily true for all Python interpreters. — Felix, Jun 24 '12 at 07:32
`recursive tail calls` yeah thats what Im also thinking, still can we always apply it, doesn't mean recursion is somewhat better using lambdas then standard `def` its really puzzling specially when you consider `it prioritizes readability over speed or expressiveness` taken from http://en.wikipedia.org/wiki/Portal:Python_programming — Samy Vilar, Jun 24 '12 at 07:36
@FelixBonkoski, Python do not optimizes the tail recursion. This code just have a little stack usage :) — Aleksei astynax Pirogov, Jun 24 '12 at 07:38
@FelixBonkoski couldn't do it I get a stack overflow ;) when using larger values ... I could try using smaller values but that along is a red flag that its going to be slower ... — Samy Vilar, Jun 24 '12 at 07:41
@astyntax appears to be correct about TRE: [Guido says this.](http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html) However, [This SO answer](http://stackoverflow.com/questions/33923/what-is-tail-recursion) seems to suggest that that there is some difference how the interpreter actually runs TR functions. Someone more qualified than me needs to answer this question! :) — Felix, Jun 24 '12 at 07:55
@FelixBonkoski nope timeit doesn't access the global scope :) thats why we have `setup = ` Timer was specifically design with such cases in mind, if you don't have setup it won't look in the global scope even you have actually defined it there. — Samy Vilar, Jun 24 '12 at 08:05
@samy You're right. I'll just shut up now until someone more qualified comes along! — Felix, Jun 24 '12 at 08:06
could you give me a pair of numbers large enough to reach the recursion limit? — mutantacule, Jun 24 '12 at 08:16
@kosii: Write a `fibonacci` function, and then use `fibonacci(1200)` and `fibonacci(1201)`. Consecutive Fibonacci numbers are the worst case for Euclid's algorithm. — Mark Dickinson, Jun 24 '12 at 08:18
@MarkDickinson and with those Fib numbers as examples, even with the OP's `lambda` form of the `gcd` function, I hit the recursion limit. Further supporting @astynax's initial remark about Python not optimizing Tail recursion, and there being no difference in how a `lambda` vs. a `def fun()` might handle TR. — Felix, Jun 24 '12 at 08:30
@FelixBonkoski: Yep; there's no tail recursion optimization in current Python. — Mark Dickinson, Jun 24 '12 at 08:43
@samy.vilar `will we ever see it?` as I linked earlier, [Guido van Rossum says TRE would be "unpythonic"](http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html) — Felix, Jun 24 '12 at 09:30
@FelixBonkoski I guess I better starting though the few first few sentences kind of made it clear :( thanks. — Samy Vilar, Jun 24 '12 at 09:37

score 6 · Answer 1 · answered Jun 24 '12 at 09:01

6

counter = 0

def gcd(a, b):
    global counter
    counter += 1
    return a if not b else gcd(b, a % b)

gcd(2**9048, 2**248212)
print counter

Prints 3. Of course there is not a lot of overhead for a recursion of depth 3.

answered Jun 24 '12 at 09:01

Niklas B.

92,950
18
194
224

yes Im quite of aware of that now, i should have used Fibonacci numbers to run my tests, learning something new everyday ... – Samy Vilar Jun 24 '12 at 09:06

Marcin · Accepted Answer · 2012-06-24T08:12:52.640

-1

The type of a lambda is exactly the same as the type of any other function, and in the case of both, if defined in another local scope, environment capture occurs.

The only difference is that functions defined with the lambda syntax do not automatically become the value of a variable in the scope in which it appears, and that lambda syntax requires the body to be one (possibly compound) expression, the value of which is returned from the function.

As to the speed of recursion - yes there's a slight overhead, but apparently not that much. The call overhead would appear to mostly be made of the cost of allocating the stack frame.

edited Jun 24 '12 at 08:12

answered Jun 24 '12 at 07:13

Marcin

48,559
18
128
201

Did you even look at the times he's showing? You are **not** seeing the _effect_ that the library function fractions.gcd() is faster. He's trying to show that it's a toss-up, and he's puzzled by that. -1 for not reading the question. – Felix Jun 24 '12 at 07:18
1

@Marcin I also defined the non-recurs function using regular python and the timings still don't differ, something rather peculiar is happening, and why haven't I reached the recursion limit? – Samy Vilar Jun 24 '12 at 07:23
@samy.vilar You are creating only one new int per stack frame, so memory consumption is not an issue. There is no mystery here. As to the recursion limit, why would you expect that you would hit it with this example? – Marcin Jun 24 '12 at 08:11
@Marcin well after some fine tuning and re running some more examples I think you right, still Im pleasantly surprised, recursion is quite fast in python, who knew, thank you. – Samy Vilar Jun 24 '12 at 08:39
1

Recursion is (significantly) slower [here](http://ideone.com/YsT85). Any explanations? – UltraInstinct Jun 24 '12 at 08:54
@Thrustmaster Yes: the recursion depth of the OP's original numbers (2**9048 and 2**248212) was only 2! With fib(100) and fib(101) the recursive depth is 100! I can't believe I didn't notice this earlier. And so, yes, recursion *is* significantly slower! – Felix Jun 24 '12 at 09:06
Ah, yes! I didnt see that. Only now, with your comment and @Niklas's answer. – UltraInstinct Jun 24 '12 at 09:10
@Marcin: The impact is in fact very significant. Most of the time is spent putting stuff on the stack, when it could be kept in the registers instead. In this particular example, this makes the algorithm about 100% slower in the worst case. – Niklas B. Jun 24 '12 at 11:26

are python lambdas implemented differently from standard functions?

2 Answers2