msgbartop
Various ramblings-on, mostly about Red5
msgbarbottom

08 Aug 09 Large if block vs list lookup

In Java, something which has always caught my eye or bugs me to no end is a large “if” block. Normally I refactor these into a “switch” to make it cleaner and easier to read, but in the case of String comparison it becomes more difficult. To diverge for a moment, I would point out that you can use a string’s hash code for a switch but you must know it ahead of final compilation (pita). So to get back to the point of this post, I want to show a little code I used today to remove an unruly looking if statement. This is the original code from Red5 (code shortened for brevity):

if (action.equals(ACTION_CREATE_STREAM)
		|| action.equals(ACTION_DELETE_STREAM)
		|| action.equals(ACTION_RELEASE_STREAM)
		|| action.equals(ACTION_PUBLISH)
		|| action.equals(ACTION_PLAY)
		|| action.equals(ACTION_SEEK)
		|| action.equals(ACTION_PAUSE)
		|| action.equals(ACTION_PAUSE_RAW)
		|| action.equals(ACTION_CLOSE_STREAM)
		|| action.equals(ACTION_RECEIVE_VIDEO)
		|| action.equals(ACTION_RECEIVE_AUDIO)) {
	//do something
}

This section has always bugged me, so I decided to make a collection containing all these strings. There may be 11 calls to String.equals in this block alone! Our “optimization” has a problem and it is that the “Constants” class containing the actions is an interface and as we all know you cant execute methods in an interface, or can we?

public static final List<String> STREAM_ACTION_LIST = new ArrayList<String>(11){
	{
		//Add all the stream actions to make lookup simpler
		add(ACTION_CREATE_STREAM);
		add(ACTION_DELETE_STREAM);
		add(ACTION_RELEASE_STREAM);
		add(ACTION_PUBLISH);
		add(ACTION_PLAY);
		add(ACTION_SEEK);
		add(ACTION_PAUSE);
		add(ACTION_PAUSE_RAW);
		add(ACTION_CLOSE_STREAM);
		add(ACTION_RECEIVE_VIDEO);
		add(ACTION_RECEIVE_AUDIO);
	}
};

Using a class initializer we can accomplish what we want! If you use this, dont forget to replace the brace characters.
So now the old if block becomes this:

if (STREAM_ACTION_LIST.contains(action)) {
	//do something
}

Tags: , ,



Reader's Comments

  1. |

    It definitely makes for cleaner code, and I agree that 99 out of 100 times, the list based code should be used.

    However, I just had to go through some code on something weÅ•e working on and move everything back to the old form, because the code in question was so hot, that the implicit creation, use and destruction of a Java iterator in the ArrayList.contains(…) method was a performance bottleneck for us.

    Now, like I said, 99 out of 100 times, the ArrayList method is better. But do measure :)

  2. |

    I “plan” to write a test for this :)

  3. |

    If you’re using Java 5.0 or 6.0 to compile, a more elegant solution would be to create an enum instead of all these unruly final Strings. Then you can use a switch.

    The enum should look like this:

    public enum StreamActions {
    ACTION_CREATE_STREAM(“string1”),
    ACTION_DELETE_STREAM(“string2”),
    ACTION_RELEASE_STREAM(“string3”),
    ACTION_PUBLISH(“string4”),
    ACTION_PLAY(“string5”),
    ACTION_SEEK(“string6”),
    ACTION_PAUSE(“string7”),
    ACTION_PAUSE_RAW(“string8”),
    ACTION_CLOSE_STREAM(“string9”),
    ACTION_RECEIVE_VIDEO(“string10”),
    ACTION_RECEIVE_AUDIO(“string11”);

    protected String actionString;

    StreamActions(String actionString) {
    this.actionString = actionString;
    }

    public String getString() {
    return actionString;
    }
    }

    Your if statement can then be replaced with:

    switch(action) {
    case ACTION_CREATE_STREAM:
    case ACTION_DELETE_STREAM:
    case ACTION_RELEASE_STREAM:
    case ACTION_PUBLISH:
    case ACTION_PLAY:
    case ACTION_SEEK:
    case ACTION_PAUSE:
    case ACTION_PAUSE_RAW:
    case ACTION_CLOSE_STREAM:
    case ACTION_RECEIVE_VIDEO:
    case ACTION_RECEIVE_AUDIO:
    //do something
    }

  4. |

    @annorax nice one! I’m sure we could replace quite a number of string constants in the server with enums, maybe I’ll get started on that…

  5. |

    A note about enum naming – a better name for this enum would be StreamAction, rather than StreamActions.

    Enum naming always confuses me, since I tend to think of enums as collections. However, much like classes, enums are actually types, whereas their values (e.g. ACTION_CREATE_STREAM etc.) are equivalent to instances of that type.

    Therefore, it is always best to use singular names rather than plural, as in the examples given by Sun in the introductory docs (http://java.sun.com/j2se/1.5.0/docs/guide/language/enums.html).

  6. |

    Don’t use that list-based code!!

    The ArrayList.contains() method will create an iterator and then walk the entire collection to find the value. Although the code looks nicer than the huge block of if/else statements, the performance won’t be any better. It’s fundamentally an O(n) algorithm.

    Instead, create a HashSet[String].

    The HashSet.contains method doesn’t create an iterator. And it doesn’t perform comparisons against every value in the collection. Instead of suffering through O(n) performance, you’ll enjoy O(1) performance. Hooray!

    Here’s the code:

    public static final Set[String] STREAM_ACTION_SET = new HashSet[String](11)
    {
    add(ACTION_CREATE_STREAM);
    add(ACTION_DELETE_STREAM);
    add(ACTION_RELEASE_STREAM);
    add(ACTION_PUBLISH);
    add(ACTION_PLAY);
    add(ACTION_SEEK);
    add(ACTION_PAUSE);
    add(ACTION_PAUSE_RAW);
    add(ACTION_CLOSE_STREAM);
    add(ACTION_RECEIVE_VIDEO);
    add(ACTION_RECEIVE_AUDIO);
    }
    };

    // …

    if (STREAM_ACTION_SET.contains(action)) {
    // LARGE SETS ARE FASTER THAN LARGE LISTS
    // FOR CHECKING VALUE CONTAINMENT!!!!!!
    }

  7. |

    Previous comment blocked by spam filter? Bummer.

    The gyst of it was that you shouldn’t use a List[T] for containment-lookup with a long list of elements, since the execution time will be proportional to the size of the list (and will require creation of an iterator.

    Instead, use a Set[T], which has constant-time performance and doesn’t create a new iterator for every containment-lookup.

  8. |

    agree with annorax, use enum! And java can optimize switch block o(1) then the linear search an ArrayList.contains has!

  9. |

    @annorax using string enums in a switch like you describe doesnt working Java 1.5/1.6 but should in 1.7. This in-fact will work:
    switch(StreamAction.valueOf(action)) {
    case CREATE_STREAM:
    case DELETE_STREAM:
    //do something
    }

  10. |

    Actually valueOf only works if the strings match the enum name like so:
    CONNECT == CONNECT
    CONNECT != connect



Leave a Comment


Fatal error: Call to undefined function akismet_counter() in C:\xampp\htdocs\paulgregoireblog\wp-content\themes\googlechrome\footer.php on line 9