Fast strcmp() wanted.
Carl Edman
cedman at lynx.ps.uci.edu
Sun Oct 7 03:03:34 AEST 1990
In article <1990Oct5.122245.392 at crappie.MorningStar.Com> karl at MorningStar.Com (Karl Fox) writes:
I write:
You can even imagine systems where it could be possible to remove
the actual string from memory, and simply assume that if the 32-bit
CRC match, the strings match. Such systems would have to be tolerant
about an occasional mismatch.
If memory serves correctly the above approach is used in some
implementations for diff. (only to give one practical, real world
example)
Diff still needs to compare the actual strings if the hash values
match. Having a diff that is some amount faster but that "is
occasionally wrong" wouldn't be too popular, I'd think.
Now, if I remember correctly, that wasn't really a problem. I haven't
got the source in front of me , but I remember it goes something like
this.
1. Read both files , calculate the CRC for each line, and then forget
the files themselves
2. Do the standard algorithm based on the CRCs alone
3. Check the correctness of the CRC comparison.
If it is correct, fine
If it isn't then
4. print a warning message
5. add another diff command to the output to make up for the
inequality of these 2 lines.
This algorithm was quite fast, and allowed the comparison of truely
giantic files. The only penalty you pay for an incorrect comparison
was a (possibly) suboptimal diff, but that was a small and relatively
infrequent problem. So you could rely on the correctness of your
diff output.
Carl Edman
Theorectial Physicist,N.:A physicist whose | Send mail
existence is postulated, to make the numbers | to
balance but who is never actually observed | cedman at golem.ps.uci.edu
in the laboratory. | edmanc at uciph0.ps.uci.edu
More information about the Alt.sources.d
mailing list