The last section is really interesting. The author presents the following algorithm as the "obvious" fast way of doing diffing:
1. Split the input into lines.
2. Hash each line to facilitate fast line equivalence testing (comparing a u32 or u64 checksum is a ton faster than memcmp() or strcmp()).
3. Identity and exclude common prefix and suffix lines.
4. Feed remaining lines into diffing algorithm.
This seems like a terrible way of finding the common prefix/suffix! Hashing each line isn't magically fast, you have to scan through each line to compute the hash. And unless you have a cryptographic hash (which would be slow as anything), you can get false positives, so you still have to compare the lines anyway. Like, a hash will tell you for sure that two lines are different, but not necessarily that they are the same: different strings can have the same hash. In a diff situation, the assumption here is that 99% of the times, the lines will be the same, only small parts of the file will change.
So, in reality, the hashing solution does this:
1. Split the files into lines
2. Scan through each line of both files, generating the hashes
3. For each pair of lines, compare the hashes. For 99% of pairs of lines (where the hash matches), scan through them again to make sure that the lines actually match
You're essentially replacing a strcmp() with a hash() + strcmp(). Compared to the naive way of just doing this:
1. Split the files into lines
2. For each pair line, strcmp() the lines once. Start from the beginning for the prefix, start from the end for the suffix, in each case, stop when you get to a mismatch
That's so much faster! Generating hashes is not free!
The hashes might be useful for the actual diffing algorithm (between the prefix/suffix) because it presumably has to do a lot more line comparing. But for finding common prefix/suffix, it seems like an awful way of doing it.
1. Split the input into lines.
2. Hash each line to facilitate fast line equivalence testing (comparing a u32 or u64 checksum is a ton faster than memcmp() or strcmp()).
3. Identity and exclude common prefix and suffix lines.
4. Feed remaining lines into diffing algorithm.
This seems like a terrible way of finding the common prefix/suffix! Hashing each line isn't magically fast, you have to scan through each line to compute the hash. And unless you have a cryptographic hash (which would be slow as anything), you can get false positives, so you still have to compare the lines anyway. Like, a hash will tell you for sure that two lines are different, but not necessarily that they are the same: different strings can have the same hash. In a diff situation, the assumption here is that 99% of the times, the lines will be the same, only small parts of the file will change.
So, in reality, the hashing solution does this:
1. Split the files into lines
2. Scan through each line of both files, generating the hashes
3. For each pair of lines, compare the hashes. For 99% of pairs of lines (where the hash matches), scan through them again to make sure that the lines actually match
You're essentially replacing a strcmp() with a hash() + strcmp(). Compared to the naive way of just doing this:
1. Split the files into lines
2. For each pair line, strcmp() the lines once. Start from the beginning for the prefix, start from the end for the suffix, in each case, stop when you get to a mismatch
That's so much faster! Generating hashes is not free!
The hashes might be useful for the actual diffing algorithm (between the prefix/suffix) because it presumably has to do a lot more line comparing. But for finding common prefix/suffix, it seems like an awful way of doing it.