PERFORMING CONCURRENT REHASHING OF A HASH TABLE FOR MULTITHREADED APPLICATIONS

• US 20120036134A1
• Filed: 04/08/2009
• Published: 02/09/2012
• Est. Priority Date: 04/08/2009
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Malakhov, Anton
• Granted Patent: US 9,563,477 B2
• Time in Patent Office: Days
• US Class Current: 707/747
• CPC Class Codes: G06F 9/5016 the resource being the memory

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.

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.

2. The method of claim 1, further comprising performing a check without locking a bucket to determine whether rehashing is needed.

3. The method of claim 1, further comprising thereafter performing a rehashing of contents of a first bucket of the first number of buckets to a second bucket of the second number of buckets when performing a lookup operation for a data pair present in the first bucket.

4. The method of claim 1, further comprising calculating a bucket index using the updated capacity, accessing a bucket using the bucket index, determining that the bucket is not rehashed, and recursively calculating a parent bucket index for a parent bucket, until a rehashed root bucket is found to which the bucket is logically mapped using the updated capacity.

5. The method of claim 4, further comprising rehashing at least part of contents of the rehashed root bucket to the bucket when or prior to searching for a data pair of the lookup request.

6. The method of claim 5, further comprising setting a partial rehash indicator when only part of the contents of the root bucket is rehashed.

7. The method of claim 4, further comprising searching the buckets for a data pair of the lookup request and returning the data pair, and not rehashing contents of the buckets.

8. The method of claim 1, further comprising responsive to a lookup operation by a first thread, not finding a requested data pair in a first bucket of the first number of buckets, comparing a current value of the hash table capacity to a value of the hash table capacity used in determining a bucket index for the lookup operation, and if the current value and the value are different, calculating an index of a closest successor bucket, accessing the closest successor bucket and determining a rehash state for the closets successor bucket.

9. The method of claim 8, further comprising restarting the lookup operation if the rehash state is not indicative of a new (non-rehashed) state.

10. The method of claim 1, further comprising combining a plurality of allocations into a single allocation for the second number of buckets.

11. The method of claim 1, further comprising publishing a plurality of allocations and publishing the updated capacity once for the plurality of allocations.

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.

13. The article of claim 12, wherein the method further comprises restarting the lookup operation if the rehash state is not indicative of a new state.

14. The article of claim 12, wherein the method further comprises rehashing a bucket of the hash table while accessing the bucket during the lookup operation.

15. The article of claim 12, wherein the lookup operation is performed by a first thread, and the hash table is expanded by a second thread after the first thread obtains the first capacity value for the calculation and a third thread begins rehashing the first bucket before the first thread accesses the first bucket.

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.

17. The system of claim 16, wherein a third thread is to perform a rehashing of contents of the first bucket of the first number of buckets to a second bucket of the second number of buckets when performing a lookup operation for a data pair present in the first bucket.

18. The system of claim 16, wherein the second thread is to calculate a bucket index for a bucket of the second number of buckets using the updated capacity, access the bucket using the bucket index, determine that the bucket is not rehashed, and recursively calculate a parent bucket index for a parent bucket to which the bucket is logically mapped, until a rehashed root bucket is found.

19. The system of claim 18, wherein the second thread is to rehash at least part of contents of the rehashed root bucket to the bucket when or prior to searching for a data pair of the lookup request.

20. The method of claim 19, wherein the second thread is to set a partial rehash indicator of the root bucket when only part of the contents of the root bucket is rehashed.