Open Effects: Programmer-guided Effects for Open World Concurrent Programs

Thumbnail Image
Date
2013-10-15
Authors
Long, Yuheng
Bagherzadeh, Mehdi
Rajan, Hridesh
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Person
Rajan, Hridesh
Professor and Department Chair of Computer Science
Research Projects
Organizational Units
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Computer Science
Abstract

The open world assumption makes the design of a type-and-effect system challenging, especially in concurrent object-oriented languages. The main problem is in the computation of the effects of a dynamically dispatched method invocation, because all possible dynamic types of its receiver are not known statically. Previous work proposes effect annotations that provide a static upper bound on the effects of a dynamically dispatched method, conservative enough to cover the effects of all methods which could possibly be executed upon its invocation. For two dynamically dispatched methods, a typical type-and-effect system may disallow concurrent execution of their invocations because their conservatively specified static effects conflict. However, such a conflict may not actually happen at runtime, depending on the dynamic types of their receivers. This work proposes open effects, a sound trust-but-verify type-and-effect system, to better enable concurrent execution of dynamically dispatched method invocations. If a programmer annotates the receiver of a certain method invocation as open, then the type system trusts the programmer and assigns an open effect to the method. The open effect is supposed, optimistically, not to conflict with other effects. Such optimistic assumptions are verified statically, if possible, or at runtime otherwise. Open effects is complementary to previously proposed static and dynamic effect analyses and combines them such that the accuracy of static analysis could help decrease the overhead of the dynamic analysis. Performance evaluations of an implementation of open effects, on various benchmarks, show that: open effects incurs negligible annotation and runtime overheads such that code with open effects does almost as well as its manually tuned concurrent version.

Comments

Copyright © 2013, Yuheng Long, Mehdi Bagherzadeh, and Hridesh Rajan

Description
Keywords
Citation
DOI
Source
Copyright
Collections