diff options
author | Derrick Stolee <dstolee@microsoft.com> | 2020-05-11 14:56:12 +0300 |
---|---|---|
committer | Junio C Hamano <gitster@pobox.com> | 2020-05-11 19:33:56 +0300 |
commit | 65c1a28bb60d1c17a672306c651bb402378f81b0 (patch) | |
tree | 4c8077d3df7884329fa1b1ab925d24e30bffdbe2 /line-log.h | |
parent | 88093289cdcfe99c5a3d7ef6f36ee45aa3018824 (diff) |
bloom: de-duplicate directory entries
When computing a changed-path Bloom filter, we need to take the
files that changed from the diff computation and extract the parent
directories. That way, a directory pathspec such as "Documentation"
could match commits that change "Documentation/git.txt".
However, the current code does a poor job of this process. The paths
are added to a hashmap, but we do not check if an entry already
exists with that path. This can create many duplicate entries and
cause the filter to have a much larger length than it should. This
means that the filter is more sparse than intended, which helps the
false positive rate, but wastes a lot of space.
Properly use hashmap_get() before hashmap_add(). Also be sure to
include a comparison function so these can be matched correctly.
This has an effect on a test in t0095-bloom.sh. This makes sense,
there are ten changes inside "smallDir" so the total number of
paths in the filter should be 11. This would result in 11 * 10 bits
required, and with 8 bits per byte, this results in 14 bytes.
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'line-log.h')
0 files changed, 0 insertions, 0 deletions