Discover the fastest way to notify event listeners defined by the JavaBeans 1.01 specification
Java 1.1, Swing, JavaBeans, and the InfoBus spec all use the delegation event model described in the JavaBeans 1.01 specification for event registration and notification (see the Resources section below for more information). Under this model, when implementing a JavaBean, you have to implement event registration and event notification code in the bean. In this article, we’ll compare the performance of several different techniques for implementing the event registration and notification code. The article is organized into two parts. The first covers the requirements for event delivery and explains the basic technique for implementing fast listener notification code. The second builds a test harness and several test cases that compare the performance of the various implementations. The article concludes by giving advice on when you should apply the optimizations presented.
Requirements for event notification
Let’s begin with a quick review of listener notification, which is in fact just another name for event delivery. Event delivery is in turn fully described in Section 6.6 of the JavaBeans 1.01 specification (see Resources).
When a JavaBean wants to trigger an event, it notifies all registered listeners by calling the event’s method on the registered listeners’ listener interfaces. Listeners register with a JavaBean by calling the bean’s add<ListenerType>(<ListenerType> listener)method.
Section 6.5.1 of the JavaBeans 1.01 specification contains an example of event-listener registration and event-listener notification. The source code from this example forms the basis of my analysis:
public interface ModelChangedListener extends
java.util.EventListener
{
void modelChanged(EventObject e);
}
public abstract class Model {
private Vector listeners = new Vector(); // list of Listeners
public synchronized void
addModelChangedListener(ModelChangedListener mcl) {
listeners.addElement(mcl);
}
public synchronized void
removeModelChangedListener(ModelChangedListener mcl) {
listeners.removeElement(mcl);
}
protected void notifyModelChanged() {
Vector l;
EventObject e = new EventObject(this);
// Must copy the Vector here in order to freeze the state of the
// set of EventListeners the event should be delivered to prior
// to delivery. This ensures that any changes made to the Vector
// from a target listener's method, during the delivery of this
// event will not take effect until after the event is delivered
synchronized(this) { l = (Vector)listeners.clone(); }
for (int i = 0; i < l.size(); i++) { // deliver it!
((ModelChangedListener)l.elementAt(i)).modelChanged(e);
}
}
}
The JavaBeans 1.01 specification specifically states that the list of listeners can potentially be updated at the same time that those very listeners are being notified of events. The target listener may modify the listener list, or a different thread may attempt to add or remove listeners.
Thus, the JavaBeans 1.01 specification allows for different implementations. An implementation can make a copy of the list of listeners, and then notify only the listeners in the copied list of events; alternately, an implementation can use the current (and potentially changing) list as it proceeds with the notifications. Using a copy means that additions and removals that take place during the notification process do not alter the list of listeners being notified of the current event. Notice that the example above uses just such a copy implementation.
In contrast to the JavaBeans 1.01 specification, the InfoBus 1.2 specification tightens the requirements for event delivery. Section 6.1 of the InfoBus 1.2 specification (see Resources) states: “Data items that implement DataItemChangeManagermust support registration and deregistration of event listeners as per section 6.5.1 of the JavaBeans 1.0 specification. Specifically, changes to the listener list may take place during notification of all listeners. Accordingly, the listener list should be copied at the beginning of a change notification, and the copy of the list used for the duration of the notification.”
What are the performance implications of this? In systems such as InfoBus, in which rapid event notification may occur, this scheme of copying and then notifying leads to many short-lived clones that can be a source of performance problems (see “Java Performance Programming, Part 1: Smart Object Management Saves the Day” in Resources). Our goal in this article is to develop a high performance alternative technique for fast listener notification. Our implementation should conform to the InfoBus specification but not produce these short-lived clones.
The basic technique
The key idea behind the technique is that object creation during notification ought to be reduced. By eliminating the clone of the Vectorin the notifyModelChanged() method above, we’d expect to be able to speed up listener notification. Well, why don’t we do just that — eliminate the clone? Unfortunately, doing so would mean that the notifyModelChanged()method would no longer comply with the InfoBus 1.2 specification. To solve this problem, the Modelwill now make a clone in addModelChangedListener()and removeModelChangedListener(), rather than notifyModelChanged(). The Model then uses Java’s atomic assignment in addModelChanged(), removeModelChanged(), and notifyModelChanged(); as a result, notify will never see the changes to the notify list once it has created a snapshot reference to it. Finally, we must continue to synchronize the add() and remove() methods, so that they will not encounter any race conditions when called from two different threads.
Here’s the sample code with our new technique applied:
public interface ModelChangedListener extends
java.util.EventListener
{
void modelChanged(EventObject e);
}
public abstract class Model {
private Vector listeners = new Vector(); // list of Listeners
public synchronized void
addModelChangedListener(ModelChangedListener mcl) {
Vector v = (Vector)listeners.clone();
v.addElement(mcl);
listeners = v; // Atomic assignment
}
public synchronized void
removeModelChangedListener(ModelChangedListener mcl) {
Vector v = (Vector)listeners.clone();
v.removeElement(mcl);
listeners = v; // Atomic assignment
}
protected void notifyModelChanged() {
Vector l;
EventObject e = new EventObject(this);
// Once a reference to the set of EventListeners is acquired
// its contents will never change because add and remove modify
// a clone of the EventListeners.
// This ensures that any changes made to the Vector
// from a target listener's method, during the delivery of this
// event will not take effect until after the event is delivered
l = listeners; // Atomic assignment
for (int i = 0; i < l.size(); i++) { // deliver it!
((ModelChangedListener)l.elementAt(i)).modelChanged(e);
}
}
}
The test harness
In order to compare different approaches, we must develop a test-harness framework that can exercise and time different event sources. Each event source needs to implement the TestSourceinterface in order to plug into the test harness. The removeModelChangedListener() method is not included in the interface, because the test harness never calls it; the fireCount() and instanceNumber() properties are used for some of the diagnostic outputs. Let’s take a look:
public interface TestSource {
public void
addModelChangedListener(ModelChangedListener listener);
public void notifyModelChanged();
public int getFireCount();
public int getInstanceNumber();
}The test harness uses the event source’s class object to create instances of objects that implement the TestSource interface. The test case classes are named Source1 through Source7. The Main method currently exercises Source1 through Source7by passing the class for these sources to the runFor()method. Below is the code for Main:
public class Main {
...
public static void main(String[] args) {
try {
...
runFor(Source1.class);
runFor(Source2.class);
runFor(Source3.class);
runFor(Source4.class);
runFor(Source5.class);
runFor(Source6.class);
runFor(Source7.class);
} catch (Throwable t) {
t.printStackTrace();
}
}
...In the code above, the runFor() method runs the test for the class passed as an argument. Instances of the event source are created and then chained together into a simple tree. When the source at the top of the tree fires an event, there is a chain reaction, and all sources in the tree end up firing an event. Thus, the runFor test models environments like InfoBus, in the sense that a change notification from one component may cause other components to deliver change events. To build the tree, the Chain class links two sources; causing source x to deliver an event in turn causes source yto deliver an event. The source code for Chainis shown below:
import java.util.*;
class Chain implements ModelChangedListener {
TestSource m_next;
Chain(TestSource s1, TestSource s2) {
s1.addModelChangedListener(this);
m_next = s2;
}
public void modelChanged(EventObject event) {
...
m_next.notifyModelChanged();
}
}
The test harness runFor() method creates six instances of the same TestSource, then links them together with instances of the Chain class, as show in the figure below.
After chaining the event sources together, the runFor()method calls src.1notifyModelChanged()once to notify src1‘s listeners. This causes all of the chained listeners to be notified as well. The first call to notifyModelChanged()is not timed, and trace diagnostics are turned on. The diagnostics serve as a crude way to verify that the event source is implemented correctly, and to prime the just-in-time (JIT) compiler by exercising the code once.
Next, the runFor() method records the start time in milliseconds and loops 50,000 times, calling src1.notifyModelChanged()on each pass through the loop. Finally, the runFor() method computes the time taken for the 50,000 calls and prints the results. Here’s the code:
static void runFor(Class sourceClass) {
try {
if (Trace.isOn()) {
Trace.out.println(sourceClass.getName());
}
TestSource src1 = (TestSource)sourceClass.newInstance();
TestSource src2 = (TestSource)sourceClass.newInstance();
TestSource src3 = (TestSource)sourceClass.newInstance();
TestSource src4 = (TestSource)sourceClass.newInstance();
TestSource src5 = (TestSource)sourceClass.newInstance();
TestSource src6 = (TestSource)sourceClass.newInstance();
Chain c1 = new Chain(src1, src2);
Chain c2 = new Chain(src2, src3);
Chain c3 = new Chain(src3, src4);
Chain c11 = new Chain(src1, src5);
Chain c12 = new Chain(src5, src6);
// Test run
src1.notifyModelChanged();
// Turn tracing off during timing run
Trace.setOn(false);
// Time 50 thousand calls
long startTime = System.currentTimeMillis();
for (int i = 0; i < 50000; i++) {
src1.notifyModelChanged();
}
long stopTime = System.currentTimeMillis();
// Turn tracing back on
if (!m_isTableOnly) {
Trace.setOn(true);
}
if (Trace.isOn()) {
Trace.out.println(sourceClass.getName()
+ " time=" + deltaSeconds(stopTime, startTime));
}
System.out.println(deltaSeconds(stopTime, startTime));
if (Trace.isOn()) {
Trace.out.println("fireCount="
+ src1.getFireCount());
}
} catch (Throwable t) {
t.printStackTrace();
}
}
protected static double deltaSeconds(long stopTime, long startTime)
{
long deltaMillis = stopTime - startTime;
return deltaMillis/1000.0;
}
Test cases
OK, now that we have the test harness in place, let’s look at some test cases. For the discussion below, the test hardware was a 300 MHz Pentium II machine with 128 MB of memory, running Windows NT 4.0 with Service Pack 5 installed, and using Sun’s JDK 1.1.8. The table at the end of this article shows the numbers for the same hardware, OS, and JDK, with additional figures from Sun’s JDK 1.3 beta with the HotSpot Client VM and IBM’s JDK 1.1.8.
Source1
The first test case is right out of the JavaBeans 1.01 specification shown above. Source1.notifyModelChanged clones the listener vector. I will not repeat the source code here; it is basically the same as the code above, with a few extra methods defined in TestSource to support diagnostics. Fifty thousand notifyModelChanged() calls take, on average, 2.7 seconds. Notice that, because of the chaining of listeners, these 50,000 calls actually cause 300,000 calls to the Source1.notifyModelChanged()method.
Source2
Source2is implemented so that there is no clone in Source2.notifyModelChanged. Again, I will not repeat the source code here, since it is essentially the same as the code above in the basic technique section. The average time for 50,000 notifyModelChangedcalls was 0.753 seconds. Voilà — Source2 is around 3.5 times faster than Source1!
Actually, the first implementation of Source2 used an Iterator to retrieve the listeners and produced an average time of 1.42 seconds. This was only about twice as fast as Source1. The slower time makes sense because each Iteratorcreated by the Vector is another short-lived object that has to be garbage collected.
Swing
After conducting the previous tests, I began thinking about Swing’s event notification performance. After digging though the Swing source code for a while, I found out that Swing uses javax.swing.event.EventListenerListto manage event listeners.
Source3
I designed Source3 to use Swing’s EventListenerListto manage Source3‘s listeners. Interestingly, there was a slight improvement over Source2. It turns out that EventListenerListuses an array to store the listeners. You can retrieve elements from arrays a little more quickly (see “Java Performance Programming, Part 2: The Cost of Casting” in Resources). Source3‘s average time was 0.566 seconds.
EventListenerListplaces listeners of different types into a single array. Every even element in the array is the class of the listener, and every odd element is the listener interface itself. Therefore, when notifying listeners, the notifyModelChanged()method must check each registered listener to verify that it is a ModelChangedListener before calling modelChanged(). I wanted to see what would happen if the listener list contained several listeners of the wrong type in addition to one of the correct type; thus, I added seven adversarial listeners to the list that would have to be skipped before reaching the ModelChangeListener. With the adversaries in place, Source3takes an average of 0.6186 seconds.
import javax.swing.event.*;
import java.awt.event.*;
import java.util.*;
/**
* Use Swing utility class with an adversary
*/
public class Source3 implements TestSource {
private EventListenerList m_listeners = new EventListenerList();
private boolean m_adversary = true;
private static int m_fireCount = 0;
private static int m_instCount = 0;
private int m_instNumber;
public Source3() {
m_instNumber = ++m_instCount;
}
public void addModelChangedListener(ModelChangedListener l) {
if (Trace.isOn()) {
Trace.out.println("addModelChangedListener l="
+ l.getClass());
}
m_listeners.add(ModelChangedListener.class, l);
if (m_adversary) {
ActionListener ladverse = new ActionListener() {
public void actionPerformed(ActionEvent e) {
}
};
m_listeners.add(ActionListener.class, ladverse);
m_listeners.add(ActionListener.class, ladverse);
m_listeners.add(ActionListener.class, ladverse);
m_listeners.add(ActionListener.class, ladverse);
m_listeners.add(ActionListener.class, ladverse);
m_listeners.add(ActionListener.class, ladverse);
m_listeners.add(ActionListener.class, ladverse);
}
}
public void removeModelChangedListener(ModelChangedListener l) {
if (Trace.isOn()) {
Trace.out.println("removeModelChangedListener l=" + l);
}
m_listeners.remove(ModelChangedListener.class, l);
}
public void notifyModelChanged() {
if (Trace.isOn()) {
Trace.out.println("notifyModelChanged size="
+ m_listeners.getListenerCount());
}
m_fireCount++;
// Makeup a EventObject
EventObject event = new EventObject(this);
Object [] listeners = m_listeners.getListenerList();
for (int i = listeners.length-2; i>=0; i-=2) {
if (listeners[i]==ModelChangedListener.class) {
if (Trace.isOn()) {
Trace.out.println("fired when i="+i);
}
((ModelChangedListener)listeners[i+1])
.modelChanged(event);
}
}
}
public int getFireCount() {
return m_fireCount;
}
public int getInstanceNumber() {
return m_instNumber;
}
}
Source4
Determined to have the fastest listener notification on the block, I revamped Source2 to use arrays as listener storage and called this test Source4. Each time a listener is added, a new array is created. The old listeners are copied into the new array and the added listener is placed at the end of the new array. Finally, the new array is stored in the listenerListfield. Since I only needed add()for the test, I left remove() as an exercise for the reader. Source4‘s average time was 0.453 seconds — smoking!
import java.util.*;
/**
* Like clone vector at add/remove but uses an array
* like the swing event listener list.
*/
public class Source4 implements TestSource {
private ModelChangedListener[] m_listeners
= new ModelChangedListener[0];
private static int m_fireCount = 0;
private static int m_instCount = 0;
private int m_instNumber;
public Source4() {
m_instNumber = ++m_instCount;
}
public void addModelChangedListener(ModelChangedListener l) {
if (Trace.isOn()) {
Trace.out.println("addModelChangedListener l="
+ l.getClass());
}
synchronized (this) {
int length = m_listeners.length;
ModelChangedListener[] els
= new ModelChangedListener[length + 1];
System.arraycopy(m_listeners, 0, els, 0, length);
els[length] = l;
m_listeners = els;
}
}
public void notifyModelChanged() {
if (Trace.isOn()) {
Trace.out.println("notifyModelChanged size="
+ m_listeners.length);
}
m_fireCount++;
// Makeup a EventObject
EventObject event = new EventObject(this);
int length = m_listeners.length;
for (int i = 0; i < length; i++) {
m_listeners[i].modelChanged(event);
}
}
public int getFireCount() {
return m_fireCount;
}
public int getInstanceNumber() {
return m_instNumber;
}
}
InfoBus
Next, I wanted to see how well javax.infobus.DataItemChangeManagerSupportperformed. Since DataItemChangeManagerSupport manages DataItemChangeListener, I had to build an adapter to adapt from DataItemChangeListener to a ModelChangedListenerso that I could use my test harness.
Source5
The addModelChangedListener() method creates an instance of the adapter and adds it as a listener to DataItemChangeManagerSupport. The notifyModelChanged()method simply calls DataItemChangeManagerSupport.fireItemValueChanged. Here is the source code:
import javax.infobus.*;
/**
* Uses infobus DataItemChangeManagerSupport by adapting
* the listeners
*/
public class Source5 implements TestSource {
private DataItemChangeManagerSupport m_listeners
= new DataItemChangeManagerSupport(this);
private static int m_fireCount = 0;
private static int m_instCount = 0;
private int m_instNumber;
public Source5() {
m_instNumber = ++m_instCount;
}
class ModelChangedListenerAdapter
extends DataItemChangeListenerSupport
implements DataItemChangeListener
{
private ModelChangedListener m_l;
ModelChangedListenerAdapter(ModelChangedListener l) {
m_l = l;
}
public void
dataItemValueChanged(DataItemValueChangedEvent event) {
m_l.modelChanged(event);
}
}
public void addModelChangedListener(ModelChangedListener l) {
if (Trace.isOn()) {
Trace.out.println("addModelChangedListener l="
+ l.getClass());
}
m_listeners.addDataItemChangeListener(
new ModelChangedListenerAdapter(l));
}
public void notifyModelChanged() {
if (Trace.isOn()) { Trace.out.println("notifyModelChanged"); }
m_fireCount++;
m_listeners.fireItemValueChanged(null, null);
}
public int getFireCount() {
return m_fireCount;
}
public int getInstanceNumber() {
return m_instNumber;
}
}
The average time for 50,000 Source5.notifyModelChangedcalls was 2.956 seconds. This is on the same order of magnitude as Source1. There is room for improvement; in fact, results along the lines of those in Source4 should be possible.
Source6
For the next test case, Source6, I made a DefaultDataItemChangeManagerthat implements the methods from DataItemChangeManagerSupport that I needed for Source5. Source6 is identical to Source5, except that I used an instance of DefaultDataItemChangeManagerinstead of an instance of DataItemChangeManagerSupport. The average time for Source6was 0.649 seconds — almost five times faster than javax.infobus.DataItemChangeManagerSupport. Here’s the code for DefaultDataItemChangeManager:
import javax.infobus.*;
import java.util.*;
public class DefaultDataItemChangeManager {
protected Object m_source;
private DataItemChangeListener[] m_listeners
= new DataItemChangeListener[0];
public DefaultDataItemChangeManager(Object source) {
m_source = source;
}
public void
addDataItemChangeListener(DataItemChangeListener listener) {
if (Trace.isOn()) {
Trace.out.println("addDataItemChangeListener l="
+ listener.getClass());
}
synchronized (this) {
int length = m_listeners.length;
DataItemChangeListener[] newListeners
= new DataItemChangeListener[length + 1];
System.arraycopy(m_listeners, 0, newListeners, 0, length);
newListeners[length] = listener;
m_listeners = newListeners;
}
}
public void
fireItemValueChanged(Object changedItem,
InfoBusPropertyMap propertyMap)
{
DataItemValueChangedEvent event
= new DataItemValueChangedEvent(m_source,
changedItem, propertyMap);
int length = m_listeners.length;
for (int i = 0; i < length; i++) {
m_listeners[i].dataItemValueChanged(event);
}
}
}
Source7
Finally, I noticed that there was still one short-lived object remaining in Source6: the event object itself. I wanted to see if eliminating the creation of the event object would have any impact on the performance. Source7 thus uses DefaultDataItemChangeManagerBroken, which in turn uses a field to store a precreated DataItemValueChangedEventinstance. Source7is indeed much faster than Source6, with an average time of 0.120 seconds. Here’s the code:
import javax.infobus.*;
import java.util.*;
public class DefaultDataItemChangeManagerBroken {
protected Object m_source;
private DataItemChangeListener[] m_listeners
= new DataItemChangeListener[0];
private DataItemValueChangedEvent m_event;
public DefaultDataItemChangeManagerBroken(Object source) {
m_source = source;
m_event = new DataItemValueChangedEvent(m_source, null, null);
}
public void
addDataItemChangeListener(DataItemChangeListener listener) {
if (Trace.isOn()) {
Trace.out.println("addDataItemChangeListener l="
+ listener.getClass());
}
synchronized (this) {
int length = m_listeners.length;
DataItemChangeListener[] newListeners
= new DataItemChangeListener[length + 1];
System.arraycopy(m_listeners, 0, newListeners, 0, length);
newListeners[length] = listener;
m_listeners = newListeners;
}
}
public void
fireItemValueChanged(Object changedItem,
InfoBusPropertyMap propertyMap)
{
int length = m_listeners.length;
for (int i = 0; i < length; i++) {
m_listeners[i].dataItemValueChanged(m_event);
}
}
}
Unfortunately, it is normally not possible to use this optimization with InfoBus. In order to be useful, the event object needs to have several of its properties set to match the event being delivered. However, none of the InfoBus DataItem<*>Eventclasses define mutator methods for the event properties. Furthermore, each DataItem<*>Eventis declared final. Therefore, the only way to initialize the properties of the event is in the events constructor.
For the DataItemValueChangedEvent, which reports the changed item in the event, an event would have to be created for each item. Additionally, instead of using a single event per item, a pool of events for a single item would have to be maintained, because two or more threads may attempt to notify listeners about changes to the same item. It would be much simpler to implement a pool of events if the events could be reused for different data items. To support this, InfoBus would have to add mutator methods to the DataItem<*>Events classes or allow classes to extend the DataItem<*>Events classes.
Performance numbers
The table below shows the performance numbers for Source1through Source7, using Sun’s JDK 1.1.8, IBM’s JDK 1.1.8, and Sun’s JDK 1.3 Beta.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Conclusion
Let me start by noting that all of the optimizations in this article should be considered only after listener notification has been determined to be either a performance bottleneck or a source of many short-lived objects that in turn lead to a performance bottleneck. Consider a simple JavaBean that only generates events in response to user mouse clicks. In this case, the user will have a difficult time generating 500 events, let alone the benchmarked 50,000 events. Even at 500 events, the longest running average time would only be 0.0296 seconds.
However, once you have determined that your bottleneck is caused by this common programming technique — that is, you have determined that your program creates a clone of a list of event listeners and then uses that list during the notification process — it can be improved upon by moving the clone to the add<ListenerType>and remove<ListenerType>calls. It appears as though the DataItemChangeManagerSupport class uses clones in all of its implementations of event delivery methods, and is therefore a likely candidate for fast listener notification optimization. Using Swing’s EventListenerList as documented gives you this optimization for free; at the same time, doing so continues to satisfy the rule that dictates that your code should ignore changes to the listener list during notification. You can even optimize your code further. Note that the EventListenerListuses a polymorphic list of listeners. It therefore has to search for the listeners to notify by matching the event type being notified with the event type registered. Furthermore, it must cast listeners to the correct listener interface. Thus, a custom array implementation can perform slightly better than the EventListenerList, but at the cost of increased memory usage. In the custom array implementation, each listener list to be notified requires an array object to store the list; on the other hand, the EventListenerList can multiplex events using a single array.
The only other short-lived object generated during listener notification is the event itself. EventListenerList‘s documented technique for caching the event further increases performance, but it is difficult to apply in practice. Events generally do not supply mutators, so events that, once cached, need to be changed require a derived class to supply mutators. InfoBus makes this impossible, because its events are declared with the final attribute. Furthermore, simple caching fails when used in a multithreaded environment, as documented in the EventListenerList. Swing is not a multithreaded environment, but InfoBus is. Object pooling, as discussed in “Java Performance Programming, Part 1: Smart Object Management Saves the Day” (see Resources) could be used to implement the cache, but the overhead and complexity might be prohibitive.
Furthermore, it appears that vendors of JIT compilers are making major progress in the effort to reduce the cost of object creation. For example, DefaultDataItemChangeManager is only twice as fast as DataItemChangeManagerSupport for the IBM compiler. Therefore, I think that optimizations focusing simply on reducing object creation and garbage collection will produce less dramatic improvements with future JITs. However, the elimination of clones will continue to result in at least a doubling of speed, with even better performance being possible if there are many listeners in the array being cloned.
