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
Raw File
.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
back to top