lecture_notes:04-07-2011
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
lecture_notes:04-07-2011 [2011/04/08 15:43] eyliaw [Hash Algorithm] |
lecture_notes:04-07-2011 [2011/04/08 15:59] eyliaw [Multithreading Tricks] |
||
|---|---|---|---|
| Line 12: | Line 12: | ||
| The algorithm also limits the size of the value field, making use of the fact that the average number of reads is the coverage c. When it has filled, it will reprobe and store the higher order bits in the extension. In the reprobed position, it avoids repeating the 2k-l key and instead stores the number of reprobes from the original position, which is a shorter value. The extra space is used for the value field. | The algorithm also limits the size of the value field, making use of the fact that the average number of reads is the coverage c. When it has filled, it will reprobe and store the higher order bits in the extension. In the reprobed position, it avoids repeating the 2k-l key and instead stores the number of reprobes from the original position, which is a shorter value. The extra space is used for the value field. | ||
| - | ===== Multithreading Tricks ===== | + | ===== Multithreading ===== |
| - | + | In order to parallelize updates to the hash table, the algorithm uses the compare and swap (CAS) instruction, which will fail if two threads attempt to modify the same location at the same time. The CAS operation will look at a location and only replace the value stored there if it equals an expected value. | |
lecture_notes/04-07-2011.txt · Last modified: 2015/07/28 15:12 by 149.155.218.110
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported
