Abstract
Most applications manipulate structured data. Modern languages and platforms provide collection frameworks with basic data structures like lists, hashtables and trees. These data structures have a range of predefined operations which include mapping, filtering or finding elements. Such bulk operations traverse the collection and process the elements sequentially. Their implementation relies on iterators, which are not applicable to parallel operations due to their sequential nature.
We present an approach to parallelizing collection operations in a generic way, used to factor out common parallel operations in collection libraries. Our framework is easy to use and straightforward to extend to new collections. We show how to implement concrete parallel collections such as parallel arrays and parallel hash maps, proposing an efficient solution to parallel hash map construction. Finally, we give benchmarks showing the performance of parallel collection operations.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Lea, D.: A Java Fork/Join Framework (2000)
Traore, D., Roch, J.-L., Maillard, N., Gautier, T., Bernard, J.: Deque-free work-optimal parallel STL algorithms. In: Proceedings of the 14th Euro-Par Conference (2008)
Odersky, M., et al.: An Overview of the Scala Programming Language. Technical Report LAMP-REPORT-2006-001, EPFL (2006)
Odersky, M., Spoon, L., Venners, B.: Programming in Scala. Artima Press (2008)
Odersky, M.: Scala 2.8 collections. EPFL (2009)
Toub, S.: Patterns of Parallel Programming. Microsoft Corporation (2010)
Doug Lea’s, Home page, http://gee.cs.oswego.edu/
Blumofe, R.D., Leiserson, C.E.: Scheduling Multithreaded Computations by Work Stealing. In: 35th IEEE Conference on Foundations of Computer Science (1994)
Cong, G., Kodali, S., Krishnamoorthy, S., Lea, D., Saraswat, V., Wen, T.: Solving Large, Irregular Graph Problems Using Adaptive Work Stealing. In: Proceedings of the 2008 37th International Conference on Parallel Processing (2008)
Boehm, H.-J., Atkinson, R., Plass, M.: Ropes: An Alternative to Strings. Software: Practice and Experience (1995)
Bagwell, P.: Ideal Hash Trees (2002)
Dragos, I., Odersky, M.: Compiling Generics Through User-Directed Type Specialization. In: Fourth ECOOP Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (2009)
Moir, M., Shavit, N.: Concurrent data structures. Handbook of Data Structures and Applications. Chapman and Hall, Boca Raton (2007)
Jones, S.P., Leshchinskiy, R., Keller, G., Chakravarty, M.M.T.: Harnessing the Multicores: Nested Data Parallelism in Haskell. Foundations of Software Technology and Theoretical Computer Science (2008)
Intel Thread Building Blocks: Tutorial (2010), http://www.intel.com
Buss, A., Harshvardhan, Papadopoulos, I., Tkachyshyn, O., Smith, T., Tanase, G., Thomas, N., Xu, X., Bianco, M., Amato, N.M., Rauchwerger, L.: STAPL: Standard Template Adaptive Parallel Library. In: Haifa Experimental Systems Conference (2010)
Allen, E., Chase, D., Hallett, J., Luchangco, V., Maessen, J.-W., Ryu, S., Steele Jr., G.L., Tobin-Hochstadt, S., et al.: The Fortress Language Specification (2008)
Steele Jr., G.L.: How to Think about Parallel Programming: Not! (2011), http://www.infoq.com/presentations/Thinking-Parallel-Programming
Georges, A., Buytaert, D., Eeckhout, L.: Statistically Rigorous Java Performance Evaluation. In: OOPSLA (2007)
Hinze, R., Paterson, R.: Finger Trees: A Simple General-purpose Data Structure. Journal of Functional Programming (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Prokopec, A., Bagwell, P., Rompf, T., Odersky, M. (2011). A Generic Parallel Collection Framework. In: Jeannot, E., Namyst, R., Roman, J. (eds) Euro-Par 2011 Parallel Processing. Euro-Par 2011. Lecture Notes in Computer Science, vol 6853. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-23397-5_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-23397-5_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-23396-8
Online ISBN: 978-3-642-23397-5
eBook Packages: Computer ScienceComputer Science (R0)