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
26
14
src/core/pool_type.hpp
4
0 comments (0 inline, 0 general)
src/core/pool_func.hpp
➞
Show inline comments
 
@@ -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;

			




        

    


    
    

    

        

                

                    src/core/pool_type.hpp
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -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;

			




        

    



    


    



    



      

      





    
    0 comments (0 inline, 0 general)
    





    


  

  







  


    




    








    
        Server instance: code.theleruby.com-48
    
    
        This site is powered by
            Kallithea,
        which is
        © 2010–2022 by various authors & licensed under GPLv3.
            – Support