home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 1 / 1904 < prev    next >
Internet Message Format  |  1990-12-28  |  3KB
  1. From: cedman@lynx.ps.uci.edu (Carl Edman)
  2. Newsgroups: alt.sources
  3. Subject: Re: Fast strcmp() wanted.
  4. Message-ID: <CEDMAN.90Oct4171710@lynx.ps.uci.edu>
  5. Date: 5 Oct 90 00:17:10 GMT
  6.     <CEDMAN.90Sep27075013@lynx.ps.uci.edu>
  7.     <1990Sep27.151543.8025@ccs.carleton.ca>
  8.     <CEDMAN.90Sep29091115@lynx.ps.uci.edu> <6003@hplabsz.HPL.HP.COM>
  9.     <1145@exodus.Eng.Sun.COM>
  10. Organization: non serviam
  11. Lines: 61
  12. Nntp-Posting-Host: lynx.ps.uci.edu
  13. In-reply-to: falk@peregrine.Sun.COM's message of 4 Oct 90 21:03:47 GMT
  14.  
  15. In article <1145@exodus.Eng.Sun.COM> falk@peregrine.Sun.COM (Ed Falk) writes:
  16.    In article <6003@hplabsz.HPL.HP.COM> sartin@hplabs.hp.com (Rob Sartin) writes:
  17.    >In article <CEDMAN.90Sep29091115@lynx.ps.uci.edu> cedman@lynx.ps.uci.edu (Carl Edman) writes:
  18.    >>string structure (or better class, long live C++ ! :-) which calculates
  19.    >>a 32-bit CRC for each string the first time and stores it somewhere.
  20.    >>Then only 1 (inlined) longword-compare will do the stringcomparisons
  21.    >>for you.
  22.    >
  23.    >Afraid not.  It'll give you an estimate of whether the strings match
  24.    >(correctly identifying those that don't).  You will need to then
  25.    >actually compare the strings if they are the same.  This method will
  26.    >also be unable to reproduce strcmp's behavior (strcmp returns a signed
  27.    >result indicated the <, =, > by being negative, zero, positive), it will
  28.    >only return a boolean (match, no match).
  29.  
  30.    Also, these two strings
  31.  
  32.        "ab\0x"
  33.        "ab\0y"
  34.  
  35.    (where x and y are any garbage that happens to be in memory after the
  36.    terminating '\0') will be evaluated as unequal.
  37.  
  38.    There are workarounds for both problems, of course, but I think there
  39.    won't be much of a performance improvement after you've done all it
  40.    requires to get it right.
  41.  
  42. Please , take note ! I did NOT suggest that this method is always the
  43. best, but I gave 3 or 4 different methods, and some hints, about when
  44. I would use which one.
  45. And I still hold that the CRC-method could be by far the most
  46. efficient under some conditions:
  47.  
  48.     - each word is checked often. Then a small overhead like f.e.
  49.     cleaning up the garbage behind the end of the string for the
  50.     one time calculation wouldn't matter
  51.  
  52.     - strings are long, so the overhead of 32-bit per string is
  53.     justified
  54.  
  55.     - you only need to know if 2 strings are identical
  56.  
  57.     - most compares between unequal strings
  58.  
  59. You can even imagine systems where it could be possible to remove
  60. the actual string from memory, and simply assume that if the 32-bit
  61. CRC match, the strings match. Such systems would have to be tolerant
  62. about an occasional mismatch.
  63.  
  64. If memory serves correctly the above approach is used in some
  65. implementations for diff. (only to give one practical, real world
  66. example)
  67.  
  68.     Carl Edman
  69.  
  70.  
  71.  
  72. Theorectial Physicist,N.:A physicist whose   | Send mail
  73. existence is postulated, to make the numbers |  to
  74. balance but who is never actually observed   | cedman@golem.ps.uci.edu
  75. in the laboratory.                           | edmanc@uciph0.ps.uci.edu
  76.