Browse Prior Art Database

Methods and Apparatus for Relaxed Speculative Dynamic Memory Allocation

IP.com Disclosure Number: IPCOM000188128D
Original Publication Date: 2009-Oct-14
Included in the Prior Art Database: 2009-Oct-14
Document File: 2 page(s) / 84K

Publishing Venue

Siemens

Related People

Juergen Carstens: CONTACT

Abstract

Software allocates and frees dynamic memory at runtime by calling the standard memory allocation functions from system libraries. Memory allocation itself is a time expensive operation: • Memory allocation involves tree operations (insertion/deletion) in the trees of allocated memory blocks and free memory blocks. • Memory allocation runs in a critical section in a multithreaded environment. Thus, each thread holds an exclusive lock while allocating memory. • Memory allocation involves the operating system overhead. Software normally processes dynamic structures as shown in Figure 1. Basically, Figure 1 illustrates that typical dynamic structures have add-operations (like AddNewEntity ( ) or Concatenate ( )) and remove-operations (like RemoveEntity ( ) or Trim ( )). Each time a new size is calculated and then dynamic memory is reallocated. And this is exactly the issue that the expensive operations of memory allocation are called intensively degrading the overall software application performance.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 56% of the total text.

Page 1 of 2

Methods and Apparatus for Relaxed Speculative Dynamic Memory Allocation

Idea: Dr. Oleksandr Pochayevets, DE-Nuremberg

Software allocates and frees dynamic memory at runtime by calling the standard memory allocation functions from system libraries. Memory allocation itself is a time expensive operation:

• Memory allocation involves tree operations (insertion/deletion) in the trees of allocated memory blocks and free memory blocks.

• Memory allocation runs in a critical section in a multithreaded environment. Thus, each thread holds an exclusive lock while allocating memory.

• Memory allocation involves the operating system overhead. Software normally processes dynamic structures as shown in Figure 1.

Basically, Figure 1 illustrates that typical dynamic structures have add-operations (like AddNewEntity ( ) or Concatenate ( )) and remove-operations (like RemoveEntity ( ) or Trim ( )). Each time a new size is calculated and then dynamic memory is reallocated. And this is exactly the issue that the expensive operations of memory allocation are called intensively degrading the overall software application performance.

This novel solution proposes methods and apparatus for relaxed dynamic memory allocation where dynamic memory is allocated speculatively in chunks of discrete size, which is calculated heuristically. Due to this the expensive memory allocation operations are not invoked each time directly, but rather speculatively reducing potential heavy-load to the dynamic memory allocator. Memory allocation is not changed when a dynamic structure is initialized. However, add-operations (like AddNewEntity ( ) or Concatenate ( )) and remove-operations (like RemoveEntity ( ) or Trim ( )) are modified as shown in Figure 2. Real memory allocation happens not each time, but only when the requested size exceeded the currently allocated size, thus, reducing potential heavy-load to the dynamic memory allocator. This solution can be applied to practically all software applications because practically all of them allocate memory dynamically.

Figure 1: Typical dynamic structures

Example of Dynamic Array Example of Dynamic String class DynArray { private:

long size;

entity array [ ] ;

public:

int AddNewEntity (entity NewEntity) ;

int RemoveEntity (int Index) ;
}
int DynArray : : AddNewEntity (entity NewEntity) { / / . . .

size += sizeof (entity) ;

/ / new allocate ( ) and free ( )

array = reallocate (size) ;

/ / . . .
}
int DynArray : : RemoveEntity (int Index) { / / . . .

size -= sizeof (entity) ;

/ / new allocate ( ) and free ( )...