4 ms·
Isn't this exactly what the author says? From the posted article: > Another common inefficiency is computing the lines and hashes of content in the common pref
by sltkr 6y ago
Isn't this exactly what the author says? From the posted article:
> Another common inefficiency is computing the lines and hashes of content in the common prefix and suffix. Use of memcmp() (or even better: hand-rolled assembly to give you the offset of the first divergence) is more efficient, as again, your C runtime library probably has assembly implementations of memcmp() which can compare input at near native memory speed.
So I think you're agreeing with him: it's a useful optimization to first remove the matching prefix and suffix using memcmp() to avoid having to do line splitting and hashing across the entire file. Especially since it's not uncommon for the files being compared to be mostly identical, with only a few changes in the middle, or some content added at the end.
- OskarS 6y agoYeah, I misread that section: he talked about how the program spent longer time in the prefix/suffix section, and how picking a better hashing algorithm would improve things, and I was going "no! don't hash at all for that part! just compare the lines!". I missed the paragraph you quoted there. Still, though, this is wrong: "Another common inefficiency is computing the lines and hashes of content in the common prefix and suffix." You have to compute the lines for the prefix at least, diffs use line numbers to indicate where the change is.
- jiggawatts 6y ago> diffs use line numbers to indicate where the change is. The optimal solution would be a minor variation on the AVX-optimised memcmp that also counts the number of times it sees the newline character as it is comparing. You still do a single pass through the data, but you get the prefix comparison and the line number in the same go. For modern CPUs, this is likely optimal.