swh:1:snp:5115096b921df712aeb2a08114fede57fb3331fb
Revision cb7a00227ff3565000af4859664c77224106dcb5 authored by Dhruba Borthakur on 05 November 2012, 07:47:06 UTC, committed by Dhruba Borthakur on 06 November 2012, 00:08:01 UTC
Summary: The method Version::GetOverlappingInputs used a sequential search to map a kay-range to a set of files. But the files are arranged in ascending order of key, so a biary search is more effective. This patch implements Version::GetOverlappingInputsBinarySearch that finds one file that corresponds to the specified key range and then iterates backwards and forwards to find all overlapping files. This patch is critical for making compactions efficient, especially when there are thousands of files in a single level. I measured that 1000 iterations of TEST_MaxNextLevelOverlappingBytes takes 16000 microseconds without this patch. With this patch, the same method takes about 4600 microseconds. Test Plan: Almost all unit tests in db_test uses this method to lookup keys. Reviewers: heyongqiang Reviewed By: heyongqiang CC: MarkCallaghan, emayanke, sheki Differential Revision: https://reviews.facebook.net/D6465
1 parent 5273c81
Tip revision: 19076c95aa2bcee55c26fcf0960cc844ad86ee9c authored by Levi Tamasi on 21 January 2021, 22:18:25 UTC
Update HISTORY.md for PR 7888 (#7890)
Update HISTORY.md for PR 7888 (#7890)
Tip revision: 19076c9
File | Mode | Size |
---|---|---|
db | ||
doc | ||
hdfs | ||
helpers | ||
include | ||
java | ||
port | ||
scribe | ||
snappy | ||
table | ||
thrift | ||
tools | ||
util | ||
.arcconfig | -rw-r--r-- | 110 bytes |
.gitignore | -rw-r--r-- | 61 bytes |
AUTHORS | -rw-r--r-- | 193 bytes |
LICENSE | -rw-r--r-- | 1.4 KB |
Makefile | -rw-r--r-- | 9.2 KB |
NEWS | -rw-r--r-- | 509 bytes |
README | -rw-r--r-- | 1.7 KB |
README.fb | -rw-r--r-- | 283 bytes |
TODO | -rw-r--r-- | 494 bytes |
build_detect_platform | -rwxr-xr-x | 7.9 KB |
build_detect_version | -rwxr-xr-x | 1.1 KB |
fbcode.gcc471.sh | -rw-r--r-- | 2.3 KB |
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...