See? Patents do help foster innovation!
Posted May 8, 2009 10:50 UTC (Fri) by efexis
In reply to: See? Patents do help foster innovation!
Parent article: KSM tries again
If you want to just compare two pages then yes, that may be true. It starts to break down though when you want to compare a page with, say, ten thousand other pages. Comparing a hash with ten thousand other hashes is going to be quicker than comparing a page with ten thousand other pages (your argument of only needing to scan the first x bytes of a page before likelyhood of finding differences holds up also when comparing hashes). If that speed increase comparing hashes outweights the time spent hashing the pages to begin with, then you are losing speed by not hashing. Of course it's not this simple; optimised sorting/indexing algorithms means you don't have to compare every page with every other page to rule out matches (as you also wouldn't have to compare every pair of hashes). For example, what's the effects of reading from all these pages many times as opposed to smaller hashes on the CPU memory cache going to be?
I think in this case, testing and observation are going to be important, it's near impossible to speculate - with the dynamicness of potentially millions of memory pages spread across similar to disparate virtual systems - what the comparitive results of the two different methods will be.
to post comments)