Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Speeding up function calls with lru_cache in Python

hackeregg.github.io

Post reply on HN
Print view View original

51–60 of 85 posts

Re: Speeding up function calls with lru_cache in Python

#51

Post by gtm1260 »

Denvercoder9 wrote: post #17
jhrmnn wrote: post #10

Earlier quoted context omitted.

It is, though. It doesn’t speed up function execution, but it literally speeds up the function call.

It only speeds up calls to pure (side-effect free) functions, that have been executed before with these exact parameters and where the result is still cached. All other calls get slower. Also, there's an argument to be made that "function call" is the overhead involved in moving control from the call site to the callee (which can be significant in interpreted languages such as Python). That's at least how I interpret…

I agree, I think of function call as the time it takes to copy the stack frame, setup variables, and move the program counter. I'm not sure that adding a decorator slows this down, but I suspect it does. A better title would just be 'add memoization in one line in python' or something.

Re: Speeding up function calls with lru_cache in Python

#52

Post by mac-chaffee »

GeoAtreides wrote: post #26
mac-chaffee wrote: post #18

Maybe I'm abusing lru_cache but another use for it is debouncing. We had a chatbot that polls a server and sends notifications, but due to clock skew it would sometimes send two notifications. So I just added the lru_cache decorator to the send(username, message) function to prevent that.

That sounds very interesting. Can you detail the problem a bit (I'm not sure I understand how clock skew affects python code) and how lru_cache decorator fixed it?

Maybe clock skew is the wrong word. Basically we'd run the script every 10 seconds, which would use the Jira API to fetch any comments made in the last 10 seconds. So sometimes Jira would return the same comment twice, causing the script to send out two notifications, about 10 seconds apart.

Re: Speeding up function calls with lru_cache in Python

#53

Post by throwaway_pdp09 »

magnio wrote: post #47
gammarator wrote: post #42

(Fibonacci numbers have a closed form analytic solution that can be computed in constant time: https://www.evanmiller.org/mathematical-hacker.html )

Yep, this is called Binet formula, and actually all linear recurrence sequences have one.

What defines 'linear' here?

Re: Speeding up function calls with lru_cache in Python

#55

Post by throwaway_pdp09 »

nimish wrote: post #54
throwaway_pdp09 wrote: post #53

Earlier quoted context omitted.

What defines 'linear' here?

The solutions form a vector space

I regret that does not elucidate. Does linear mean additions only? Or non-exponentiation, or something else?

Re: Speeding up function calls with lru_cache in Python

#56

Post by WJW »

nimithryn wrote: post #45
gammarator wrote: post #42

(Fibonacci numbers have a closed form analytic solution that can be computed in constant time: https://www.evanmiller.org/mathematical-hacker.html )

Does this work in practice for large values of n? You will be limited by numerical error in phi.

The Fibonacci series grows so fast that for "large" values of N you'll need a arbitrary size integer implementation anyway, so at that point you might as well go for a (non-IEEE) arbitrary size float type and get all the significant digits you need.

Re: Speeding up function calls with lru_cache in Python

#57

Post by SCLeo »

ritter2a wrote: post #29
asicsp wrote: post #5

Instead of the last quote in the article, I prefer this one (got it from [0]) >"There are two hard things in computer science: cache invalidation, naming things, and off-by-one errors." – Martin Fowler And there's plenty of similar articles, for example [1] [2] [0] https://www.mediawiki.org/wiki/Naming_things [1] https://dbader.org/blog/python-memoization [2] https://mike.place/2016/memoization/

Even in this version, the quote still feels incomplete without someone shouting "Concurrency!" while it is delivered...

Concurrency.""There are three hard things in computer science: cache invalidation, naming things, off-by-one errors, and

Re: Speeding up function calls with lru_cache in Python

#59

Post by hyperman1 »

Immortal333 wrote: post #48
anandoza wrote: post #31

> As, we can see the optimal cache size of fib function is 5. Increasing cache size will not result in much gain in terms of speedup. Try it with fib(35), curious what you find.

After, reading your comment. I cross checked result and found out that 3 is most optimal size. I even ran fib(40) on it. with size 2, There are many misses but after 3 and on wards misses are constant(if fib(40), then misses are only 40 which emulates DP approach of O(N)). Why 3 is optimal, because of how recursion and LRU work. I wish i can explain it using animation. You can play with it. https://repl.it/repls/Noct…

It makes sense. f(n) depends on f(n-1) and f(n-2). So if the cache is able to produce these 2 values, you basically get the linear algorithm from the article. I assume the running f(n) also takes up a cache slot, hence 3 instead of 2.

If this theory is correct, every recursive function f(n) requiring access to f(n-x) should have x+1 as maximum usefull cache size.

Re: Speeding up function calls with lru_cache in Python

#60

Post by OskarS »

nimithryn wrote: post #45
gammarator wrote: post #42

(Fibonacci numbers have a closed form analytic solution that can be computed in constant time: https://www.evanmiller.org/mathematical-hacker.html )

Does this work in practice for large values of n? You will be limited by numerical error in phi.

It does not! It fails very early (I tested it once in Python, and it failed on something like F(70) or something) and should not ever be used for practical calculation of Fibonacci numbers.

For small values, the iterative version works just fine. For larger values, there are other methods: one obvious one is using the matrix form of the Fibonacci numbers, which just requires you to take an exponent of a 2x2 matrix (which you can do quickly because of exponentiation by squaring).

Post reply on HN