Why does Java's String class not implement a more efficient indexOf()?

Question

Following the below question on Stack Overflow

https://stackoverflow.com/questions/5564610/fast-alernative-for-stringindexofstring-str

I got to wondering why it is that java (6 at least) not use a more efficient implementation?

Following is the code:

java.lang.String#indexOf(String str)

1762    static int indexOf(char[] source, int sourceOffset, int sourceCount,
1763                       char[] target, int targetOffset, int targetCount,
1764                       int fromIndex) {
1765        if (fromIndex >= sourceCount) {
1766            return (targetCount == 0 ? sourceCount : -1);
1767        }
1768        if (fromIndex < 0) {
1769            fromIndex = 0;
1770        }
1771        if (targetCount == 0) {
1772            return fromIndex;
1773        }
1774
1775        char first  = target[targetOffset];
1776        int max = sourceOffset + (sourceCount - targetCount);
1777
1778        for (int i = sourceOffset + fromIndex; i <= max; i++) {
1779            /* Look for first character. */
1780            if (source[i] != first) {
1781                while (++i <= max && source[i] != first);
1782            }
1783
1784            /* Found first character, now look at the rest of v2 */
1785            if (i <= max) {
1786                int j = i + 1;
1787                int end = j + targetCount - 1;
1788                for (int k = targetOffset + 1; j < end && source[j] ==
1789                         target[k]; j++, k++);
1790
1791                if (j == end) {
1792                    /* Found whole string. */
1793                    return i - sourceOffset;
1794                }
1795            }
1796        }
1797        return -1;
1798    }

Answer 1

"Efficiency" is all about tradeoffs, and the "best" algorithm will depend on many factors. In the case of indexOf(), one of those factors is the expected size of strings.

The JDK's algorithm is based on simple indexed reference into existing character arrays. The Knuth-Morris-Pratt that you reference needs to create a new int[] that's the same size as the input string. For Boyer-Moore, you need several external tables, at least one of which is two-dimensional (I think; I've never implemented B-M).

So the question becomes: are allocating the additional objects and building lookup tables offset by the increased performance of the algorithm? Remember, we're not talking about a change from O(N²) to O(N), but simply a reduction in the number of steps taken for each N.

And I would expect that the JDK designers said something like "for strings less than X characters, the simple approach is faster, we don't expect regular use of strings longer than that, and people who do use longer strings will know how to optimize their searches."

Answer 2

The standard efficient string searching algorithm that everyone knows is Boyer-Moore. Among other things it requires building a transition table that is the same size as your character set. In the case of ASCII, that's an array with 256 entries, which is a constant overhead that pays off on long strings, and doesn't slow small strings by enough for anyone to care. But Java uses 2-byte characters which makes that table 64K in size. In normal usage this overhead exceeds the expected speedup from Boyer-Moore, so Boyer-Moore is not worthwhile.

Of course most of that table is going to have the same entry, so you might think that you can just store exceptions in an efficient way, and then supply defaults for anything that is not in your exceptions. Unfortunately the ways of doing this come with lookup overhead that makes them too expensive to be efficient. (For one issue, remember that an if that takes an unexpected branch causes a pipeline stall and those tend to be expensive.)

Please note that with Unicode this issue is highly dependent on your encoding. When Java was written, Unicode fit within 64 K, so Java just used 2 bytes per character and the length of the string was simply the number of bytes divided by 2. (This encoding was called UCS-2.) This made it fast to jump to any particular character or extract any particular substring, and the inefficiency for indexOf() was a non-issue. Unfortunately Unicode has since grown, so a Unicode character does not always fit in a Java character. This got Java into the size issues that they were trying to avoid. (Their encoding is now UTF-16.) For backwards compatibility they couldn't change the size of a Java character, but now there is a meme that Unicode characters and Java characters are the same thing. They aren't, but few Java programmers know it, and even fewer are likely to encounter it in daily life. (Note that Windows and .NET followed the same path, for the same reasons.)

In some other languages and environments UTF-8 is used instead. It has the nice properties that ASCII is valid Unicode and Boyer-Moore is efficient. The trade-off is that failure to pay attention to variable byte issues hits you a lot more obviously than it does in UTF-16.

Answer 3

It mostly comes down to this: the most obvious improvement is from Boyer-Moore, or some variant of it. B-M and variant's, however, really want a completely different interface.

In particular, Boyer-Moore and derivatives really work in two steps: first you do an initialization. This builds a table based purely on the string you're searching for. That creates a table you can then use to search for that string as often as you want.

You certainly could fit this into the existing interface by memoizing the table and using it for subsequent searches of the same target string. I don't think that would fit very well with Sun's original intent for this function: that it be a low-level building block that wouldn't depend on much of anything else. Making it a higher-level function that depends on quite a bit of other infrastructure would mean (among other things) that you'd have to ensure that none of the memoizing infrastructure it used could ever use the substring searching.

I think the most likely outcome of that would be simply re-implementing something like this (i.e., a standalone search routine) under a different name, with a higher-level routine under the existing name. All things considered, I think it would probably make more sense to just write a new higher-level routine with a new name.

The obvious alternative to that would be to use some sort of stripped-down version of memoizing, that (for example) stored only one table statically, and re-used it iff the target string was identical to the one used to the create the table. That's certainly possible, but would be far short of optimal for a lot of use cases. Making it thread-safe would also be non-trivial.

Another possibility would be to expose the two-step nature of B-M searching explicitly. I doubt anybody would really like that idea though -- it carries a fairly high cost (clumsiness, lack of familiarity) and little or no benefit for a lot of use-cases (most studies on the subject indicate that average string length is something like 20 characters).