Low GC Coding: Efficient listeners (exercise)
Overview
There are many ways to implement a listener pattern depending on the assumptions you want to make.
This is an exercise to get you thinking about how these can be implemented efficiently.
Simple set of listeners
Implement a thread safe set of listeners which supports add and remove. Assume there is *many* more events than add/removes and you want to optimize the notification use case.
public interface Observer {
void update(Observable o, Object arg);
}
public class Observable {
public void addObserver(Observer o) {
}
public void removeObserver(Observer o) {
}
public void notifyObservers(Object arg) {
// must be thread safe
// no locks, no garbage
}
}
In case you think this is an easy task, note that the built-in Observable uses both a lock and creates lots of garbage.
As a part of this task, you should use a set to ignore duplicates, but keep the order Observers were added. i.e. call them in this order.
Bonus Exercise
a) Compare the performance with the built-in Observable for 0, 1 and 10 Observers. Can you explain the results you get?
b) change the order each time the notifyObservers is called (or almost every time) so that each Observable has an equal change of being first. (do this without locks or creating garbage)
b) change the order each time the notifyObservers is called (or almost every time) so that each Observable has an equal change of being first. (do this without locks or creating garbage)
Solution
Solution to follow after some time to solve the problem yourself.
Possible solution - CopyOnWriteArraySet
Running the following with -XX:-UseTLAB -XX:+DoEscapeAnalysis -XX:+AggressiveOpts
public class TestIterations {
public static void main(String... ignored) {
CopyOnWriteArraySet observers = new CopyOnWriteArraySet<>();
for (int i = 0; i < 100; i++) {
long before = memoryUsed();
callObservers(observers);
long size = memoryUsed() - before;
System.out.printf("10000x Iterations used %,d bytes%n", size);
}
}
private static void callObservers(CopyOnWriteArraySet observers) {
for (int j = 0; j < 10000; j++) {
for (Observer observer : observers) {
observer.update(null, null);
}
}
}
static int counter = 0;
static class MyObserver implements Observer {
@Override
public void update(Observable o, Object arg) {
counter++;
}
}
public static long memoryUsed() {
return Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
}
}
prints
10000x Iterations used 240,000 bytes
10000x Iterations used 240,000 bytes
10000x Iterations used 240,000 bytes
10000x Iterations used 240,000 bytes
10000x Iterations used 240,000 bytes
10000x Iterations used 240,000 bytes
10000x Iterations used 240,000 bytes
10000x Iterations used 240,000 bytes
10000x Iterations used 240,000 bytes
It is possible to avoid any garbage.
You are right, java.util.Observable is inefficient, I'm glad I have never used it :-) I would probably investigate using a simple array of observers, and using a linked list. I guess an array is faster, but I'm not sure.
ReplyDeleteWe use a CopyOnWriteArraySet.
ReplyDeleteCopyOnWriteArraySet is a pretty good solution, but you still need to create an iterator (or risk an exception)
ReplyDeleteAn array is the fastest solution (zero-GC), but you have to think of a simple way to update it in a thread safe way.
It would be interesting to see if the JVM can optimise away the Iterator.
The JVM doesn't optimize the Iterator construction away in Java 7 update 15.
DeleteAdded a few attempts at:
ReplyDeletehttps://github.com/dbudworth/vanilla-test
the memory stats are funky and I'm not sure why. When you shuffle around the order that they are called, the middle one is always 0 memory.
Before I made it in to a unified test running, they all reported zero bytes on each run... kinda at a loss as to the cause of the randomness there.
Forgot to say:
DeleteEach call to dispatch to the observers cycles who goes first, in the absence of removals, it's fair round robin.
also, the checks for first and total runs aren't thread safe in the CasCall version, didn't bother making them safe as you wouldn't actually have that code in a real impl. It's just there to prove that it works (from a single thread only, of course)
We use a slightly modified version of COWAL - the major difference is public getArray method (that returns volatile array ref).
ReplyDeleteAs the instance of COWAL is used only internally - we able to control all access to it and use array only for reading values to eliminate short-lived iterator instance on each notification.
This is a good site for learning java. For those who want to learn Java by programs for free check this site http://www.javatheprogram.blogspot.com.
ReplyDelete