Skip to main content
main-content

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

2018 | OriginalPaper | Buchkapitel

Efficient Lock-Free Removing and Compaction for the Cache-Trie Data Structure

verfasst von: Aleksandar Prokopec

Erschienen in: Euro-Par 2018: Parallel Processing

Verlag: Springer International Publishing

share
TEILEN

Abstract

The recently proposed cache-trie data structure improves the performance of lock-free Ctries by maintaining an auxiliary data structure called a cache. The cache allows basic operations to run in expected O(1), instead of the previous \(O(\log n)\) bound. While earlier work showed that cache-tries improve inserts and lookups by 1.5–5\(\times \) on standard workloads, the remove operation was not previously examined. One of the main challenges of remove is to compact the trie – removing the elements should recycle the unused parts of the data structure.
In this paper, we describe a new non-compacting and two new compacting non-blocking variants of the remove operation for cache-tries. We ensure that each remove implementation runs in expected O(1) time. Compared to standard Ctries, performance improvements range between \(10\%\) and \(35\%\), depending on the size of the data structure, the parallelism level and the hardware architecture.
Fußnoten
1
Other arities are possible, but we found 16 to work well, because the node fits into a 64 byte cache-line when JVM’s compressed object pointers are used.
 
Literatur
2.
Zurück zum Zitat Areias, M., Rocha, R.: A lock-free hash trie design for concurrent tabled logic programs. Int. J. Parallel Program. 44(3), 386–406 (2016) CrossRef Areias, M., Rocha, R.: A lock-free hash trie design for concurrent tabled logic programs. Int. J. Parallel Program. 44(3), 386–406 (2016) CrossRef
3.
16.
Zurück zum Zitat Liang, F.M.: Word Hy-phen-a-tion by Com-pu-ter. Ph.D. thesis, Stanford University, Stanford, CA 94305, June 1983. also available as Stanford University, Department of Computer Science Report No. STAN-CS-83-977 Liang, F.M.: Word Hy-phen-a-tion by Com-pu-ter. Ph.D. thesis, Stanford University, Stanford, CA 94305, June 1983. also available as Stanford University, Department of Computer Science Report No. STAN-CS-83-977
20.
Zurück zum Zitat Prokopec, A., Petrashko, D., Odersky, M.: Efficient lock-free work-stealing iterators for data-parallel collections. In: 2015 23rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, pp. 248–252, March 2015 Prokopec, A., Petrashko, D., Odersky, M.: Efficient lock-free work-stealing iterators for data-parallel collections. In: 2015 23rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, pp. 248–252, March 2015
21.
Zurück zum Zitat Prokopec, A.: Data structures and algorithms for data-parallel computing in a managed runtime. Ph.D. thesis, IC, Lausanne (2014) Prokopec, A.: Data structures and algorithms for data-parallel computing in a managed runtime. Ph.D. thesis, IC, Lausanne (2014)
26.
Zurück zum Zitat Prokopec, A.: Analysis of Concurrent Lock-Free Hash Tries with Constant-Time Operations. ArXiv e-prints, December 2017 Prokopec, A.: Analysis of Concurrent Lock-Free Hash Tries with Constant-Time Operations. ArXiv e-prints, December 2017
31.
Zurück zum Zitat Prokopec, A., Bagwell, P., Odersky, M.: Cache-aware lock-free concurrent hash tries. Technical report (2011) Prokopec, A., Bagwell, P., Odersky, M.: Cache-aware lock-free concurrent hash tries. Technical report (2011)
34.
37.
Zurück zum Zitat Prokopec, A., Miller, H., Haller, P., Schlatter, T., Odersky, M.: FlowPools: a lock-free deterministic concurrent dataflow abstraction, proofs. Technical report (2012) Prokopec, A., Miller, H., Haller, P., Schlatter, T., Odersky, M.: FlowPools: a lock-free deterministic concurrent dataflow abstraction, proofs. Technical report (2012)
38.
Zurück zum Zitat Prokopec, A., Miller, H., Schlatter, T., Haller, P., Odersky, M.: Flowpools: a lock-free deterministic concurrent dataflow abstraction. In: LCPC, pp. 158–173 (2012) CrossRef Prokopec, A., Miller, H., Schlatter, T., Haller, P., Odersky, M.: Flowpools: a lock-free deterministic concurrent dataflow abstraction. In: LCPC, pp. 158–173 (2012) CrossRef
40.
Zurück zum Zitat Prokopec, A., Odersky, M.: Isolates, channels, and event streams for composable distributed programming. In: 2015 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward!), pp. 171–182. Onward! 2015. ACM, New York (2015). https://​doi.​org/​10.​1145/​2814228.​2814245 Prokopec, A., Odersky, M.: Isolates, channels, and event streams for composable distributed programming. In: 2015 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward!), pp. 171–182. Onward! 2015. ACM, New York (2015). https://​doi.​org/​10.​1145/​2814228.​2814245
42.
Zurück zum Zitat Prokopec, A., Petrashko, D., Odersky, M.: On lock-free work-stealing iterators for parallel data structures, p. 10 (2014) Prokopec, A., Petrashko, D., Odersky, M.: On lock-free work-stealing iterators for parallel data structures, p. 10 (2014)
43.
Zurück zum Zitat Pugh, W.: Concurrent maintenance of skip lists. Technical report, College Park, MD, USA (1990) Pugh, W.: Concurrent maintenance of skip lists. Technical report, College Park, MD, USA (1990)
44.
Zurück zum Zitat Schlatter, T., Prokopec, A., Miller, H., Haller, P., Odersky, M.: Multi-lane flowpools: a detailed look, p. 13 (2012) Schlatter, T., Prokopec, A., Miller, H., Haller, P., Odersky, M.: Multi-lane flowpools: a detailed look, p. 13 (2012)
45.
Zurück zum Zitat Shafiei, N.: Non-blocking patricia tries with replace operations. In: 2013 IEEE 33rd International Conference on Distributed Computing Systems, pp. 216–225, July 2013 Shafiei, N.: Non-blocking patricia tries with replace operations. In: 2013 IEEE 33rd International Conference on Distributed Computing Systems, pp. 216–225, July 2013
47.
Metadaten
Titel
Efficient Lock-Free Removing and Compaction for the Cache-Trie Data Structure
verfasst von
Aleksandar Prokopec
Copyright-Jahr
2018
DOI
https://doi.org/10.1007/978-3-319-96983-1_41

Premium Partner