[jboss-dev-forums] [JBoss Microcontainer Development] - Re: Optimizing ControllerState
kabir.khan@jboss.com
do-not-reply at jboss.com
Wed Oct 28 12:15:15 EDT 2009
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
|
View the original post : http://www.jboss.org/index.html?module=bb&op=viewtopic&p=4262763#4262763
Reply to the post : http://www.jboss.org/index.html?module=bb&op=posting&mode=reply&p=4262763
More information about the jboss-dev-forums
mailing list