From b8889129c6c2b747ff771b711cfbbf91bca93bb6 Mon Sep 17 00:00:00 2001 From: Dan Goodliffe Date: Sat, 22 Apr 2023 11:44:38 +0100 Subject: Fix the instancing maintenance --- gfx/gl/instanceVertices.h | 83 ++++++++++++++++++++++++------------ test/test-instancing.cpp | 105 +++++++++++++++++++++++++++++++++++++++++----- 2 files changed, 152 insertions(+), 36 deletions(-) diff --git a/gfx/gl/instanceVertices.h b/gfx/gl/instanceVertices.h index c2ddb1d..036b48e 100644 --- a/gfx/gl/instanceVertices.h +++ b/gfx/gl/instanceVertices.h @@ -32,37 +32,38 @@ public: InstanceProxy & operator=(InstanceProxy && other) { + if (instances) { + instances->release(*this); + } instances = std::exchange(other.instances, nullptr); index = other.index; + return *this; + } + template + T & + operator=(U && v) + { + return instances->at(index) = std::forward(v); } operator T &() { - return *get(); + return instances->at(index); } operator const T &() const { - return *get(); - } - template - T & - operator=(U && v) - { - instances->map(); - return instances->data[index] = std::forward(v); + return instances->at(index); } T * get() { - instances->map(); - return &instances->data[index]; + return &instances->at(index); } const T * get() const { - instances->map(); - return &instances->data[index]; + return &instances->at(index); } T * operator->() @@ -77,12 +78,12 @@ public: T & operator*() { - return *get(); + return instances->at(index); } const T & operator*() const { - return *get(); + return instances->at(index); } private: @@ -100,22 +101,16 @@ public: if (!unused.empty()) { auto idx = unused.back(); unused.pop_back(); - new (data + idx) T(std::forward(params)...); + index[idx] = next++; + new (&at(idx)) T(std::forward(params)...); return InstanceProxy {this, idx}; } if (next >= capacity) { resize(capacity * 2); } - new (data + next) T(std::forward(params)...); - return InstanceProxy {this, next++}; - } - - void - release(const InstanceProxy & p) - { - map(); - data[p.index].~T(); - unused.push_back(p.index); + index.emplace_back(next++); + new (data + index.back()) T(std::forward(params)...); + return InstanceProxy {this, index.size() - 1}; } const auto & @@ -135,6 +130,30 @@ public: protected: friend InstanceProxy; + void + release(const InstanceProxy & p) + { + // Destroy p's object + at(p.index).~T(); + if (next-- > index[p.index]) { + // Remember p.index is free index now + unused.push_back(p.index); + // Move last object into p's slot + new (&at(p.index)) T {std::move(data[next])}; + (data[next]).~T(); + for (auto & i : index) { + if (i == next) { + i = index[p.index]; + break; + } + } + index[p.index] = 100000; + } + else { + index.pop_back(); + } + } + void allocBuffer(std::size_t newCapacity) { @@ -160,6 +179,13 @@ protected: capacity = newCapacity; } + T & + at(size_t pindex) + { + map(); + return data[index[pindex]]; + } + void map() const { @@ -179,7 +205,12 @@ protected: glBuffer buffer; mutable T * data {}; + // Size of buffer std::size_t capacity {}; + // # used of capacity std::size_t next {}; + // Index into buffer given to nth proxy + std::vector index; + // List of free spaces in index std::vector unused; }; diff --git a/test/test-instancing.cpp b/test/test-instancing.cpp index 2eb3647..8837071 100644 --- a/test/test-instancing.cpp +++ b/test/test-instancing.cpp @@ -1,10 +1,12 @@ #define BOOST_TEST_MODULE instancing +#include "stream_support.hpp" #include "testHelpers.h" #include "testMainWindow.h" #include "ui/applicationBase.h" #include #include +#include #include @@ -20,28 +22,25 @@ BOOST_AUTO_TEST_CASE(createDestroy) BOOST_REQUIRE(data); BOOST_CHECK_EQUAL(0, next); BOOST_CHECK(unused.empty()); + BOOST_CHECK(index.empty()); unmap(); BOOST_CHECK(!data); } -BOOST_AUTO_TEST_CASE(storeRetreive) -{ // Read write raw buffer, not normally allowed - std::vector test(capacity); - map(); - std::copy(test.begin(), test.end(), data); - BOOST_CHECK_EQUAL_COLLECTIONS(test.begin(), test.end(), data, data + capacity); -} - BOOST_AUTO_TEST_CASE(acquireRelease) { { auto proxy = acquire(); *proxy = 20; BOOST_CHECK_EQUAL(1, next); + BOOST_REQUIRE_EQUAL(1, index.size()); + BOOST_CHECK_EQUAL(0, index.front()); + BOOST_CHECK(unused.empty()); } - BOOST_CHECK_EQUAL(1, next); + BOOST_CHECK_EQUAL(0, next); BOOST_CHECK_EQUAL(1, unused.size()); BOOST_CHECK_EQUAL(0, unused.front()); + BOOST_CHECK_EQUAL(1, index.size()); } BOOST_AUTO_TEST_CASE(acquireReleaseMove) @@ -54,9 +53,10 @@ BOOST_AUTO_TEST_CASE(acquireReleaseMove) *proxy2 = 40; BOOST_CHECK_EQUAL(1, next); } - BOOST_CHECK_EQUAL(1, next); + BOOST_CHECK_EQUAL(0, next); BOOST_CHECK_EQUAL(1, unused.size()); BOOST_CHECK_EQUAL(0, unused.front()); + BOOST_CHECK_EQUAL(1, index.size()); } BOOST_AUTO_TEST_CASE(initialize) @@ -78,4 +78,89 @@ BOOST_AUTO_TEST_CASE(resize) BOOST_CHECK_EQUAL_COLLECTIONS(expected.begin(), expected.end(), proxies.begin(), proxies.end()); } +BOOST_AUTO_TEST_CASE(shuffle) +{ + std::vector proxies; + BOOST_CHECK_EQUAL(0, proxies.emplace_back(acquire(0))); + BOOST_CHECK_EQUAL(1, proxies.emplace_back(acquire(1))); + BOOST_CHECK_EQUAL(2, proxies.emplace_back(acquire(2))); + BOOST_CHECK_EQUAL(3, proxies.emplace_back(acquire(3))); + BOOST_CHECK_EQUAL(4, next); + BOOST_CHECK_EQUAL(data + 0, proxies[0].get()); + BOOST_CHECK_EQUAL(data + 1, proxies[1].get()); + BOOST_CHECK_EQUAL(data + 2, proxies[2].get()); + BOOST_CHECK_EQUAL(data + 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]); + // Remove 1, 3 moves to [1] + proxies.erase(proxies.begin() + 1); + BOOST_REQUIRE_EQUAL(4, index.size()); + BOOST_REQUIRE_EQUAL(1, unused.size()); + BOOST_CHECK_EQUAL(1, unused[0]); + BOOST_CHECK_EQUAL(data + 0, proxies[0].get()); + BOOST_CHECK_EQUAL(data + 2, proxies[1].get()); + BOOST_CHECK_EQUAL(data + 1, proxies[2].get()); + // Remove 1, 2 moves to [1] + proxies.erase(proxies.begin() + 1); + BOOST_REQUIRE_EQUAL(4, index.size()); + BOOST_REQUIRE_EQUAL(2, unused.size()); + BOOST_CHECK_EQUAL(1, unused[0]); + BOOST_CHECK_EQUAL(2, unused[1]); + BOOST_CHECK_EQUAL(data + 0, proxies[0].get()); + BOOST_CHECK_EQUAL(data + 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_REQUIRE_EQUAL(1, unused.size()); + BOOST_CHECK_EQUAL(1, unused[0]); + BOOST_CHECK_EQUAL(data + 0, proxies[0].get()); + BOOST_CHECK_EQUAL(data + 1, proxies[1].get()); + BOOST_CHECK_EQUAL(data + 2, proxies[2].get()); +} + +BOOST_DATA_TEST_CASE(shuffle_random, boost::unit_test::data::xrange(0, 10), x) +{ + std::ignore = x; + std::mt19937 gen(std::random_device {}()); + std::map::InstanceProxy> proxies; + const std::string_view actions = "aaaaaaaarararrraarrrararararaarrrarararararararararraarrrraaaarararaararar"; + int n {}; + for (const auto action : actions) { + switch (action) { + case 'a': + BOOST_REQUIRE_EQUAL(n, proxies.emplace(n, acquire(n)).first->second); + n++; + break; + case 'r': + BOOST_REQUIRE(!proxies.empty()); + auto e = std::next(proxies.begin(), + std::uniform_int_distribution<> {0, static_cast(proxies.size() - 1)}(gen)); + proxies.erase(e); + break; + } + + BOOST_REQUIRE_EQUAL(next, proxies.size()); + for (const auto & [n, p] : proxies) { + BOOST_REQUIRE_EQUAL(n, p); + } + std::set iused; + for (size_t i {}; i < index.size(); i++) { + if (std::find(unused.begin(), unused.end(), i) == unused.end()) { + iused.emplace(index[i]); + } + } + BOOST_TEST_CONTEXT(index) { + BOOST_REQUIRE_EQUAL(iused.size(), next); + if (!iused.empty()) { + BOOST_REQUIRE_EQUAL(*iused.begin(), 0); + BOOST_REQUIRE_EQUAL(*iused.rbegin(), next - 1); + } + } + } +} + BOOST_AUTO_TEST_SUITE_END() -- cgit v1.2.3