Adaptive memory allocation
First Claim
Patent Images
1. A method in a data processing system for allocating memory by a memory allocation function, comprising:
- receiving a memory request for a reference to a block of memory;
returning the reference to the block of memory to satisfy the request;
forming a plurality of linked-lists referring to memory blocks of a plurality of sizes, each of the plurality of linked-lists referring to memory blocks of a common size;
setting a fast access tree to refer to a first one of the plurality of linked-lists; and
setting a general access tree to refer to a second one and a third one of the plurality of linked-lists, wherein a size of a memory block referred to by the first linked-list is larger than a size of a memory block referred to by the second linked-list and smaller than a size of a memory block referred to by the third linked-list.
3 Assignments
0 Petitions
Accused Products
Abstract
This functions maintains two trees: a fast access tree referring to memory blocks of a size most often requested, and a general access tree referring to memory blocks of a size less often requested. After satisfying a request for a memory block, the function adjusts the trees to ensure that the fast access tree refers to memory blocks of the size most often requested. By providing such functionality, the function improves its performance over time through self-adaptation.
187 Citations
18 Claims
-
1. A method in a data processing system for allocating memory by a memory allocation function, comprising:
-
receiving a memory request for a reference to a block of memory; returning the reference to the block of memory to satisfy the request; forming a plurality of linked-lists referring to memory blocks of a plurality of sizes, each of the plurality of linked-lists referring to memory blocks of a common size; setting a fast access tree to refer to a first one of the plurality of linked-lists; and setting a general access tree to refer to a second one and a third one of the plurality of linked-lists, wherein a size of a memory block referred to by the first linked-list is larger than a size of a memory block referred to by the second linked-list and smaller than a size of a memory block referred to by the third linked-list. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A system for allocating memory, comprising:
-
means for receiving a memory request for a reference to a block of memory; means for returning the reference to the block of memory to satisfy the request; and means for forming a plurality of linked-lists referring to memory blocks of a plurality of sizes, each of the plurality of linked-lists referring to memory blocks of a common size; means for setting a fast access tree to refer to a first one of the plurality of linked-lists; means for setting a general access tree to refer to a second one and a third one of the plurality of linked-lists, wherein a size of a memory block referred to by the first linked-list is larger than a size of a memory block referred to by the second linked-list and smaller than a size of a memory block referred to by the third linked-list.
-
-
7. A data processing system for providing access to memory, comprising:
-
a memory including; an access tree structure comprising a fast access tree and a general access tree; a program including a memory access function that provides access to the memory, forms a plurality of linked-lists referring to memory blocks of a plurality of sizes, each of the plurality of linked-lists referring to memory blocks of a common size, sets the fast access tree to refer to a first one of the plurality of linked-lists, and sets the general access tree to refer to a second one and a third one of the plurality of linked-lists, wherein a size of a memory block referred to by the first linked-list is larger than a size of a memory block referred to by the second linked-list and smaller than a size of a memory block referred to by the third linked-list; and a processor for executing the program. - View Dependent Claims (8, 9, 10, 11, 12, 13, 14)
-
-
15. A computer-readable medium including instructions for performing a method for allocating memory by a memory allocation function, the method comprising:
-
receiving a memory request for a reference to a block of memory; returning the reference to the block of memory to satisfy the request; forming a plurality of linked-lists referring to memory blocks of a plurality of sizes, each of the plurality of linked-lists referring to memory blocks of a common size; setting a fast access tree to refer to a first one of the plurality of linked-lists; setting a general access tree to refer to a second one and a third one of the plurality of linked-lists, wherein a size of a memory block referred to by the first linked-list is larger than a size of a memory block referred to by the second linked-list and smaller than a size of a memory block referred to by the third linked-list. - View Dependent Claims (16, 17, 18)
-
Specification