6 Search Results for "Schäfer, Max"

Document
Artifact
DOI: 10.4230/DARTS.7.2.5
Enabling Additional Parallelism in Asynchronous JavaScript Applications (Artifact)

Authors: Ellen Arteca, Frank Tip, and Max Schäfer

Published in: DARTS, Volume 7, Issue 2, Special Issue of the 35th European Conference on Object-Oriented Programming (ECOOP 2021)

Abstract
JavaScript is a single-threaded programming language, so asynchronous programming is practiced out of necessity to ensure that applications remain responsive in the presence of user input or interactions with file systems and networks. However, many JavaScript applications execute in environments that do exhibit concurrency by, e.g., interacting with multiple or concurrent servers, or by using file systems managed by operating systems that support concurrent I/O. In this paper, we demonstrate that JavaScript programmers often schedule asynchronous I/O operations suboptimally, and that reordering such operations may yield significant performance benefits. Concretely, we define a static side-effect analysis that can be used to determine how asynchronous I/O operations can be refactored so that asynchronous I/O-related requests are made as early as possible, and so that the results of these requests are awaited as late as possible. While our static analysis is potentially unsound, we have not encountered any situations where it suggested reorderings that change program behavior. We evaluate the refactoring on 20 applications that perform file- or network-related I/O. For these applications, we observe average speedups ranging between 0.99% and 53.6% for the tests that execute refactored code (8.1% on average).
Cite as

Ellen Arteca, Frank Tip, and Max Schäfer. Enabling Additional Parallelism in Asynchronous JavaScript Applications (Artifact). In Special Issue of the 35th European Conference on Object-Oriented Programming (ECOOP 2021). Dagstuhl Artifacts Series (DARTS), Volume 7, Issue 2, pp. 5:1-5:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{arteca_et_al:DARTS.7.2.5,
  author =	{Arteca, Ellen and Tip, Frank and Sch\"{a}fer, Max},
  title =	{{Enabling Additional Parallelism in Asynchronous JavaScript Applications (Artifact)}},
  pages =	{5:1--5:6},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2021},
  volume =	{7},
  number =	{2},
  editor =	{Arteca, Ellen and Tip, Frank and Sch\"{a}fer, Max},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DARTS.7.2.5},
  URN =		{urn:nbn:de:0030-drops-140290},
  doi =		{10.4230/DARTS.7.2.5},
  annote =	{Keywords: asynchronous programming, refactoring, side-effect analysis, performance optimization, static analysis, JavaScript}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2021.7
Enabling Additional Parallelism in Asynchronous JavaScript Applications

Authors: Ellen Arteca, Frank Tip, and Max Schäfer

Published in: LIPIcs, Volume 194, 35th European Conference on Object-Oriented Programming (ECOOP 2021)

Abstract
JavaScript is a single-threaded programming language, so asynchronous programming is practiced out of necessity to ensure that applications remain responsive in the presence of user input or interactions with file systems and networks. However, many JavaScript applications execute in environments that do exhibit concurrency by, e.g., interacting with multiple or concurrent servers, or by using file systems managed by operating systems that support concurrent I/O. In this paper, we demonstrate that JavaScript programmers often schedule asynchronous I/O operations suboptimally, and that reordering such operations may yield significant performance benefits. Concretely, we define a static side-effect analysis that can be used to determine how asynchronous I/O operations can be refactored so that asynchronous I/O-related requests are made as early as possible, and so that the results of these requests are awaited as late as possible. While our static analysis is potentially unsound, we have not encountered any situations where it suggested reorderings that change program behavior. We evaluate the refactoring on 20 applications that perform file- or network-related I/O. For these applications, we observe average speedups ranging between 0.99% and 53.6% for the tests that execute refactored code (8.1% on average).
Cite as

Ellen Arteca, Frank Tip, and Max Schäfer. Enabling Additional Parallelism in Asynchronous JavaScript Applications. In 35th European Conference on Object-Oriented Programming (ECOOP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 194, pp. 7:1-7:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{arteca_et_al:LIPIcs.ECOOP.2021.7,
  author =	{Arteca, Ellen and Tip, Frank and Sch\"{a}fer, Max},
  title =	{{Enabling Additional Parallelism in Asynchronous JavaScript Applications}},
  booktitle =	{35th European Conference on Object-Oriented Programming (ECOOP 2021)},
  pages =	{7:1--7:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-190-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{194},
  editor =	{M{\o}ller, Anders and Sridharan, Manu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2021.7},
  URN =		{urn:nbn:de:0030-drops-140501},
  doi =		{10.4230/LIPIcs.ECOOP.2021.7},
  annote =	{Keywords: asynchronous programming, refactoring, side-effect analysis, performance optimization, static analysis, JavaScript}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.13
Approximate Pricing in Networks: How to Boost the Betweenness and Revenue of a Node

Authors: Ruben Brokkelkamp, Sven Polak, Guido Schäfer, and Yllka Velaj

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
We introduce and study two new pricing problems in networks: Suppose we are given a directed graph G = (V, E) with non-negative edge costs (c_e)_{e in E}, k commodities (s_i, t_i, w_i)_{i in [k]} and a designated node u in V. Each commodity i in [k] is represented by a source-target pair (s_i, t_i) in V x V and a demand w_i>0, specifying that w_i units of flow are sent from s_i to t_i along shortest s_i, t_i-paths (with respect to (c_e)_{e in E}). The demand of each commodity is split evenly over all shortest paths. Assume we can change the edge costs of some of the outgoing edges of u, while the costs of all other edges remain fixed; we also say that we price (or tax) the edges of u. We study the problem of pricing the edges of u with respect to the following two natural objectives: (i) max-flow: maximize the total flow passing through u, and (ii) max-revenue: maximize the total revenue (flow times tax) through u. Both variants have various applications in practice. For example, the max flow objective is equivalent to maximizing the betweenness centrality of u, which is one of the most popular measures for the influence of a node in a (social) network. We prove that (except for some special cases) both problems are NP-hard and inapproximable in general and therefore resort to approximation algorithms. We derive approximation algorithms for both variants and show that the derived approximation guarantees are best possible.
Cite as

Ruben Brokkelkamp, Sven Polak, Guido Schäfer, and Yllka Velaj. Approximate Pricing in Networks: How to Boost the Betweenness and Revenue of a Node. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{brokkelkamp_et_al:LIPIcs.ISAAC.2019.13,
  author =	{Brokkelkamp, Ruben and Polak, Sven and Sch\"{a}fer, Guido and Velaj, Yllka},
  title =	{{Approximate Pricing in Networks: How to Boost the Betweenness and Revenue of a Node}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.13},
  URN =		{urn:nbn:de:0030-drops-115091},
  doi =		{10.4230/LIPIcs.ISAAC.2019.13},
  annote =	{Keywords: Network pricing, Stackelberg network pricing, betweenness centrality, revenue maximization}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.50
The Ground-Set-Cost Budgeted Maximum Coverage Problem

Authors: Irving van Heuven van Staereling, Bart de Keijzer, and Guido Schäfer

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
We study the following natural variant of the budgeted maximum coverage problem: We are given a budget B and a hypergraph G = (V, E), where each vertex has a non-negative cost and a non-negative profit. The goal is to select a set of hyperedges T subseteq E such that the total cost of the vertices covered by T is at most B and the total profit of all covered vertices is maximized. Besides being a natural generalization of the well-studied maximum coverage problem, our motivation for investigating this problem originates from its application in the context of bid optimization in sponsored search auctions, such as Google AdWords. It is easily seen that this problem is strictly harder than budgeted max coverage, which means that the problem is (1-1/e)-inapproximable. The difference of our problem to the budgeted maximum coverage problem is that the costs are associated with the covered vertices instead of the selected hyperedges. As it turns out, this difference refutes the applicability of standard greedy approaches which are used to obtain constant factor approximation algorithms for several other variants of the maximum coverage problem. Our main results are as follows: - We obtain a (1 - 1/sqrt(e))/2-approximation algorithm for graphs. - We derive a fully polynomial-time approximation scheme (FPTAS) if the incidence graph of the hypergraph is a forest (i.e., the hypergraph is Berge-acyclic). We also extend this result to incidence graphs with a fixed-size feedback hyperedge node set. - We give a (1-epsilon)/(2d^2)-approximation algorithm for every epsilon > 0, where d is the maximum degree of a vertex in the hypergraph.
Cite as

Irving van Heuven van Staereling, Bart de Keijzer, and Guido Schäfer. The Ground-Set-Cost Budgeted Maximum Coverage Problem. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 50:1-50:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{vanheuvenvanstaereling_et_al:LIPIcs.MFCS.2016.50,
  author =	{van Heuven van Staereling, Irving and de Keijzer, Bart and Sch\"{a}fer, Guido},
  title =	{{The Ground-Set-Cost Budgeted Maximum Coverage Problem}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{50:1--50:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.50},
  URN =		{urn:nbn:de:0030-drops-65020},
  doi =		{10.4230/LIPIcs.MFCS.2016.50},
  annote =	{Keywords: maximum coverage problem, approximation algorithms, hypergraphs, submodular optimization, sponsored search}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2016.2
QL: Object-oriented Queries on Relational Data

Authors: Pavel Avgustinov, Oege de Moor, Michael Peyton Jones, and Max Schäfer

Published in: LIPIcs, Volume 56, 30th European Conference on Object-Oriented Programming (ECOOP 2016)

Abstract
This paper describes QL, a language for querying complex, potentially recursive data structures. QL compiles to Datalog and runs on a standard relational database, yet it provides familiar-looking object-oriented features such as classes and methods, reinterpreted in logical terms: classes are logical properties describing sets of values, subclassing is implication, and virtual calls are dispatched dynamically by considering the most specific classes containing the receiver. Furthermore, types in QL are prescriptive and actively influence program evaluation rather than just describing it. In combination, these features enable the development of concise queries based on reusable libraries, which are written in a purely declarative style, yet can be efficiently executed even on very large data sets. In particular, we have used QL to implement static analyses for various programming languages, which scale to millions of lines of code.
Cite as

Pavel Avgustinov, Oege de Moor, Michael Peyton Jones, and Max Schäfer. QL: Object-oriented Queries on Relational Data. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 2:1-2:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{avgustinov_et_al:LIPIcs.ECOOP.2016.2,
  author =	{Avgustinov, Pavel and de Moor, Oege and Jones, Michael Peyton and Sch\"{a}fer, Max},
  title =	{{QL: Object-oriented Queries on Relational Data}},
  booktitle =	{30th European Conference on Object-Oriented Programming (ECOOP 2016)},
  pages =	{2:1--2:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-014-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{56},
  editor =	{Krishnamurthi, Shriram and Lerner, Benjamin S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.2},
  URN =		{urn:nbn:de:0030-drops-60968},
  doi =		{10.4230/LIPIcs.ECOOP.2016.2},
  annote =	{Keywords: Object orientation, Datalog, query languages, prescriptive typing}
}
Document
DOI: 10.4230/DagRep.4.5.40
The Future of Refactoring (Dagstuhl Seminar 14211)

Authors: Danny Dig, William G. Griswold, Emerson Murphy-Hill, and Max Schäfer

Published in: Dagstuhl Reports, Volume 4, Issue 5 (2014)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 14211 on "The Future of Refactoring." Over the past decade, refactoring has become firmly established as an essential part of industrial software development. At the same time, academic interest in refactoring has grown at a fast pace, resulting in a large body of literature on many different aspects of refactoring. The aim of this seminar was to provide a forum for refactoring researchers and practitioners to discuss what has been achieved, get to know each others' work, and plan future collaboration. This report presents abstracts of the participants' talks and summaries of breakout sessions, and introduces some joint projects that were started as a result of the seminar.
Cite as

Danny Dig, William G. Griswold, Emerson Murphy-Hill, and Max Schäfer. The Future of Refactoring (Dagstuhl Seminar 14211). In Dagstuhl Reports, Volume 4, Issue 5, pp. 40-67, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{dig_et_al:DagRep.4.5.40,
  author =	{Dig, Danny and Griswold, William G. and Murphy-Hill, Emerson and Sch\"{a}fer, Max},
  title =	{{The Future of Refactoring (Dagstuhl Seminar 14211)}},
  pages =	{40--67},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{5},
  editor =	{Dig, Danny and Griswold, William G. and Murphy-Hill, Emerson and Sch\"{a}fer, Max},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.4.5.40},
  URN =		{urn:nbn:de:0030-drops-46807},
  doi =		{10.4230/DagRep.4.5.40},
  annote =	{Keywords: Refactoring}
}
  • Refine by Author
  • 4 Schäfer, Max
  • 2 Arteca, Ellen
  • 2 Schäfer, Guido
  • 2 Tip, Frank
  • 1 Avgustinov, Pavel
  • Show More...

  • Refine by Classification
  • 2 Software and its engineering → Automated static analysis
  • 2 Software and its engineering → Concurrent programming structures
  • 2 Software and its engineering → Software performance
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 2 JavaScript
  • 2 asynchronous programming
  • 2 performance optimization
  • 2 refactoring
  • 2 side-effect analysis
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2016
  • 2 2021
  • 1 2014
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact