%0 Conference Paper %1 Cohen:2017:LLS %A Cohen, Nachshon %A Tal, Arie %A Petrank, Erez %B Proceedings of the 22Nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming %D 2017 %I ACM %K Concurrency DataStructures LayoutLock MostlyImmutable %P 17--29 %R 10.1145/3018743.3018753 %T Layout Lock: A Scalable Locking Paradigm for Concurrent Data Layout Modifications %X Data-structures can benefit from dynamic data layout modifications when the size or the shape of the data structure changes during the execution, or when different phases in the program execute different workloads. However, in a modern multi-core environment, layout modifications involve costly synchronization overhead. In this paper we propose a novel layout lock that incurs a negligible overhead for reads and a small overhead for updates of the data structure. We then demonstrate the benefits of layout changes and also the advantages of the layout lock as its supporting synchronization mechanism for two data structures. In particular, we propose a concurrent binary search tree, and a concurrent array set, that benefit from concurrent layout modifications using the proposed layout lock. Experience demonstrates performance advantages and integration simplicity. %@ 978-1-4503-4493-7

@inproceedings{Cohen:2017:LLS, abstract = {Data-structures can benefit from dynamic data layout modifications when the size or the shape of the data structure changes during the execution, or when different phases in the program execute different workloads. However, in a modern multi-core environment, layout modifications involve costly synchronization overhead. In this paper we propose a novel layout lock that incurs a negligible overhead for reads and a small overhead for updates of the data structure. We then demonstrate the benefits of layout changes and also the advantages of the layout lock as its supporting synchronization mechanism for two data structures. In particular, we propose a concurrent binary search tree, and a concurrent array set, that benefit from concurrent layout modifications using the proposed layout lock. Experience demonstrates performance advantages and integration simplicity.}, acmid = {3018753}, added-at = {2017-04-16T22:08:28.000+0200}, author = {Cohen, Nachshon and Tal, Arie and Petrank, Erez}, biburl = {https://www.bibsonomy.org/bibtex/2e7150b0f4bf24ad49b6d5f6daf451ac0/gron}, booktitle = {Proceedings of the 22Nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming}, description = {Layout Lock}, doi = {10.1145/3018743.3018753}, interhash = {caf524ba527fc3cc3b51ce4b4e6785cc}, intrahash = {e7150b0f4bf24ad49b6d5f6daf451ac0}, isbn = {978-1-4503-4493-7}, keywords = {Concurrency DataStructures LayoutLock MostlyImmutable}, location = {Austin, Texas, USA}, numpages = {13}, pages = {17--29}, publisher = {ACM}, series = {PPoPP '17}, timestamp = {2017-04-16T22:08:28.000+0200}, title = {{Layout Lock: A Scalable Locking Paradigm for Concurrent Data Layout Modifications}}, year = 2017 }