Optimized least recently used lookup cache
AssigneeInternational Business Machines Corporation
InventorsGreg R. Mewhinney, Mysore Sathyanarayana Srinivas
Life of this patent
Estimating the term…
Abstract
A method, computer program product, and a data processing system for maintaining objects in a lookup cache is provided. A primary list is populated with a first plurality of objects. The primary list is an unordered list of the first plurality of objects. A secondary list is populated with a second plurality of objects. The secondary list is an ordered list of the second plurality of objects. Periodically, at least one object of the first plurality of objects is demoted to the secondary list, and at least one object of the second plurality of objects is promoted to the primary list.
Claims14
A computer-implemented method of maintaining objects in lists in a lookup cache, comprising:
- populating, by a processor, a primary list in the lookup cache and a secondary list in the lookup cache with objects;
- accumulating, by the processor, a count of the number of times each object in each list in the lookup cache is requested;
- identifying, by the processor, objects in the secondary list that are used more often than objects in the primary list and objects in the primary list that are used less often than objects in the secondary list, wherein the identification is based on the count of the number of times each object in the lookup cache is requested;
- determining, by the processor, a total number of objects to swap between the primary list and the secondary list based on swapping as many of the identified objects as possible without changing a total number of objects in either the primary list or the secondary list;
- and
- swapping, by the processor, the total number of objects between the primary list and the secondary list without changing the total number of objects in either the primary list or the secondary list, wherein the primary list is an unordered list and the secondary list has an order maintained by the processor that is based on the count.
A computer program product stored in a computer recordable-type medium for maintaining objects in lists in a lookup cache, the computer program product comprising:
- computer usable instructions for populating a primary list in the lookup cache;
- computer usable instructions for populating a secondary list in the lookup cache with objects;
- computer usable instructions for accumulating a count of the number of times each object in each list in the lookup cache is requested;
- computer usable instructions for identifying objects in the secondary list that are used more often than objects in the primary list and objects in the primary list that are used less often than objects in the secondary list, wherein the identification is based on the count of the number of times each object in the lookup cache is requested;
- computer usable instructions for determining a total number of objects to swap between the primary list and the secondary list based on swapping as many of the identified objects as possible without changing a total number of objects in either the primary list or the secondary list;
- and
- computer usable instructions for swapping the total number of objects between the primary list and the secondary list without changing the total number of objects in either the primary list or the secondary list, wherein the primary list is an unordered list and the secondary list has an order maintained by the processor that is based on the count.
A data processing system for maintaining objects in lists in a lookup cache, comprising:
- a memory that contains a set of instructions and the lookup cache;
- and
- a processing unit, responsive to execution of the set of instructions, that populates a primary list in the lookup cache and a secondary list in the lookup cache with objects;
- accumulates a count of the number of times each object in each list in the lookup cache is requested;
- identifies objects in the secondary list that are used more often than objects in the primary list and objects in the primary list that are used less often than objects in the secondary list, wherein the identification is based on the count of the number of times each object in the lookup cache is requested;
- determines a total number of objects to swap between the primary list and the secondary list based on swapping as many of the identified objects as possible without changing a total number of objects in either the primary list or the secondary list;
- and swaps the total number of objects between the primary list and the secondary list without changing the total number of objects in either the primary list or the secondary list, wherein the primary list is an unordered list and the secondary list has an order maintained by the processor that is based on the count.
Dependencies are inferred from the claim text.