RECORD
Empirical Evaluation of a Thread-Safe Dynamic Range Min-Max Tree using HTM
Distributed, Parallel, and Cluster Computing · Submitted 18 Mar 2016
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We have also shown that HTM performs better than locks when the number of write operations increase, making it a practical structure to use in several write-intensive contexts.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Succinct trees, such as wavelet trees and those based on, for instance, range Min-Max trees (RMMTs), are a family of practical data structures that store information close to their information-theoretic space lower bound. These structures are often static; meaning that once they are built, nodes cannot be added, deleted or modified. This read-only property simplifies concurrency. However, newer versions of these data structures allow for a fair degree of dynamism. Parallel programming using Hardware Transactional Memory(HTM), has been available in mainstream microprocessors since a few years ago. One limitation of HTM is still on the size of each transaction. This is why HTM's use, for the moment, is limited to operations that involve few memory addresses that need to be updated atomically, or where the level of concurrency is low. We provide the first available implementation of a concurrent, dynamic RMMT based on HTM, and we compare empirically how well HTM performs compared to a naive implementation using locks. We have shown that because of the formal properties of RMMTs, HTM is a good fit for adding concurrency to otherwise slow lock-based alternatives. We have also shown that HTM performs better than locks when the number of write operations increase, making it a practical structure to use in several write-intensive contexts. This is, as far as we know, the only practical implementation of RMMTs thoroughly tested using HTM.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Succinct trees, such as wavelet trees and those based on, for instance, range Min-Max trees (RMMTs), are a family of practical data structures that store information close to their information-theoretic space lower bound. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s1 | These structures are often static; meaning that once they are built, nodes cannot be added, deleted or modified. | background 1.00 | 0.05 | 0.02 | asserted 0.95 |
| s2 | This read-only property simplifies concurrency. | background 0.99 | 0.05 | 0.02 | asserted 1.00 |
| s3 | However, newer versions of these data structures allow for a fair degree of dynamism. | background 0.98 | 0.05 | 0.02 | asserted 0.96 |
| s4 | Parallel programming using Hardware Transactional Memory(HTM), has been available in mainstream microprocessors since a few years ago. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s5 | One limitation of HTM is still on the size of each transaction. | background 0.80 | 0.07 | 0.02 | asserted 0.99 |
| s6 | This is why HTM's use, for the moment, is limited to operations that involve few memory addresses that need to be updated atomically, or where the level of concurrency is low. | background 0.86 | 0.07 | 0.03 | asserted 0.94 |
| s7 | We provide the first available implementation of a concurrent, dynamic RMMT based on HTM, and we compare empirically how well HTM performs compared to a naive implementation using locks. | contribution 1.00 | 0.96 | 0.17 | asserted 1.00 |
| s8 | We have shown that because of the formal properties of RMMTs, HTM is a good fit for adding concurrency to otherwise slow lock-based alternatives. | result 0.55 | 0.94 | 0.43 | asserted 1.00 |
| s9 | We have also shown that HTM performs better than locks when the number of write operations increase, making it a practical structure to use in several write-intensive contexts. | result 0.93 | 0.95 | 0.44 | asserted 1.00 |
| s10 | This is, as far as we know, the only practical implementation of RMMTs thoroughly tested using HTM. | contribution 0.62 | 0.46 | 0.14 | asserted 0.93 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Succinct trees, such as wavelet trees and those based on, for instance, range Min-Max trees (RMMTs), are a family of practical data structures that store information close to their information-theoretic space lower bound. These structures are often static; meaning that once they are built, nodes cannot be added, deleted or modified. This read-only property simplifies concurrency. However, newer versions of these data structures allow for a fair degree of dynamism. Parallel programming using Hardware Transactional Memory(HTM), has been available in mainstream microprocessors since a few years ago. One limitation of HTM is still on the size of each transaction. This is why HTM's use, for the moment, is limited to operations that involve few memory addresses that need to be updated atomically, or where the level of concurrency is low. We provide the first available implementation of a concurrent, dynamic RMMT based on HTM, and we compare empirically how well HTM performs compared to a naive implementation using locks. We have shown that because of the formal properties of RMMTs, HTM is a good fit for adding concurrency to otherwise slow lock-based alternatives. We have also shown that HTM performs better than locks when the number of write operations increase, making it a practical structure to use in several write-intensive contexts. This is, as far as we know, the only practical implementation of RMMTs thoroughly tested using HTM.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.