diff options
| -rw-r--r-- | core/templates/paged_array.h | 349 | ||||
| -rw-r--r-- | tests/test_main.cpp | 1 | ||||
| -rw-r--r-- | tests/test_paged_array.h | 153 |
3 files changed, 503 insertions, 0 deletions
diff --git a/core/templates/paged_array.h b/core/templates/paged_array.h new file mode 100644 index 0000000000..71183c4ad8 --- /dev/null +++ b/core/templates/paged_array.h @@ -0,0 +1,349 @@ +/*************************************************************************/ +/* paged_array.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef PAGED_ARRAY_H +#define PAGED_ARRAY_H + +#include "core/os/memory.h" +#include "core/os/spin_lock.h" +#include "core/typedefs.h" + +// PagedArray is used mainly for filling a very large array from multiple threads efficiently and without causing major fragmentation + +// PageArrayPool manages central page allocation in a thread safe matter + +template <class T> +class PagedArrayPool { + T **page_pool = nullptr; + uint32_t pages_allocated = 0; + + uint32_t *available_page_pool = nullptr; + uint32_t pages_available = 0; + + uint32_t page_size = 0; + SpinLock spin_lock; + +public: + uint32_t alloc_page() { + spin_lock.lock(); + if (unlikely(pages_available == 0)) { + uint32_t pages_used = pages_allocated; + + pages_allocated++; + page_pool = (T **)memrealloc(page_pool, sizeof(T *) * pages_allocated); + available_page_pool = (uint32_t *)memrealloc(available_page_pool, sizeof(uint32_t) * pages_allocated); + + page_pool[pages_used] = (T *)memalloc(sizeof(T) * page_size); + available_page_pool[0] = pages_used; + + pages_available++; + } + + pages_available--; + uint32_t page = available_page_pool[pages_available]; + spin_lock.unlock(); + + return page; + } + T *get_page(uint32_t p_page_id) { + return page_pool[p_page_id]; + } + + void free_page(uint32_t p_page_id) { + spin_lock.lock(); + available_page_pool[pages_available] = p_page_id; + pages_available++; + spin_lock.unlock(); + } + + uint32_t get_page_size_shift() const { + return get_shift_from_power_of_2(page_size); + } + + uint32_t get_page_size_mask() const { + return page_size - 1; + } + + void reset() { + ERR_FAIL_COND(pages_available < pages_allocated); + if (pages_allocated) { + for (uint32_t i = 0; i < pages_allocated; i++) { + memfree(page_pool[i]); + } + memfree(page_pool); + memfree(available_page_pool); + page_pool = nullptr; + available_page_pool = nullptr; + pages_allocated = 0; + pages_available = 0; + } + } + bool is_configured() const { + return page_size > 0; + } + + void configure(uint32_t p_page_size) { + ERR_FAIL_COND(page_pool != nullptr); //sanity check + ERR_FAIL_COND(p_page_size == 0); + page_size = nearest_power_of_2_templated(p_page_size); + } + + PagedArrayPool(uint32_t p_page_size = 4096) { // power of 2 recommended because of alignment with OS page sizes. Even if element is bigger, its still a multiple and get rounded amount of pages + configure(p_page_size); + } + + ~PagedArrayPool() { + ERR_FAIL_COND_MSG(pages_available < pages_allocated, "Pages in use exist at exit in PagedArrayPool"); + reset(); + } +}; + +// PageArray is a local array that is optimized to grow in place, then be cleared often. +// It does so by allocating pages from a PagedArrayPool. +// It is safe to use multiple PagedArrays from different threads, sharing a single PagedArrayPool + +template <class T> +class PagedArray { + PagedArrayPool<T> *page_pool = nullptr; + + T **page_data = nullptr; + uint32_t *page_ids = nullptr; + uint32_t max_pages_used = 0; + uint32_t page_size_shift = 0; + uint32_t page_size_mask = 0; + uint64_t count = 0; + + _FORCE_INLINE_ uint32_t _get_pages_in_use() const { + if (count == 0) { + return 0; + } else { + return ((count - 1) >> page_size_shift) + 1; + } + } + + void _grow_page_array() { + //no more room in the page array to put the new page, make room + if (max_pages_used == 0) { + max_pages_used = 1; + } else { + max_pages_used *= 2; // increase in powers of 2 to keep allocations to minimum + } + page_data = (T **)memrealloc(page_data, sizeof(T *) * max_pages_used); + page_ids = (uint32_t *)memrealloc(page_ids, sizeof(uint32_t) * max_pages_used); + } + +public: + _FORCE_INLINE_ const T &operator[](uint64_t p_index) const { + CRASH_BAD_UNSIGNED_INDEX(p_index, count); + uint32_t page = p_index >> page_size_shift; + uint32_t offset = p_index & page_size_mask; + + return page_data[page][offset]; + } + _FORCE_INLINE_ T &operator[](uint64_t p_index) { + CRASH_BAD_UNSIGNED_INDEX(p_index, count); + uint32_t page = p_index >> page_size_shift; + uint32_t offset = p_index & page_size_mask; + + return page_data[page][offset]; + } + + _FORCE_INLINE_ void push_back(const T &p_value) { + uint32_t remainder = count & page_size_mask; + if (unlikely(remainder == 0)) { + // at 0, so time to request a new page + uint32_t page_count = _get_pages_in_use(); + uint32_t new_page_count = page_count + 1; + + if (unlikely(new_page_count > max_pages_used)) { + ERR_FAIL_COND(page_pool == nullptr); //sanity check + + _grow_page_array(); //keep out of inline + } + + uint32_t page_id = page_pool->alloc_page(); + page_data[page_count] = page_pool->get_page(page_id); + page_ids[page_count] = page_id; + } + + // place the new value + uint32_t page = count >> page_size_shift; + uint32_t offset = count & page_size_mask; + + if (!__has_trivial_constructor(T)) { + memnew_placement(&page_data[page][offset], T(p_value)); + } else { + page_data[page][offset] = p_value; + } + + count++; + } + + void clear() { + //destruct if needed + if (!__has_trivial_destructor(T)) { + for (uint64_t i = 0; i < count; i++) { + uint32_t page = i >> page_size_shift; + uint32_t offset = i & page_size_mask; + page_data[page][offset].~T(); + } + } + + //return the pages to the pagepool, so they can be used by another array eventually + uint32_t pages_used = _get_pages_in_use(); + for (uint32_t i = 0; i < pages_used; i++) { + page_pool->free_page(page_ids[i]); + } + + count = 0; + + //note we leave page_data and page_indices intact for next use. If you really want to clear them call reset() + } + + void reset() { + clear(); + if (page_data) { + memfree(page_data); + memfree(page_ids); + page_data = nullptr; + page_ids = nullptr; + max_pages_used = 0; + } + } + + // This takes the pages from a source array and merges them to this one + // resulting order is undefined, but content is merged very efficiently, + // making it ideal to fill content on several threads to later join it. + + void merge_unordered(PagedArray<T> &p_array) { + ERR_FAIL_COND(page_pool != p_array.page_pool); + + uint32_t remainder = count & page_size_mask; + + T *remainder_page = nullptr; + uint32_t remainder_page_id; + + if (remainder > 0) { + uint32_t last_page = _get_pages_in_use() - 1; + remainder_page = page_data[last_page]; + remainder_page_id = page_ids[last_page]; + } + + count -= remainder; + + uint32_t src_pages = p_array._get_pages_in_use(); + uint32_t page_size = page_size_mask + 1; + + for (uint32_t i = 0; i < src_pages; i++) { + uint32_t page_count = _get_pages_in_use(); + uint32_t new_page_count = page_count + 1; + + if (unlikely(new_page_count > max_pages_used)) { + _grow_page_array(); //keep out of inline + } + + page_data[page_count] = p_array.page_data[i]; + page_ids[page_count] = p_array.page_ids[i]; + if (i == src_pages - 1) { + //last page, only increment with remainder + count += p_array.count & page_size_mask; + } else { + count += page_size; + } + } + p_array.count = 0; //take away the other array pages + + //handle the remainder page if exists + if (remainder_page) { + uint32_t new_remainder = count & page_size_mask; + + if (new_remainder > 0) { + //must merge old remainder with new remainder + + T *dst_page = page_data[_get_pages_in_use() - 1]; + uint32_t to_copy = MIN(page_size - new_remainder, remainder); + + for (uint32_t i = 0; i < to_copy; i++) { + if (!__has_trivial_constructor(T)) { + memnew_placement(&dst_page[i + new_remainder], T(remainder_page[i + remainder - to_copy])); + } else { + dst_page[i + new_remainder] = remainder_page[i + remainder - to_copy]; + } + + if (!__has_trivial_destructor(T)) { + remainder_page[i + remainder - to_copy].~T(); + } + } + + remainder -= to_copy; //subtract what was copied from remainder + count += to_copy; //add what was copied to the count + + if (remainder == 0) { + //entire remainder copied, let go of remainder page + page_pool->free_page(remainder_page_id); + remainder_page = nullptr; + } + } + + if (remainder > 0) { + //there is still remainder, append it + uint32_t page_count = _get_pages_in_use(); + uint32_t new_page_count = page_count + 1; + + if (unlikely(new_page_count > max_pages_used)) { + _grow_page_array(); //keep out of inline + } + + page_data[page_count] = remainder_page; + page_ids[page_count] = remainder_page_id; + + count += remainder; + } + } + } + + uint64_t size() const { + return count; + } + + void set_page_pool(PagedArrayPool<T> *p_page_pool) { + ERR_FAIL_COND(max_pages_used > 0); //sanity check + + page_pool = p_page_pool; + page_size_mask = page_pool->get_page_size_mask(); + page_size_shift = page_pool->get_page_size_shift(); + } + + ~PagedArray() { + reset(); + } +}; + +#endif // PAGED_ARRAY_H diff --git a/tests/test_main.cpp b/tests/test_main.cpp index 9f2c2d6911..5d961854cb 100644 --- a/tests/test_main.cpp +++ b/tests/test_main.cpp @@ -54,6 +54,7 @@ #include "test_oa_hash_map.h" #include "test_object.h" #include "test_ordered_hash_map.h" +#include "test_paged_array.h" #include "test_pck_packer.h" #include "test_physics_2d.h" #include "test_physics_3d.h" diff --git a/tests/test_paged_array.h b/tests/test_paged_array.h new file mode 100644 index 0000000000..6b61160229 --- /dev/null +++ b/tests/test_paged_array.h @@ -0,0 +1,153 @@ +/*************************************************************************/ +/* test_paged_array.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef TEST_PAGED_ARRAY_H +#define TEST_PAGED_ARRAY_H + +#include "core/templates/paged_array.h" + +#include "thirdparty/doctest/doctest.h" + +namespace TestPagedArray { + +// PagedArray + +TEST_CASE("[PagedArray] Simple fill and refill") { + PagedArrayPool<uint32_t> pool; + PagedArray<uint32_t> array; + array.set_page_pool(&pool); + + for (uint32_t i = 0; i < 123456; i++) { + array.push_back(i); + } + CHECK_MESSAGE( + array.size() == 123456, + "PagedArray should have 123456 elements."); + + bool all_match = true; + for (uint32_t i = 0; i < 123456; i++) { + if (array[i] != i) { + all_match = false; + break; + } + } + + CHECK_MESSAGE( + all_match, + "PagedArray elements should match from 0 to 123455."); + + array.clear(); + + CHECK_MESSAGE( + array.size() == 0, + "PagedArray elements should be 0 after clear."); + + for (uint32_t i = 0; i < 999; i++) { + array.push_back(i); + } + CHECK_MESSAGE( + array.size() == 999, + "PagedArray should have 999 elements."); + + all_match = true; + for (uint32_t i = 0; i < 999; i++) { + if (array[i] != i) { + all_match = false; + } + } + + CHECK_MESSAGE( + all_match, + "PagedArray elements should match from 0 to 998."); + + array.reset(); //reset so pagepool can be reset + pool.reset(); +} + +TEST_CASE("[PagedArray] Shared pool fill, including merging") { + PagedArrayPool<uint32_t> pool; + PagedArray<uint32_t> array1; + PagedArray<uint32_t> array2; + array1.set_page_pool(&pool); + array2.set_page_pool(&pool); + + for (uint32_t i = 0; i < 123456; i++) { + array1.push_back(i); + } + CHECK_MESSAGE( + array1.size() == 123456, + "PagedArray #1 should have 123456 elements."); + + bool all_match = true; + for (uint32_t i = 0; i < 123456; i++) { + if (array1[i] != i) { + all_match = false; + } + } + + CHECK_MESSAGE( + all_match, + "PagedArray #1 elements should match from 0 to 123455."); + + for (uint32_t i = 0; i < 999; i++) { + array2.push_back(i); + } + CHECK_MESSAGE( + array2.size() == 999, + "PagedArray #2 should have 999 elements."); + + all_match = true; + for (uint32_t i = 0; i < 999; i++) { + if (array2[i] != i) { + all_match = false; + } + } + + CHECK_MESSAGE( + all_match, + "PagedArray #2 elements should match from 0 to 998."); + + array1.merge_unordered(array2); + + CHECK_MESSAGE( + array1.size() == 123456 + 999, + "PagedArray #1 should now be 123456 + 999 elements."); + + CHECK_MESSAGE( + array2.size() == 0, + "PagedArray #2 should now be 0 elements."); + + array1.reset(); //reset so pagepool can be reset + array2.reset(); //reset so pagepool can be reset + pool.reset(); +} +} // namespace TestPagedArray + +#endif // TEST_PAGED_ARRAY_H |