Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Following the below question on Stack Overflow

http://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    }
share|improve this question
2  
Note that this is not Java 6 in general, but OpenJDK code. –  Péter Török Apr 6 '11 at 10:51
1  
@ Péter Török, true enough, but unzipping the src.zip of jdk1.6.0_23 and looking at the String.java file I see the same exact code –  Yaneeve Apr 6 '11 at 11:08
1  
@Yaneeve, hmmm, interesting... if I were an Oracle lawyer, I would certainly have some thoughts about this :-) –  Péter Török Apr 6 '11 at 11:52
2  
This routine is optimized under the covers (when available) via SSE4.2 instructions - if your hardware supports it, just enable support with the appropriate JVM flag. –  Nim Apr 6 '11 at 12:26
1  
@Peter - why? He hasn't copied the Java 6 code, or violated a trade secret / non-disclosure agreement. His just said that the two files are the same in this area. –  Stephen C Apr 6 '11 at 14:49

3 Answers 3

"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(N2) 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."

share|improve this answer

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.

share|improve this answer
    
IMO, claiming that a 64K allocation "exceeds the expected speedup" makes no sense. One is memory size, the other CPU cycles. They're not directly comparable. –  Jerry Coffin Apr 6 '11 at 14:29
1  
@jerry-coffin: A direct comparison is reasonable. It takes non-negligible CPU cycles to allocate data and initialize a 64K data structure. –  btilly Apr 6 '11 at 15:47
1  
+1 for the in-depth description of the costs of Boyer-Moore –  kdgregory Apr 6 '11 at 16:04
    
initializing is obviously linear on the size, but at least in a typical case, allocation is roughly constant speed. –  Jerry Coffin Apr 6 '11 at 17:15

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).

share|improve this answer
1  
Even if you expose the two-step nature of BM, I doubt that you would get good performance because a 64K jump table can't fit in a level 1 CPU cache. The cost of having to hit a slower cache is likely to outweigh the fact that you need fewer operations. –  btilly Apr 6 '11 at 16:53
    
@btilly: That would make a big difference if you were really likely to use the whole table -- but at least in a typical case, ~1K of the table is going to sit in the cache, and the rest will only get touched during initialization. –  Jerry Coffin Apr 6 '11 at 17:12
    
@jerry-coffin: You clearly don't care about being able to process Asian text. –  btilly Apr 6 '11 at 18:57
1  
@btilly: Not so -- it's not that I don't care; it's that I'm aware that at least for many users, it's much less common. Even when you are dealing with Asian text, it's rare to search for a single string containing Korean and 3 different varieties of Japanese characters and 2 different varieties of Chinese characters, etc. Yes, Asian alphabets are larger than English, but no, a typical string still doesn't contain tens of thousands of unique characters. For, say, a 20-character string, you never need more than 20 cache lines of the table. –  Jerry Coffin Apr 6 '11 at 19:07
    
In the worst case, you use one cache line per unique character in the search string. –  Jerry Coffin Apr 6 '11 at 19:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.