Optimizing ControllerState

[alesj]

At AS6 meeting we came across some "shocking" ControllerState numbers. :-)

Number of created instances was big,
and the number of equals() and hashCode() invocations was just outrageous ~ 12M.
(if I remember the numbers correctly)

The equals/hash invocations are result of state comparison,
which is done via List::indexOf. (we keep the states in a list)

 protected int getStateIndex(ControllerState state, boolean allowNotFound)
 {
 if (state == null)
 throw new IllegalArgumentException("Null state");

 int stateIndex = states.indexOf(state);
 if (stateIndex < 0 && allowNotFound == false)
 throw new IllegalArgumentException("No such state " + state + " in states " + states);

 return stateIndex;
 }

So, each time we compare two states, which we do quite a lot,
we're checking it against the list's elements.

This definitely calls for some optimization,
specially as we only expect to have a few diff ControllerState instances.

We should have some CS registry to reuse existing immutable instances,
not to mention changing compare impl.

This is my (very) naive approach, hence some feedback welcome.

Index: dependency/src/main/java/org/jboss/dependency/plugins/AbstractController.java
===================================================================
--- dependency/src/main/java/org/jboss/dependency/plugins/AbstractController.java (revision 91575)
+++ dependency/src/main/java/org/jboss/dependency/plugins/AbstractController.java (working copy)
@@ -265,6 +265,8 @@
 if (states.contains(state))
 return;

+ state.order(before);
+
 if (before == null)
 {
 states.add(state);
@@ -1973,16 +1975,12 @@

 public boolean isBeforeState(ControllerState state, ControllerState reference)
 {
- int stateIndex = getStateIndex(state, true);
- int referenceIndex = getStateIndex(reference, true);
- return stateIndex < referenceIndex;
+ return state.compareTo(reference) < 0;
 }

 public boolean isAfterState(ControllerState state, ControllerState reference)
 {
- int stateIndex = getStateIndex(state, true);
- int referenceIndex = getStateIndex(reference, true);
- return stateIndex > referenceIndex;
+ return state.compareTo(reference) > 0;
 }

 public Iterator<ControllerState> iterator()
Index: dependency/src/main/java/org/jboss/dependency/spi/ControllerState.java
===================================================================
--- dependency/src/main/java/org/jboss/dependency/spi/ControllerState.java (revision 91575)
+++ dependency/src/main/java/org/jboss/dependency/spi/ControllerState.java (working copy)
@@ -24,7 +24,9 @@
 import java.io.ObjectStreamException;
 import java.io.Serializable;
 import java.util.HashMap;
+import java.util.List;
 import java.util.Map;
+import java.util.ArrayList;

 import org.jboss.util.JBossObject;
 import org.jboss.util.JBossStringBuilder;
@@ -33,43 +35,48 @@
 * Description of state.
 *
 * @author <a href="[e-mail]">Adrian Brock</a>
+ * @author <a href="[e-mail]">Ales Justin</a>
 * @version $Revision$
 */
-public class ControllerState extends JBossObject implements Serializable
+public class ControllerState extends JBossObject implements Serializable, Comparable<ControllerState>
 {
- private static final long serialVersionUID = 2L;
+ private static final long serialVersionUID = 3L;

 /** Error */
- public static final ControllerState ERROR = new ControllerState("**ERROR**");
+ public static final ControllerState ERROR = new ControllerState("**ERROR**", -1);

 /** Not installed state */
- public static final ControllerState NOT_INSTALLED = new ControllerState("Not Installed");
+ public static final ControllerState NOT_INSTALLED = new ControllerState("Not Installed", 0);

 /** Pre install state */
- public static final ControllerState PRE_INSTALL = new ControllerState("PreInstall");
+ public static final ControllerState PRE_INSTALL = new ControllerState("PreInstall", 1);

 /** Described state */
- public static final ControllerState DESCRIBED = new ControllerState("Described");
+ public static final ControllerState DESCRIBED = new ControllerState("Described", 2);

 /** Instantiated state */
- public static final ControllerState INSTANTIATED = new ControllerState("Instantiated");
+ public static final ControllerState INSTANTIATED = new ControllerState("Instantiated", 3);

 /** Configured state */
- public static final ControllerState CONFIGURED = new ControllerState("Configured");
+ public static final ControllerState CONFIGURED = new ControllerState("Configured", 4);

 /** Create state */
- public static final ControllerState CREATE = new ControllerState("Create");
+ public static final ControllerState CREATE = new ControllerState("Create", 5);

 /** Start state */
- public static final ControllerState START = new ControllerState("Start");
+ public static final ControllerState START = new ControllerState("Start", 6);

 /** Installed state */
- public static final ControllerState INSTALLED = new ControllerState("Installed");
+ public static final ControllerState INSTALLED = new ControllerState("Installed", 7);

 /** The state string */
 protected final String stateString;

+ /** The dynamic order */
+ protected int order;
+
 private static Map<String, ControllerState> values = new HashMap<String, ControllerState>();
+ private static List<ControllerState> states = new ArrayList<ControllerState>();

 static
 {
@@ -88,12 +95,15 @@
 * Create a new state
 *
 * @param stateString the string representation
+ * @param order the order
 */
- public ControllerState(String stateString)
+ private ControllerState(String stateString, int order)
 {
 if (stateString == null)
 throw new IllegalArgumentException("Null state string");
+
 this.stateString = stateString;
+ this.order = order;
 }

 /**
@@ -110,10 +120,16 @@
 {
 if (object == null || object instanceof ControllerState == false)
 return false;
+
 ControllerState other = (ControllerState) object;
- return stateString.equals(other.stateString);
+ return order == other.order;
 }
-
+
+ public int compareTo(ControllerState other)
+ {
+ return order - other.order;
+ }
+
 public void toString(JBossStringBuilder buffer)
 {
 buffer.append(stateString);
@@ -133,4 +149,56 @@
 {
 return values.get(stateString);
 }
+
+ /**
+ * Get state instance.
+ *
+ * @param stateString the state string
+ * @return new state instance
+ */
+ public static ControllerState getInstance(String stateString)
+ {
+ if (stateString == null)
+ throw new IllegalArgumentException("Null state string.");
+
+ ControllerState state = values.get(stateString);
+ if (state != null)
+ return state;
+
+ state = new ControllerState(stateString, -1);
+ // cache it
+ values.put(stateString, state);
+ return state;
+ }
+
+ /**
+ * Modify order.
+ *
+ * @param before the before ref
+ */
+ public void order(ControllerState before)
+ {
+ // do string, as we might not be properly ordered yet
+ for (ControllerState cs : states)
+ {
+ if (cs.stateString.equals(stateString))
+ return;
+ }
+
+ if (before == null)
+ {
+ order = states.size();
+ states.add(this);
+ }
+ else
+ {
+ int index = states.indexOf(before);
+ order = index;
+ // shift others
+ for (int i = index; i < states.size(); i++)
+ states.get(i).order++;
+ // add this state
+ states.add(index, this);
+ }
+ }
 }

[adrian.brock]

The whole point is that you're supposed to be able to add/interpolate new states.
You might as well just make it an enum if you're going to add an ordinal to the state
(especially if they are sequential ;-)

The real problem is using an ad hoc shared list of states and having to find out where in
the list you are everytime, i.e. are you trying to transistion to before
or after the current state.

Like we've discussed before, this logic goes away if you specify what
transistions/path the context should go through.
https://jira.jboss.org/jira/browse/JBKERNEL-48

The only hard part is for backwards comapbility you've got to generate a path
from the legacy shared states when somebody invokes

change(ControllerContext, newControllerState);

and similar for install() if the ControllerMode is AUTOMATIC.

So I'd spend my time on JBKERNEL-48 rather than trying to fix the before/after
stuff that is going to go away anyway.

[adrian.brock]

"alesj" wrote:
At AS6 meeting we came across some "shocking" ControllerState numbers. :-)

Number of created instances was big,

This needs a static method to be able to create/use shared instances of the states
and deprecating the public constructors.

We did a similar thing in JMX for ObjectNames a while ago:
http://www.j2ee.me/j2ee/1.4/docs/api/javax/management/ObjectName.html#getInstance(javax.management.ObjectName)

Looking at the MC, the biggest use of "new ControllerState()" is in the xml parsing and
annotation handling.

[alesj]

The whole point is that you're supposed to be able to add/interpolate new states.

Sure, but that doesn't mean we should to create 2M immutable instances where only a hand full of them differ.
Not to mention huge contention on equals/hashCode.

Having some synched registry of those immutable instances,
who's equals/hashCode impl is O(1) op is what we need.

The real problem is using an ad hoc shared list of states and having to find out where in
the list you are everytime, i.e. are you trying to transistion to before
or after the current state.

Like we've discussed before, this logic goes away if you specify what
transistions/path the context should go through.
https://jira.jboss.org/jira/browse/JBKERNEL-48

The only hard part is for backwards comapbility you've got to generate a path
from the legacy shared states when somebody invokes

change(ControllerContext, newControllerState);

and similar for install() if the ControllerMode is AUTOMATIC.

So I'd spend my time on JBKERNEL-48 rather than trying to fix the before/after
stuff that is going to go away anyway.

I definitely agree JBKERNEL-48 is what we should have at the end,
but this doesn't change the fact that we need to change the actual
ControllerState impl to be a lot more optimal - instance # and compareTo.

CompareTo is, like you already mentioned, trickier with more generic transitions/path.
It might not even be able to compare, but that would mostly come from abusing api (e.g. wrong usage).
But still the new impl shouldn't be as slow as states.indexOf is/was,
some additional data/computation can easily be executed,
specially with limited number of instances flowing around.

[adrian.brock]

There's also a simple optimization you can add to ControllerState.equals()
Currently it will be doing a string comparison even when the comparison is with itself. :-(

 public boolean equals(Object object)
 {
+ if (object == this)
+ return true;
 if (object == null || object instanceof ControllerState == false)
 return false;
 ControllerState other = (ControllerState) object;
 return stateString.equals(other.stateString);
 }

[alesj]

This needs a static method to be able to create/use shared instances of the states
and deprecating the public constructors.

See my naive approach. ;-)

[alesj]

There's also a simple optimization you can add to ControllerState.equals()
Currently it will be doing a string comparison even when the comparison is with itself. :-(

 public boolean equals(Object object)
 {
+ if (object == this)
+ return true;
 if (object == null || object instanceof ControllerState == false)
 return false;
 ControllerState other = (ControllerState) object;
 return stateString.equals(other.stateString);
 }

I think I tried this one + doing a check on state string's hash
(checking actual string only if hash's matched; same hash != same state),
but it didn't visible speed things, hence more drastic change is wip.

[kabirkhan]

The whole point is that you're supposed to be able to add/interpolate new states.
You might as well just make it an enum if you're going to add an ordinal to the state
(especially if they are sequential ;-)

Ales's suggestion actually handles addition of states, although in different controllers states could be different. E.g. In Controller 1 State-A should be before State-B, and in Controller 2 State-B should be before State-A

[kabirkhan]

I have been playing a bit with an alternative implementation of ControllerStateModel, and am getting some good numbers. Here's my benchmark

 public void benchmarkControllerStateModel(ControllerStateModelFactory factory) throws Throwable
 {
 int counter = 0;

 ControllerStateModelAdapter model = factory.createControllerStateModel();

 ControllerState[] states = new ControllerState[NUM_STATES];
 for (int i = 0 ; i < NUM_STATES ; i++)
 {
 states = new ControllerState("State" + i);
 model.addState(states, null);
 }

 //Just make sure things were added
 assertEquals(new ControllerState("State" + (NUM_STATES - 2)), model.getPreviousState(new ControllerState("State" + (NUM_STATES -1))));

 ControllerState[] input = new ControllerState[ITERATIONS];
 for (int i = 0 ; i < ITERATIONS ; i++)
 {
 int stateIndex = (int)Math.round(Math.random() * (NUM_STATES - 1));
 input = STATE_FACTORY.getState(states[stateIndex].getStateString());
 }

 System.out.println("========= Starting benchmark =========================");
 System.out.println("Iterations: " + ITERATIONS);
 System.out.println("States: " + NUM_STATES);
 System.out.println("State Model Factory: " + factory);
 System.out.println("State Factory: " + STATE_FACTORY);
 System.out.println("=====================================================");

 long start = System.currentTimeMillis();

 for (int i = 1 ; i < ITERATIONS - 2 ; i++)
 {
 ControllerState state1 = model.isAfterState(input, input[i-1]) ? input : input[i-1];
 ControllerState state2 = model.isBeforeState(input, input[i+1]) ? input : input[i+1];
 state1 = model.getNextState(state1);
 state2 = model.getPreviousState(state2);
 if (state1 != null && state2 != null)
 counter++;
 else
 counter--;
 }
 System.out.println("========= Test took " + (System.currentTimeMillis() - start) + " ms");
 System.out.println(counter);
 }

Here is the alternative implementation I hacked together. I also have a test that ensures that this behaves the same way as the existing one in AbstractController (apart from the listIterator, which I did not bother to implement yet):

 private static class MapControllerStateModel extends ControllerStateModelAdapter
 {
 ControllerStateWrapper first;
 ControllerStateWrapper last;
 private Map<ControllerState, ControllerStateWrapper> states = new HashMap<ControllerState, ControllerStateWrapper>();

 public void addState(ControllerState state, ControllerState before)
 {
 if (states.containsKey(state))
 return;

 if (before == null)
 {
 ControllerStateWrapper newState = new ControllerStateWrapper(state);
 ControllerStateWrapper previous = last;
 if (previous != null)
 {
 newState.setIndex(previous.getIndex() + 1);
 previous.setAfter(newState);
 newState.setBefore(previous);
 }
 else
 {
 newState.setIndex(0);
 }
 last = newState;
 states.put(state, newState);
 }
 else
 {
 ControllerStateWrapper next = getState(before);
 if (next == null)
 throw new IllegalArgumentException("No such state " + state + " in states " + states);

 ControllerStateWrapper newState = new ControllerStateWrapper(state);
 newState.setIndex(next.getIndex());
 newState.setAfter(next);
 newState.setBefore(next.getBefore());
 next.setBefore(newState);
 if (newState.getBefore() == null)
 first = newState;

 while (next != null)
 {
 next.incrementIndex();
 next = next.getAfter();
 }

 states.put(state, newState);
 }
 }


 protected ControllerStateWrapper getState(ControllerState state)
 {
 return getState(state, false);
 }

 protected ControllerStateWrapper getState(ControllerState state, boolean allowNotFound)
 {
 if (state == null)
 throw new IllegalArgumentException("Null state");

 ControllerStateWrapper found = states.get(state);
 if (found == null && !allowNotFound)
 throw new IllegalArgumentException("No such state " + state + " in states " + states);

 return found;
 }

 protected int getStateIndex(ControllerState state)
 {
 return getStateIndex(state, false);
 }

 protected int getStateIndex(ControllerState state, boolean allowNotFound)
 {
 ControllerStateWrapper stateWrapper = getState(state, allowNotFound);
 return stateWrapper == null ? -1 : stateWrapper.getIndex();
 }

 public ControllerState getPreviousState(ControllerState state)
 {
 ControllerStateWrapper previous = getState(state).getBefore();
 return previous == null ? null : previous.getState();
 }

 public ControllerState getNextState(ControllerState state)
 {
 ControllerStateWrapper next = getState(state).getAfter();
 return next == null ? null : next.getState();
 }

 public boolean isBeforeState(ControllerState state, ControllerState reference)
 {
 int stateIndex = getStateIndex(state, true);
 int referenceIndex = getStateIndex(reference, true);
 return stateIndex < referenceIndex;
 }

 public boolean isAfterState(ControllerState state, ControllerState reference)
 {
 int stateIndex = getStateIndex(state, true);
 int referenceIndex = getStateIndex(reference, true);
 return stateIndex > referenceIndex;
 }

 public Iterator<ControllerState> iterator()
 {
 return new StateIterator(first);
 }

 public ListIterator<ControllerState> listIteraror()
 {
 return null;//states.listIterator(states.size() - 1);
 }

 private static class StateIterator implements Iterator<ControllerState>
 {
 ControllerStateWrapper current;

 public StateIterator(ControllerStateWrapper current)
 {
 this.current = current;
 }

 public void remove()
 {
 throw new UnsupportedOperationException("Remove not allowed on ControllerStateModel");
 }

 public ControllerState next()
 {
 if (current == null)
 throw new NoSuchElementException();
 ControllerState state = current.getState();
 current = current.getAfter();
 return state;
 }

 public boolean hasNext()
 {
 return current != null;
 }
 }

 private static class ControllerStateWrapper
 {
 final ControllerState state;
 int index;
 ControllerStateWrapper before;
 ControllerStateWrapper after;

 public ControllerStateWrapper(ControllerState state)
 {
 this.state = state;
 }

 public int getIndex()
 {
 return index;
 }

 public void setIndex(int index)
 {
 this.index = index;
 }

 public void incrementIndex()
 {
 this.index++;
 }

 public ControllerStateWrapper getBefore()
 {
 return before;
 }

 public void setBefore(ControllerStateWrapper before)
 {
 this.before = before;
 }

 public ControllerStateWrapper getAfter()
 {
 return after;
 }

 public void setAfter(ControllerStateWrapper after)
 {
 this.after = after;
 }

 public ControllerState getState()
 {
 return state;
 }
 }
 }

The old implementation's time increases with the number of states:

========= Starting benchmark =========================
Iterations: 1000000
States: 5
State Model Factory: Abstract Controller (List)
State Factory: Cached states
=====================================================
========= Test took 765 ms

========= Starting benchmark =========================
Iterations: 1000000
States: 10
State Model Factory: Abstract Controller (List)
State Factory: Cached states
=====================================================
========= Test took 1373 ms

========= Starting benchmark =========================
Iterations: 1000000
States: 15
State Model Factory: Abstract Controller (List)
State Factory: Cached states
=====================================================
========= Test took 1623 ms

========= Starting benchmark =========================
Iterations: 1000000
States: 20
State Model Factory: Abstract Controller (List)
State Factory: Cached states
=====================================================
========= Test took 1933 ms

========= Starting benchmark =========================
Iterations: 1000000
States: 30
State Model Factory: Abstract Controller (List)
State Factory: Cached states
=====================================================
========= Test took 2892 ms

========= Starting benchmark =========================
Iterations: 1000000
States: 40
State Model Factory: Abstract Controller (List)
State Factory: Cached states
=====================================================
========= Test took 3902 ms

The alternative implementation stays pretty constant, at less time than 5 entries in the existing implementation :-)

========= Starting benchmark =========================
Iterations: 1000000
States: 5
State Model Factory: Map ControllerStateModel
State Factory: Cached states
=====================================================
========= Test took 342 ms

========= Starting benchmark =========================
Iterations: 1000000
States: 10
State Model Factory: Map ControllerStateModel
State Factory: Cached states
=====================================================
========= Test took 329 ms

========= Starting benchmark =========================
Iterations: 1000000
States: 15
State Model Factory: Map ControllerStateModel
State Factory: Cached states
=====================================================
========= Test took 338 ms

========= Starting benchmark =========================
Iterations: 1000000
States: 20
State Model Factory: Map ControllerStateModel
State Factory: Cached states
=====================================================
========= Test took 340 ms

========= Starting benchmark =========================
Iterations: 1000000
States: 30
State Model Factory: Map ControllerStateModel
State Factory: Cached states
=====================================================
========= Test took 375 ms

========= Starting benchmark =========================
Iterations: 1000000
States: 40
State Model Factory: Map ControllerStateModel
State Factory: Cached states
=====================================================
========= Test took 342 ms

For fun I put in 5000 states in the new model, it is still faster than the existing one with 5 states ;-)

========= Starting benchmark =========================
Iterations: 1000000
States: 5000
State Model Factory: Map ControllerStateModel
State Factory: Cached states
=====================================================
========= Test took 379 ms

[kabirkhan]

The code is a bit mangled here, so the full thing can be found here https://svn.jboss.org/repos/jbossas/projects/kernel/trunk/dependency/src/test/java/org/jboss/test/dependency/controller/test/ControllerStateModelTestCase.java

[alesj]

Looks good.
I need to check the test, if you're not actually having "375 - new Random(50).nextInt()" in it for your model stopwatch.
:-)

But this means you'll have to properly clean out
all "states" variable usage in AbstractController.

Which will also help once we move to a more generic (aka non-linear) model.
Meaning we would only have to change some pieces of the model,
but not any of the logic of AbstractController.

[kabirkhan]

Cool,

Let me know when you have checked it and I can add this to AbstractController.

One minor issue is the iterator() and listIterator() methods, which are not thread safe at the moment. The other methods are called with a lock taken in AbstractController. For the iterator methods I need to readLock, take a snapshot into a list and return iterators to that list.

Another thing I have not checked is how states work in a hierarchy of controllers

[alesj]

Let me know when you have checked it and I can add this to AbstractController.

That was a joke. ;-)

One minor issue is the iterator() and listIterator() methods, which are not thread safe at the moment. The other methods are called with a lock taken in AbstractController. For the iterator methods I need to readLock, take a snapshot into a list and return iterators to that list.

What about if you already keep states in thread safe collection?
Too much overhead with double synching then - AC's lock + synched collection?

Another thing I have not checked is how states work in a hierarchy of controllers

Afaik, it shouldn't be a problem, as we don't use anything extraordinary.

[kabirkhan]

Replacing the use of 'states' in AbstractController it is making the assumption in some places that NOT_INSTALLED will always be the first state, e.g.

 protected boolean incrementState(ControllerContext context, boolean trace)
 {
 ControllerState fromState = context.getState();

 Controller fromController = context.getController();
 Set<ControllerContext> fromContexts = null;

 int currentIndex = -1;
 if (ControllerState.ERROR.equals(fromState))
 {
 errorContexts.remove(context);
 Throwable error = null;
 unlockWrite();
 try
 {
 install(context, ControllerState.ERROR, ControllerState.NOT_INSTALLED);

Should this be enforced, i.e. we throw an error if someone tries to add a state before NOT_INSTALLED?

[kabirkhan]

Replacing the use of 'states' in AbstractController it is making the assumption in some places that NOT_INSTALLED will always be the first state, e.g.

I'll rephrase :-)

When looking at AbstractController to use ControllerStateModel instead of 'states', I found that it seems to be making the assumption that...