master

GGitHub [libc++] Speed up set_intersection() by fast-forwarding over ranges of non-matching elements with one-sided binary search. (#75230)

a0662176创建于 2024年7月19日历史提交

文件	最后提交记录	最后更新时间
adaptor.pass.cpp	[libcxx][NFC] Consolidate testing concept CanBePiped (#80154) Almost every test needed a CanBePiped concept and each implemented it separately, but identically. Consolidate all implementations into test_range.h.	2 年前
base.pass.cpp	[libc++] Make <ranges> non-experimental When we ship LLVM 16, <ranges> won't be considered experimental anymore. We might as well do this sooner rather than later. Differential Revision: https://reviews.llvm.org/D132151	3 年前
begin.pass.cpp	[libc++] Speed up set_intersection() by fast-forwarding over ranges of non-matching elements with one-sided binary search. (#75230) One-sided binary search, aka meta binary search, has been in the public domain for decades, and has the general advantage of being constant time in the best case, with the downside of executing at most 2*log(N) comparisons vs classic binary search's exact log(N). There are two scenarios in which it really shines: the first one is when operating over non-random-access iterators, because the classic algorithm requires knowing the container's size upfront, which adds N iterator increments to the complexity. The second one is when traversing the container in order, trying to fast-forward to the next value: in that case the classic algorithm requires at least O(N*log(N)) comparisons and, for non-random-access iterators, O(N^2) iterator increments, whereas the one-sided version will yield O(N) operations on both counts, with a best-case of O(log(N)) comparisons which is very common in practice.	1 年前
ctad.compile.pass.cpp	[libc++] Make <ranges> non-experimental When we ship LLVM 16, <ranges> won't be considered experimental anymore. We might as well do this sooner rather than later. Differential Revision: https://reviews.llvm.org/D132151	3 年前
ctor.default.pass.cpp	[libc++] Make <ranges> non-experimental When we ship LLVM 16, <ranges> won't be considered experimental anymore. We might as well do this sooner rather than later. Differential Revision: https://reviews.llvm.org/D132151	3 年前
ctor.view.pass.cpp	[libc++][ranges] P2711R1 Making multi-param constructors of views explicit Implemented [[ https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p2711r1.html | P2711R1 ]] for existing views. (join_with_view is not yet implemented) Reviewed By: #libc, philnik Differential Revision: https://reviews.llvm.org/D144822	3 年前
dangling.cache.pass.cpp	[libc++][test] Cleanup typos and unnecessary semicolons (#73435) I've structured this into a series of commits for even easier reviewing, if that helps. I could easily split this up into separate PRs if desired, but as this is low-risk with simple edits, I thought one PR would be easiest. * Drop unnecessary semicolons after function definitions. * Cleanup comment typos. * Cleanup static_assert typos. * Cleanup test code typos. + There should be no functional changes, assuming I've changed all occurrences. * ~~Fix massive test code typos.~~ + This was a real problem, but needed more surgery. I reverted those changes here, and @philnik777 is fixing this properly with #73444. * clang-formatting as requested by the CI.	2 年前
end.pass.cpp	[libc++] Make <ranges> non-experimental When we ship LLVM 16, <ranges> won't be considered experimental anymore. We might as well do this sooner rather than later. Differential Revision: https://reviews.llvm.org/D132151	3 年前
general.pass.cpp	[libc++] Make <ranges> non-experimental When we ship LLVM 16, <ranges> won't be considered experimental anymore. We might as well do this sooner rather than later. Differential Revision: https://reviews.llvm.org/D132151	3 年前
size.pass.cpp	[libc++] Make <ranges> non-experimental When we ship LLVM 16, <ranges> won't be considered experimental anymore. We might as well do this sooner rather than later. Differential Revision: https://reviews.llvm.org/D132151	3 年前
types.h	[libc++] Speed up set_intersection() by fast-forwarding over ranges of non-matching elements with one-sided binary search. (#75230) One-sided binary search, aka meta binary search, has been in the public domain for decades, and has the general advantage of being constant time in the best case, with the downside of executing at most 2*log(N) comparisons vs classic binary search's exact log(N). There are two scenarios in which it really shines: the first one is when operating over non-random-access iterators, because the classic algorithm requires knowing the container's size upfront, which adds N iterator increments to the complexity. The second one is when traversing the container in order, trying to fast-forward to the next value: in that case the classic algorithm requires at least O(N*log(N)) comparisons and, for non-random-access iterators, O(N^2) iterator increments, whereas the one-sided version will yield O(N) operations on both counts, with a best-case of O(log(N)) comparisons which is very common in practice.	1 年前