summaryrefslogtreecommitdiff
path: root/t/t5308-pack-detect-duplicates.sh
AgeCommit message (Collapse)AuthorFilesLines
2017-08-09sha1_file: drop experimental GIT_USE_LOOKUP searchLibravatar Jeff King1-10/+1
Long ago in 628522ec14 (sha1-lookup: more memory efficient search in sorted list of SHA-1, 2007-12-29) we added sha1_entry_pos(), a binary search that uses the uniform distribution of sha1s to scale the selection of mid-points. As this was a performance experiment, we tied it to the GIT_USE_LOOKUP environment variable and never enabled it by default. This code was successful in reducing the number of steps in each search. But the overhead of the scaling ends up making it slower when the cache is warm. Here are best-of-five timings for running rev-list on linux.git, which will have to look up every object: $ time git rev-list --objects --all >/dev/null real 0m35.357s user 0m35.016s sys 0m0.340s $ time GIT_USE_LOOKUP=1 git rev-list --objects --all >/dev/null real 0m37.364s user 0m37.045s sys 0m0.316s The USE_LOOKUP version might have more benefit on a cold cache, as the time to fault in each page would dominate. But that would be for a single lookup. In practice, most operations tend to look up many objects, and the whole pack .idx will end up warm. It's possible that the code could be better optimized to compete with a naive binary search for the warm-cache case, and we could have the best of both worlds. But over the years nobody has done so, and this is largely dead code that is rarely run outside of the test suite. Let's drop it in the name of simplicity. This lets us remove sha1_entry_pos() entirely, as the .idx lookup code was the only caller. Note that sha1-lookup.c still contains sha1_pos(), which differs from sha1_entry_pos() in two ways: - it has a different interface; it uses a function pointer to access sha1 entries rather than a size/offset pair describing the table's memory layout - it only scales the initial selection of "mi", rather than each iteration of the search We can't get rid of this function, as it's called from several places. It may be that we could replace it with a simple binary search, but that's out of scope for this patch (and would need benchmarking). Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2013-09-04t5308: check that index-pack --strict detects duplicate objectsLibravatar Jeff King1-0/+7
Commit 68be2fea (receive-pack, fetch-pack: reject bogus pack that records objects twice, 2011-11-16) taught index-pack to notice and reject duplicate objects if --strict is given (which it is for incoming packs, if transfer.fsckObjects is set). However, it never tested the code, because we did not have an easy way of generating such a bogus pack. Now that we have test infrastructure to handle this, let's confirm that it works. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2013-08-24sha1-lookup: handle duplicate keys with GIT_USE_LOOKUPLibravatar Jeff King1-0/+73
The sha1_entry_pos function tries to be smart about selecting the middle of a range for its binary search by looking at the value differences between the "lo" and "hi" constraints. However, it is unable to cope with entries with duplicate keys in the sorted list. We may hit a point in the search where both our "lo" and "hi" point to the same key. In this case, the range of values between our endpoints is 0, and trying to scale the difference between our key and the endpoints over that range is undefined (i.e., divide by zero). The current code catches this with an "assert(lov < hiv)". Moreover, after seeing that the first 20 byte of the key are the same, we will try to establish a value from the 21st byte. Which is nonsensical. Instead, we can detect the case that we are in a run of duplicates, and simply do a final comparison against any one of them (since they are all the same, it does not matter which). If the keys match, we have found our entry (or one of them, anyway). If not, then we know that we do not need to look further, as we must be in a run of the duplicate key. Signed-off-by: Jeff King <peff@peff.net> Acked-by: Nicolas Pitre <nico@fluxnic.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>