Groovy
  1. Groovy
  2. GROOVY-4993

@Memoized AST Transformation for Methods

    Details

    • Type: New Feature New Feature
    • Status: Closed
    • Priority: Minor Minor
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 2.2.0-beta-1
    • Component/s: None
    • Labels:

      Description

      The whole idea is similar to existing great @Lazy annotation, but it differs in concept: instead of being applied to fields it is applied to methods, thus providing a wider field of use. When applied to getters it serves as an alternative to @Lazy, but applied to other methods it provides what @Lazy can't. Thus it eliminates the need for heavy refactoring in certain situations, by simply letting the user add the annotation to the method.

      Here is a suggestion of how it could work:

      @Cached
      T createX() {
        new T(1, 2, 3)
      }   
      

      gets transformed into:

      private T $createX$result
      T $createX() {
        new T(1, 2, 3)
      }
      T createX() {
        T $result_local = $createX$result
        if ($result_local != null)
          return $result_local
        else {
          synchronized (this) {
            if ($createX$result == null) {
              $createX$result = $createX()
            }
            return $createX$result
          }
        }
      }
      

      This whole thing could be extended to cache different results of a method depending on its arguments, but it's a topic for a discussion.

        Activity

        Hide
        thurston n added a comment -

        The suggested transformation is an example of the (in)famous double-checked locking--which is not multi-thread safe as written.
        In order for the code to be multi-thread safe, the variable must be declared volatile

        private volatile T $createX$result 
        

        The change in the JMM that guarantees mult-thread safety is as of JDK 1.5 IIRC

        Show
        thurston n added a comment - The suggested transformation is an example of the (in)famous double-checked locking--which is not multi-thread safe as written. In order for the code to be multi-thread safe, the variable must be declared volatile private volatile T $createX$result The change in the JMM that guarantees mult-thread safety is as of JDK 1.5 IIRC
        Hide
        Jochen Theodorou added a comment -

        I agree, as long as the part asking $createX$result is not synchronized with the part writing it, you have a multithreading issue.... unless your class is otherwise immutable (final fields only) and if it doesn't matter if $createX is called multiple times, then it will work as well.

        Show
        Jochen Theodorou added a comment - I agree, as long as the part asking $createX$result is not synchronized with the part writing it, you have a multithreading issue.... unless your class is otherwise immutable (final fields only) and if it doesn't matter if $createX is called multiple times, then it will work as well.
        Hide
        thurston n added a comment -

        Hmmm, maybe I don't understand the purpose of the @Cached annotation.
        Of course you could do:

        private final T $createX$result = createX(); //with proper tranform of createX to check for null of course
        

        that would also be multi-thread safe. But what would the meaning of @Cached be?
        Anyways, volatile will make the example code multi-thread safe as written

        Show
        thurston n added a comment - Hmmm, maybe I don't understand the purpose of the @Cached annotation. Of course you could do: private final T $createX$result = createX(); //with proper tranform of createX to check for null of course that would also be multi-thread safe. But what would the meaning of @Cached be? Anyways, volatile will make the example code multi-thread safe as written
        Hide
        Nikita Y Volkov added a comment -

        What I was proposing here was actually called Memoization. You'll find the answers to all the questions about it on the link provided. I didn't know about it at the time, so there are several things I'd like to change about this proposition now:
        1. Change the annotation name to `@Memoized`
        2. Make the methods marked with it cache results in a hash table by arguments list

        About the implementation - I can't comment on it.

        Show
        Nikita Y Volkov added a comment - What I was proposing here was actually called Memoization . You'll find the answers to all the questions about it on the link provided. I didn't know about it at the time, so there are several things I'd like to change about this proposition now: 1. Change the annotation name to `@Memoized` 2. Make the methods marked with it cache results in a hash table by arguments list About the implementation - I can't comment on it.
        Hide
        thurston n added a comment -

        Is memoization applicable to a method that returns a new instance of an object (as in the example provided)?
        That's an interesting question.
        I always thought of memoization as applying to things like calculating factorials or sorting a provided list. Although, I guess you could argue that at least in the 2nd case you're returning a new List.
        Does the returned object have to be immutable?
        I was thinking that @Cached just literally meant:
        1. if method is being invoked on instance A for the first time, then execute the method and return result
        2. else, then return result of #1 (skipping execution of the method).
        I guess that's a looser form of memoization; I guess the language formalists will have to render judgment

        Show
        thurston n added a comment - Is memoization applicable to a method that returns a new instance of an object (as in the example provided)? That's an interesting question. I always thought of memoization as applying to things like calculating factorials or sorting a provided list. Although, I guess you could argue that at least in the 2nd case you're returning a new List. Does the returned object have to be immutable? I was thinking that @Cached just literally meant: 1. if method is being invoked on instance A for the first time, then execute the method and return result 2. else, then return result of #1 (skipping execution of the method). I guess that's a looser form of memoization; I guess the language formalists will have to render judgment
        Hide
        Nikita Y Volkov added a comment - - edited

        If I understand you correctly that's a tighter implementation you're talking about (and what I was originally talking about in this proposal), i.e. memoizing a method with an argument list equal to [] (an empty list). The first time this method gets called with the argument list equal to [] it calculates the result, caches it in a hash table like so: cache[[]] = result and returns the result. Every other time it's called it simply returns cache[[]].

        Storing the results in a hash table allows to also cache all the other executions of this method, for instance, calling it with an argument list [1231, "asdfa"] will at first execution create another record in the cache like so: cache[[1231, "asdfa"]] = result and return it all the other times the method gets called with arguments [1231, "asdfa"].

        This technique has a very wide application range, not just math calculations - basically, any side-effectless method. For instance parsing the same file, of which you know that it didn't change, making a remote request which you know to bring you the same result - basically any operation you know to take longer than a hash-table search.

        This technique will require additional RAM, but then again it will still be managed garbage collector.

        On the question about restricting it to immutables only - i think it would be an overcomplication. The user of the feature should know what he's doing, otherwise he doesn't have a reason to do it. Any kind of restriction would be an overcomplication resulting in excessive calculations actually since since it's a dynamic language, and again since it's a dynamic language it won't make sense anyway. This feature really is a basic stuff.

        Show
        Nikita Y Volkov added a comment - - edited If I understand you correctly that's a tighter implementation you're talking about (and what I was originally talking about in this proposal), i.e. memoizing a method with an argument list equal to [] (an empty list). The first time this method gets called with the argument list equal to [] it calculates the result, caches it in a hash table like so: cache[[]] = result and returns the result. Every other time it's called it simply returns cache[[]] . Storing the results in a hash table allows to also cache all the other executions of this method, for instance, calling it with an argument list [1231, "asdfa"] will at first execution create another record in the cache like so: cache[ [1231, "asdfa"] ] = result and return it all the other times the method gets called with arguments [1231, "asdfa"] . This technique has a very wide application range, not just math calculations - basically, any side-effectless method. For instance parsing the same file, of which you know that it didn't change, making a remote request which you know to bring you the same result - basically any operation you know to take longer than a hash-table search. This technique will require additional RAM, but then again it will still be managed garbage collector. On the question about restricting it to immutables only - i think it would be an overcomplication. The user of the feature should know what he's doing, otherwise he doesn't have a reason to do it. Any kind of restriction would be an overcomplication resulting in excessive calculations actually since since it's a dynamic language, and again since it's a dynamic language it won't make sense anyway. This feature really is a basic stuff.
        Hide
        Jochen Theodorou added a comment -

        Nikita forget about my comment before, I misunderstood the proposal. If you look at http://roshandawrani.wordpress.com/2010/10/18/groovy-new-feature-closures-can-now-memorize-their-results/ then you can read that Groovy now provides a way to use memoization, but for Closures only. You want to extend that to methods through a static annotation?

        Show
        Jochen Theodorou added a comment - Nikita forget about my comment before, I misunderstood the proposal. If you look at http://roshandawrani.wordpress.com/2010/10/18/groovy-new-feature-closures-can-now-memorize-their-results/ then you can read that Groovy now provides a way to use memoization, but for Closures only. You want to extend that to methods through a static annotation?
        Hide
        Nikita Y Volkov added a comment -

        I believe that this annotation has at least as many rights to be as @Lazy.

        The most evident advantage it will provide is handy optimization: the developer will be able to simply go thru his code and just mark the appropriate methods @Memoized and see the performance boost right away, without changing a single statement in the actual program code. Most times the developer won't even need to analyze the code - just looking at the method name will give him enough information to make a decision whether it should be memoized. All this and not only is not the case with closures.

        Show
        Nikita Y Volkov added a comment - I believe that this annotation has at least as many rights to be as @Lazy . The most evident advantage it will provide is handy optimization: the developer will be able to simply go thru his code and just mark the appropriate methods @Memoized and see the performance boost right away, without changing a single statement in the actual program code. Most times the developer won't even need to analyze the code - just looking at the method name will give him enough information to make a decision whether it should be memoized. All this and not only is not the case with closures.
        Hide
        Guillaume Delcroix added a comment -

        I quite like the idea of having @Memoized that'd work for methods the same as it does for closures with the memoize() function.

        Show
        Guillaume Delcroix added a comment - I quite like the idea of having @Memoized that'd work for methods the same as it does for closures with the memoize() function.
        Hide
        Andrey Bloschetsov added a comment - - edited

        Someone is now engaged with this functionality? I think I could implement this.

        Show
        Andrey Bloschetsov added a comment - - edited Someone is now engaged with this functionality? I think I could implement this.
        Hide
        Paul King added a comment -

        Andrey, I don't believe anyone is working on this at the moment. It would be great if someone could!

        It might pay to sketch your design here first before doing too much work. Ideas which have been discussed in the community seem to gain acceptance the quickest - but if you provide a method variant of the Closure memoize you probably will be close to what will be deemed most useful.

        Show
        Paul King added a comment - Andrey, I don't believe anyone is working on this at the moment. It would be great if someone could! It might pay to sketch your design here first before doing too much work. Ideas which have been discussed in the community seem to gain acceptance the quickest - but if you provide a method variant of the Closure memoize you probably will be close to what will be deemed most useful.
        Hide
        Andrey Bloschetsov added a comment - - edited

        The main points of the implementation:

        • Annotation name is Memoized;
        • Sketch of ASTTransformation implementation:
              public void visit(ASTNode[] nodes, SourceUnit source) {
                  // check params
          
                  AnnotatedNode annNode = (AnnotatedNode) nodes[1];
                  if (annNode instanceof MethodNode) {
                      AnnotationNode ann = (AnnotationNode) nodes[0];
                      if (!MY_TYPE.equals(ann.getClassNode())) {
                          MethodNode methodNode = (MethodNode) annNode;
                          Statement origCode = methodNode.getCode(); // get original code from method
                          Closure<?> closure = null; // TODO create closure with origCode call
                          closure = Memoize.buildMemoizeFunction(new UnlimitedConcurrentCache(), closure); // memoize closure
                          Statement newCode = null; // TODO create statement that call closure and return result
                          methodNode.setCode(newCode);
                      }
                  }
              }
          
        Show
        Andrey Bloschetsov added a comment - - edited The main points of the implementation: Annotation name is Memoized; Sketch of ASTTransformation implementation: public void visit(ASTNode[] nodes, SourceUnit source) { // check params AnnotatedNode annNode = (AnnotatedNode) nodes[1]; if (annNode instanceof MethodNode) { AnnotationNode ann = (AnnotationNode) nodes[0]; if (!MY_TYPE.equals(ann.getClassNode())) { MethodNode methodNode = (MethodNode) annNode; Statement origCode = methodNode.getCode(); // get original code from method Closure<?> closure = null ; // TODO create closure with origCode call closure = Memoize.buildMemoizeFunction( new UnlimitedConcurrentCache(), closure); // memoize closure Statement newCode = null ; // TODO create statement that call closure and return result methodNode.setCode(newCode); } } }
        Hide
        Andrey Bloschetsov added a comment -

        I sent a pull request: https://github.com/groovy/groovy-core/pull/154
        If there are any comments, please let me know.

        Show
        Andrey Bloschetsov added a comment - I sent a pull request: https://github.com/groovy/groovy-core/pull/154 If there are any comments, please let me know.
        Hide
        Andrey Bloschetsov added a comment -

        In the next iteration I could add:

        • Annotation parameters for realization through Closure.memoizeAtLeast, Closure.memoizeAtMost and Closure.memoizeBetween;
        • Handler for abstract methods;
        • Handler for methods that return the void.
        Show
        Andrey Bloschetsov added a comment - In the next iteration I could add: Annotation parameters for realization through Closure.memoizeAtLeast, Closure.memoizeAtMost and Closure.memoizeBetween; Handler for abstract methods; Handler for methods that return the void.
        Hide
        Paul King added a comment -

        Added some comments to the pull request

        Show
        Paul King added a comment - Added some comments to the pull request
        Hide
        Paul King added a comment -

        pull request applied thanks to Andrey Bloschetsov

        Show
        Paul King added a comment - pull request applied thanks to Andrey Bloschetsov

          People

          • Assignee:
            Paul King
            Reporter:
            Nikita Y Volkov
          • Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development