diff options
author | Vojtech Bubnik <bubnikv@gmail.com> | 2021-07-09 13:53:16 +0300 |
---|---|---|
committer | Vojtech Bubnik <bubnikv@gmail.com> | 2021-07-09 13:53:29 +0300 |
commit | e4fd6a828f2b3b0a84aabc6971390d61e56eed95 (patch) | |
tree | 3efaf42fd71f5fd3d02a2372314b0a4123c549ce /tests/libslic3r | |
parent | c8a46c1f24752862bf52cb911e532253ca9246fd (diff) |
1) Fixed a significant bug in MutablePriorityQueue when setting
the indices allowing rescheduling of values in the middle of the queue.
2) Implemented a cache friendly variant - MutableSkipHeapPriorityQueue
based on
https://playfulprogramming.blogspot.com/2015/08/cache-optimizing-priority-queue.html
https://github.com/rollbear/prio_queue/blob/master/prio_queue.hpp
Diffstat (limited to 'tests/libslic3r')
-rw-r--r-- | tests/libslic3r/CMakeLists.txt | 1 | ||||
-rw-r--r-- | tests/libslic3r/test_mutable_priority_queue.cpp | 330 |
2 files changed, 331 insertions, 0 deletions
diff --git a/tests/libslic3r/CMakeLists.txt b/tests/libslic3r/CMakeLists.txt index 5a4203ea0..575878cf2 100644 --- a/tests/libslic3r/CMakeLists.txt +++ b/tests/libslic3r/CMakeLists.txt @@ -12,6 +12,7 @@ add_executable(${_TEST_NAME}_tests test_placeholder_parser.cpp test_polygon.cpp test_mutable_polygon.cpp + test_mutable_priority_queue.cpp test_stl.cpp test_meshsimplify.cpp test_meshboolean.cpp diff --git a/tests/libslic3r/test_mutable_priority_queue.cpp b/tests/libslic3r/test_mutable_priority_queue.cpp new file mode 100644 index 000000000..83ac28793 --- /dev/null +++ b/tests/libslic3r/test_mutable_priority_queue.cpp @@ -0,0 +1,330 @@ +#include <catch2/catch.hpp> + +#include <queue> + +#include "libslic3r/MutablePriorityQueue.hpp" + +// based on https://raw.githubusercontent.com/rollbear/prio_queue/master/self_test.cpp +// original source Copyright Björn Fahller 2015, Boost Software License, Version 1.0, http://www.boost.org/LICENSE_1_0.txt + +TEST_CASE("Skip addressing", "[MutableSkipHeapPriorityQueue]") { + using skip_addressing = SkipHeapAddressing<8>; + SECTION("block root") { + REQUIRE(skip_addressing::is_block_root(1)); + REQUIRE(skip_addressing::is_block_root(9)); + REQUIRE(skip_addressing::is_block_root(17)); + REQUIRE(skip_addressing::is_block_root(73)); + REQUIRE(! skip_addressing::is_block_root(2)); + REQUIRE(! skip_addressing::is_block_root(3)); + REQUIRE(! skip_addressing::is_block_root(4)); + REQUIRE(! skip_addressing::is_block_root(7)); + REQUIRE(! skip_addressing::is_block_root(31)); + } + SECTION("block leaf") { + REQUIRE(! skip_addressing::is_block_leaf(1)); + REQUIRE(! skip_addressing::is_block_leaf(2)); + REQUIRE(! skip_addressing::is_block_leaf(3)); + REQUIRE(skip_addressing::is_block_leaf(4)); + REQUIRE(skip_addressing::is_block_leaf(5)); + REQUIRE(skip_addressing::is_block_leaf(6)); + REQUIRE(skip_addressing::is_block_leaf(7)); + REQUIRE(skip_addressing::is_block_leaf(28)); + REQUIRE(skip_addressing::is_block_leaf(29)); + REQUIRE(skip_addressing::is_block_leaf(30)); + REQUIRE(! skip_addressing::is_block_leaf(257)); + REQUIRE(skip_addressing::is_block_leaf(255)); + } + SECTION("Obtaining child") { + REQUIRE(skip_addressing::child_of(1) == 2); + REQUIRE(skip_addressing::child_of(2) == 4); + REQUIRE(skip_addressing::child_of(3) == 6); + REQUIRE(skip_addressing::child_of(4) == 9); + REQUIRE(skip_addressing::child_of(31) == 249); + } + SECTION("Obtaining parent") { + REQUIRE(skip_addressing::parent_of(2) == 1); + REQUIRE(skip_addressing::parent_of(3) == 1); + REQUIRE(skip_addressing::parent_of(6) == 3); + REQUIRE(skip_addressing::parent_of(7) == 3); + REQUIRE(skip_addressing::parent_of(9) == 4); + REQUIRE(skip_addressing::parent_of(17) == 4); + REQUIRE(skip_addressing::parent_of(33) == 5); + REQUIRE(skip_addressing::parent_of(29) == 26); + REQUIRE(skip_addressing::parent_of(1097) == 140); + } +} + +template<size_t block_size = 16> +static auto make_test_priority_queue() +{ + return make_miniheap_mutable_priority_queue<std::pair<int, size_t>, block_size, false>( + [](std::pair<int, size_t> &v, size_t idx){ v.second = idx; }, + [](std::pair<int, size_t> &l, std::pair<int, size_t> &r){ return l.first < r.first; }); +} + +TEST_CASE("Mutable priority queue - basic tests", "[MutableSkipHeapPriorityQueue]") { + SECTION("a default constructed queue is empty") { + auto q = make_test_priority_queue(); + REQUIRE(q.empty()); + REQUIRE(q.size() == 0); + } + SECTION("an empty queue is not empty when one element is inserted") { + auto q = make_test_priority_queue(); + q.push(std::make_pair(1, 0U)); + REQUIRE(!q.empty()); + REQUIRE(q.size() == 1); + } + SECTION("a queue with one element has it on top") { + auto q = make_test_priority_queue(); + q.push(std::make_pair(8, 0U)); + REQUIRE(q.top().first == 8); + } + SECTION("a queue with one element becomes empty when popped") { + auto q = make_test_priority_queue(); + q.push(std::make_pair(9, 0U)); + q.pop(); + REQUIRE(q.empty()); + REQUIRE(q.size() == 0); + } + SECTION("insert sorted stays sorted") { + auto q = make_test_priority_queue(); + for (auto i : { 1, 2, 3, 4, 5, 6, 7, 8 }) + q.push(std::make_pair(i, 0U)); + REQUIRE(q.top().first == 1); + q.pop(); + REQUIRE(q.top().first == 2); + q.pop(); + REQUIRE(q.top().first == 3); + q.pop(); + REQUIRE(q.top().first == 4); + q.pop(); + REQUIRE(q.top().first == 5); + q.pop(); + REQUIRE(q.top().first == 6); + q.pop(); + REQUIRE(q.top().first == 7); + q.pop(); + REQUIRE(q.top().first == 8); + q.pop(); + REQUIRE(q.empty()); + } + SECTION("randomly inserted elements are popped sorted") { + auto q = make_test_priority_queue(); + std::random_device rd; + std::mt19937 gen(rd()); + std::uniform_int_distribution<> dist(1, 100000); + int n[36000]; + for (auto& i : n) { + i = dist(gen); + q.push(std::make_pair(i, 0U)); + } + + REQUIRE(!q.empty()); + REQUIRE(q.size() == 36000); + std::sort(std::begin(n), std::end(n)); + for (auto i : n) { + REQUIRE(q.top().first == i); + q.pop(); + } + REQUIRE(q.empty()); + } +} + +TEST_CASE("Mutable priority queue - reshedule first", "[MutableSkipHeapPriorityQueue]") { + SECTION("reschedule top with highest prio leaves order unchanged") { + auto q = make_miniheap_mutable_priority_queue<std::pair<std::pair<int, int*>, size_t>, 4, false>( + [](std::pair<std::pair<int, int*>, size_t>& v, size_t idx) { v.second = idx; }, + [](std::pair<std::pair<int, int*>, size_t>& l, std::pair<std::pair<int, int*>, size_t>& r) { return l.first.first < r.first.first; }); + + // 0 1 2 3 4 5 6 7 8 + int nums[] = { 32, 1, 88, 16, 9, 11, 3, 22, 23 }; + for (auto &i : nums) + q.push(std::make_pair(std::make_pair(i, &i), 0U)); + REQUIRE(q.top().first.first == 1); + REQUIRE(q.top().first.second == &nums[1]); + REQUIRE(*q.top().first.second == 1); + + // Update the top element. + q.top().first.first = 2; + q.update(1); + + REQUIRE(q.top().first.first == 2); + REQUIRE(q.top().first.second == &nums[1]); + q.pop(); + REQUIRE(q.top().first.first == 3); + REQUIRE(q.top().first.second == &nums[6]); + q.pop(); + REQUIRE(q.top().first.first == 9); + REQUIRE(q.top().first.second == &nums[4]); + q.pop(); + REQUIRE(q.top().first.first == 11); + REQUIRE(q.top().first.second == &nums[5]); + q.pop(); + REQUIRE(q.top().first.first == 16); + REQUIRE(q.top().first.second == &nums[3]); + q.pop(); + REQUIRE(q.top().first.first == 22); + REQUIRE(q.top().first.second == &nums[7]); + q.pop(); + REQUIRE(q.top().first.first == 23); + REQUIRE(q.top().first.second == &nums[8]); + q.pop(); + REQUIRE(q.top().first.first == 32); + REQUIRE(q.top().first.second == &nums[0]); + q.pop(); + REQUIRE(q.top().first.first == 88); + REQUIRE(q.top().first.second == &nums[2]); + q.pop(); + REQUIRE(q.empty()); + } + SECTION("reschedule to mid range moves element to correct place") { + auto q = make_miniheap_mutable_priority_queue<std::pair<std::pair<int, int*>, size_t>, 4, false>( + [](std::pair<std::pair<int, int*>, size_t>& v, size_t idx) { v.second = idx; }, + [](std::pair<std::pair<int, int*>, size_t>& l, std::pair<std::pair<int, int*>, size_t>& r) { return l.first.first < r.first.first; }); + + // 0 1 2 3 4 5 6 7 8 + int nums[] = { 32, 1, 88, 16, 9, 11, 3, 22, 23 }; + for (auto& i : nums) + q.push(std::make_pair(std::make_pair(i, &i), 0U)); + REQUIRE(q.top().first.first == 1); + REQUIRE(q.top().first.second == &nums[1]); + REQUIRE(*q.top().first.second == 1); + + // Update the top element. + q.top().first.first = 12; + q.update(1); + + REQUIRE(q.top().first.first == 3); + REQUIRE(q.top().first.second == &nums[6]); + q.pop(); + REQUIRE(q.top().first.first == 9); + REQUIRE(q.top().first.second == &nums[4]); + q.pop(); + REQUIRE(q.top().first.first == 11); + REQUIRE(q.top().first.second == &nums[5]); + q.pop(); + REQUIRE(q.top().first.first == 12); + REQUIRE(q.top().first.second == &nums[1]); + q.pop(); + REQUIRE(q.top().first.first == 16); + REQUIRE(q.top().first.second == &nums[3]); + q.pop(); + REQUIRE(q.top().first.first == 22); + REQUIRE(q.top().first.second == &nums[7]); + q.pop(); + REQUIRE(q.top().first.first == 23); + REQUIRE(q.top().first.second == &nums[8]); + q.pop(); + REQUIRE(q.top().first.first == 32); + REQUIRE(q.top().first.second == &nums[0]); + q.pop(); + REQUIRE(q.top().first.first == 88); + REQUIRE(q.top().first.second == &nums[2]); + q.pop(); + REQUIRE(q.empty()); + } + SECTION("reschedule to last moves element to correct place", "heap") + { + auto q = make_miniheap_mutable_priority_queue<std::pair<std::pair<int, int*>, size_t>, 4, false>( + [](std::pair<std::pair<int, int*>, size_t>& v, size_t idx) { v.second = idx; }, + [](std::pair<std::pair<int, int*>, size_t>& l, std::pair<std::pair<int, int*>, size_t>& r) { return l.first.first < r.first.first; }); + + // 0 1 2 3 4 5 6 7 8 + int nums[] = { 32, 1, 88, 16, 9, 11, 3, 22, 23 }; + for (auto& i : nums) + q.push(std::make_pair(std::make_pair(i, &i), 0U)); + REQUIRE(q.top().first.first == 1); + REQUIRE(q.top().first.second == &nums[1]); + REQUIRE(*q.top().first.second == 1); + + // Update the top element. + q.top().first.first = 89; + q.update(1); + + REQUIRE(q.top().first.first == 3); + REQUIRE(q.top().first.second == &nums[6]); + q.pop(); + REQUIRE(q.top().first.first == 9); + REQUIRE(q.top().first.second == &nums[4]); + q.pop(); + REQUIRE(q.top().first.first == 11); + REQUIRE(q.top().first.second == &nums[5]); + q.pop(); + REQUIRE(q.top().first.first == 16); + REQUIRE(q.top().first.second == &nums[3]); + q.pop(); + REQUIRE(q.top().first.first == 22); + REQUIRE(q.top().first.second == &nums[7]); + q.pop(); + REQUIRE(q.top().first.first == 23); + REQUIRE(q.top().first.second == &nums[8]); + q.pop(); + REQUIRE(q.top().first.first == 32); + REQUIRE(q.top().first.second == &nums[0]); + q.pop(); + REQUIRE(q.top().first.first == 88); + REQUIRE(q.top().first.second == &nums[2]); + q.pop(); + REQUIRE(q.top().first.first == 89); + REQUIRE(q.top().first.second == &nums[1]); + q.pop(); + REQUIRE(q.empty()); + } + SECTION("reschedule top of 2 elements to last") { + auto q = make_test_priority_queue<8>(); + q.push(std::make_pair(1, 0U)); + q.push(std::make_pair(2, 0U)); + REQUIRE(q.top().first == 1); + // Update the top element. + q.top().first = 3; + q.update(1); + REQUIRE(q.top().first == 2); + } + SECTION("reschedule top of 3 elements left to 2nd") { + auto q = make_test_priority_queue<8>(); + q.push(std::make_pair(1, 0U)); + q.push(std::make_pair(2, 0U)); + q.push(std::make_pair(4, 0U)); + REQUIRE(q.top().first == 1); + // Update the top element. + q.top().first = 3; + q.update(1); + REQUIRE(q.top().first == 2); + } + SECTION("reschedule top of 3 elements right to 2nd") { + auto q = make_test_priority_queue<8>(); + q.push(std::make_pair(1, 0U)); + q.push(std::make_pair(4, 0U)); + q.push(std::make_pair(2, 0U)); + REQUIRE(q.top().first == 1); + // Update the top element. + q.top().first = 3; + q.update(1); + REQUIRE(q.top().first == 2); + } + SECTION("reschedule top random gives same resultas pop/push") { + std::random_device rd; + std::mt19937 gen(rd()); + std::uniform_int_distribution<unsigned> dist(1, 100000); + + auto pq = make_test_priority_queue<8>(); + std::priority_queue<int, std::vector<int>, std::greater<>> stdq; + + for (size_t outer = 0; outer < 100; ++ outer) { + int num = gen(); + pq.push(std::make_pair(num, 0U)); + stdq.push(num); + for (size_t inner = 0; inner < 100; ++ inner) { + int newval = gen(); + // Update the top element. + pq.top().first = newval; + pq.update(1); + stdq.pop(); + stdq.push(newval); + auto n = pq.top().first; + auto sn = stdq.top(); + REQUIRE(sn == n); + } + } + } +} |