This week I was given the task of optimizing the performance of UI using a JFace TableViewer. After profiling things, I noticed that adding a simple row was resulting in 1000's of comparisons on a large table. This seemed odd to me so I checked out the JFace code to see just what was going on. The indexForElement method uses a binary search to find where an element should be inserted. Here is an excerpt of the method.
// find first item > element
while (compare == 0) {
++mid;
if (mid >= count) {
break;
}
data = table.getItem(mid).getData();
compare = sorter.compare(this, data, element);
}
return mid;
Basically when an equal element in the eyes of the sorter is found, the method increments through the elements in the table until it finds one that is different. This becomes the insertion point.
So what is the problem? Well the code I was working on contained a sorter that had an "unsorted" state in addition to a sorted one. In this case it returned 0 for all comparisions between elements. This turned the performance of the indexForElement method to N/2 for all you Big O fans. This implementation is also a problem for tables that contain large numbers of equal items as well. While the performance of the indexForElement method wouldn't necessarily be N/2 it would still be slower than it has to be.
There are a number of solutions to my problem. First, I could have changed the sorter to return something besides 0. This wasn't really the problem though. Instead I extended TableViewer and overrode the indexForElement to return the index of the first row found whose comparison is equal to the target element. This results in the element being inserted in an order that is consistent with sorting. However there is no guarantee where in a block of equal rows a new element will be inserted.
The moral of this blog entry is that the default algorithms that an API uses aren't always the best for all cases.
Previous Topic
