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 ObjectFactory
(the "new" keyword always allocates on the heap, JADE 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 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 pool.Subsequent iterations are not only faster but very consistent in time as no memory allocation/garbage collection will ever occur.
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 time.
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.
Pool context 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).
Although pool contexts may "clean" a big "mess" in record time (recycling is done all at once, almost instantaneously and way faster than GC). Still you may run into memory problems if you let the "mess" gets out of control!
Now, not all your methods need to be executed in a pool context, only the "dirty" ones (the one generating a lot of garbage).
// Karatsuba multiplication.
// A lot of intermediate calculations, use of PoolContext recommended.
LargeInteger product(LargeInteger a, LargeInteger b) {
PoolContext.enter(); // Enters local pool.
try {
LargeInteger aR = ...;
LargeInteger aL = ...;
LargeInteger bR = ...;
LargeInteger bL = ...;
LargeInteger x1 = aL.multiply(bL);
LargeInteger x2 = aR.multiply(bR);
LargeInteger x3 = aL.add(bL).multiply(aR.add(bR));
// Calculates x1.shift(n) + (x3 - x1 - x2).shift(n / 2) + x2;
LargeInteger result = ...
return (LargeInteger) result.export();
} finally {
PoolContext.exit(); // Exits local pool, objects recycled all at once,
} // regardless of the number of objects allocated.
Iterations are often good candidates for pool context as
they typically generate a lot of garbage.
public Matrix pow(int exp) { // exp > 0
PoolContext.enter();
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();
} finally {
PoolContext.exit();
}
}
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.
Finally, individual recycling is possible for methods having access
to the object pool. It is the case for member methods (ref.
protected method recycle) and
methods having direct access to the factory
instances (usually private). The 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 only objects
a.recycle(); // belonging to the current pool context.
a = b;
b = c;
}
return a;
}
Note: Pool allocation/recycling is effective only if the current thread
executes within a pool context; otherwise heap allocations are being performed and
GC does the recycling.
No, as long as you 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 pool objects are thread-local.
The "export" rule guarantees that global objects (shared by all threads)
end up being exported to the heap (root context), with GC doing the
recycling (if necessary, see next question).
It is also possible to export to the heap directly either by executing
within an inner HeapContext or
by moving pool objects to the heap.
Failure to follow the "export rule" results in IllegalAccessError being
raised during execution.
In truth, pool contexts 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.
RealtimeObject or any
real-time class. But if the new class
adds new real-time members then the
export and the
toHeap methods have to be
overriden to export or move to the heap these new members. For example:
public class MyRealtimeClass extends RealtimeObject {
private OtherRealtimeClass _rtMember;
public Object export() {
_rtMember.export();
return super.export();
}
public Object toHeap() {
_rtMember.toHeap();
return super.toHeap();
}
}
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 converting immutable objects to/from mutable objects. The JADE library
provides inner Value classes for such purpose (e.g.
Float64.Value,
FastString.Value, etc.).
Concurrent access/modification of the system state is typically performed
through a ReentrantLock. For example:
public final class Coordinates extends RealtimeObject {
... // See Item 2.
public static final class Value { // Mutable image.
private volatile double latValue;
private volatile double longValue;
public Coordinates get() { // On the "stack"
return Coordinates.valueOf(latValue, longValue);
}
public void set(Coordinates coordinates) {
latValue = coordinates.latitude;
longValue = coordinates.longitude;
}
}
}
class Navigator extends Thread {
final ReentrantLock accessLock = new ReentrantLock();
final Coordinates.Value position = new Coordinates.Value();
final Quantity.Value velocity = new Quantity.Value(Velocity.ZERO);
public void run() {
while (...) {
PoolContext.enter();
try {
Coordinates c = calculatePosition(); // On the stack.
Velocity v = calculateVelocity(); // On the stack.
accessLock.lock(); // Atomic update.
position.set(c);
velocity.set(v);
accessLock.unlock();
} finally {
PoolContext.exit();
}
}
}
}
Finally, 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 and
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 STRING_BUFFER_FACTORY = new ObjectFactory() {
public Object create() {
return new StringBuffer(26);
}
};
// Unlike toString() the following method avoids heap allocation.
public CharSequence toChars() {
StringBuffer sb = (StringBuffer) STRING_BUFFER_FACTORY.object();
... // Format sb (e.g. using TypeFormat)
return sb; // Allocated on the "stack" when executing in a pool context.
}
Classes avoiding dynamic memory allocation are significantly faster.
For example, our XML 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. JADE'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 LargeInteger in a pool context is at least 5x faster than adding
java.math.BigInteger, our public domain FastString
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 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 JADE 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:
- Faster execution. Objects have already been allocated, initialized and are more likely to be in the CPU cache (increases responsiveness).
- By limiting/eliminating garbage, we ensure that a concurrent collector can always keep up with the garbage flow and avoid a stop-the-world collection situation (a disaster for real-time system). Furthermore, the collector total CPU usage can be significantly reduced (maximizes processing efficiency).
-
ConcurrentContextare 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). There is therefore 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 most expensive objects at initialization (this has the effect of pre-populating the pools for subsequent utilizations, a little like "warming up a turbo engine")!