Opened 5 years ago

Last modified 5 years ago

#16353 needs_work enhancement

A cached_function with selective memory

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.4
Component: performance Keywords:
Cc: dkrenn, vdelecroix Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: u/ncohen/16353 (Commits) Commit: 7eb8f900f1a143c6cc85b9382a365b57a9c42ecc
Dependencies: Stopgaps:

Description (last modified by ncohen)

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

Nathann

Change History (44)

comment:1 Changed 5 years ago by ncohen

  • Branch set to u/ncohen/16353
  • Status changed from new to needs_review

comment:2 Changed 5 years ago by git

  • Commit set to e06b947ab12f9f754363847c996b251f5682c125

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

e06b947trac #16353: A cached_function with selective memory

comment:3 follow-ups: Changed 5 years ago by vbraun

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

comment:4 in reply to: ↑ 3 Changed 5 years ago by ncohen

-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

comment:5 Changed 5 years ago by ncohen

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

Nathann

comment:6 in reply to: ↑ 3 Changed 5 years ago by elixyre

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...

comment:7 follow-ups: Changed 5 years ago by nbruin

-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.

comment:8 in reply to: ↑ 7 Changed 5 years ago by ncohen

-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

comment:9 in reply to: ↑ 7 Changed 5 years ago by leif

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.

comment:10 Changed 5 years ago by nthiery

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

comment:11 Changed 5 years ago by vbraun

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.

comment:12 Changed 5 years ago by nthiery

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.

comment:13 Changed 5 years ago by ncohen

  • Cc vdelecroix added

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

Nathann

comment:14 Changed 5 years ago by git

  • Commit changed from e06b947ab12f9f754363847c996b251f5682c125 to 5beca48866f16c29e71a00ae0f9bbfe6eaa80e50

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

5beca48trac #16353: A cached_function with selective memory

comment:15 Changed 5 years ago by git

  • Commit changed from 5beca48866f16c29e71a00ae0f9bbfe6eaa80e50 to 7eb8f900f1a143c6cc85b9382a365b57a9c42ecc

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

7eb8f90trac #16353: A cached_function with selective memory

comment:16 follow-up: Changed 5 years ago by vbraun

comment:11 still applies

comment:17 in reply to: ↑ 16 Changed 5 years ago by ncohen

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

comment:18 follow-up: Changed 5 years ago by vbraun

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

comment:19 in reply to: ↑ 18 Changed 5 years ago by ncohen

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

comment:20 follow-up: Changed 5 years ago by vbraun

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.

comment:21 in reply to: ↑ 20 Changed 5 years ago by ncohen

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

comment:22 follow-up: Changed 5 years ago by vbraun

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.

comment:23 in reply to: ↑ 22 ; follow-up: Changed 5 years ago by ncohen

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

comment:24 in reply to: ↑ 23 ; follow-ups: Changed 5 years ago by vbraun

Replying to ncohen:

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.

Last edited 5 years ago by vbraun (previous) (diff)

comment:25 in reply to: ↑ 24 ; follow-up: Changed 5 years ago by ncohen

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

comment:26 Changed 5 years ago by ncohen

  • Description modified (diff)

comment:27 in reply to: ↑ 25 ; follow-up: Changed 5 years ago by mathzeta2

Replying to ncohen:

[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/.

comment:28 in reply to: ↑ 27 Changed 5 years ago by ncohen

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

comment:29 in reply to: ↑ 24 Changed 5 years ago by kcrisman

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.

comment:30 follow-up: Changed 5 years ago by vbraun

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.

comment:31 in reply to: ↑ 30 Changed 5 years ago by kcrisman

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.

comment:32 Changed 5 years ago by kcrisman

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

comment:33 follow-up: Changed 5 years ago by ncohen

  • Milestone changed from sage-6.3 to sage-duplicate/invalid/wontfix
  • Status changed from needs_review to positive_review

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

comment:34 in reply to: ↑ 33 Changed 5 years ago by kcrisman

  • Milestone changed from sage-duplicate/invalid/wontfix to sage-6.3
  • Status changed from positive_review to needs_review

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.

comment:35 follow-up: Changed 5 years ago by ncohen

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

comment:36 in reply to: ↑ 35 ; follow-up: Changed 5 years ago by nbruin

Replying to ncohen:

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.

comment:37 in reply to: ↑ 36 ; follow-up: Changed 5 years ago by ncohen

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

comment:38 in reply to: ↑ 37 ; follow-up: Changed 5 years ago by nbruin

Replying to ncohen:

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?

comment:39 in reply to: ↑ 38 Changed 5 years ago by ncohen

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

Last edited 5 years ago by ncohen (previous) (diff)

comment:40 Changed 5 years ago by ncohen

(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)

comment:41 follow-up: Changed 5 years ago by ncohen

  • Status changed from needs_review to needs_work

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

comment:42 in reply to: ↑ 41 Changed 5 years ago by kcrisman

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.

comment:43 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:44 Changed 5 years ago by ncohen

  • Authors Nathann Cohen deleted
Note: See TracTickets for help on using tickets.