package-summary

Documentation of 'javolution37.javolution.realtime.package-summary' Java class javolution37.javolution.realtime

Overview
Package
Class

All Classes

Interface Summary
Interface	Description
Realtime	This interface identifies classes whose instances can be moved to different `ObjectSpace` for higher performance and higher predictability.

Class Summary
Class	Description
ConcurrentContext	This class represents a concurrent context; it is used to accelerate execution of concurrent algorithms on multi-processors systems.
ConcurrentContext.Logic	This abstract class represents some parameterized code which may be executed concurrently.
ConcurrentThread	This class represents "worker" threads employed by `ConcurrentContext` to perform concurrent execution on multi-processors systems.
Context	This class represents a real-time context; they are typically thread-local but they can also be associated to particular objects.
HeapContext	This class represents a heap context; it is used to allocate objects from the heap exclusively.
LocalContext	This class represents a local context; it is used to define locally scoped setting through the use of `LocalReference` typically wrapped within a static method.
LocalReference<T>	This class represents a reference whose setting is local to the current `LocalContext`; setting outside of any `LocalContext` scope affects the reference default value (equivalent to `LocalReference.setDefault(T)`).
LogContext	This class represents a logging context; it allows for object-based/thread-based logging and logging specializations (such as `StandardLog` to leverage `java.util.logging` capabilities).
ObjectFactory<T>	This class represents an object factory; it allows for object recycling and pre-allocation.
ObjectPool<T>	This abstract class represents an object pool managed by a `PoolContext`.
PoolContext	This class represents a pool context; it is used to recycle objects transparently, reduce memory allocation and avoid garbage collection.
Realtime.ObjectSpace	This class represents an object space which determinates when object recycling occurs.
RealtimeObject	This class provides a default implementation of the `Realtime` interface.
RealtimeObject.Factory<T extends RealtimeObject>	This abstract class represents the factory responsible for the creation of `RealtimeObject` instances.
StackReference<T>	This class encapsulates a reference allocated on the current stack when executing in `PoolContext`.

Exception Summary
Exception	Description
ConcurrentException	This class encapsulates errors or exceptions raised during the execution of concurrent threads (`ConcurrentException` are raised upon exit of the `ConcurrentContext`).

Package javolution37.javolution.realtime Description

Provides real-time javolution.realtime.Context for higher performance and higher predictability of Java bytecode execution.

Overview:

This package provides thread-local contexts integrated with the Real-Time Specification for Java (RTSJ). They can be used to significantly decrease the "worst-case" execution time, leverage most of RTSJ capabilities and reduce/eliminate the need for object creation and garbage collection.

Reducing "worst-case" execution time.

There are many factors impacting the "worst-case" execution time among them just-in-time compilation, garbage collection, class initialization (see "Validating Java for Safety Critical Applications" for an overview). Unexpected delays can be reduced through Ahead-Of-Time compilation, Realtime/Incremental Garbage Collection, ClassInitializer and time-deterministic collections classes. Still, the first time an operation is performed is often the "worst-case" time because of the initial objects creation which occurs then. To address this issue, Javolution allows thread-local contexts to be serialized/deserialized and loaded at start-up. Then, applications threads have consistent, fast performance from start to end! For example:

    public class MyPeriodicThread extends NoHeapRealtimeThread {
        // Retrieves pool context "sized" from previous execution profile. 
        InputStream xml = MyPeriodicThread.class.getResourceAsStream("/pool-" + getName() + ".xml");
        PoolContext pool = (xml != null) ? (PoolContext) new ObjectReader().read(xml) : new PoolContext();
        public void run() {
            while (!terminate) {
                Context.enter(pool);
                try {
                    ... // Consistently fast, factory-produced objects have already been created.
                } finally {
                    Context.exit(pool); // Recycles all pool objects to the exception of the ones preserved.
                }
                RealtimeThread.waitForNextPeriod();
            }
            // Saves pool context (optional).
            new ObjectWriter().write(pool, new FileOutputStream("bin/pool-" + getName() + ".xml"));
        }
    }

Note: Worst case execution time can be decreased even further by using PersistentReference to hold global data time consuming to regenerate.

Leveraging RTSJ capabilities.
The Javolution library is the first library to be fully RTSJ compliant. For example, if the capacity of a collection increases, the extension part is allocated from the same memory area as the collection itself (regardless of the current memory area). Reusable can be static (allocated in ImmortalMemory) and safely used by any real-time threads. Similarly, contexts can be allocated in a specific memory area and their behavior is not affected by the current thread execution area. In other words, NoHeapRealTimeThread may run in ScopedMemory and create (through factories) persistent objects from a PoolContext in ImmortalMemory with Javolution doing the recycling (necessary as ImmortalMemory is never garbage collected).
It should be noted that the standard Java library is not RTSJ-Safe and its use is likely to result in run-time errors or memory leaks with RTSJ VMs (see collection classes presentation). The following illustrates a typical problem with static class members (automatically allocated in ImmortalMemory with RTSJ VMs):public class XmlFormat { // RTSJ Unsafe! Memory leaks (when entries removed) or IllegalAssignmentError (when new entries while in ScopedArea). static HashMap<Class, XmlFormat> ClassToFormat = HashMap<Class, XmlFormat>(); // RTSJ Safe! Removed entries are internally recycled, new entries are in ImmortalMemory. static FastMap<Class, XmlFormat> ClassToFormat = FastMap<Class, XmlFormat>(); }
Reducing Object Creation / Garbage Collection.
The cost of allocating large objects (or arrays) is still significant (memory has to be allocated, initialized and later garbage collected). This cost is somewhat proportional to the size of the object being allocated. To drastically increase the execution speed, applications may create new objects through factories and allow for transparent object recycling and/or pre-allocation at start-up.

FAQ:

I am writing an application using third party libraries. I cannot avoid GC unless I get the source and patch it to Javolution. Can I still make my application real-time ?
You cannot get determinism using "any" library (including Java standard library) regardless of the garbage collector issue. Array resizing, lazy initialization, map rehashing (...) would all introduce unexpected delays (this is why Javolution comes with its own real-time collection implementation). Still, you have several options:
- Use incremental/real-time collectors (if few milliseconds delays are acceptable). These collectors work faster if you limit the amount of garbage produced (e.g. using pool contexts).
- Run your real-time code using a NoHeapRealtimeThread at higher priority than the garbage collector. This may require using pool contexts in ImmortalMemory for persistency (as ScopedArea can only be used for temporary objects).
Can you explain a little how the PoolContext works? I looked at the example code in the Javadoc, and I'm still a little fuzzy on where and what the "magic" is that it performs...
The basic idea is to associate objects pools to Java threads. These pools can be nested, with the heap being the root of all pools. You may consider pools' objects as part of the thread stack memory, with pools being pushed and popped as the thread enters/exits PoolContext. To allocate from its stack, a thread needs to execute within a pool context and create new objects using factories (the "new" keyword always allocates on the heap, Javolution does not/cannot change the Java Virtual Machine behavior). This mechanism is similar to the allocation on the stack of locally declared primitive variables, but now extended to non-primitive types.

Classes encapsulating calls to object factories within factory methods (e.g. valueOf(...)) and whose methods do not create temporary objects on the heap are known as "real-time compliant".

How do I make my own classes real-time compliant?

The simplest way is to extend RealtimeObject and use a factory to create new instances. For example:

    public static final class Coordinates extends RealtimeObject {
        private double _latitude;
        private double _longitude;        
        private static final Factory<Coordinates> FACTORY = new Factory<Coordinates>() {
              protected Coordinates create() {
                  return new Coordinates();
              }
        };
        public Coordinates(double latitude, double longitude) {
            _latitude = latitude;
            _longitude = longitude;
        } 
        private Coordinates() {} 
        public static Coordinates valueOf(double latitude, double longitude) {
            Coordinates c = FACTORY.object();
            c._latitude = latitude;
            c._longitude = longitude;
            return c;
        }
    }

Et voila! Your class is now real-time compliant!

The following code shows the accelerating effect of stack allocations.

     public static void main(String[] args) {
        ClassInitializer.initialize(PoolContext.class); // To avoid measuring class initialization time.
        Coordinates[] vertices = new Coordinates[100000];
        for (int i=0; i < 10; i++) {     
            long time = System.nanoTime();
            PoolContext.enter();
            try {
                for (int j = 0; j < vertices.length; j++) {
                    vertices[j] = Coordinates.valueOf(i, j);
                    //vertices[j] = new Coordinates(i, j); 
                }
            }finally {
                PoolContext.exit();
            }
            time = System.nanoTime()-time;
            System.out.println("Time = " + time / 1E6);
         }
     }

The first iteration is slower in this example because the pool context has not be loaded at start-up (any context can be serialized/deserialized) and most objects are created during the first iteration.
Subsequent iterations are not only faster but very consistent in time as no memory allocation/garbage collection will ever occur.

 
Time = 36.576713
Time = 10.310808
Time = 10.024459
Time = 10.228395
Time = 10.078376
Time = 10.298236
Time = 10.480103
Time = 10.081449
Time = 10.236496
Time = 10.247391

The same program allocating directly on the heap (e.g. new Coordinates(i, j)) produces the following result:

Time = 27.496512
Time = 13.557868
Time = 12.621716
Time = 51.020451
Time = 9.327443
Time = 8.798604
Time = 23.881527
Time = 8.829055
Time = 60.977303
Time = 7.708242

As you can see there is much more fluctuation in execution time due to garbage collections interferences (making the average time several times greater).

As a rule, I am skeptical of classes that pool small objects. At one time (5 years ago) it was a big win. Over time, the advantage has diminished as garbage collectors improve. Object pools can make it much more difficult for the garbage collector to do its job efficiently, and can have adverse effects on footprint. (Joshua Bloch)
Stack allocation is a simple and transparent way to make your methods "clean" (no garbage generated), it has also the side effect of making your methods faster and more time-predictable. If all your methods are "clean" then your whole application is "clean", faster and more time-predictable (aka real-time).

Not all VMs are created equals. The speed and real-time characteristics for object creation/garbage collection may vary significantly. By using stack allocation you ensure consistent behavior regardless of the client vm.

Applications may use the facility to different degrees. For example, to improve performance one might identify the biggest "garbage producers" and use stack allocations instead of heap allocations for those only. Others might want to run high priority threads in a pool context and by avoiding heap allocations (and potential GC wait), make these threads highly deterministic.

In practice, very few methods declare a pool context for local stack allocations, only the "dirty" ones (the one generating a lot of garbage). Iterations are often good candidates as they typically generate a lot of garbage. For example:
```
   public Matrix pow(int exp) {
       PoolContext.enter(); // Starts local stack allocation.
       try { 
           Matrix pow2 = this;
           Matrix result = null;
           while (exp >= 1) { // Iteration.
                if ((exp & 1) == 1) {
                   result = (result == null) ? pow2 : result.times(pow2);
                }
                pow2 = pow2.times(pow2);
                exp >>>= 1;
           } 
           return result.export(); // Exports result to outer stack (or heap).
       } finally {
            PoolContext.exit(); // Resets local stack (all temporary objects recycled at once).
       }
    }
```
For the very "dirty" (e.g. very long interations), one pool context might not be enough and may cause memory overflow. You might have to break down the iteration loop and use inner pool contexts. Also, by using multiple layers of small nested pool contexts instead of a single large pool, one keeps the pools' memory footprint very low and still benefits fully from the facility. Pools of a few dozens objects are almost as efficient as larger pools. This is because entering/exiting pool contexts is fast and the CPU cache is more effective with small pools.

Individual recycling is possible for methods having access to the object pool. It is the case for code declaring factory instances (usually private) or for RealtimeObject sub-classes through the protected recycle method.
```
       
    // Use of factory pool access to recycle immediately.
    //
    ObjectPool<char[]> charsPool = CHAR_1024_FACTORY.currentPool();
    char[] buffer = charsPool.next(); // Next object from pool.
    for (int i = reader.read(buffer, 0, buffer.length); i > 0;) {
        ...
    } 
    charsPool.recycle(buffer); // Puts object back into its pool immediatly (optional).
    ...
    private static final ObjectFactory<char[]> CHAR_1024_FACTORY = new ObjectFactory<char[]>() { 
        public char[] create() { return new char[1024]; }
    };
        
    // Use of protected recycle method to recycle immediately.
    //
    public LargeInteger gcd(LargeInteger that) {
        LargeInteger a = this.abs();
        LargeInteger b = that.abs();
        while (!b.isZero()) {
            LargeInteger tmp = a.divide(b);
            LargeInteger c = tmp.getRemainder();
            tmp.recycle(); // tmp is always a new object (safe to recycle).
            if ((a != this) && (a != that) && // a is not a current input,
                    (a != b) && (a != c)) // nor a persistent object,
                a.recycle(); // it is then safe to recycle.
            a = b;
            b = c;
        }
        return a;
    }
```

Are not PoolContext inherently unsafe (e.g. immutable objects changing suddenly values) ?
No, as long as you export or preserve the objects which might be referenced outside of the pool context, immutable objects stay immutable! Furthermore, you do not have to worry about thread synchronization as stack objects are thread-local.

In practice, very few methods have to worry about these constraints. They are:
1. The methods with the pool context try, finally block statement defined. They have to ensure that objects created/modified inside the context scope and accessible outside of the scope are exported (a return value typically).
2. The methods creating or modifying static objects. Becauses static objects can be accessed from any thread, local objects need to be moved to the heap or better preserved when made accessible from a static object (when using preserve, one will have to unpreserved at a later time, typically when the preserved value is replaced).
For additional safety, IllegalAccessError are raised during execution when the rules above are broken.

In truth, object spaces promote the use of immutable objects (as their allocation cost is being significantly reduced), reduces thread interaction (e.g. race conditions) and often lead to safer, faster and more robust applications.

Our application is hard real-time, we cannot afford to run GC ever, can we still use Javolution ?

A resounding Yes! The easiest way is to ensure that all your threads run in a pool context, only static constants are exported to the heap and your system state can be updated without allocating new objects. This last condition is easily satisfied by using mutable objects or by preventing local (on the stack) immutable objects from being automatically recycled. The following illustrates this capability:


         // This thread recycles its objects itself (very fast).
         class Navigator extends RealtimeThread {
             private Coordinates position = Coordinates.valueOf(0, 0);
             public void run() {
                 while (true) {
                     PoolContext.enter();
                     try {
                         Coordinates newPosition = calculatePosition().preserve();  // On the stack.
                         position.unpreserve();      // Old position to be recycled upon context exit.
                         synchronized (this) {       // Updates shared position.
                             position = newPosition;
                         } 
                     } finally {                     
                         PoolContext.exit();  // Recycles all stack objects except the new position object
                     }                        // (very fast, just a stack pointer reset).
                 }
             }
             public synchronized Coordinates getPosition() {  // On the stack of the calling thread.
                 return position.copy();
             }
          }

Some JDK library classes may create temporary objects on the heap and therefore should be avoided or replaced by "cleaner" classes (e.g. FastMap instead of java.lang.HashMap, TextBuilder instead of java.lang.StringBuffer (setLength(0) allocates a new internal array) and TypeFormat for parsing/formatting of primitive types).

What performance gain can I expect by using a pool context?
Classes avoiding dynamic memory allocation are significantly faster. For example, our XmlSaxParserImpl and XmlPullParserImpl are 3-5x faster than any conventional xml parsers. To avoid synchronization issues, it is often easier to allocate new objects. Other techniques such as the "returnValue" parameter are particularly ugly and unsafe as they require mutability. Javolution's real-time facility promotes the dynamic creation of immutable objects as these object creations are fast and have no adverse effect on garbage collection. Basically, with pool contexts, the CPU is busy doing the "real thing" not "memory management"!

The cost of allocating on the heap is somewhat proportional to the size of the object being allocated. By avoiding this cost you can drastically increase the execution speed. The largest objects benefit the most. For example, adding LargeInteger in a pool context is at least 8x faster than adding java.math.BigInteger, our Text class can be several orders of magnitude faster than java.lang.String. Not surprising when you know that even "empty" Strings take 40 bytes of memory which have to be initialized and garbage collected!

Recycling objects is always more efficient than just recycling memory (aka GC). Our FastMap is a complex object using preallocated linked lists. It is fast but costly to build. Nevertheless, in a pool context it can be used as a throw-away map because the construction cost is then reduced to nothing!

Virtual Machines with real-time garbage collection are becoming more and more popular. Do we still need object recycling?
The major issue with real-time applications is to ensure a minimal "worst-case" execution time. Avoiding unwanted pauses (GC or Just-In-Time compilation) is necessary but not sufficient. Object creation is still time consuming for large objects. By allowing object creation to occur at start-up for reuse latter, the "worst-case" execution time can be considerably reduced.

Could you show us practical examples?

Sure, here is a code excerpt from a developer working on genetic algorithms:

    public static void main(String[] args) {
        FastTable<Amoeba> population = new FastTable<Amoeba>();
        FastTable<Amoeba> survivors  = new FastTable<Amoeba>();
        for (int i = 0; i < POPULATION_SIZE; i++) {
            population.add(Amoeba.newInstance()); // Initial population.
        }
        while (...) {
            PoolContext.enter();
            try {
                double average = averageFor(population);
                for (int i=0; i < POPULATION_SIZE; i++) {
                    Amoeba a = population.get(i);
                    if (a.getSurvivalLevel() >= average) {
                        survivors.add(a);
                    } else {
                        a.unpreserve(); // Will be recycled.
                    }
                }
                population.clear();
                population.addAll(survivors); 
                for (int i = population.size(); i < POPULATION_SIZE; i++) {
                    Amoeba male = survivors.get(MathLib.randomInt(0, survivors.size()-1));
                    Amoeba female = survivors.get(MathLib.randomInt(0, survivors.size()-1));
                    population.add(pair(male, female).preserve()); // New amoeba allocated on the stack but preserved!
                }
                survivors.clear();
                generation++;
            } finally {
                PoolContext.exit(); // Recycles stack objects (instantaneous).
            }
        }
    }

The same code without pool context is several times slower (due to numerous amibeas objects created for each generation)!

Skip navigation links

Overview
Package
Class

All Classes

Package javolution37.javolution.realtime

Package javolution37.javolution.realtime Description

Overview:

Reducing "worst-case" execution time.

Leveraging RTSJ capabilities.

Reducing Object Creation / Garbage Collection.

FAQ: