Revision 5b7e09bd6f0a3776688a806402684a9fc3cf2482 authored by JiYou on 18 April 2019, 01:12:20 UTC, committed by Facebook Github Bot on 18 April 2019, 01:15:20 UTC
Summary: `GetOverlappingInputsRangeBinarySearch` firstly use binary search to find a index in the given range `[begin, end]`. But after find the index, then use linear search to find the `start_index` and `end_index`. So the search process degraded to linear time. Here optmize the search process with below changes: - use `std::lower_bound` and `std::upper_bound` to get `lg(n)` search complexity. - use uniformed lambda for search process. - simplify process for `within_interval` true or false. - remove function `ExtendFileRangeWithinInterval` and `ExtendFileRangeOverlappingInterval`. Signed-off-by: JiYou <jiyou09@gmail.com> Pull Request resolved: https://github.com/facebook/rocksdb/pull/4987 Differential Revision: D14984192 Pulled By: riversand963 fbshipit-source-id: fae4b8e59a21b7e350718d60cdc94dd55ac81e89
1 parent 248b6b5
File | Mode | Size |
---|---|---|
buckifier | ||
build_tools | ||
cache | ||
cmake | ||
coverage | ||
db | ||
docs | ||
env | ||
examples | ||
hdfs | ||
include | ||
java | ||
memtable | ||
monitoring | ||
options | ||
port | ||
table | ||
third-party | ||
tools | ||
util | ||
utilities | ||
.clang-format | -rw-r--r-- | 138 bytes |
.gitignore | -rw-r--r-- | 740 bytes |
.lgtm.yml | -rw-r--r-- | 67 bytes |
.travis.yml | -rw-r--r-- | 3.4 KB |
AUTHORS | -rw-r--r-- | 322 bytes |
CMakeLists.txt | -rw-r--r-- | 35.9 KB |
CODE_OF_CONDUCT.md | -rw-r--r-- | 249 bytes |
CONTRIBUTING.md | -rw-r--r-- | 706 bytes |
COPYING | -rw-r--r-- | 17.7 KB |
DEFAULT_OPTIONS_HISTORY.md | -rw-r--r-- | 1.5 KB |
DUMP_FORMAT.md | -rw-r--r-- | 763 bytes |
HISTORY.md | -rw-r--r-- | 76.4 KB |
INSTALL.md | -rw-r--r-- | 7.5 KB |
LANGUAGE-BINDINGS.md | -rw-r--r-- | 1.1 KB |
LICENSE.Apache | -rw-r--r-- | 11.1 KB |
LICENSE.leveldb | -rw-r--r-- | 1.5 KB |
Makefile | -rw-r--r-- | 66.6 KB |
README.md | -rw-r--r-- | 1.8 KB |
ROCKSDB_LITE.md | -rw-r--r-- | 1.0 KB |
TARGETS | -rw-r--r-- | 26.8 KB |
USERS.md | -rw-r--r-- | 5.6 KB |
Vagrantfile | -rw-r--r-- | 1017 bytes |
WINDOWS_PORT.md | -rw-r--r-- | 12.5 KB |
appveyor.yml | -rw-r--r-- | 436 bytes |
defs.bzl | -rw-r--r-- | 1005 bytes |
issue_template.md | -rw-r--r-- | 243 bytes |
src.mk | -rw-r--r-- | 30.1 KB |
thirdparty.inc | -rw-r--r-- | 7.7 KB |
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...