Previous | Table of Contents | Next

How fast is Boyer-Moore? Listing 14.1 is a C implementation of Boyer-Moore searching; Listing 14.2 is a test-bed program that searches up to the first 32K of a file for a pattern. Table 14.1 (all times measured with Turbo Profiler on a 20 MHz cached 386, searching a modified version of the text of this chapter) shows that this implementation is generally much slower than REPNZ SCASB, although it does come close when searching for long patterns. Listing 14.1 is designed primarily to make later assembly implemenmore comprehensible, rather than faster; Sedge’s implementation uses arrays rather than pointers, is a great deal more compact and very clever, and may be somewhat faster. Regardless, the far superior performance of REPNZ SCASB clearly indicates that assembly language is in order at this point.

| “g;” | “Yogi” | “igoY” | “Adrian” | “Conclusion” | “You don’t know what you know”
--- | --- | --- | --- | --- | --- | ---
Searching approach | (16K) | (16K) | (16K) | (<1K) | (16K) | (16K)
REPNZ SCASB on first char a(Listing 9.1) | 8.2 | 7.5 | 9.7 | 0.4 | 7.4 | 8.1
REPNZ SCASB on least common char (Listing 9.2) | 7.6 | 7.5 | 7.5 | 0.5 | 7.5 | 7.5
Boyer-Moore in C (Listing 14.1) | 71.0 | 38.4 | 37.7 | 1.8 | 18.2 | 9.2
Standard Boyer-Moore in ASM(code not shown) | 38.5 | 21.0 | 20.5 | 0.8 | 9.4 | 4.8
Quick handling of first mismatch Boyer-Moore in ASM(Listing 14.3) | 14.1 | 8.9 | 7.7 | 0.4 | 4.0 | 2.0
<=255 pattern length + sentinelBoyer-Moore in ASM(Listing 14.4) | 8.1 | 5.2 | 4.6 | 0.3 | 2.6 | 1.2
Search pattern (approximate distance searched before match is shown in parentheses). Times are in milliseconds; shorter is better.
Table 14.1 Comparison of searching techniques.

The entry “Standard Boyer-Moore in ASM” in Table 14.1 refers to straight-forward hand optimization of Listing 14.1, code that is not included in this chapter for the perfectly good reason that it is slower in most cases than REPNZ SCASB. I say this casually now, but not so yesterday, when I had all but concluded that Boyer-Moore was simply inferior on the x86, due to two architectural quirks: the string instructions and slow branch. I had even coined a neat phrase for it: Architecture is destiny. Has a nice ring, doesn’t it?

Previous | Table of Contents | Next

Graphics Programming Black Book © 2001 Michael Abrash