Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Method and Apparatus to allow predictive modification of malloc data structures improved performance of the malloc sub-system

IP.com Disclosure Number: IPCOM000182314D
Original Publication Date: 2009-Apr-27
Included in the Prior Art Database: 2009-Apr-27
Document File: 2 page(s) / 96K

Publishing Venue

IBM

Abstract

Disclosed is a method to allow predictive modification of the datastructures/algorithms of the memory allocation subsystem to achieve better performance.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 2

Method and Apparatus to allow predictive modification of malloc data structures improved performance of the malloc sub -system

Authors:

Rajbir Bhattacharjee , Madhusudanan Kandasamy , Vidya Ranganathan

Disclosed is a method to allow predictive modification of the datastructures/algorithms of the memory allocation subsystem to achieve better performance.

Most applications rely on the malloc subsystem for allocation and management of heap memory. Most modern day malloc subsystems maintain either a tree-based or a bucket-based data structures to allow for efficient management. When a request for memory allocation is received via the malloc() subroutine, a best-fit chunk of memory must be found. The time required for search determines the speed of the malloc sub-system.

Bucket-based allocators can perform the search operation in O(n) time. However, the drawback of bucket based allocators is wastage of memory, as the request must be rounded-up to the next higher bucket size. Also the prospect of coalescing adjacent chunks of memory in the free-

p

                                                     ool is limited. Tree based allocators allow for better space usage, by compromising on the time required for search.

Most modern malloc algorithms rely on a tree-based data structure. When a request for malloc() arrives, the tree must be searched for the best fit. The search is time consuming, and determines the efficiency of the malloc subsystem. If the next request can be approximated or predicted before it actually arrives, the tree can be rearranged so that the search can become faster. However, the computational overhead for such a prediction is usually high, and as all the computation required for prediction must be completed within the call to malloc(), overall,

prediction does not lead to any performance improvement of the malloc sub-system.

If the next request can be predicted from the previous n requests, the best fit node for the next

                             malloc-thread , and promoted nearer the root of the tree by means of rotations, while the application is doing some other work. If the next request to malloc() matches the predicted request, there will be a massive increase of

probable request can be searched beforehand by a

performance. If not, then there is no loss of performance.

Many statistical, mathematical and machine learning methods exist that can predict numbers in a sequence to a high degree of accuracy. Some of these methods can give a quantitative measure of what is the probability of the prediction being correct. This probabilit...