Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::PoolMemoryAllocator Class Reference

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 defrag ()
 Defragments the global 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 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 size_t unguardedMemGlobalFreelist ()
 

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 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 at most TABLE_SIZE bytes per invocation of allocate.

For each requested memory segment of n 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 55 of file PoolMemoryAllocator.h.

Member Typedef Documentation

◆ MemElemPtr

Definition at line 61 of file PoolMemoryAllocator.h.

Constructor & Destructor Documentation

◆ PoolMemoryAllocator()

ogdf::PoolMemoryAllocator::PoolMemoryAllocator ( )
inline

Definition at line 71 of file PoolMemoryAllocator.h.

◆ ~PoolMemoryAllocator()

ogdf::PoolMemoryAllocator::~PoolMemoryAllocator ( )
inline

Definition at line 72 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)
inlinestatic

Returns true iff allocate can be invoked with nBytes.

Definition at line 78 of file PoolMemoryAllocator.h.

◆ 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.

◆ defrag()

static void ogdf::PoolMemoryAllocator::defrag ( )
static

Defragments the global free lists.

This methods sorts the global free lists, so that successive elements come after each other. This can improve perfomance for data structure that allocate many elements from the pool like lists and graphs.

◆ enterCS()

static void ogdf::PoolMemoryAllocator::enterCS ( )
inlinestaticprivate

Definition at line 118 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.

◆ leaveCS()

static void ogdf::PoolMemoryAllocator::leaveCS ( )
inlinestaticprivate

Definition at line 124 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 130 of file PoolMemoryAllocator.h.

◆ slicesPerBlock() [2/2]

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

Definition at line 135 of file PoolMemoryAllocator.h.

◆ unguardedMemGlobalFreelist()

static size_t ogdf::PoolMemoryAllocator::unguardedMemGlobalFreelist ( )
staticprivate

Member Data Documentation

◆ BLOCK_SIZE

constexpr size_t ogdf::PoolMemoryAllocator::BLOCK_SIZE = 8192
staticconstexprprivate

Definition at line 68 of file PoolMemoryAllocator.h.

◆ MIN_BYTES

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

Definition at line 66 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 152 of file PoolMemoryAllocator.h.

◆ s_mutex

std::mutex ogdf::PoolMemoryAllocator::s_mutex
staticprivate

Definition at line 164 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 149 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 166 of file PoolMemoryAllocator.h.

◆ TABLE_SIZE

constexpr size_t ogdf::PoolMemoryAllocator::TABLE_SIZE = 256
staticconstexprprivate

Definition at line 67 of file PoolMemoryAllocator.h.


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