EarthWeb   
   datamation.com Brought to you by EarthWeb

HomeSubscribeSearchFAQSitemapContact Us
     

   

  Search Tips
  Advanced Search
   
  

  
Go to ITKnowledge Enterprise

Michael Abrash's Graphics Programming Black Book, Special Edition Michael Abrash's Graphics Programming Black Book, Special Edition
by Michael Abrash
The Coriolis Group
ISBN: 1576101746   Pub Date: 07/01/97

Search this book:
 
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

homesubscribesearchfaqsitemapcontactus
Products |  Contact Us |  About Us |  Privacy  |  Ad Info  |  Home

Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.