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

11–20 of 85 posts

Re: Speeding up function calls with lru_cache in Python

#11

Post by shankysingh »

Immortal333 wrote: post #8
Denvercoder9 wrote: post #3

Caching the result is not speeding up function calls.

Author here. Sorry, If it feels misleading. I have no intention to mislead anybody. If you can suggest alternative title, I am happy to change title.

Thanks for article

Just a side note: with Fibonacci + caching it solidly become Dynamic programming problem so Time complexity reduces from quadratic to o(n), IIRC .

There is a whole class of problems where recursion + memoization(caching) = Top Down Dynamic programming , The other way to Increase performance and actually reduce call stack in these class of problems including Fibonacci would be Bottom Up Dynamic Programming

Some gists I found on it https://gist.github.com/trtg/4662449

Re: Speeding up function calls with lru_cache in Python

#13

Post by Immortal333 »

shankysingh wrote: post #11
Immortal333 wrote: post #8

Earlier quoted context omitted.

Author here. Sorry, If it feels misleading. I have no intention to mislead anybody. If you can suggest alternative title, I am happy to change title.

Thanks for article Just a side note: with Fibonacci + caching it solidly become Dynamic programming problem so Time complexity reduces from quadratic to o(n), IIRC . There is a whole class of problems where recursion + memoization(caching) = Top Down Dynamic programming , The other way to Increase performance and actually reduce call stack in these class of problems including Fibonacci would be Bottom Up Dynamic Prog…

Yes, I have mentioned DP in my article as just reference. The Purpose of article was to show that how easy it is to implement caching in python using lru_cache decorator which is in std lib. So, We don't have to install any 3rd party lib.

Re: Speeding up function calls with lru_cache in Python

#14

Post by shankysingh »

Immortal333 wrote: post #13
shankysingh wrote: post #11

Earlier quoted context omitted.

Thanks for article Just a side note: with Fibonacci + caching it solidly become Dynamic programming problem so Time complexity reduces from quadratic to o(n), IIRC . There is a whole class of problems where recursion + memoization(caching) = Top Down Dynamic programming , The other way to Increase performance and actually reduce call stack in these class of problems including Fibonacci would be Bottom Up Dynamic Prog…

Yes, I have mentioned DP in my article as just reference. The Purpose of article was to show that how easy it is to implement caching in python using lru_cache decorator which is in std lib. So, We don't have to install any 3rd party lib.

oh sorry , somehow I missed it :)

Re: Speeding up function calls with lru_cache in Python

#15

Post by adrianmonk »

Denvercoder9 wrote: post #3

Caching the result is not speeding up function calls.

One way to optimize performance is to change program text from one thing into something else. In this case, "function calls" refers to the text before the transformation is applied.

It seems reasonable to me to describe an optimization by identifying where it can be applied. If someone wrote a blog post titled "optimizing multiplication by 2" and went on to describe changing "x * 2" into "x + x", there would be nothing unusual about that. It would no longer be multiplication, but we wouldn't necessarily expect it to be.

I agree it can be interpreted another way in this case, though. So while I maintain it is not wrong, I admit it is ambiguous. Someone could have used the same title had they written about a one-line optimization to the Python interpreter.

Re: Speeding up function calls with lru_cache in Python

#16

Post by kevin_thibedeau »

jhrmnn wrote: post #10
Denvercoder9 wrote: post #3

Caching the result is not speeding up function calls.

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

It speeds up algorithms that are amenable to memoization.

Re: Speeding up function calls with lru_cache in Python

#17

Post by Denvercoder9 »

jhrmnn wrote: post #10
Denvercoder9 wrote: post #3

Caching the result is not speeding up function calls.

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 interpreted it at first.

Re: Speeding up function calls with lru_cache in Python

#18

Post by mac-chaffee »

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.

Re: Speeding up function calls with lru_cache in Python

#19

Post by trombonechamp »

thechao wrote: post #9
bravura wrote: post #4

I recently discovered that joblib can do something similar, both on disk and in memory: https://joblib.readthedocs.io/en/latest/memory.html

This memoizes closures of functions, and lets them be executed on other processors? Does it support dependency tracking between memoized closures (incremental recomputation), or do I have to roll that, myself?

Unfortunately you need to roll that yourself in joblib. But it is automatic in bionic (https://github.com/square/bionic), assuming your workflow can be structured in the way bionic likes.

Re: Speeding up function calls with lru_cache in Python

#20

Post by Denvercoder9 »

Immortal333 wrote: post #8
Denvercoder9 wrote: post #3

Caching the result is not speeding up function calls.

Author here. Sorry, If it feels misleading. I have no intention to mislead anybody. If you can suggest alternative title, I am happy to change title.

I'd suggest something along the lines of "Speeding up functions [in Python] by caching results" :)
Post reply on HN