[llvm-bugs] [Bug 39129] New: std::lower_bound speed can be improved.

[via llvm-bugs]

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: unassignedclangbugs at nondot.org
          Reporter: denis.yaroshevskij at gmail.com
                CC: llvm-bugs at lists.llvm.org, mclow.lists at 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20180929/0e861e5e/attachment.html>