Speeding up function calls with lru_cache in Python • Hacker News Board

Re: Speeding up function calls with lru_cache in Python

#71

Post by crystaln » Sun, Jun 28, 2020, 6:45 PM UTC

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.

This is neat atho I would agree it isn’t the right tool. The reason is that the time until a second message with the same content can be sent is indeterminate, based on how many intervening messages are sent. If your app does want to send the same notice twice, with an hour in between, and there are no intervening messages, it would fail, so the behavior is unpredictable.

A timed algorithm seems better suited. That said, it probably doesn’t matter much.

Re: Speeding up function calls with lru_cache in Python

#72

Post by akdas » Sun, Jun 28, 2020, 6:56 PM UTC

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…

Plugging my own writing, but I did a deep dive on top-down vs. bottom-up dynamic programming on my blog: https://avikdas.com/2019/04/15/a-graphical-introduction-to-d...

The follow-up posts go into even more detail on individual problems that can be solved using either form of dynamic programming, including some real-world problems like content-aware image resizing.

Re: Speeding up function calls with lru_cache in Python

#73

Post by huijzer » Sun, Jun 28, 2020, 7:30 PM UTC

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.

I noticed that anytime I thought I was clever by using memoization on a function with side-effects, that it in fact could become very complicated very quickly. It's a bit similar in your situation: What if someone actually wants to send the same message twice? Depending on your codebase it could be hard to debug the issue which will arise.

One thing where I do think it is kind of safe is for loading a file into a class instance. The memoization will avoid defining (1) a method to check to see if the file is loaded, (2) a method to load the file and (3) a class variable which points to the loaded file.

Re: Speeding up function calls with lru_cache in Python

#74

Post by schuppentier » Sun, Jun 28, 2020, 7:49 PM UTC

mac-chaffee wrote: post #52

GeoAtreides wrote: post #26

Earlier quoted context omitted.

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.

That sounds to me like a Push setup would be preferable here. There are a number of Jira add-ons that can run code in response to system events like a new comment. That way you should be able to avoid the concurrency problems completely.

Re: Speeding up function calls with lru_cache in Python

#75

Post by zo1 » Sun, Jun 28, 2020, 9:11 PM UTC

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 comment entry that you get back from JIRA should have a unique "ID" attached to it that you can use to do a duplicate check on. According to you, your function signature is send(username, message), in which case this solution will fail if the same user makes the same comment on two different issues.

Have a look at their REST API docs for retrieving comments on an Issue:

https://docs.atlassian.com/software/jira/docs/api/REST/8.10....

You'll see that they respond with an ID for each comment. That ID is unique and probably the PK of the comment on the JIRA application's DB. That is the the key that you need to use to do a duplicate check. Not username and message content.

Re: Speeding up function calls with lru_cache in Python

#76

Post by zo1 » Sun, Jun 28, 2020, 9:19 PM UTC

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?

It's not clock skew of the CPU/Python in any sense. My theory: Their script is run every 10seconds without taking into account the execution time of previous runs, and they noticed duplicates as the same message would be picked up on multiple executions of their polling script because of probably network delays on the REST API they're querying. So they used the lru_cache decorator to filter out duplicates according to the message content and the user that made it. Really bad design if you ask me, as it's essentially "throwing spaghetti" onto the wall instead of figuring out what's really going wrong. As other people have mentioned, they should instead be using a plain ID to filter out duplicates because it is the most unique identifier.

Re: Speeding up function calls with lru_cache in Python

#77

Post by thechao » Sun, Jun 28, 2020, 9:30 PM UTC

trombonechamp wrote: post #19

thechao wrote: post #9

Earlier quoted context omitted.

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.

Bionic is what I'm looking for (right on their use-case page): a Make replacement that can work with intermediate computations, and not just files.

Re: Speeding up function calls with lru_cache in Python

#78

Post by eindiran » Sun, Jun 28, 2020, 10:47 PM UTC

akdas wrote: post #72

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…

Plugging my own writing, but I did a deep dive on top-down vs. bottom-up dynamic programming on my blog: https://avikdas.com/2019/04/15/a-graphical-introduction-to-d... The follow-up posts go into even more detail on individual problems that can be solved using either form of dynamic programming, including some real-world problems like content-aware image resizing.

Thank you for the link, I enjoyed the post a lot. The drawings you've done add a lot to the explanation. Do you have any other deep dives you've done in the same style that you'd recommend?

Re: Speeding up function calls with lru_cache in Python

#79

Post by andreareina » Mon, Jun 29, 2020, 1:48 AM UTC

raymondh wrote: post #69

andreareina wrote: post #28

lru_cache doesn't work with lists or dicts, or indeed any non-hashable data, so it's not quite a transparent change. About half the time I use a cache I end up implementing my own.

What approach are you using to efficiently store and look up non-hashable function arguments?

Converting to tuple has mostly been enough. I want to say always, but I don't trust my memory that much, haha.

Re: Speeding up function calls with lru_cache in Python

#80

Post by nimish » Mon, Jun 29, 2020, 2:12 AM UTC

throwaway_pdp09 wrote: post #55

nimish wrote: post #54

Earlier quoted context omitted.

The solutions form a vector space

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

If A and B are a solution, then A+B is also a solution. For a constant r, if C is a solution, r*C is also solution.

That's it. The nice closed form of exponentials as solutions is just for linear difference equations with constant coefficients. In that case, you can always find a solution by trying λ^n and seeing what that forces λ to be -- it'll be a root of some polynomial.