https://bugs.llvm.org/show_bug.cgi?id=39129
Bug ID: 39129
Summary: std::lower_bound speed can be improved.
Product: libc++
Version: unspecified
Hardware: PC
OS: All
Status: NEW
Severity: enhancement
Priority: P
Component: All Bugs
Assignee: unassignedclangb...@nondot.org
Reporter: denis.yaroshevs...@gmail.com
CC: llvm-bugs@lists.llvm.org, mclow.li...@gmail.com
Recently Sean Parent discovered that his quickly hacked implementation of
lower_bound is faster than the one that comes with the libcxx:
https://twitter.com/SeanParent/status/1042925651898974210
I did a quick experiment - the problem seems to be that he is using size_t
while std::lower_bound uses std::iterator_traits<I>::difference_type. size_t is
quicker to divide by two.
http://quick-bench.com/WhkonNgX40J3hk0A2Q8kQown96I
I ran some more measurements - the patterns seems to stay the same - here is
binary search in 1000 integers, measured for looking up each number:
https://plot.ly/~dyaroshev/110/#/
--
You are receiving this mail because:
You are on the CC list for the bug._______________________________________________
llvm-bugs mailing list
llvm-bugs@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
