Under the Cover

See also [http://github.com/maxifier/mxcache/wiki/Building-MxCache](Building MxCache)

Here is class diagram how it really works under the cover:

For each cached method MxCache creates a set of objects:

• One Stored<Key><Value>Cache instance per cache owner instace;
• One <Key><Value>Storage instance per cache owner instace;
• One DependencyNode instance per cache owner instance or per all instaces (in case of static dependency tracking);
• One MutableStatisticsImpl instance per all instances (but in case of per-instance statistics there might be one per instance);
• One KeyValueCalculable instance (generated code) per all instances.

###Generated Code For each cached method MxCache generates:

• a single one-line class Calculatable that delegates call to original class;
• a single field that holds cache reference;
• a single method that delegates call to cache;
• it renames original method, say if it is called getFoo(), it will be renamed as getFoo$create$0().

Example. Imagine you have class like that:

import com.maxifier.mxcache.Cached;

public class Main {
    @Cached
    static long C(int n, int k) {
        if(n < 0 || k < 0 || k > n) {
            return 0;
        }
        if(k == 0 || k == n) {
            return 1;
        }
        return C(n-1, k-1) + C(n-1, k);
    }

    public static void main(String[] args) {
        long t1 = System.currentTimeMillis();
        System.out.println(C(30, 15));
        long t2 = System.currentTimeMillis();
        System.out.println("Time = " + (t2 - t1));
    }
}

MxCache will generate something like the following (this code was obtained by decompiling mxcache-instrumented class and beautifying the result):

import com.maxifier.mxcache.CacheFactory;
import com.maxifier.mxcache.caches.Cache;
import com.maxifier.mxcache.caches.ObjectLongCache;
import com.maxifier.mxcache.caches.ObjectLongCalculatable;
import com.maxifier.mxcache.context.CacheContext;
import com.maxifier.mxcache.tuple.TupleGenerator;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.util.List;

public class Main {
    // this is generated cache references
    // it is package local because Cleanable needs to access it
    static transient ObjectLongCache C$cache$0;
    // cached objects support serialization, and they have exactly the same serialVersionUID as if there were no caches.
    // MxCache generates this field if no serialVersionUID field was there before.
    static final long serialVersionUID = 0x886ab23e5dfd7c0cL;
    private void readObject(ObjectInputStream objectinputstream) throws ClassNotFoundException, IOException {
        registerCache(CacheFactory.getContext(objectinputstream));
        objectinputstream.defaultReadObject();
    }
 
    // This class takes care of extracting cache references from the instance
    // The instace itself is the only place where caches are stored and the only place MxCache get references back from.
    private static class Cleanable implements com.maxifier.mxcache.clean.Cleanable<Main> {
        public void appendStaticCachesTo(List list) {
            list.add(Main.C$cache$0);
        }

        public Cache getStaticCache(int i) {
            switch (i) {
                case 0: return Main.C$cache$0;
            }
            throw new IllegalArgumentException("Invalid cache id");
        }

        public void appendInstanceCachesTo(List list, Main obj) {
            // no instance caches -> nothing to append
        }

        public Cache getInstanceCache(Main obj, int i) {
            throw new IllegalArgumentException("Invalid cache id");
        }
    }
 
    static {
        registerStatic();
    }

    public Main() {
        registerCache(CacheFactory.getDefaultContext());
    }
 
    private static void registerStatic() {
        CacheFactory.registerClass(Main.class, new Cleanable(), /* groups */ null, /* tags */ null);

        // We ask TupleGenerator to generate class
        // Tuple is used to hold references to cache parameters, so we need this class before we can actually proceed.
        // See below for an example of generated tuple class.
        TupleGenerator.getTupleClass(int.class, int.class);

        // When MxCache needs to invoke actual method that performs calculations, it uses Calculable to refer to it.
        class Calculable$C$_cls0 implements ObjectLongCalculatable<Tuple$II> {
            // arguments get there wrapped to tuple there
            public long calculate(Object obj, Tuple$II key) {
                // obj is ignored as this calculable represents static method
                return Main.C$create(key.getElement0(), key.getElement1());
            }
        }
 
        // first register all caches found in the class
        CacheFactory.registerCache(Main.class, 0, Tuple$II.class, Long.TYPE, /* groups */ null, /* tags */ null, new Calculable$C$_cls0(), /* Method name */ "C", /* Method signature */ "(II)J");
 
        // than instantiate caches
        C$cache$0 = (ObjectLongCache) CacheFactory.createCache(Main.class, 0, /* instance, null for static caches */ null); 
    }

    private void registerCache(CacheContext cachecontext) {
        CacheFactory.registerInstance(this, Main.class);
    }
 
    static long C(int i, int j) { 
        if (C$cache$0 == null) {
            throw new IllegalStateException("@Cached method Main#C(II)J is called before cache is initialized.\nIt usually happens when @Cached method overrides superclass method, and this method is called from superclass constructor somehow before\nconstructor of class containing the cache finished, e.g. when superclass constructor invokes SwingWorker that makes use of this cached method");
        }
        // not that two arguments are wrapped into Tuple
        return C$cache$0.getOrCreate(new Tuple$II(i, j));
    }

    // this method contains original code from method C.
    static long C$create(int n, int k) {
        if(n < 0 || k < 0 || k > n) {
            return 0;
        }
        if(k == 0 || k == n) {
            return 1;
        }
        return C(n-1, k-1) + C(n-1, k);
    }

    public static void main(String args[]) {
        long t1 = System.currentTimeMillis();
        System.out.println(C(30, 15));
        long t2 = System.currentTimeMillis();
        System.out.println("Time = " + (t2 - t1));
    }  
}

Please note that actually source code of your class is not altered - the modifications are done directly in bytecode.

All the source code listed above is obtained by decompilation of resulting bytecode. Actually MxCache contains a lot of generated code. There's a Calculable, Cache, Storage, etc. class for any combination of reference and primitive types, e.g.

• ObjectObjectCache;
• IntObjectCache;
• ObjectLongCache;
• FloatDoubleCache.

All such classes are generated from template with Generate class.

###Locks There are two distinct types of caches and storages in MxCache:

• simple that hold a lock for the whole cache;
• element-locked caches that can lock a single element and not entire cache.

When cache is being cleaned, MxCache walks over the dependency graph and marks the necessary caches as 'dirty'. The 'dirty' cache would be cleaned immediately if the lock of this cache is not occupied. If the lock is held by someone, the cache will be invalidated right before the lock is released.

###Resources & Dependency-Tracking Each cache holds a reference to DependencyNode that contains all the information about dependencies between caches. Cached method A is considered dependent on cache B if cached method A has ever called cached method B.

Each DependencyNode contains a list of caches that belong to it (usually only one, in this case a special SingletonDependencyNode implementation is used), and a list of references to DependencyNodes of dependent caches.

When a cached method enters stack, it puts a notice of that to a special ThreadLocal, and remembers, who was on the top before. DependencyTracker class takes care of it:

DependencyNode callerNode = DependencyTracker.track(getDependencyNode());
try {
  ...the logic goes here...
} finally {
  DependencyTracker.exit(callerNode);
}

DependencyTracker also marks the node that was on the top before as dependant node of current node.

Resource holds read-write lock inside.

When someone calls Resource.readStart(), the resource checks who is on the top, and marks this one as dependant.

When someone calls Resource.writeEnd(), MxCache collects the list of dependent caches, locks it, releases Resource lock and then clears all dependent nodes.

Resource.clearDependentCaches() first locks write lock, and then does the same thing like writeEnd().

---

Q: Isn't it too expensive from performance prospective?

A: No, querying of ThreadLocal takes only a few ns in modern JVM, and I believe it's not a hige cost for such a feature as dependency tracking. Cleaning of Dependant Caches

When MxCache wants to clear something, it first traverses all dependency tree (depth-first).

After acquiring the whole list, it locks it at once (see Locking Procedure). When all locks are aquired, MxCache tries to acquire list again, and proceeds with cleaning only if the list hasn't changed. If the list is changed, it releases any locks held and starts everything from scratch.

###Resource Views When MxCache traverses dependency tree and finds a ResourceView, it first checks that corresponding method return value has changed and proceeds with the subtree of the node only if it has really changed.

This logic is incapsulated in a special type of DependencyNodes: ViewableMultiple<ValueType>DependencyNode and ViewableSingleton<Type>DependencyNode where Type is return type of cached method.

###Complex Keys With MxCache you can use complex keys, i.e. methods that has more than one arguments.

In this case all arguments are wrapped into Tuple. A separate Tuple implementation will be generated for each argument type combination, all Objects are erased to Object.

TupleGenerator generates tuple class for each generic tuple type. Here is an example of generated tuple class:

class Tuple$II extends Tuple {
    public final int $0;
    public final int $1;

    public Tuple$II(int i, int j) {
        $0 = i;
        $1 = j;
    }

    public int getElement0() {
        return $0;
    }

    public int getElement1() {
        return $1;
    }

    public Object get(int i) {
        switch (i) {
            case 0: return $0;
            case 1: return $1;
        }
        throw new IllegalArgumentException("Tuple " + this + " doesn't contain element with index " + i);
    }

    // There are also methods getBoolean(), getByte(), getChar(), getShort(), getFloat(), getDouble().
    // All of them throw IllegalArgumentException.

    public int getInt(int i) {
        switch (i) {
            case 0: return $0;
            case 1: return $1;
        }
        throw new IllegalArgumentException("Tuple " + this + " doesn't contain element with index " + i);
    }

    public long getLong(int i) {
        switch (i) {
            case 0: return $0;
            case 1: return $1;
        }
        throw new IllegalArgumentException("Tuple " + this + " doesn't contain element with index " + i);
    }

    public int size() {
        return 2;
    }

    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (!(obj instanceof Tuple$II)) {
            return false;
        }
        Tuple$II that = (Tuple$II) obj;
        return $0 == that.$0 && $1 == that.$1;
    }

    public int hashCode() {
        return (31 + $0) * 31 + $1;
    }

    public String toString() {
        return "Tuple<int, int>(" + $0 + ", " + $1 + ")";
    }
}

Please note that actually source code for tuple classes is never generated - they are generated directly in bytecode.

All the source code listed is obtained by decompilation of resulting bytecode.

###Wrapping of Primitive Strategies & Transformations With MxCache you can use a strategy that supports only Object/Object variant even for primitive caches (i.e. if your strategy extends ObjectObjectStorage, you can still use it even if your method look like long getSomething(int key)).

It is done by wrapping your cache with cache instance that wraps arguments. The same approach is used for transforming of keys and values: a wrapper is generated that calls specified methods.