Sonntag, 17. März 2013

Fun with Active Annotations: Memoization

With the next release of Xtend only 3 days away, I did some experimenting with the latest language feature: active annotations. In short, active annotations allow you to participate in the Xtend-to-Java compilation process, altering the AST or even generating whole new classes and resources. But not only that: Any change you make is automatically visible in content assist, the outline view, navigation etc. Plus, you can add errors and warnings to the Xtend source.

My first idea was to build an annotation that can memoize any method. Memoization means remembering the return value for given parameters and returning this cached value when the method is called again with the same parameters. This is useful for expensive calculations and recursive algorithms.

So I want this Xtend code

to compile into this Java code

This is done by the following annotation processor. It has different handling for 0, 1 and multiple parameters to optimize performance.

As you can see, the body of the method is replaced with a call to a cache. The cache is populated with values from an initializer method that has the body of the original method. For methods without parameters, I just use double null check synchronization. For everything else there is Guava's wonderful LoadingCache. For methods with one parameter, the cache key is the type of the single paramter. For methods with multiple paramters, I added a small helper class that holds an array of parameters and provides an equals and hashcode method. Some of the finer points like exception handling, method overloading and primitive types are also handled by the annotation processor in order to generate production quality code.

This could be further expanded with expiration strategies and other options defined in the annotation. But for now, I'm pretty pleased with the results. Getting the 40th fibonacci number takes only 1 millisecond on my laptop. Without memoization, this goes up to 5 full seconds.