Allocates memory in large chunks for better runtime. More...

#include <ogdf/basic/memory/PoolMemoryAllocator.h>

Classes
struct	MemElem
	Basic memory element used to realize a linked list of deallocated memory segments. More...

Public Member Functions
	PoolMemoryAllocator ()

	~PoolMemoryAllocator ()

Static Public Member Functions
static void *	allocate (size_t nBytes)
	Allocates memory of size `nBytes`. More...

static bool	checkSize (size_t nBytes)
	Returns true iff allocate can be invoked with `nBytes`. More...

static void	cleanup ()
	Frees all allocated memory. More...

static void	deallocate (size_t nBytes, void *p)
	Deallocates memory at address `p` which is of size `nBytes`. More...

static void	deallocateList (size_t nBytes, void pHead, void pTail)
	Deallocate a complete list starting at `pHead` and ending at `pTail`. More...

static void	defragGlobal ()
	Defragments the global free lists. More...

static void	defragThread ()
	Defragments the thread's free lists. More...

static void	flushPool ()
	Flushes all free but allocated bytes (s_tp) to the thread-global list (s_pool) of allocated bytes. More...

static void	getGlobalFreeListSizes (std::vector< size_t > &sizes)
	Reports the number of pooled memory chunks in the global free lists for each possible size up to TABLE_SIZE. More...

static void	getThreadFreeListSizes (std::vector< size_t > &sizes)
	Reports the number of pooled memory chunks in the thread's free lists for each possible size up to TABLE_SIZE. More...

static size_t	memoryAllocatedInBlocks ()
	Returns the total amount of memory (in bytes) allocated from the system. More...

static size_t	memoryInGlobalFreeList ()
	Returns the total amount of memory (in bytes) available in the global free lists. More...

static size_t	memoryInThreadFreeList ()
	Returns the total amount of memory (in bytes) available in the thread's free lists. More...

Private Types
using	MemElemPtr = MemElem *

Static Private Member Functions
static MemElemPtr	allocateBlock ()

static void	enterCS ()

static void *	fillPool (MemElemPtr &pFreeBytes, uint16_t nBytes)

static void	leaveCS ()

static void	makeSlices (MemElemPtr p, int nWords, int nSlices)

static int	slicesPerBlock (uint16_t nBytes)

static int	slicesPerBlock (uint16_t nBytes, int &nWords)

Static Private Attributes
static constexpr size_t	BLOCK_SIZE = 8192

static constexpr size_t	MIN_BYTES = sizeof(MemElemPtr)

static BlockChain *	s_blocks
	Holds all allocated memory independently of whether it is cleared in chunks of size BLOCK_SIZE. More...

static long long	s_globallyAllocatedBytes
	Holds the number of globally allocated bytes for debugging. More...

static thread_local long long	s_locallyAllocatedBytes
	Holds the number of thread-locally allocated bytes for debugging. More...

static std::mutex	s_mutex

static PoolElement	s_pool [TABLE_SIZE]
	Contains allocated but free memory that may be used by all threads. Filled upon exiting a thread that allocated memory that was later freed. More...

static thread_local MemElemPtr	s_tp [TABLE_SIZE]
	Contains the allocated but free memory for a single thread. More...

static constexpr size_t	TABLE_SIZE = 256

Detailed Description

Allocates memory in large chunks for better runtime.

Possibly allocates more memory than required. Newly allocated chunks contain BLOCK_SIZE many bytes. Can allocate elements of size at most TABLE_SIZE.

For each requested memory segment of BLOCK_SIZE bytes, OGDF_POINTER_SIZE bytes are allocated in addition to store a pointer to another segment of memory.

This allows to store memory that is requested to be deallocated in a single linked list, and re-distribute it upon later allocation requests, instead of actually decallocating it.

Definition at line 59 of file PoolMemoryAllocator.h.

Member Typedef Documentation

◆ MemElemPtr

using ogdf::PoolMemoryAllocator::MemElemPtr = MemElem*

private

Definition at line 65 of file PoolMemoryAllocator.h.

Constructor & Destructor Documentation

◆ PoolMemoryAllocator()

ogdf::PoolMemoryAllocator::PoolMemoryAllocator ( )

inline

Definition at line 75 of file PoolMemoryAllocator.h.

◆ ~PoolMemoryAllocator()

ogdf::PoolMemoryAllocator::~PoolMemoryAllocator ( )

inline

Definition at line 77 of file PoolMemoryAllocator.h.

Member Function Documentation

◆ allocate()

static void* ogdf::PoolMemoryAllocator::allocate ( size_t nBytes )

static

Allocates memory of size nBytes.

◆ allocateBlock()

static MemElemPtr ogdf::PoolMemoryAllocator::allocateBlock ( )

staticprivate

◆ checkSize()

static bool ogdf::PoolMemoryAllocator::checkSize ( size_t nBytes )

static

Returns true iff allocate can be invoked with nBytes.

◆ cleanup()

static void ogdf::PoolMemoryAllocator::cleanup ( )

static

Frees all allocated memory.

◆ deallocate()

static void ogdf::PoolMemoryAllocator::deallocate	(	size_t	nBytes,
		void *	p
	)

static

Deallocates memory at address p which is of size nBytes.

◆ deallocateList()

static void ogdf::PoolMemoryAllocator::deallocateList	(	size_t	nBytes,
		void *	pHead,
		void *	pTail
	)

static

Deallocate a complete list starting at pHead and ending at pTail.

The elements are assumed to be chained using the first word of each element and elements are of size nBytes. In contrasting to linear-time element-wise deallocation this method takes constant time.

◆ defragGlobal()

static void ogdf::PoolMemoryAllocator::defragGlobal ( )

static

Defragments the global free lists.

This method sorts the global free lists, so that successive parts of memory come after each other. This can improve performance for data structures that allocate many elements from the pool like lists and graphs.

◆ defragThread()

static void ogdf::PoolMemoryAllocator::defragThread ( )

static

Defragments the thread's free lists.

This method sorts the thread's free lists, so that successive parts of memory come after each other. This can improve performance for data structures that allocate many elements from the pool like lists and graphs.

◆ enterCS()

static void ogdf::PoolMemoryAllocator::enterCS ( )

inlinestaticprivate

Definition at line 136 of file PoolMemoryAllocator.h.

◆ fillPool()

static void* ogdf::PoolMemoryAllocator::fillPool	(	MemElemPtr &	pFreeBytes,
		uint16_t	nBytes
	)

staticprivate

◆ flushPool()

static void ogdf::PoolMemoryAllocator::flushPool ( )

static

Flushes all free but allocated bytes (s_tp) to the thread-global list (s_pool) of allocated bytes.

◆ getGlobalFreeListSizes()

static void ogdf::PoolMemoryAllocator::getGlobalFreeListSizes ( std::vector< size_t > & sizes )

static

Reports the number of pooled memory chunks in the global free lists for each possible size up to TABLE_SIZE.

◆ getThreadFreeListSizes()

static void ogdf::PoolMemoryAllocator::getThreadFreeListSizes ( std::vector< size_t > & sizes )

static

Reports the number of pooled memory chunks in the thread's free lists for each possible size up to TABLE_SIZE.

◆ leaveCS()

static void ogdf::PoolMemoryAllocator::leaveCS ( )

inlinestaticprivate

Definition at line 142 of file PoolMemoryAllocator.h.

◆ makeSlices()

static void ogdf::PoolMemoryAllocator::makeSlices	(	MemElemPtr	p,
		int	nWords,
		int	nSlices
	)

staticprivate

◆ memoryAllocatedInBlocks()

static size_t ogdf::PoolMemoryAllocator::memoryAllocatedInBlocks ( )

static

Returns the total amount of memory (in bytes) allocated from the system.

◆ memoryInGlobalFreeList()

static size_t ogdf::PoolMemoryAllocator::memoryInGlobalFreeList ( )

static

Returns the total amount of memory (in bytes) available in the global free lists.

◆ memoryInThreadFreeList()

static size_t ogdf::PoolMemoryAllocator::memoryInThreadFreeList ( )

static

Returns the total amount of memory (in bytes) available in the thread's free lists.

◆ slicesPerBlock() [1/2]

static int ogdf::PoolMemoryAllocator::slicesPerBlock ( uint16_t nBytes )

inlinestaticprivate

Definition at line 148 of file PoolMemoryAllocator.h.

◆ slicesPerBlock() [2/2]

static int ogdf::PoolMemoryAllocator::slicesPerBlock	(	uint16_t	nBytes,
		int &	nWords
	)

inlinestaticprivate

Definition at line 153 of file PoolMemoryAllocator.h.

Member Data Documentation

◆ BLOCK_SIZE

constexpr size_t ogdf::PoolMemoryAllocator::BLOCK_SIZE = 8192

staticconstexprprivate

Definition at line 72 of file PoolMemoryAllocator.h.

◆ MIN_BYTES

constexpr size_t ogdf::PoolMemoryAllocator::MIN_BYTES = sizeof(MemElemPtr)

staticconstexprprivate

Definition at line 70 of file PoolMemoryAllocator.h.

◆ s_blocks

BlockChain* ogdf::PoolMemoryAllocator::s_blocks

staticprivate

Holds all allocated memory independently of whether it is cleared in chunks of size BLOCK_SIZE.

Definition at line 164 of file PoolMemoryAllocator.h.

◆ s_globallyAllocatedBytes

long long ogdf::PoolMemoryAllocator::s_globallyAllocatedBytes

staticprivate

Holds the number of globally allocated bytes for debugging.

Definition at line 168 of file PoolMemoryAllocator.h.

◆ s_locallyAllocatedBytes

thread_local long long ogdf::PoolMemoryAllocator::s_locallyAllocatedBytes

staticprivate

Holds the number of thread-locally allocated bytes for debugging.

Definition at line 170 of file PoolMemoryAllocator.h.

◆ s_mutex

std::mutex ogdf::PoolMemoryAllocator::s_mutex

staticprivate

Definition at line 180 of file PoolMemoryAllocator.h.

◆ s_pool

PoolElement ogdf::PoolMemoryAllocator::s_pool[TABLE_SIZE]

staticprivate

Contains allocated but free memory that may be used by all threads. Filled upon exiting a thread that allocated memory that was later freed.

Definition at line 178 of file PoolMemoryAllocator.h.

◆ s_tp

thread_local MemElemPtr ogdf::PoolMemoryAllocator::s_tp[TABLE_SIZE]

staticprivate

Contains the allocated but free memory for a single thread.

Definition at line 182 of file PoolMemoryAllocator.h.

◆ TABLE_SIZE

constexpr size_t ogdf::PoolMemoryAllocator::TABLE_SIZE = 256

staticconstexprprivate

Definition at line 71 of file PoolMemoryAllocator.h.

The documentation for this class was generated from the following file:

include/ogdf/basic/memory/PoolMemoryAllocator.h

OpenGraph DrawingFramework

Classes

Public Member Functions

Static Public Member Functions

Private Types

Static Private Member Functions

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ MemElemPtr

Constructor & Destructor Documentation

◆ PoolMemoryAllocator()

◆ ~PoolMemoryAllocator()

Member Function Documentation

◆ allocate()

◆ allocateBlock()

◆ checkSize()

◆ cleanup()

◆ deallocate()

◆ deallocateList()

◆ defragGlobal()

◆ defragThread()

◆ enterCS()

◆ fillPool()

◆ flushPool()

◆ getGlobalFreeListSizes()

◆ getThreadFreeListSizes()

◆ leaveCS()

◆ makeSlices()

◆ memoryAllocatedInBlocks()

◆ memoryInGlobalFreeList()

◆ memoryInThreadFreeList()

◆ slicesPerBlock() [1/2]

◆ slicesPerBlock() [2/2]

Member Data Documentation

◆ BLOCK_SIZE

◆ MIN_BYTES

◆ s_blocks

◆ s_globallyAllocatedBytes

◆ s_locallyAllocatedBytes

◆ s_mutex

◆ s_pool

◆ s_tp

◆ TABLE_SIZE

Open
Graph Drawing
Framework