Smart Data Structures: An Online Machine Learning Approach to Multicore Data Structures

As multicores become prevalent, the complexity of programming is skyrocketing. One major difficulty is efficiently orchestrating collaboration among threads through shared data structures. Unfortunately, choosing and hand-tuning data structure algorithms to get good performance across a variety of machines and inputs is a herculean task to add to the fundamental difficulty of getting a parallel program correct. To help mitigate these complexities, this paper develops a new class of parallel data structures called Smart Data Structures that leverage online machine learning to adapt automatically.