See? Patents do help foster innovation!

Posted May 8, 2009 14:19 UTC (Fri) by nix (subscriber, #2304)
In reply to: See? Patents do help foster innovation! by efexis
Parent article: KSM tries again

What I'd do there is hash the first 32/64/128 bytes or thereabouts of a
page (one cacheline) and then use that partial hash to eliminate the
majority of pages from comparison. (But this obvious solution, which took
less than five seconds to think of, may be patented. Bleah.)

See? Patents do help foster innovation!

Posted May 15, 2009 19:43 UTC (Fri) by nevyn (guest, #33129) [Link]

Speed improvement: Don't bother hashing it, just use the first 8 bytes of the page as the first pass value. I'd assume that couldn't be patented (given how it's a trivial optimization of what the memcmp() is doing) ... but who knows.

We can avoid reading the whole page for each comparison, even in the worst case.

Posted Nov 17, 2009 16:03 UTC (Tue) by gmatht (guest, #58961) [Link]

Say that they have a binary tree. Each left edge is labelled 0, and each
right edge is labelled 1. Whenever we read a bit from the page we follow the
edge with the label of the bit. So for example, if we look for the zero page
in the tree then we navigate to the leftmost child node.

This is clearly very inefficient, as this simple algorithms needs exactly
(4096*8) branches to find any page. However we read the page exactly once
for all comparisons. And we can optimize it, e.g. if we have a chain of
nodes with only single children we can merge them into a single edge.

Another approach would be to make use of the fact that if say, we know all
child pages of the current node start with "Foo" we don't need to compare
the first 3 characters anymore. As such, we'd usually only have to access
each cache-line once.