US 8,819,386 B1Granted

Memory efficient use of dynamic data structures used to manage sparsely accessed data

AssigneeEMC Corporation

InventorClifford Mather

Life of this patent

Estimating the term…

Loading patent…

Abstract

When a dynamic data structure is used for managing sparsely accessed data stored in memory of a digital computer, pages of the memory are dynamically allocated and de-allocated to respective portions of the dynamic data structure so that the pages become distributed over the portions of the dynamic data structure and the de-allocated pages include free pages that are mapped in the dynamic data structure and free pages that are not mapped in the dynamic data structure. To reduce memory fragmentation and recover memory, upon de-allocating a page of memory from a portion of the data structure, a determination is made whether or not to un-map the de-allocated page from the portion of the dynamic data structure so that un-mapping of the de-allocated page has a probability that is the inverse of a superlinear function of the number of allocated pages in the portion of the dynamic data structure.

Claims20

Dependent claims

A method of using a dynamic data structure for managing sparsely accessed data stored in memory of a digital computer, said method comprising a data processor of the digital computer executing computer instructions stored in a non-transitory computer readable storage medium to perform the steps of:

(a) dynamically allocating and de-allocating pages of the memory to respective portions of the dynamic data structure so that allocated pages of the memory and de-allocated pages of the memory become distributed over the portions of the dynamic data structure, and the de-allocated pages of the memory include free pages that are mapped in the dynamic data structure and free pages that are not mapped in the dynamic data structure;
(b) upon de-allocating an allocated page of the memory from one of the portions of the dynamic data structure, determining whether a probability of un-mapping the de-allocated page from said one of the portions of the dynamic data structure is the inverse of a superlinear function of the number of allocated pages in said one of the portions of the dynamic data structure;
(c) based on the determination of the probability, determining whether or not to un-map the de-allocated page from said one of the portions of the dynamic data structure;
and
(d) in response to step (c) determining to un-map the de-allocated page from said one of the portions of the dynamic data structure, un-mapping the de-allocated page from said one of the portions of the dynamic data structure.

2 more elements

A digital computer comprising a data processor, memory, and a non-transitory computer readable storage medium storing computer instructions that, when executed by the data processor, use a dynamic data structure for managing sparsely accessed data in the memory by performing the steps of:

(a) dynamically allocating and de-allocating pages of the memory to respective portions of the dynamic data structure so that allocated pages of the memory and de-allocated pages of the memory become distributed over the portions of the dynamic data structure, and the de-allocated pages of the memory include free pages that are mapped in the dynamic data structure and free pages that are not mapped in the dynamic data structure;
(b) upon de-allocating an allocated page of the memory from one of the portions of the dynamic data structure, determining whether a probability of un-mapping the de-allocated page from said one of the portions of the dynamic data structure is the inverse of a superlinear function of the number of allocated pages in said one of the portions of the dynamic data structure;
(c) based on the determination of the probability, determining whether or not to un-map the de-allocated page from said one of the portions of the dynamic data structure;
and
(d) in response to step (c) determining to un-map the de-allocated page from said one of the portions of the dynamic data structure, un-mapping the de-allocated page from said one of the portions of the dynamic data structure.

2 more elements

A non-transitory computer-readable storage medium containing computer instructions that, when executed by a data processor, perform the steps of:

(a) dynamically allocating and de-allocating pages of the memory to respective portions of the dynamic data structure so that allocated pages of the memory and de-allocated pages of the memory become distributed over the portions of the dynamic data structure, and the de-allocated pages of the memory include free pages that are mapped in the dynamic data structure and free pages that are not mapped in the dynamic data structure;
(b) upon de-allocating an allocated page of the memory from one of the portions of the dynamic data structure, determining whether a probability of un-mapping the de-allocated page from said one of the portions of the dynamic data structure is the inverse of a superlinear function of the number of allocated pages in said one of the portions of the dynamic data structure;
(c) based on the determination of the probability, determining whether or not to un-map the de-allocated page from said one of the portions of the dynamic data structure;
and
(d) in response to step (c) determining to un-map the de-allocated page from said one of the portions of the dynamic data structure, un-mapping the de-allocated page from said one of the portions of the dynamic data structure.

2 more elements

Dependencies are inferred from the claim text.