16:6 T. Maier et al.
Using an update function in the update interface deserves some attention, because the interface
changes the way both experienced and inexperienced users interact with the table. Most interfaces
fall into one of two categories: They either return mutable references to table elements—forcing
the user to implement atomic operations on the data type; or they oer an update function, which
usually replaces the current value with a new one—making it very hard to implement atomic read
modify write operations (find + increment + overwrite not necessarily atomic). We made sure
that using our interface, experienced users can implement both atomic and non-atomic changes
to our table. The correct behavior can be chosen according to the specic update function (line 8),
e.g., overwrite (using single word store), increment (using fetch and add).
In Algorithm 1, we show the pseudocode of the insertOrUpdate function. The operation com-
putes the hash value of the key (line 1) and proceeds to look for an element with the appropriate
key (beginning at the corresponding position). If no element matching the key is found (when an
empty space is encountered (line 5)), then the new element has to be inserted. This is done using
a CAS operation (line 6). A failed swap can only be caused by another insertion into the same cell.
In this case, we have to revisit the same cell (line 9), to check if the inserted element matches the
current key. If a cell storing the same key is found, then it will be updated using the atomicUpdate
function (line 11). This function is usually implemented by evaluating the passed update function
(up) and using a CAS operation, to change the cell. In the case of multiple concurrent updates, at
least one will be successful.
Lookup. For the performance of many hash table workloads lookup operations are even more
important than table modications. In folkloreHT, lookups can proceed without any memory
changes.
find(k) returns the value that has been stored with the key k or ⊥ if the key has not been
stored. The following problem arises, because we use 64 bits each for the key and the value. This is
necessary, because it allows storing a pointer as value. To implement a correct nd operation one
has to be aware that using modern hardware it is impossible to atomically read both the key and
the value together
2
(together they have 128 bits). Therefore—even though any change to a cell is
atomic—it is possible for a cell to be changed in between reading its key and its value, this is called
a torn read. To argue the correctness of our find implementation, we have to make sure that torn
reads cannot lead to any wrong behavior. There are two kinds of interesting torn reads: First an
empty key is read while the searched key is inserted into the same cell. In this case, the element is
not found (consistent, since it has not been fully inserted). Second, the element is updated between
the key being read and the data being read. Since the data is read second, only the newer data is
read. This is consistent with a nished update.
Deletions. delete(k) Returns true if an element with key k was present and is successfully re-
moved. FolkloreHT does not support true deletions (deletions that reclaim previously used mem-
ory). Simply deleting elements from folkloreHT is not possible, because we have to make sure
that future lookup operations can still nd displaced elements. The same problem arises when
rearranging elements.
The only way folkloreHT can support deletions is using dummy elements—called tombstones.
Usually the key stored in a cell is replaced with del_key. Future operations will scan over deleted
elements like over any other nonempty entry. This means that the cell cannot be used anymore. Us-
ing tombstones for handling deleted elements is usually not feasible, because the starting capacity
has to be set dependent on the number of overall insertions (deletion does not free up any deleted
2
The element is not read atomically, because x86 processor specications do not guarantee atomicity for 128-bit reads.
ACM Transactions on Parallel Computing, Vol. 5, No. 4, Article 16. Publication date: February 2019.
剩余31页未读，继续阅读
weixin_38653296
- 粉丝: 2
- 资源: 911
我的内容管理
展开
最新资源
- 李兴华Java基础教程：从入门到精通
- U盘与硬盘启动安装教程：从菜鸟到专家
- C++面试宝典：动态内存管理与继承解析
- C++ STL源码深度解析：专家级剖析与关键技术
- C/C++调用DOS命令实战指南
- 神经网络补偿的多传感器航迹融合技术
- GIS中的大地坐标系与椭球体解析
- 海思Hi3515 H.264编解码处理器用户手册
- Oracle基础练习题与解答
- 谷歌地球3D建筑筛选新流程详解
- CFO与CIO携手：数据管理与企业增值的战略
- Eclipse IDE基础教程：从入门到精通
- Shell脚本专家宝典：全面学习与资源指南
- Tomcat安装指南：附带JDK配置步骤
- NA3003A电子水准仪数据格式解析与转换研究
- 自动化专业英语词汇精华：必备术语集锦
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
