Concurrent Circular Reference Attribute Grammars
Öqvist, Jesper LU and Hedin, Görel LU
(2017)
10th ACM SIGPLAN International Conference on Software Language Engineering (SLE 2017)
p.151-162
- Abstract
- Reference Attribute Grammars (RAGs) is a declarative executable formalism used for constructing compilers and related tools. Existing implementations support concurrent evaluation only with global evaluation locks. This may lead to long latencies in interactive tools, where interactive and background threads query attributes concurrently.
We present lock-free algorithms for concurrent attribute evaluation, enabling low latency in interactive tools. Our algorithms support important extensions to RAGs like circular (fixed-point) attributes and higher-order attributes.
We have implemented our algorithms in Java, for the JastAdd metacompiler. We evaluate the implementation on a JastAdd-specified compiler for the Java... (More) - Reference Attribute Grammars (RAGs) is a declarative executable formalism used for constructing compilers and related tools. Existing implementations support concurrent evaluation only with global evaluation locks. This may lead to long latencies in interactive tools, where interactive and background threads query attributes concurrently.
We present lock-free algorithms for concurrent attribute evaluation, enabling low latency in interactive tools. Our algorithms support important extensions to RAGs like circular (fixed-point) attributes and higher-order attributes.
We have implemented our algorithms in Java, for the JastAdd metacompiler. We evaluate the implementation on a JastAdd-specified compiler for the Java language, demonstrating very low latencies for interactive attribute queries, on the order of milliseconds. Furthermore, initial experiments show a speedup of about a factor 2 when using four parallel compilation threads. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/2b62015f-7268-42da-b4a5-9f0fa975138a
- author
- Öqvist, Jesper
LU
and Hedin, Görel
LU
- organization
- publishing date
- 2017-10-23
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- reference attribute grammar, concurrency, parallelization, memoization, circular attributes
- host publication
- Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering
- pages
- 12 pages
- publisher
- Association for Computing Machinery (ACM)
- conference name
- 10th ACM SIGPLAN International Conference on Software Language Engineering (SLE 2017)
- conference location
- Vancouve, Canada
- conference dates
- 2017-10-23 - 2017-10-24
- external identifiers
-
- scopus:85037169886
- ISBN
- 978-1-4503-5525-4
- DOI
- 10.1145/3136014.3136032
- project
- Contributions to Declarative Implementation of Static Program Analysis
- ELLIIT LU P05: Scalable Language Tools for Cyber-Physical Systems
- language
- English
- LU publication?
- yes
- id
- 2b62015f-7268-42da-b4a5-9f0fa975138a
- date added to LUP
- 2017-12-12 10:19:17
- date last changed
- 2022-04-25 04:19:06
@inproceedings{2b62015f-7268-42da-b4a5-9f0fa975138a,
abstract = {{Reference Attribute Grammars (RAGs) is a declarative executable formalism used for constructing compilers and related tools. Existing implementations support concurrent evaluation only with global evaluation locks. This may lead to long latencies in interactive tools, where interactive and background threads query attributes concurrently.<br/><br/>We present lock-free algorithms for concurrent attribute evaluation, enabling low latency in interactive tools. Our algorithms support important extensions to RAGs like circular (fixed-point) attributes and higher-order attributes.<br/><br/>We have implemented our algorithms in Java, for the JastAdd metacompiler. We evaluate the implementation on a JastAdd-specified compiler for the Java language, demonstrating very low latencies for interactive attribute queries, on the order of milliseconds. Furthermore, initial experiments show a speedup of about a factor 2 when using four parallel compilation threads.}},
author = {{Öqvist, Jesper and Hedin, Görel}},
booktitle = {{Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering}},
isbn = {{978-1-4503-5525-4}},
keywords = {{reference attribute grammar; concurrency; parallelization; memoization; circular attributes}},
language = {{eng}},
month = {{10}},
pages = {{151--162}},
publisher = {{Association for Computing Machinery (ACM)}},
title = {{Concurrent Circular Reference Attribute Grammars}},
url = {{http://dx.doi.org/10.1145/3136014.3136032}},
doi = {{10.1145/3136014.3136032}},
year = {{2017}},
}