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
File | Mode | Size |
---|---|---|
win | ||
README | -rw-r--r-- | 405 bytes |
atomic_pointer.h | -rw-r--r-- | 4.7 KB |
port.h | -rw-r--r-- | 697 bytes |
port_example.h | -rw-r--r-- | 4.6 KB |
port_posix.cc | -rw-r--r-- | 1.8 KB |
port_posix.h | -rw-r--r-- | 10.6 KB |
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...