Reorganization of collisions in a hash bucket of a hash table to improve system performance

Claim 5

The method of claim 2 wherein the buckets are the cache line size and wherein the step of accessing the one bucket includes the one bucket being stored with an exact fit into one of the cache lines.

Claim 10

The method of claim 5 wherein the step of moving the indicated data includes moving the indicated data to a first entry in the first bucket in the one chain.

Claim 11

The method of claim 6 wherein the first bucket has least recently used data and wherein the step of moving the indicated data includes moving the least recently used data out of the first bucket.

Claim 12

The method of claim 7 wherein the step of moving the least recently used data includes moving the least recently used data into a bucket that follows the first bucket in the sequence.

Claim 15

The method of claim 9 wherein the predetermined number of buckets have an end bucket with a last entry, further including the steps of: moving the data in the last entry of the end bucket of the predetermined number of buckets into a first entry of the one bucket; and moving the data in the entries of the one bucket before the one entry to next entries in the one bucket.

Claim 18

A computer system comprising: a cache with cache lines having a cache line size; a memory containing a hash manager and a hash table having a plurality of chains of buckets, each bucket containing entries storing data and being the cache line size, the hash manager for receiving requests to access the data in the buckets of the chains of the hash table, for accessing the buckets of the chains to access the data, and for positioning most recently used data in a first bucket of each chain after the chain has been accessed; and a processor for running the hash manager and for storing each bucket into one of the cache lines with an exact fit after the bucket has been accessed.

Claim 19

A computer system comprising: a cache with cache lines having a cache line size; a memory containing a hash manager and a hash table having a plurality of chains of buckets, each bucket containing entries storing data and being the cache line size, the hash manager for receiving requests to access the data in the buckets of the chains of the hash table, for accessing the buckets of the chains to access the data, and for positioning most recently used data in a first bucket of each chain after the chain has been accessed; and a processor for running the hash manager and for storing each bucket into one of the cache lines with an exact fit after the bucket has been accessed.

Claim 20

The computer system of claim 12 wherein the cache is contained in the processor.

Claim 23

A computer system comprising: a memory containing a hash table storing data in buckets and a hash manager for accessing the data in the buckets in the hash table, the buckets having a bucket size; and a processor with a cache having cache lines of the bucket size, the processor for running the hash manager wherein the processor stores each bucket accessed by the hash manager into one of the cache lines of the cache with an exact fit when the data stored in the bucket is accessed.

Claim 24

A computer system comprising: a memory containing a hash table storing data in buckets and a hash manager for accessing the data in the buckets in the hash table, the buckets having a bucket size; and a processor with a cache having cache lines of the bucket size, the processor for running the hash manager wherein the processor stores each bucket accessed by the hash manager into one of the cache lines of the cache with an exact fit when the data stored in the bucket is accessed.

Claim 25

A computer-readable medium having instructions for controlling a computer system to perform a method for accessing records having keys with a plurality of values, the computer system having a processor with a cache and a main memory storing a hash table with chains of buckets, each bucket having entries containing a plurality of the records, the buckets in each chain forming a sequence from a first bucket to a last bucket, the method comprising the steps of: receiving a request from a caller to access a requested record that is identified by a key value; hashing the key value into an index referring to one of the chains using a hash function; searching for the requested record by accessing each bucket in sequence in the indexed chain beginning with the first bucket, whereupon each accessed bucket is loaded into the cache, and by examining the key value of each record in each accessed bucket to determine if the record is the requested record; returning the requested record to the caller; and while the loaded buckets remain in the cache, rearranging the records in the loaded buckets in the cache to improve performance of subsequent accesses of the indexed chain.

Claim 26

A computer-readable medium having instructions for controlling a computer system to perform a method for accessing records having keys with a plurality of values, the computer system having a processor with a cache and a main memory storing a hash table with chains of buckets, each bucket having entries containing a plurality of the records, the buckets in each chain forming a sequence from a first bucket to a last bucket, the method comprising the steps of: receiving a request from a caller to access a requested record that is identified by a key value; hashing the key value into an index referring to one of the chains using a hash function; searching for the requested record by accessing each bucket in sequence in the indexed chain beginning with the first bucket, whereupon each accessed bucket is loaded into the cache, and by examining the key value of each record in each accessed bucket to determine if the record is the requested record; returning the requested record to the caller; and while the loaded buckets remain in the cache, rearranging the records in the loaded buckets in the cache to improve performance of subsequent accesses of the indexed chain.

Claim 27

A computer-readable medium containing instructions for controlling a computer system to perform a method, the computer system having a memory cache with cache lines having a cache line size and the computer system further having a hash manager that accesses data in a hash table having buckets containing entries, a plurality of the entries being occupied entries containing data, the buckets being the cache line size, the method comprising the steps of: receiving requests by the hash manager to input data into the hash table and generating collisions such that a plurality of occupied entries are contained in each bucket; receiving a plurality of requests for accessing the buckets of the hash table by the hash manager; and while the hash manager processes the plurality of requests for accessing the hash table, accessing the buckets, wherein each accessed bucket is stored with an exact fit into one of the cache lines; relocating the data in at least one of the occupied entries of at least one of the buckets to a new location among the occupied entries in the at least one bucket to improve performance of the hash manager.

Claim 28

A computer-readable medium containing instructions for controlling a computer system to perform a method, the computer system having a memory cache with cache lines having a cache line size and the computer system further having a hash manager that accesses data in a hash table having buckets containing entries, a plurality of the entries being occupied entries containing data, the buckets being the cache line size, the method comprising the steps of: receiving requests by the hash manager to input data into the hash table and generating collisions such that a plurality of occupied entries are contained in each bucket; receiving a plurality of requests for accessing the buckets of the hash table by the hash manager; and while the hash manager processes the plurality of requests for accessing the hash table, accessing the buckets, wherein each accessed bucket is stored with an exact fit into one of the cache lines; relocating the data in at least one of the occupied entries of at least one of the buckets to a new location among the occupied entries in the at least one bucket to improve performance of the hash manager.

Claim 29

A computer-readable medium containing instructions for controlling a computer system to perform a method for accessing a hash table having chains of buckets with each bucket having a plurality of entries storing data, the entries in the buckets in a chain forming a sequence from a first entry of a first bucket to a last entry of a last bucket, the computer system having a cache with cache lines having a cache line size, the buckets being the cache line size, the method comprising the steps of: receiving a request to access requested data stored in a selected entry; accessing the bucket in the chain that contains the selected entry, wherein the bucket is stored with an exact fit into one of the cache lines; returning the requested data from the selected entry; moving the data contained in the first entry of the first bucket and the data contained in the entries following the first entry of the first bucket but before the selected entry to next entries in the sequence responsive to said steps of receiving, accessing and returning; and moving the requested data to the first entry in the first bucket of the chain.

Claim 30

A computer-readable medium containing instructions for controlling a computer system to perform a method for accessing a hash table having chains of buckets with each bucket having a plurality of entries storing data, the entries in the buckets in a chain forming a sequence from a first entry of a first bucket to a last entry of a last bucket, the computer system having a cache with cache lines having a cache line size, the buckets being the cache line size, the method comprising the steps of: receiving a request to access requested data stored in a selected entry; accessing the bucket in the chain that contains the selected entry, wherein the bucket is stored with an exact fit into one of the cache lines; returning the requested data from the selected entry; moving the data contained in the first entry of the first bucket and the data contained in the entries following the first entry of the first bucket but before the selected entry to next entries in the sequence responsive to said steps of receiving, accessing and returning; and moving the requested data to the first entry in the first bucket of the chain.

Claim 31

A computer-readable medium containing instructions for controlling a computer system to perform a method in the computer system for accessing a hash table having chains of buckets with each bucket having a plurality of entries storing data, the buckets in a chain forming a sequence from a first bucket to a last bucket, the computer system having a cache with cache lines having a cache line size, the buckets being the cache line size, the method comprising the steps of: receiving a plurality of requests to access the hash table, wherein each request indicates the data in one of the entries in one of the buckets in one of the chains; and for each of the received plurality of requests, accessing the indicated data in the one entry in the one bucket in the one chain whereupon the one bucket is stored with an exact fit into one of the cache lines, and moving the indicated data to the first bucket in the one chain after accessing the indicated data.

Claim 32

A computer-readable medium containing instructions for controlling a computer system to perform a method in the computer system for accessing a hash table having chains of buckets with each bucket having a plurality of entries storing data, the buckets in a chain forming a sequence from a first bucket to a last bucket, the computer system having a cache with cache lines having a cache line size, the buckets being the cache line size, the method comprising the steps of: receiving a plurality of requests to access the hash table, wherein each request indicates the data in one of the entries in one of the buckets in one of the chains; and for each of the received plurality of requests, accessing the indicated data in the one entry in the one bucket in the one chain whereupon the one bucket is stored with an exact fit into one of the cache lines, and moving the indicated data to the first bucket in the one chain after accessing the indicated data.

Claim 33

The computer-readable medium of claim 19 wherein the step of moving the indicated data includes moving the indicated data to a first entry in the first bucket in the one chain.

Claim 34

The computer-readable medium of claim 20 wherein the first bucket has least recently used data and wherein the step of moving the indicated data includes moving the least recently used data out of the first bucket.

Claim 35

The computer-readable medium of claim 21 wherein the step of moving the least recently used data includes moving the least recently used data into a bucket that follows the first bucket in the sequence.

Claim 36

A computer-readable medium containing instructions for controlling a computer system to perform a method in the computer system for accessing a hash table having chains of buckets with each bucket having a plurality of entries storing data, the entries in the buckets in each chain forming a sequence from a first entry in a first bucket to a last entry in a last bucket, the method comprising the steps of: receiving a request to access the hash table that indicates the data in one of the entries in one of the buckets in one of the chains; accessing the indicated data in the one entry in the one bucket in the one chain; moving the data contained in the first entry in the first bucket in the one chain and the data contained in the entries that follow the first entry in the first bucket for a predetermined number of buckets to next entries in the sequence responsive to said step of accessing the indicated data; and moving the indicated data to the first entry in the first bucket in the one chain.

Claim 37

A computer-readable medium containing instructions for controlling a computer system to perform a method in the computer system for accessing a hash table having chains of buckets with each bucket having a plurality of entries storing data, the entries in the buckets in each chain forming a sequence from a first entry in a first bucket to a last entry in a last bucket, the method comprising the steps of: receiving a request to access the hash table that indicates the data in one of the entries in one of the buckets in one of the chains; accessing the indicated data in the one entry in the one bucket in the one chain; moving the data contained in the first entry in the first bucket in the one chain and the data contained in the entries that follow the first entry in the first bucket for a predetermined number of buckets to next entries in the sequence responsive to said step of accessing the indicated data; and moving the indicated data to the first entry in the first bucket in the one chain.

Claim 38

The computer-readable medium of claim 23 wherein the predetermined number of buckets have an end bucket with a last entry, further including the steps of: moving the data in the last entry of the end bucket of the predetermined number of buckets into a first entry of the one bucket; and moving the data in the entries of the one bucket before the one entry to next entries in the one bucket.

Claim 39

A computer-readable medium containing instructions for controlling a computer system to perform a method in the computer system for accessing a hash table having chains of buckets with each bucket having a plurality of entries storing data, the entries in the buckets in a chain forming a sequence from a first entry of a first bucket to a last entry of a last bucket, the method comprising the steps of: receiving a request to access the hash table that indicates the data in one of the entries in one of the buckets in one of the chains, the one entry having a relative position that is relative to other entries of the one bucket; accessing the indicated data in the one entry in the one bucket in the one chain; moving the data contained in the entries at the relative positions of the first bucket and of the buckets that follow the first bucket but before the one bucket into entries at the relative location in next buckets responsive to said step of accessing the indicated data; and moving the indicated data to the entry at the relative position in the first bucket in the one chain.

Claim 40

A computer-readable medium containing instructions for controlling a computer system to perform a method in the computer system for accessing a hash table having chains of buckets with each bucket having a plurality of entries storing data, the entries in the buckets in a chain forming a sequence from a first entry of a first bucket to a last entry of a last bucket, the method comprising the steps of: receiving a request to access the hash table that indicates the data in one of the entries in one of the buckets in one of the chains, the one entry having a relative position that is relative to other entries of the one bucket; accessing the indicated data in the one entry in the one bucket in the one chain; moving the data contained in the entries at the relative positions of the first bucket and of the buckets that follow the first bucket but before the one bucket into entries at the relative location in next buckets responsive to said step of accessing the indicated data; and moving the indicated data to the entry at the relative position in the first bucket in the one chain.

Claim 41

A computer-readable medium containing instructions for controlling a computer system to perform a method in the computer system having a processor with a cache comprising cache lines having a cache line size, comprising the steps of: providing a hash table to a memory of the computer system, the hash table having buckets of the cache line size storing data; and accessing data stored in one of the buckets of the hash table whereupon the processor loads the one bucket into the cache such that the one bucket is stored with an exact fit into one of the cache lines.

Claim 42

A computer-readable medium containing instructions for controlling a computer system to perform a method in the computer system having a processor with a cache comprising cache lines having a cache line size, comprising the steps of: providing a hash table to a memory of the computer system, the hash table having buckets of the cache line size storing data; and accessing data stored in one of the buckets of the hash table whereupon the processor loads the one bucket into the cache such that the one bucket is stored with an exact fit into one of the cache lines.