A study of data structures with a deep heap shape
A study of data structures with a deep heap shape
复制标题
深堆形数据结构研究
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
E. Petrank
中科院分区：
文献类型：
--
作者：
Haggai Eran;E. Petrank
计算环境变得越来越并行，我们很可能会在明天的台式机和服务器平台上看到更多的内核。在高度并行的系统中，跟踪垃圾收集器可能无法很好地扩展，因为深堆结构会阻碍并行跟踪。以前的工作已经发现了标准Java基准测试中的漏洞。在这项工作中，我们检查这些标准的基准测试，并分析它们，以揭示数据结构，使当前的Java基准测试创建深堆形状。事实证明，这个问题主要表现在使用队列和链表的基准测试中。然后，我们提出了一个新的无锁队列数据结构的建设与额外的引用，使更好的垃圾收集器并行低开销。
Computing environments become increasingly parallel, and it seems likely that we will see more cores on tomorrow's desktops and server platforms. In a highly parallel system, tracing garbage collectors may not scale well due to deep heap structures that hinder parallel tracing. Previous work has discovered vulnerabilities within standard Java benchmarks. In this work we examine these standard benchmarks and analyze them to expose the data structures that make current Java benchmarks create deep heap shapes. It turns out that the problem is manifested mostly with benchmarks that employ queues and linked-lists. We then propose a new construction of a lock-free queue data structure with extra references that enables better garbage collector parallelism at a low overhead.