Add a paged array template

Used for reusable stacks, or filling arrays from multiple threads efficiently.

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