A cached_function with selective memory

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Here is a new input_filter argument for cached functions which makes it remember only "some" output, depending on the input.

Nathann

CC: @dkrenn @videlec

Component: performance

Branch/Commit: u/ncohen/16353 @ 7eb8f90

Issue created by migration from https://trac.sagemath.org/ticket/16353

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Branch: u/ncohen/16353

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

e06b947

trac #16353: A cached_function with selective memory

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Commit: e06b947

[vbraun]

comment:3

-1 because it isn't needed and only serves to facilitate bad code designs

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:4

-1 because it isn't needed and only serves to facilitate bad code designs

Daniel Krenn said on the mailing list that it would help him. -1 to dishonest comments. By the way, I still do not know how to avoid this bad design, but we can continue discussing it on the sage-devel thread, I am genuinely interested.

Nathann

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:5

By the way I don't get how you can say that a feature like "only cache small results" is not useful.

Nathann

[3f8450e1-87bf-41c6-ab53-29a0552debb3]

comment:6

Replying to @vbraun:

-1 because it isn't needed and only serves to facilitate bad code designs

Could you argue that?

I could easily imagine some could code which are usually use to compute small things but some crazy researcher could want compute big things (one times) and be exhaustive on those big things...

[nbruin]

comment:7

-1 for feature creep. People use cached_function/cached_method to be fast. Adding another parameter/filter slows things down.

-1 for obscuring serious programming logic: in any non-trivial situation, you need a strategy to decide which inputs do need caching and which don't. The strategy there will need tuning and/or may have to change depending on application. Something like that shouldn't be hidden in a decorator that you slap on a function. That strategy could probably do a much better job if it's properly integrated with the rest of the code, and not just has a preview by peeking at the input parameters.

I think it's a code smell when this seems attractive: some things seem worthwhile to cache but generally it's too expensive. The "worthwhile" part is coming from your particular application, so THAT is where you should cache or probably more appropriately: where you should build a data structure that stores the required intermediate results.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:8

-1 for feature creep. People use cached_function/cached_method to be fast. Adding another parameter/filter slows things down.

If there was not a "key" parameter to normalize the input I would have agreed with that. Please tell me why this feature is needed and "clean" and not mine. I was looking at it while I wrote this patch, and the cost of mine is less important.

-1 for obscuring serious programming logic: in any non-trivial situation, you need a strategy to decide which inputs do need caching and which don't. The strategy there will need tuning and/or may have to change depending on application. Something like that shouldn't be hidden in a decorator that you slap on a function. That strategy could probably do a much better job if it's properly integrated with the rest of the code, and not just has a preview by peeking at the input parameters.

You can define the filter wherever you want, and make it as long and complicated as you want. And when you have defined it, how do you plan on making "cached_method" behave according to it except through the decorator ?

I think it's a code smell when this seems attractive:

Come on guy, caching the output of calls which give a small output does not seem that far fetched. Why can't you see it ?

some things seem worthwhile to cache but generally it's too expensive.

Indeed. I want to filter them out.

Nathann

[83660e46-0051-498b-a8c1-f7a7bd232b5a]

comment:9

If none of what we've suggested so far on sage-devel appears to fit, I still think your algorithm or function(s) isn't designed well, and you can always implement your custom cache explicitly with a few lines of code (including some projective cache which just stores whether a solution exists, but not the solution itself, in case you want to stay with the boolean existence parameter).

Otherwise I'd suggest to probabky implement a different decorator instead.

[nthiery]

comment:10

Just my 2 cents: I could see use cases for this feature. In particular if the caching strategy could be made configurable at runtime by the user:

class XXX:
    @cached_method
    def f(...): ...

XXX.f.set_input_filter(...)

So if this can be implemented without slowing down the standard use case, I don't see why not?

If the current implementation is deemed to introduce too large of an overhead (time+memory with the extra slot), an alternative might be to implement this feature in a subclass, have set_input_filter change the class of the cached method to this subclass if needed, and have __init__ call set_input_filter when relevant? If it's all pure Cython maybe changing the class is not an option; in this case we would need to choose the class once for all in the factory function, before __init__ is called.

Cheers, Nicolas

[vbraun]

comment:11

Thats still crazy, decorators are a useful metaprogramming tool but you are essentially creating two function bodies that don't / can't talk to each other. If you really want to have a decorator to help with managing the cache then make the decision to cache available inside the function body. E.g.

@sometimes_cached_function
def bar(x, y, z):
   w = do_long_computation(x, y, z)
   if want_to_cache(x, y, z, w):
      bar.set_cache((x, y, z), w)  
      # or some variation thereof that uses the original arguments
   return w

Though really the advantage over

bar_cache = dict()

def bar(x, y, z):
    try:
        return bar_cache[(x,y,z)]
    except KeyError: 
        w = do_long_computation(x, y, z)
    if want_to_cache(x,y,z,w):
        bar_cache[(x,y,z)] = w 
    return w

is pretty slim. You save maybe 2 lines at the expense of making it harder to understand to somebody who doesn't know about the memoization machinery.

[nthiery]

comment:12

I agree that the fact that the two functions can't talk is a limitation. But on the other hand having two functions that clearly decouples the two logics (how to compute / when to cache) does bring something. Especially if it makes the caching strategy user configurable.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:13

Here is a new version which creates a new class. This way nobody is hurt and the feature exists !

Nathann

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e06b947 to 5beca48

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

5beca48

trac #16353: A cached_function with selective memory

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

7eb8f90

trac #16353: A cached_function with selective memory

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 5beca48 to 7eb8f90

[vbraun]

comment:16

comment:11 still applies

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:17

comment:11 still applies

You are welcome to implement what you suggest, for I do not know how to write it. I need the feature I implemented and it is sufficient for my needs.

Nathann

[vbraun]

comment:18

What do you need it for? The original use case that you presented on sage-devel is IMHO invalid.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:19

What do you need it for? The original use case that you presented on sage-devel is IMHO invalid.

Volker, aren't you tired of this ? I need this function, you know it can be useful, you know what I need it for, are you going to prevent me from adding a function because of what I want to use it FOR ?

Nathann

[vbraun]

comment:20

I told you already on sage-devel that you don't need this, the sooner you refactor your code to use sane function names the quicker we can close this ticket as invalid.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:21

I told you already on sage-devel that you don't need this, the sooner you refactor your code to use sane function names the quicker we can close this ticket as invalid.

This ticket is not invalid, this ticket implements a feature I need, and a feature that several other developpers acknowledged as being potentially useful. I don't even get how you can honestly deny that filtering what is being cached, even if the two functions "don't talk", can be useful.

Stop this game and look at the code. It does not slow anything down because it is a new class, it solves my problem and it is clearly the kind of stuff that other persons may need too. There's no reason to refuse it a priori.

Nathann

[vbraun]

comment:22

Even if you would need this functionality (you don't), there is no reason to lock us into a memoization api that (even you agree) isn't good.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:23

Even if you would need this functionality (you don't), there is no reason to lock us into a memoization api that (even you agree) isn't good.

Okay. Now it's my turn. I claim that you are an eagle with 15 arms and 36 beaks, and that you own a pink bright camping-car parked right under the Eiffel Tower. The cops called you yesterday at 10:34, 11:34 and 15:30 and you refused to answer their questions pretending that you had gone mute the day before

Truths:

1) I need this feature. There's nobody that can assert it with more certainty than I. You can say that I don't many times, and truth be told, it changes nothing to the fact that I am still stuck if I can't do that.

2) I have absolutely nothing against the caching method I implement, and I never said that it was not good. I would not write a branch if I thought it was not good and useful for Sage.

Stop talking nonsense.

Nathann

[vbraun]

comment:24

Replying to @nathanncohen:

Okay. Now it's my turn. I claim that you are an eagle with 15 arms and 36 beaks, and that you own a pink bright camping-car parked right under the Eiffel Tower. The cops called you yesterday at 10:34, 11:34 and 15:30 and you refused to answer their questions pretending that you had gone mute the day before

Aaahh I thought that the guy hiding in the shadows looked like you ;-)

1) I need this feature.

No. You happen to have a hammer in your hand, and now everything looks vaguely similar to nails. Trust me, not everything is a nail and there are more elegant solutions to your problem.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:25

No. You happen to have a hammer in your hand, and now everything looks vaguely familiar to nails. Trust me, not everything is a nail and there are more elegant solutions to your problem.

Review this patch of write a better code. This branch implements a mechanism to decide which answers will be cached, and it can be used to only cache the most useful answers of a recursive function.

Nathann

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
-Here is a new `input_filter` argument for cached functions which makes it remember only "some" output, depending on the input. This should not be too ressource-consuming.
+Here is a new `input_filter` argument for cached functions which makes it remember only "some" output, depending on the input.

 Nathann

[mathzeta]

comment:27

Replying to @nathanncohen:

[snip]... and it can be used to only cache the most useful answers of a recursive function.

How do you tell which values are the most useful? Except no-argument functions, I usually don't like the wide spread of cached_method in Sage. One caching strategy that I find useful in practice for recursive functions is LRU (least recently used) cache. In Python 3 it is implement in the functools module: https://docs.python.org/3/library/functools.html#functools.lru_cache and for Python 2 there are already several implementations, like the backport at http://code.activestate.com/recipes/578078-py26-and-py30-backport-of-python-33s-lru-cache/.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:28

Yo !

How do you tell which values are the most useful?

I do not know in general, it depends on the function you are decorating.

Nathann

[kcrisman]

comment:29

1) I need this feature.

No. You happen to have a hammer in your hand, and now everything looks vaguely similar to nails. Trust me, not everything is a nail and there are more elegant solutions to your problem.

Then write the more elegant solution. I agree that we can have feature creep at times, and I'm sure ncohen does too, based on many comments on sage-devel. But if there is some canonical way to do some specific example of Nathann's (obviously not the toy cases in the doctest here) then let's add that to the documentation, so that when other people who want to do what he does show up, they can look at a well-annotated example of why it's so horrible to do this filtering. There's no need to browbeat.

I don't even get how you can honestly deny that filtering what is being cached, even if the two functions "don't talk", can be useful.

Yeah, I'm not sure why this can't be useful either, even if for some reason it doesn't need a new decorator. As a non-cache-expert, I guess Volker's suggestion of

bar_cache = dict()

def bar(x, y, z):
    try:
        return bar_cache[(x,y,z)]
    except KeyError: 
        w = do_long_computation(x, y, z)
    if want_to_cache(x,y,z,w):
        bar_cache[(x,y,z)] = w 
    return w

seems fine too, especially if documented somewhere. There has to be some compromise here; it's not that important. (As opposed to rewriting Sage in Ruby or something.)

---

Naturally, I have no ball in the technicalities of this game. I do have a ball in the game of people getting along enough to not squabble and get personal over this stuff. "The open source community is just so fricking nice" is what we want people to think about when they think of Sage community.

[vbraun]

comment:30

I did sketch how to organize Nathan's original code already at https://groups.google.com/d/msg/sage-devel/OPe5VJpBiB4/OswLwqsMJKcJ. I can make the actual change if Nathan doesn't want do it himself... Honestly, the filtering feature proposed here is only useful to enable dummy flags as arguments to functions to change their behaviour:

@cached_function(filter=lambda x,dummy: dummy)
def foo(x, dummy=False):
    if dummy:
        return bar(x)
    else:
        return baz(x)

If you want to cache bar and not baz then just provide two different functions. And if you can't split up the function easily because they are multiple-page case switches then you need to refactor them regardless of the caching.

[kcrisman]

comment:31

I did sketch how to organize Nathan's original code already at https://groups.google.com/d/msg/sage-devel/OPe5VJpBiB4/OswLwqsMJKcJ.

What I find interesting about this is the quote

No. The tests of the work_for_case_x function go to that function. This ties the tests much better to the implementation than what you currently have.

I agree with that and implemented it earlier but it was refused during a review.

so maybe some of the problem is external to this particular ticket? Maybe in the other review one could ask for a second opinion from elsewhere, always a reasonable thing to do.

designs.orthogonal_array doesn't return some kind of array

Probably that is the real problem. In the current stable branch,

def orthogonal_array(k,n,t=2,check=True):
    r"""
    Return an orthogonal array of parameters `k,n,t`.

And I don't see anywhere in the code, or doctested, that you should get a boolean or an integer. This must be a recent thing (I do see it in 6.3.beta3) and I would definitely agree that was bad design. It seems that #16286 and #15310 were the culprits, I have found it now. (Note to Volker - all those git-induced commits made it very, very hard to track down what should have been extremely straightforward in such a new file! Oh well, I'll get there eventually.)

---

That doesn't mean one can't have a cache with selective memory, but maybe we can disentangle that from the very strange decision made there.

[kcrisman]

comment:32

Okay, see here for some other thoughts on the 'orthogonal' (pun intended) question of this.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:33

Okay guys, you won again ! I will just write three times the same caching mechanism in three different functions, as it is clearly a better design.

Nathann

[kcrisman]

comment:34

Okay guys, you won again ! I will just write three times the same caching mechanism in three different functions, as it is clearly a better design.

? I'm just going to point out that I didn't say anything about caching design (just asked naive questions). Just about finding some compromise. I'm sure something useful and agreeable will come out of this, even if it's from someone else taking up the code later.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:35

Just adding something : unless this ticket is reviewed I will have to implement the caching method manually in 4 different functions.

I also forgot to add another reason for having a function like that :

A cached function cannot (safely) return mutable answers. If you return a list and that the user modifies the list, then it also modifies the list stored in the function's cache.

Thus, as my functions return some mutable answers (lists) which I do not want to cache but I am forced to, I have to turn them into tuples before returning them (which again triggers useless copies later). With the 10 lines from this branch I would be able to say that I don't want to cache those answers. Which I never wanted to cache anyway.

Just saying...

Nathann

[nbruin]

comment:36

Replying to @nathanncohen:

Just adding something : unless this ticket is reviewed I will have to implement the caching method manually in 4 different functions.

I also forgot to add another reason for having a function like that :

A cached function cannot (safely) return mutable answers. If you return a list and that the user modifies the list, then it also modifies the list stored in the function's cache.

You are right in noting that. You could of course document that the result returned shouldn't be modified (but instead copied if modification is needed), and that is probably the most efficient solution for an internal routine, where the caller can then make a copy only when necessary. And indeed, you can enforce (one level at the time) by using tuples.

If you want an always-safe-to-mutate result, you would always need to copy into cache (or copy the result once it's written into the cache), which is not what is proposed on this ticket. In fact, copying is a complicated, data type dependent operation (think tuple of lists, for instance -- how deep do you have to go with copying?)

It seems to me that this additional motivation for using the decorator provides another argument against the utility and wisdom of the proposed decorator for producing clear, readable, and maintainable code.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:37

You are right in noting that. You could of course document that the result returned shouldn't be modified (but instead copied if modification is needed), and that is probably the most efficient solution for an internal routine, where the caller can then make a copy only when necessary. And indeed, you can enforce (one level at the time) by using tuples.

It is not an internal routine.

If you want an always-safe-to-mutate result, you would always need to copy into cache (or copy the result once it's written into the cache), which is not what is proposed on this ticket. In fact, copying is a complicated, data type dependent operation (think tuple of lists, for instance -- how deep do you have to go with copying?)

I repeat : I do NOT want to cache this output.

It seems to me that this additional motivation for using the decorator provides another argument against the utility and wisdom of the proposed decorator for producing clear, readable, and maintainable code.

Understand what you want to understand. I am telling you that I will have to implement 4 times the same code in different functions, and that all my problems could be solved with the clear and understandable lines that this branch implements, at absolutely no cost for anybody else.

The code will less clear because of that, the design files will contain code dedicated to caching that does not belong there, and of course I will be implementing manually what could be done by a decorator.

Waste of time.

Nathann

[nbruin]

comment:38

Replying to @nathanncohen:

It is not an internal routine.

If you want an always-safe-to-mutate result, you would always need to copy into cache (or copy the result once it's written into the cache), which is not what is proposed on this ticket. In fact, copying is a complicated, data type dependent operation (think tuple of lists, for instance -- how deep do you have to go with copying?)

I repeat : I do NOT want to cache this output.

How can you tell from the input parameters whether the caller is going to mutate the result you're returning? Surely a non-internal routine will have uniform input/output specifications, i.e., always return either mutable types or immutable types?

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:39

How can you tell from the input parameters whether the caller is going to mutate the result you're returning?

O_O

It is simple :

1) If I can use the feature implemented in this branch

--> I can only cache the return values I am interested in caching (they are boolean-->immutable) and I can return other values as mutable types, which is their most natural type.

2) If I cannot use the feature implemented in this branch, I have to use cached_method

--> Thus I have to cache everything that my function returns, and so I cannot return immutables types anymore. And I have to return tuples of tuples instead of lists, which complicated matters uselessly.

Surely a non-internal routine will have uniform input/output specifications, i.e., always return either mutable types or immutable types?

No. My function returns booleans or lists of lists, depending on what the user asks. If I have to make it tuples of tuples and cache them for naught, it's a waste for everybody.

With this branch, I can cache only what I want and not have to change what my function returns to fit the cached_method's needs.

Nathann

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:40

(Of course, what I said above is that if I cannot use this branch's code then I will just implement manually the caching mechanism in all 4 functions, because caching everything just isn't a clean solution)

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:41

This ticket is not really waiting for a review, given that it has been refused in its current form. As Karl-Dieter does not want it to be closed as wontfix, I set it to needs_work until somebody changes the implementation. The problem in the combinatorial designs code has been fixed with a specific caching system.

Nathann

[kcrisman]

comment:42

This ticket is not really waiting for a review, given that it has been refused in its current form. As Karl-Dieter does not want it to be closed as wontfix, I set it to needs_work until somebody changes the implementation. The problem in the combinatorial designs code has been fixed with a specific caching system.

This seems reasonable.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Changed author from Nathann Cohen to none