From 340dc8fa5be06ed909fe54bc4ca135921dc70cae Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sun, 30 Jun 2024 12:30:48 +0100 Subject: Maintain a reverse index in instance vertices Removes need to search unused and/or index when moving/adding things --- gfx/gl/instanceVertices.h | 24 ++++++++++++------ test/test-instancing.cpp | 64 +++++++++++++++++++++++++++++++++++++++++------ test/testHelpers.h | 8 ++++++ 3 files changed, 80 insertions(+), 16 deletions(-) diff --git a/gfx/gl/instanceVertices.h b/gfx/gl/instanceVertices.h index ad1716d..28e11ee 100644 --- a/gfx/gl/instanceVertices.h +++ b/gfx/gl/instanceVertices.h @@ -107,10 +107,12 @@ public: auto idx = unused.back(); unused.pop_back(); index[idx] = base::size(); + reverseIndex.emplace_back(idx); base::emplace_back(std::forward(params)...); return InstanceProxy {this, idx}; } index.emplace_back(base::size()); + reverseIndex.push_back(base::size()); base::emplace_back(std::forward(params)...); return InstanceProxy {this, index.size() - 1}; } @@ -132,24 +134,27 @@ public: } protected: + static constexpr auto npos = static_cast(-1); friend InstanceProxy; void release(const size_t pidx) { - if (base::size() - 1 != index[pidx]) { + if (const size_t last = base::size() - 1; last != index[pidx]) { lookup(pidx) = std::move(base::back()); - *std::find_if(index.begin(), index.end(), [this, old = base::size() - 1](const auto & i) { - return i == old && !std::binary_search(unused.begin(), unused.end(), &i - index.data()); - }) = index[pidx]; + const auto movedKey = reverseIndex[last]; + index[movedKey] = std::exchange(index[pidx], npos); + reverseIndex[index[movedKey]] = movedKey; } base::pop_back(); + reverseIndex.pop_back(); if (pidx == index.size() - 1) { index.pop_back(); } else { - // Remember p.index is free index now, keeping it sorted - unused.insert(std::upper_bound(unused.begin(), unused.end(), pidx), pidx); + index[pidx] = npos; + // Remember p.index is free index now + unused.emplace_back(pidx); } } @@ -168,8 +173,10 @@ protected: last = --std::find_if(std::make_reverse_iterator(last), std::make_reverse_iterator(first), pred).base(); if (first < last) { std::iter_swap(first, last); - std::iter_swap(std::find(index.begin(), index.end(), first - base::begin()), - std::find(index.begin(), index.end(), last - base::begin())); + const auto fidx = static_cast(first - base::begin()), + lidx = static_cast(last - base::begin()); + std::swap(index[reverseIndex[fidx]], index[reverseIndex[lidx]]); + std::swap(reverseIndex[fidx], reverseIndex[lidx]); } } return first; @@ -177,6 +184,7 @@ protected: // Index into buffer given to nth proxy std::vector index; + std::vector reverseIndex; // List of free spaces in index std::vector unused; }; diff --git a/test/test-instancing.cpp b/test/test-instancing.cpp index 37f32c8..77467d8 100644 --- a/test/test-instancing.cpp +++ b/test/test-instancing.cpp @@ -13,12 +13,33 @@ BOOST_GLOBAL_FIXTURE(ApplicationBase); BOOST_GLOBAL_FIXTURE(TestMainWindow); -BOOST_FIXTURE_TEST_SUITE(i, InstanceVertices) +struct TestInstanceVertices : public InstanceVertices { + void + checkReverseIndex(std::source_location ctx = std::source_location::current()) + { + BOOST_TEST_CONTEXT(ctx.function_name() << ":" << ctx.line()) { + std::vector genIndexIndex(size(), npos); + for (size_t i {}; i < index.size(); i++) { + if (index[i] != npos) { + BOOST_REQUIRE_EQUAL(genIndexIndex.at(index[i]), npos); + genIndexIndex.at(index[i]) = i; + } + } + + BOOST_TEST_CONTEXT(reverseIndex << genIndexIndex) { + BOOST_CHECK_EQUAL_COLCOL(reverseIndex, genIndexIndex); + } + } + } +}; + +BOOST_FIXTURE_TEST_SUITE(i, TestInstanceVertices) BOOST_AUTO_TEST_CASE(createDestroy) { BOOST_CHECK(unused.empty()); BOOST_CHECK(index.empty()); + BOOST_CHECK(reverseIndex.empty()); } BOOST_AUTO_TEST_CASE(acquireRelease) @@ -29,11 +50,14 @@ BOOST_AUTO_TEST_CASE(acquireRelease) BOOST_CHECK_EQUAL(1, size()); BOOST_REQUIRE_EQUAL(1, index.size()); BOOST_CHECK_EQUAL(0, index.front()); + BOOST_REQUIRE_EQUAL(1, reverseIndex.size()); + BOOST_CHECK_EQUAL(0, reverseIndex.front()); BOOST_CHECK(unused.empty()); } BOOST_CHECK_EQUAL(0, size()); BOOST_CHECK(unused.empty()); BOOST_CHECK(index.empty()); + BOOST_CHECK(reverseIndex.empty()); } BOOST_AUTO_TEST_CASE(acquireReleaseMove) @@ -50,6 +74,7 @@ BOOST_AUTO_TEST_CASE(acquireReleaseMove) BOOST_CHECK_EQUAL(0, size()); BOOST_CHECK(unused.empty()); BOOST_CHECK(index.empty()); + BOOST_CHECK(reverseIndex.empty()); } BOOST_AUTO_TEST_CASE(autoMapUnmap) @@ -100,15 +125,13 @@ BOOST_AUTO_TEST_CASE(shuffle) BOOST_CHECK_EQUAL(at(2), *proxies[2].get()); BOOST_CHECK_EQUAL(at(3), *proxies[3].get()); BOOST_CHECK(unused.empty()); - BOOST_REQUIRE_EQUAL(4, index.size()); - BOOST_CHECK_EQUAL(0, index[0]); - BOOST_CHECK_EQUAL(1, index[1]); - BOOST_CHECK_EQUAL(2, index[2]); - BOOST_CHECK_EQUAL(3, index[3]); + BOOST_CHECK_EQUAL_COLVALS(index, 0, 1, 2, 3); + checkReverseIndex(); // Remove 1, 3 moves to [1] proxies.erase(proxies.begin() + 1); BOOST_REQUIRE_EQUAL(3, proxies.size()); - BOOST_REQUIRE_EQUAL(4, index.size()); + BOOST_CHECK_EQUAL_COLVALS(index, 0, npos, 2, 1); + BOOST_CHECK_EQUAL_COLVALS(reverseIndex, 0, 3, 2); BOOST_REQUIRE_EQUAL(1, unused.size()); BOOST_CHECK_EQUAL(1, unused[0]); BOOST_CHECK_EQUAL(at(0), *proxies[0].get()); @@ -117,6 +140,8 @@ BOOST_AUTO_TEST_CASE(shuffle) // Remove 1, 2 moves to [1] proxies.erase(proxies.begin() + 1); BOOST_REQUIRE_EQUAL(4, index.size()); + BOOST_CHECK_EQUAL_COLVALS(index, 0, npos, npos, 1); + checkReverseIndex(); BOOST_REQUIRE_EQUAL(2, unused.size()); BOOST_CHECK_EQUAL(1, unused[0]); BOOST_CHECK_EQUAL(2, unused[1]); @@ -124,12 +149,33 @@ BOOST_AUTO_TEST_CASE(shuffle) BOOST_CHECK_EQUAL(at(1), *proxies[1].get()); // Add new, takes 2 at [2] BOOST_CHECK_EQUAL(4, proxies.emplace_back(acquire(4))); - BOOST_REQUIRE_EQUAL(4, index.size()); + BOOST_CHECK_EQUAL_COLVALS(index, 0, npos, 2, 1); + checkReverseIndex(); BOOST_REQUIRE_EQUAL(1, unused.size()); BOOST_CHECK_EQUAL(1, unused[0]); BOOST_CHECK_EQUAL(at(0), *proxies[0].get()); BOOST_CHECK_EQUAL(at(1), *proxies[1].get()); BOOST_CHECK_EQUAL(at(2), *proxies[2].get()); + // Add new, takes 1 at [3] + BOOST_CHECK_EQUAL(5, proxies.emplace_back(acquire(5))); + BOOST_REQUIRE_EQUAL(proxies.size(), reverseIndex.size()); + BOOST_CHECK_EQUAL_COLVALS(index, 0, 3, 2, 1); + checkReverseIndex(); + // Add new, takes 4 at [4] + BOOST_CHECK_EQUAL(6, proxies.emplace_back(acquire(6))); + BOOST_REQUIRE_EQUAL(proxies.size(), reverseIndex.size()); + BOOST_CHECK_EQUAL_COLVALS(index, 0, 3, 2, 1, 4); + checkReverseIndex(); + // Remove [0] + proxies.erase(proxies.begin()); + BOOST_REQUIRE_EQUAL(proxies.size(), reverseIndex.size()); + BOOST_CHECK_EQUAL_COLVALS(index, npos, 3, 2, 1, 0); + checkReverseIndex(); + // Remove [3] + proxies.erase(proxies.begin()); + BOOST_REQUIRE_EQUAL(proxies.size(), reverseIndex.size()); + BOOST_CHECK_EQUAL_COLVALS(index, npos, 1, 2, npos, 0); + checkReverseIndex(); } BOOST_DATA_TEST_CASE(shuffle_random, boost::unit_test::data::xrange(0, 10), x) @@ -163,6 +209,7 @@ BOOST_DATA_TEST_CASE(shuffle_random, boost::unit_test::data::xrange(0, 10), x) iused.emplace(index[i]); } } + checkReverseIndex(); BOOST_TEST_CONTEXT(index) { BOOST_REQUIRE_EQUAL(iused.size(), size()); @@ -202,6 +249,7 @@ BOOST_AUTO_TEST_CASE(partition_by, *boost::unit_test::timeout(1)) // The partition point is right... BOOST_CHECK(!pred(*matchedEnd)); BOOST_CHECK(pred(*--matchedEnd)); + checkReverseIndex(); } BOOST_AUTO_TEST_SUITE_END() diff --git a/test/testHelpers.h b/test/testHelpers.h index c9fd6dc..a261b3d 100644 --- a/test/testHelpers.h +++ b/test/testHelpers.h @@ -51,3 +51,11 @@ loadFixtureJson(const std::filesystem::path & path) BOOST_CHECK(VAR); \ } \ else + +#define BOOST_CHECK_EQUAL_COLCOL(cola_, colb_) \ + BOOST_CHECK_EQUAL_COLLECTIONS(cola_.begin(), cola_.end(), colb_.begin(), colb_.end()) +#define BOOST_CHECK_EQUAL_COLVALS(col_, ...) \ + { \ + const std::initializer_list vals {__VA_ARGS__}; \ + BOOST_CHECK_EQUAL_COLLECTIONS(col_.begin(), col_.end(), vals.begin(), vals.end()); \ + } -- cgit v1.2.3