# HG changeset patch
# User Peter Nelson <peter1138@openttd.org>
# Date 2024-02-17 18:29:21
# Node ID c42d642d099c94a2e3c9d61c06b629106500a5f3
# Parent  77bdfd1c02e19e5e7c17dfed0a4639a22f748b8c

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.

diff --git a/src/core/pool_func.hpp b/src/core/pool_func.hpp
--- a/src/core/pool_func.hpp
+++ b/src/core/pool_func.hpp
@@ -11,6 +11,7 @@
 #define POOL_FUNC_HPP
 
 #include "alloc_func.hpp"
+#include "bitmath_func.hpp"
 #include "mem_func.hpp"
 #include "pool_type.hpp"
 #include "../error_func.h"
@@ -60,6 +61,16 @@ DEFINE_POOL_METHOD(inline void)::ResizeF
 	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;
 }
 
@@ -69,25 +80,20 @@ DEFINE_POOL_METHOD(inline void)::ResizeF
  */
 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;
 }
@@ -122,6 +128,7 @@ DEFINE_POOL_METHOD(inline void *)::Alloc
 		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;
 }
@@ -190,7 +197,10 @@ DEFINE_POOL_METHOD(void)::FreeItem(size_
 	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. */
@@ -202,6 +212,8 @@ DEFINE_POOL_METHOD(void)::CleanPool()
 	}
 	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;
diff --git a/src/core/pool_type.hpp b/src/core/pool_type.hpp
--- a/src/core/pool_type.hpp
+++ b/src/core/pool_type.hpp
@@ -83,6 +83,9 @@ struct Pool : PoolBase {
 
 	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
@@ -95,6 +98,7 @@ struct Pool : PoolBase {
 	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;