git.py: when seeking inside a midx, use statistical guessing.
git.py: when seeking inside a midx, use statistical guessing.

Instead of using a pure binary search (where we seek to the middle of the
area and do a greater/lesser comparison) we now use an "interpolation
search" (http://en.wikipedia.org/wiki/Interpolation_search), which means we
seek to where we statistically *expect* the desired value to be.

In my test data, this reduces the number of typical search steps in my test
midx from 8.7 steps/object to 4.8 steps/object.

This reduces memory churn when using a midx, since sometimes a given search
region spans two pages, and this technique allows us to more quickly
eliminate one of the two pages sometimes, allowing us to dirty one fewer
page.

Unfortunately the implementation requires some futzing, so this actually
makes memtest run about 35% *slower*.  Will try to fix that next.

The original link to this algorithm came from this article:
http://sna-projects.com/blog/2010/06/beating-binary-search/

Thanks, article!

Signed-off-by: Avery Pennarun <e03ccfb89d416c4697ad6970ce86a92c1c28a78e@gmail.com>

mhoeher/bup,mhoeher/bup,ToxicFrog/bup,gevaerts/bup,pombredanne/bup,tjanez/bup,jbaber/bup,jbaber/bup,gevaerts/bup,tjanez/bup,pombredanne/bup,jbaber/bup,jbaber/bup,apenwarr/bup,jbaber/bup,apenwarr/bup,mhoeher/bup,ToxicFrog/bup,mhoeher/bup,tjanez/bup,pombredanne/bup,ToxicFrog/bup,pombredanne/bup,apenwarr/bup,ToxicFrog/bup,gevaerts/bup,pombredanne/bup,ToxicFrog/bup,tjanez/bup,mhoeher/bup,mhoeher/bup,gevaerts/bup,pombredanne/bup,apenwarr/bup,tjanez/bup,jbaber/bup,gevaerts/bup,tjanez/bup