Provides real-time {@link javolution.realtime.Context} for higher performance and higher predictability of Java bytecode execution.
The rationale for this package is:
If "new" objects, already built can be access efficiently and transparently ({@link javolution.realtime.PoolContext PoolContext}) and concurrency is encapsulated ({@link javolution.realtime.ConcurrentContext ConcurrentContext}), then code execution:
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 {@link javolution.realtime.PoolContext PoolContext}. To allocate from its stack, a thread needs to execute within a pool context and create new objects using {@link javolution.realtime.ObjectFactory 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 objects.
Note: Classes encapsulating calls to object factories within
their factory methods (e.g. valueOf(...)
) and
whose methods do not allocate directly on the heap are known
as "real-time compliant".
The simplest way is to extend {@link javolution.realtime.RealtimeObject RealtimeObject} and use a factory to create new instances. For example:
public final class Coordinates extends RealtimeObject { private double latitude; private double longitude; private static final Factory FACTORY = new Factory() { public Object create() { return new Coordinates(); } }; private Coordinates() {} public static Coordinates valueOf(double latitude, double longitude) { Coordinates c = (Coordinates) 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 pool contexts.
public static void main(String[] args) { Coordinates[] vertices = new Coordinates[1000000]; for (int i=0; i < 10; i++) { long time = System.currentTimeMillis(); PoolContext.enter(); try { for (int j = 0; j < vertices.length; j++) { vertices[j] = Coordinates.valueOf(i, j); } }finally { PoolContext.exit(); } time = System.currentTimeMillis()-time; System.out.println("Time = " + time); } }The first iteration is always slower as objects are allocated from the heap and populate the stack.
Time = 1547 Time = 93 Time = 94 Time = 94 Time = 94 Time = 93 Time = 94 Time = 94 Time = 93 Time = 94Note: Real-time threads may perform a first iteration at initialization. This also ensures that all necessary classes are initialized and the critical loop can execute in a very predictable manner.
The same program allocating directly on the heap (e.g. new Coordinates(i, j)
)
produces the following result:
Time = 937 Time = 703 Time = 1078 Time = 641 Time = 656 Time = 656 Time = 641 Time = 671 Time = 641 Time = 656Not only code execution is 6x time slower but there is much more fluctuation in the execution time due to GC.
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).
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.multiply(pow2); } pow2 = pow2.multiply(pow2); exp >>>= 1; } return (Matrix) 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 contexts.
Product[] products = ... // Very long array. Money total = Money.ZERO; PoolContext.enter(); try { for (int i=0; i < products.length;) { PoolContext.enter(); // Inner pool context. try { // Processes up to 1024 products at a time. for (int j=0; (j < 1024) && (i < products.length); j++) { total = total.add(products[i++].price()); } total.export(); } finally { PoolContext.exit(); } } total.export(); } finally { PoolContext.exit(); }Note: 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 member methods (ref. protected method {@link javolution.realtime.RealtimeObject#recycle recycle}) and methods having direct access to the {@link javolution.realtime.ObjectFactory factory} instances (usually private). The {@link javolution.realtime.ArrayPool ArrayPool} class has its pools public and therefore allows for individual recycling of any array.
// ArrayPool. ObjectPool pool = ArrayPool.charArray(1024); char[] buffer = (char[]) pool.next(); // Gets buffer from stack (or heap). for (int i = reader.read(buffer, 0, buffer.length); i > 0;) { ... } pool.recycle(buffer); // Puts buffer back. // Member method (use of protected recycle method). 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(); // Individual recycling affects local objects only a.recycle(); // (no effect on heap objects or outer objects). a = b; b = c; } return a; }
No, as long as you {@link javolution.realtime.RealtimeObject#export export} 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 the "export rule". They are:
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 {@link javolution.realtime.RealtimeObject#export exported}.
The methods creating or modifying static
real-time objects.
Becauses static
objects can be accessed from any thread, they have to be
{@link javolution.realtime.RealtimeObject#moveHeap moved to the heap} after creation or modification.
For additional safety, IllegalAccessError are raised during execution when the rules above are broken.
In truth, stack allocations 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.
Note: There is one thing to be attentive about, though! It is very easy to make a class real-time compliant by sub-classing {@link javolution.realtime.RealtimeObject RealtimeObject} or any {@link javolution.realtime.Realtime real-time} class. But if the new class adds new {@link javolution.realtime.Realtime real-time} variable members then the {@link javolution.realtime.Realtime#move move} method has to be overriden to move these new members as well. For example:public class MyRealtimeClass extends RealtimeObject { private OtherRealtimeClass _rtMember; public void move(ContextSpace cs)) { super.move(cs); _rtMember.move(cs); } }
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 {@link javolution.realtime.RealtimeObject#preserve preventing} local (on the stack) immutable objects from being automatically recycled. The following illustrates this new capability and also shows how easy it is for functions to return more than one object (with no garbage generated).
class Navigator extends Thread { private Coordinates position = Coordinates.valueOf(0, 0); private long time; public void run() { while (true) { PoolContext.enter(); try { long newTime = ...; Coordinates newPosition = calculatePosition(newTime); // On the stack. synchronized (this) { // Atomic update. time = newTime; position.preserve(false); // Allows old position to be recycled. position = newPosition; position.preserve(true); // Prevents recycling of new position upon exit. } } finally { PoolContext.exit(); } } } public synchronized TimePosition getTimePosition() { // On the stack. TimePosition tp = (TimePosition) TimePosition.FACTORY.object(); tp.time = time; tp.position = position.copy(); // Local copy on the stack. return tp; } public static class TimePosition { // Atomic data structure. public static final ObjectFactory FACTORY = new ObjectFactory() { public Object create() { return new TimePosition(); } } public long time; public Coordinates position; } }
Finally, some JDK library classes may create temporary objects on the heap and
therefore should be avoided or replaced by "cleaner" classes
(e.g. {@link javolution.util.FastMap FastMap} instead of java.lang.HashMap
,
{@link javolution.lang.TextBuilder TextBuilder} instead of java.lang.StringBuffer
(setLength(0)
allocates a new internal array) and
{@link javolution.lang.TypeFormat TypeFormat} for parsing/formatting of primitive types).
PoolContext
with the Java core library?
Yes, although these library calls will not execute faster (Java library always uses the heap context). Nonetheless, you may significantly accelerate your application and reduce garbage by using object factories to produce instances of Java library classes and by executing your code within a pool context.
private static final ObjectFactory LINE_FACTORY = new ObjectFactory() { public Object create() { return new Line2D.Double(); // java.awt.geom.Line2D.Double } }; public void paint(Graphics g) { Graphics2D g2 = (Graphics2D) g; PoolContext.enter(); try { ... Line2D.Double line = (Line2D.Double) LINE_FACTORY.object(); line.setLine(x1, y1, x2, y2); g2.draw(line); ... } finally { PoolContext.exit(); } }
Classes avoiding dynamic memory allocation are significantly faster. For example, our XML {@link javolution.xml.sax.RealtimeParser RealtimeParser} is 3-5x faster than conventional SAX2 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 or postponing this
cost you can drastically increase the execution speed. The largest objects
benefit the most. For example, adding org.jscience.math.numbers.LargeInteger
in a pool context is at least 5x faster than adding
java.math.BigInteger
, our public domain {@link javolution.lang.Text Text}
can be several orders of magnitude faster than java.lang.String
(see benchmark).
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 way more powerful than just recycling memory (aka GC). Our {@link javolution.util.FastMap 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!
Concurrent garbage collection is a perfect complement to Javolution real-time facility (Ref. New HotspotTM JVM). In particular, without preemptable garbage collection we cannot ensure that periodic real-time threads start on-time.
For real-time applications, the advantages of the facility are threefold:
ConcurrentContext
are easy to use in low-level operations
and have almost no overhead. On multi-processors systems (including processors
with Hyper-Threading technology) sequential high-level operations can automatically
take advantage of all processors available (optimizes CPU repartition).Nowadays, more and more virtual machines with schedulable/time-bounded garbage collectors are available (e.g. Jamaica VM or PERC VM) These VMs have one thing in common though. If they cannot keep up with the garbage flow they revert to a "stop the world" collection (no much choice there). Therefore, there is a good incentive to limit garbage either by manually pooling objects (error prone) or by using solutions such as the one advocated here (easier and safer).
For applications based upon the Real-Time Specification for Java (RTSJ)
all threads (including NoHeapRealtimeThread
) can run in
ImmortalMemory
(with pool contexts for the recycling) and avoid memory clashes!
This should not be a problem as the pool's size adjusts automatically and transparently. One solution is to run each song creation in a pool context and use object factories for the objects persistent through the song (e.g. Swing Widgets). Short-live objects can be allocated on the stack (inner pool context) or even on the heap if you are using a concurrent garbage collector. Because there is no burst of allocation/deallocation, full GC never has to run and incremental gc interruptions are typically less than a few milliseconds. To ensure the fastest response time, it is recommended to create a "dummy song" or at least to create the objects expensive to build at start-up (this has the effect of pre-populating the pools for subsequent utilizations, kind of "warming up a turbo engine")!