Cache-optimized hash table data structure
AssigneeAlcatel Lucent
InventorJeroen van Bemmel
Life of this patent
Estimating the term…
Abstract
Various exemplary embodiments relate to a system for hashing a value into a cache, the system including a processor for performing a series of instructions; a memory; and the cache including a plurality of slots, each slot including two locations to store values, each location comprising a tag value and an index, the cache in communication with the memory and the processor, the cache configured to calculate a target slot in the cache for an object, determine if a location is available, store a characteristic of the object in the index of the location, and update the tag value of the location.
Claims20
A system comprising:
- a processor configured to perform a series of instructions;
- a memory;
- and
- the cache comprising a plurality of slots, each slot comprising two locations to store values, each location comprising a tag value and an index, the cache in communication with the memory and the processor, wherein the cache is configured to calculate a target slot in the cache for an object, determine if either of the two locations is available, store a characteristic of the object in the index of the available location, and update the tag value of the available location.
A system comprising:
- a processor configured to perform a series of instructions;
- a memory;
- and
- the cache comprising a plurality of slots, each slot comprising two locations, each location comprising a tag value and an index, the cache in communication with the memory and the processor, the cache configured to calculate a target slot in the cache for an object, determine that a characteristic of an object is stored in a first location in a first slot in the cache, determine if the first location is a primary location of the target slot, and update a first index and a first tag value of the first location.
An apparatus comprising:
- a processor;
- a memory;
- and
- a cache memory comprising:
- one or more cache lines;
- and a hash table allocated within a cache line, the hash table comprising a number of slots, each slot comprising two locations, and each location comprising a tag value and an index.
Dependencies are inferred from the claim text.