Advanced

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) In Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering 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:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
reference attribute grammar, concurrency, parallelization, memoization, circular attributes
in
Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering
pages
12 pages
publisher
ACM
conference name
10th ACM SIGPLAN International Conference on Software Language Engineering (SLE 2017)
external identifiers
  • scopus:85037169886
ISBN
978-1-4503-5525-4
DOI
10.1145/3136014.3136032
language
English
LU publication?
yes
id
2b62015f-7268-42da-b4a5-9f0fa975138a
date added to LUP
2017-12-12 10:19:17
date last changed
2018-01-07 12:28:19
@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},
  keyword      = {reference attribute grammar,concurrency,parallelization,memoization,circular attributes},
  language     = {eng},
  month        = {10},
  pages        = {151--162},
  publisher    = {ACM},
  title        = {Concurrent Circular Reference Attribute Grammars},
  url          = {http://dx.doi.org/10.1145/3136014.3136032},
  year         = {2017},
}