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
.gitignore
make_config.mk
*.a
*.arc
*.d
*.dylib*
*.gcda
*.gcno
*.o
*.so
*.so.*
*_test
*_bench
*_stress
*.out
*.class
*.jar
*.*jnilib*
*.d-e
*.o-*
*.swp
*~
*.vcxproj
*.vcxproj.filters
*.sln
*.cmake
CMakeCache.txt
CMakeFiles/
build/
ldb
manifest_dump
sst_dump
blob_dump
column_aware_encoding_exp
util/build_version.cc
build_tools/VALGRIND_LOGS/
coverage/COVERAGE_REPORT
.gdbhistory
.gdb_history
package/
unity.a
tags
etags
rocksdb_dump
rocksdb_undump
db_test2
trace_analyzer
trace_analyzer_test
java/out
java/target
java/test-libs
java/*.log
java/include/org_rocksdb_*.h
.idea/
*.iml
rocksdb.cc
rocksdb.h
unity.cc
java/crossbuild/.vagrant
.vagrant/
java/**/*.asc
java/javadoc
scan_build_report/
t
LOG
db_logs/
tp2/
fbcode/
fbcode
buckifier/*.pyc
Computing file changes ...