poor performance in OmmConsumerImpl.unregister(handle)

daniel.lipofsky · August 2023

When large number of handles are registered then calls to OmmConsumerImpl.unregister(handle) become very slow.

I traced this to WlItemHandler.removeUserRequestFromClosedStream(WlRequest) which iterates over a LinkedList using an integer index, calling LinkedList.get(i) for each index. Since get(i) is O(N) on a LinkedList (each time it is called it has to walk down the list to get to that index), just this step is O(N²). If it finds a match it then calls LinkedList.remove(i) which again has to walk down the entire list to find that index and remove it.

Calling this on every handle in a set of 379233 handles took 48 minutes! 99% of the CPU time is in WlItemHandler.removeUserRequestFromClosedStream(WlRequest).

If you use an iterator you can just walk the list just once, turning the method into O(N). The performance improvement will be enormous. Basically change this

    private int removeUserRequestFromClosedStream(WlRequest wlRequest) {
        for (int i = 0; i < _userStreamIdListToRecover.size(); i++) {
            int listStreamId = _userStreamIdListToRecover.get(i);

            if (listStreamId == wlRequest.requestMsg().streamId()) {
                _userStreamIdListToRecover.remove(i);
                break;
            }
        }
    ...

to

    private int removeUserRequestFromClosedStream(WlRequest wlRequest) {
        Iterator<Integer> iter = _userStreamIdListToRecover.iterator();
        while (iter.hasNext()) {
            int listStreamId = iter.next();
            if (listStreamId == wlRequest.requestMsg().streamId()) {
                iter.remove();
                break;
            }
        }
    ...

or in this case you could even just do

   private int removeUserRequestFromClosedStream(WlRequest wlRequest) {
        _userStreamIdListToRecover.remove(wlRequest.requestMsg().streamId());
    ...

and let Java do the iterate and remove for you.

This method also has an iteration over _statusMsgDispatchList that needs the same treatment (since it does additional actions inside the loop you either have to use the first iterator form I provided, or you have check the boolean result if you use the second form and do the actions outside the loop).

There are dozens of examples of this same problem in this class, and they really all should be fixed. You might also consider a different Collection type. LinkedHashSet want to preserve order and don't want duplicates (and I assume you never want duplicates of handles) or just HashSet if you don't care about order. Both would give O(1) performance (constant time) for these operations and thus be even faster. ArrayList would be faster if you really need to access by index but would cause the remove to go back to O(N).