Back to results
US 10,649,676 B1Granted
Memory compression for immutable data structures
AssigneeMicrosoft Technology Licensing, LLC
InventorBart Johan Fred De Smet
Life of this patent
Estimating the term…
Abstract
Duplicates of immutable data objects are identified and deduplicated. This is performed by performing a bottom up deduplication, such that objects in hierarchically lower levels of a data structure are deduplicated first. Deduplication identifies duplicates of a particular object through value equality analysis and replaces pointers to duplicate objects and the duplicate objects themselves, with a reference to the particular object. This process is repeated for hierarchically higher data objects, but where the value equality analysis includes, among other things, evaluating the equality of references to hierarchically lower data objects.
Claims20
A method of compressing immutable data structures on a computing system, the method comprising:
- identifying first level immutable data objects of a first immutable data object type at a first level of a multilevel data structure;
- populating a first lookup table with entries, each entry comprising a first level immutable data object and a first level value of the first level immutable data object;
- wherein populating the first lookup table comprises, as a result of identifying a first instance of a particular first level immutable data object, populating an entry with the particular first level immutable data object;
- for the particular first level immutable data object, identifying a duplicate instance of the particular first level immutable data object, the duplicate instance of the particular first level immutable data object being pointed to by a first pointer from a particular instance of a particular second level immutable data object;
- as a result of the particular first level immutable data object being in the lookup table, replacing the first pointer with a reference to the first instance of the particular first level immutable data object;
- causing the duplicate instance of the particular first level immutable data object to be removed from memory, freeing storage space on the computing system;
- identifying second level immutable data objects at a second level of the multilevel data structure;
- populating a second lookup table with entries, each of one or more of the entries comprising a second level immutable data object and a second level reference to a first instance of a first level immutable data object;
- and
- wherein populating the second lookup table comprises populating a particular second level lookup table entry with the particular second level immutable data object and the reference to the first instance of the particular first level immutable data object.
7 more elements
A computer system comprising:
- one or more processors;
- and
- one or more computer-readable media having stored thereon instructions that are executable by the one or more processors to configure the computer system to compress immutable data structures on a computing system, including instructions that are executable to configure the computer system to perform at least the following:
- identify first level immutable data objects of a first immutable data object type at a first level of a multilevel data structure;
- populate a first lookup table with entries, each entry comprising a first level immutable data object and a first level value of the first level immutable data object;
- wherein populating the first lookup table comprises, as a result of identifying a first instance of a particular first level immutable data object, populating an entry with the particular first level immutable data object;
- for the particular first level immutable data object, identify a duplicate instance of the particular first level immutable data object, the duplicate instance of the particular first level immutable data object being pointed to by a first pointer from a particular instance of a particular second level immutable data object;
- as a result of the particular first level immutable data object being in the lookup table, replace the first pointer with a reference to the first instance of the particular first level immutable data object;
- cause the duplicate instance of the particular first level immutable data object to be removed from memory, freeing storage space on the computing system;
- identify second level immutable data objects at a second level of the multilevel data structure;
- populate a second lookup table with entries, each of one or more of the entries comprising a second level immutable data object and a second level reference to a first instance of a first level immutable data object;
- and
- wherein populating the second lookup table comprises populating a particular second level lookup table entry with the particular second level immutable data object and the reference to the first instance of the particular first level immutable data object.
10 more elements
A computer system comprising:
- one or more processors;
- and
- one or more computer-readable media having stored thereon instructions that are executable by the one or more processors to configure the computer system to implement:
- a heap walker, wherein the heap walker comprises a comparator;
- wherein the comparator is configured to compare objects in an object heap with entries in lookup tables, the entries in the lookup tables being entered into the lookup tables as a result of identifying particular instances of objects, to determine if objects in the object heap are duplicates of objects in the lookup tables, wherein the comparator is configured to compare references of objects in the object heap to hierarchically lower level objects to references of objects in the lookup tables to determine if objects in the object heap are duplicates of objects in the lookup tables;
- and
- wherein the heap walker is configured to replace duplicates in the object heap with references to the particular instances of objects.
4 more elements
Dependencies are inferred from the claim text.