PERFORMING CONCURRENT REHASHING OF A HASH TABLE FOR MULTITHREADED APPLICATIONS
First Claim
Patent Images
1. A method comprising:
- allocating a second number of buckets for a hash table shared concurrently by a plurality of threads, the hash table having a first number of buckets, the second number of buckets being at least equal to the first number of buckets and each of the second number of buckets is logically mapped onto a corresponding parent one of the first or the second number of buckets; and
publishing an updated capacity of the hash table including the first and second number of buckets, wherein the allocating is completed by publishing the updated capacity and without performing any rehashing of contents of the first number of buckets.
1 Assignment
0 Petitions
Accused Products
Abstract
In one embodiment, the present invention includes a method for allocating a second number of buckets for a hash table shared concurrently by a plurality of threads, where the second number of buckets are logically mapped onto a corresponding parent one of the first number of buckets, and publishing an updated capacity of the hash table to complete the allocation, without performing any rehashing, such that the rehashing can later be performed in an on-demand, per bucket basis. Other embodiments are described and claimed.
-
Citations
20 Claims
-
1. A method comprising:
-
allocating a second number of buckets for a hash table shared concurrently by a plurality of threads, the hash table having a first number of buckets, the second number of buckets being at least equal to the first number of buckets and each of the second number of buckets is logically mapped onto a corresponding parent one of the first or the second number of buckets; and publishing an updated capacity of the hash table including the first and second number of buckets, wherein the allocating is completed by publishing the updated capacity and without performing any rehashing of contents of the first number of buckets. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. An article comprising a machine-readable storage medium including instructions that if executed by a machine enable the machine to perform a method comprising:
-
performing a lookup operation to a hash table shared concurrently by a plurality of threads, including calculating a bucket index for a first bucket of the hash table using a first capacity value for the hash table, accessing the first bucket using the bucket index, and determining that the first bucket does not include a data pair of the lookup operation; comparing a current capacity value of the hash table capacity to the first capacity value, and if the current capacity value and the first value are different, calculating an updated bucket index using the current capacity value; and if the updated bucket index and the bucket index are different, calculating a next bucket index, accessing a next bucket corresponding to the updated bucket index, and determining a rehash state for the next bucket. - View Dependent Claims (13, 14, 15)
-
-
16. A system comprising:
-
a microprocessor including a first core and a second core each to execute one or more threads, wherein a first thread is to allocate a second number of buckets for a hash table shared concurrently by a plurality of threads, the hash table previously having a first number of buckets, the second number of buckets being at least equal to the first number of buckets, where each of the second number of buckets is logically mapped onto either a corresponding parent one of the first number of buckets or one of the second number of buckets, and publish an updated capacity of the hash table including the first and second number of buckets, wherein the first thread is to complete the allocation by publishing the updated capacity and without performing any rehashing of contents of the first number of buckets, and a second thread is to perform a lookup operation to a first bucket of the first number of buckets without checking a lock variable to determine whether rehashing is needed; and a shared memory coupled to the microprocessor to store the hash table, the hash table to be concurrently accessed by at least some of the plurality of threads. - View Dependent Claims (17, 18, 19, 20)
-
Specification