cpp/openttd-patchpack/source Changeset - r28778:c42d642d099c

Changeset - r28778:c42d642d099c

Parent rev.

Child rev.

[Not reviewed]

master

0 2 0

Peter Nelson - 10 months ago 2024-02-17 18:29:21
peter1138@openttd.org

Change: Improve performance of finding free pool slots. (#12055)

Add a bitmap of used pool slots which allows finding a free pool slot without having to check if each index is already used or not.

Loosely based on a JGRPP patch.

2 files changed with 30 insertions and 14 deletions:

src/core/pool_func.hpp

src/core/pool_type.hpp

0 comments (0 inline, 0 general)

src/core/pool_func.hpp

➞

Show inline comments

@@ @@ -8,12 +8,13 @@ @@
 /** @file pool_func.hpp Some methods of Pool are placed here in order to reduce compilation time and binary size. */
 #ifndef POOL_FUNC_HPP
 #define POOL_FUNC_HPP
 #include "alloc_func.hpp"
 #include "bitmath_func.hpp"
 #include "mem_func.hpp"
 #include "pool_type.hpp"
 #include "../error_func.h"
 #include "../saveload/saveload_error.hpp" // SlErrorCorruptFmt
@@ @@ -57,40 +58,45 @@ DEFINE_POOL_METHOD(inline void)::ResizeF @@
 	size_t new_size = std::min(Tmax_size, Align(index + 1, Tgrowth_step));
 	this->data = ReallocT(this->data, new_size);
 	MemSetT(this->data + this->size, 0, new_size - this->size);
 	this->used_bitmap.resize(Align(new_size, BITMAP_SIZE) / BITMAP_SIZE);
 	if (this->size % BITMAP_SIZE != 0) {
 		/* Already-allocated bits above old size are now unused. */
 		this->used_bitmap[this->size / BITMAP_SIZE] &= ~((~static_cast<BitmapStorage>(0)) << (this->size % BITMAP_SIZE));
+	}
 	if (new_size % BITMAP_SIZE != 0) {
 		/* Bits above new size are considered used. */
 		this->used_bitmap[new_size / BITMAP_SIZE] |= (~static_cast<BitmapStorage>(0)) << (new_size % BITMAP_SIZE);
+	}
 	this->size = new_size;
+}
 /**
  * Searches for first free index
  * @return first free index, NO_FREE_ITEM on failure
  */
 DEFINE_POOL_METHOD(inline size_t)::FindFirstFree()
+{
 	size_t index = this->first_free;
 	for (; index < this->first_unused; index++) {
 		if (this->data[index] == nullptr) return index;
+	}
 	if (index < this->size) {
 		return index;
 	for (auto it = std::next(std::begin(this->used_bitmap), this->first_free / BITMAP_SIZE); it != std::end(this->used_bitmap); ++it) {
 		BitmapStorage available = ~(*it);
 		if (available == 0) continue;
 		return std::distance(std::begin(this->used_bitmap), it) * BITMAP_SIZE + FindFirstBit(available);
+	}
 	assert(index == this->size);
 	assert(this->first_unused == this->size);
 	if (index < Tmax_size) {
 		this->ResizeFor(index);
 		return index;
 	if (this->first_unused < Tmax_size) {
 		this->ResizeFor(this->first_unused);
 		return this->first_unused;
+	}
-	assert(this->items == Tmax_size);
+	assert(this->first_unused == Tmax_size);
 	return NO_FREE_ITEM;
+}
 /**
  * Makes given index valid
@@ @@ -119,12 +125,13 @@ DEFINE_POOL_METHOD(inline void *)::Alloc @@
 	} else if (Tzero) {
 		item = (Titem *)CallocT<byte>(size);
 	} else {
 		item = (Titem *)MallocT<byte>(size);
+	}
 	this->data[index] = item;
 	SetBit(this->used_bitmap[index / BITMAP_SIZE], index % BITMAP_SIZE);
 	item->index = (Tindex)(uint)index;
 	return item;
+}
 /**
  * Allocates new item
@@ @@ -187,24 +194,29 @@ DEFINE_POOL_METHOD(void)::FreeItem(size_ @@
 	} else {
 		free(this->data[index]);
+	}
 	this->data[index] = nullptr;
 	this->first_free = std::min(this->first_free, index);
 	this->items--;
 	if (!this->cleaning) Titem::PostDestructor(index);
 	if (!this->cleaning) {
 		ClrBit(this->used_bitmap[index / BITMAP_SIZE], index % BITMAP_SIZE);
 		Titem::PostDestructor(index);
+	}
+}
 /** Destroys all items in the pool and resets all member variables. */
 DEFINE_POOL_METHOD(void)::CleanPool()
+{
 	this->cleaning = true;
 	for (size_t i = 0; i < this->first_unused; i++) {
 		delete this->Get(i); // 'delete nullptr;' is very valid
+	}
 	assert(this->items == 0);
 	free(this->data);
 	this->used_bitmap.clear();
 	this->used_bitmap.shrink_to_fit();
 	this->first_unused = this->first_free = this->size = 0;
 	this->data = nullptr;
 	this->cleaning = false;
 	if (Tcache) {
 		while (this->alloc_cache != nullptr) {

src/core/pool_type.hpp

➞

Show inline comments

@@ @@ -80,24 +80,28 @@ template <class Titem, typename Tindex, @@
 struct Pool : PoolBase {
 	/* Ensure Tmax_size is within the bounds of Tindex. */
 	static_assert((uint64_t)(Tmax_size - 1) >> 8 * sizeof(Tindex) == 0);
 	static constexpr size_t MAX_SIZE = Tmax_size; ///< Make template parameter accessible from outside
 	using BitmapStorage = size_t;
 	static constexpr size_t BITMAP_SIZE = std::numeric_limits<BitmapStorage>::digits;
 	const char * const name; ///< Name of this pool
 	size_t size;         ///< Current allocated size
 	size_t first_free;   ///< No item with index lower than this is free (doesn't say anything about this one!)
 	size_t first_unused; ///< This and all higher indexes are free (doesn't say anything about first_unused-1 !)
 	size_t items;        ///< Number of used indexes (non-nullptr)
 #ifdef WITH_ASSERT
 	size_t checked;      ///< Number of items we checked for
 #endif /* WITH_ASSERT */
 	bool cleaning;       ///< True if cleaning pool (deleting all items)
 	Titem **data;        ///< Pointer to array of pointers to Titem
 	std::vector<BitmapStorage> used_bitmap; ///< Bitmap of used indices.
 	Pool(const char *name);
 	void CleanPool() override;
 	/**
 	 * Returns Titem with given index

0 comments (0 inline, 0 general)