summaryrefslogtreecommitdiff
path: root/t/t4013/diff.format-patch_--attach_--stdout_initial..master
diff options
context:
space:
mode:
authorLibravatar Junio C Hamano <gitster@pobox.com>2007-12-30 03:13:27 -0800
committerLibravatar Junio C Hamano <gitster@pobox.com>2008-04-09 01:30:18 -0700
commit12ecb01107c4e77d3bccb5be5a0230c4546dafaf (patch)
tree022b8c212b7bd7cbd5bd7636f9d8ab8f04646960 /t/t4013/diff.format-patch_--attach_--stdout_initial..master
parentsha1-lookup: more memory efficient search in sorted list of SHA-1 (diff)
downloadtgif-12ecb01107c4e77d3bccb5be5a0230c4546dafaf.tar.xz
sha1-lookup: make selection of 'middle' less aggressive
If we pick 'mi' between 'lo' and 'hi' at 50%, which was what the simple binary search did, we are halving the search space whether the entry at 'mi' is lower or higher than the target. The previous patch was about picking not the middle but closer to 'hi', when we know the target is a lot closer to 'hi' than it is to 'lo'. However, if it turns out that the entry at 'mi' is higher than the target, we would end up reducing the search space only by the difference between 'mi' and 'hi' (which by definition is less than 50% --- that was the whole point of not using the simple binary search), which made the search less efficient. And the risk of overshooting becomes very high, if we try to be too precise. This tweaks the selection of 'mi' to be a bit closer to the middle than we would otherwise pick to avoid the problem. Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 't/t4013/diff.format-patch_--attach_--stdout_initial..master')
0 files changed, 0 insertions, 0 deletions