maybe.tex
5.22 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
\section{\texttt{\large maybe} Statement Semantics}
\label{sec-maybe}
To begin we provide an overview of the \texttt{maybe} statements semantics,
describing how it structures uncertainty in variable values and runtime
execution. We refer to each of the values or code paths a \texttt{maybe}
statement can choose from as an \textit{alternative}.
\begin{figure}[t]
\begin{minted}[fontsize=\footnotesize]{java}
// Setting variables
int retryInterval = maybe 1-16;
String policy = maybe "auto", "quality", "perf";
// Function alternatives
@maybe
int myFunction(int a) { /* First alternative */ }
@maybe
int myFunction(int a) { /* Second alternative */ }
// Inlining evaluation code
maybe {
ret = fastPowerHungryAlgorithm(input);
} or {
ret = slowPowerEfficientAlgorithm(input);
} analyze {
return { "repeat": false,
"score" : nanoTime() + powerDrain() }
}
\end{minted}
\vspace*{-0.2in}
\caption{\textbf{More \texttt{maybe} Statements}}
\label{fig-maybeexamples}
\vspace*{-0.2in}
\end{figure}
\subsection{Setting Variables}
Variables can be used to represent uncertainty. Examples include an integer
storing how often a timer should trigger communication with a remote server,
or a string containing the name of a policy used to coordinate multiple code
blocks through the app. Figure~\ref{fig-maybeexamples} shows examples of an
integer that can take on values between 1 and 16, and a string that be set to
either ``auto'', ``quality'', or ``perf''.
\subsection{Controlling Code Flow}
Code flow can also represent uncertainty, and we expect this to be the most
common use of \texttt{maybe} statements. Examples include evaluating
multiple algorithms to compute the same result or code paths that represent
different energy-performance or energy-quality tradeoffs.
Figure~\ref{fig-example-maybe} shows the \texttt{maybe} statement in its
simplest form controlling execution of multiple code blocks. If multiple
alternatives are specified, the system chooses one to execute; if only one
alternative is specified, the system chooses whether or not to execute it.
Single-alternative \texttt{maybe} statements can encapsulate
or reorganize logic that does not affect correctness, but may (or
may not) improve performance if executed.
Figure~\ref{fig-maybeexamples} shows several extensions of the \texttt{maybe}
statement providing syntactic sugar. \texttt{maybe} function annotations
allow uncertainty to be expressed at the function level, with the
alternatives consisting of multiple function definitions with identical
signatures. Finally, \texttt{maybe} blocks that require special performance
evaluation logic can include that in the form of a \texttt{better} statement
following the main \texttt{maybe} block, as shown in the final example.
\texttt{better} blocks provide application-specific logic that analyze the
selected execution path. The \texttt{better} block must return a single JSON
object that includes two components: A score, with smaller being interpreted
as better; and a boolean indicating whether the system should use the same
branch next time, or if it is free to try another. Note that hints and
dedicated evaluation logic can also be applied to variable and function-level
\texttt{maybe} statements through annotations. We will return to post-mortem
evaluation in Section~\ref{sec-certainty}.
\subsection{Discussion}
We have yet to determine how well programmers will be able to use the
\texttt{maybe} statement. Structurally \texttt{maybe} statements are similar
to the common \texttt{if-else} construct in that at the bottom of the
statement the programmer may not be sure which block was executed. However,
while with \texttt{if-else} blocks it can be determined which block was
executed by examining the branch conditions, \texttt{maybe} statements
require developers record which alternative was executed if downstream code
depends on the decision. To coordinate the adaptation of multiple code paths
a single \texttt{maybe} variable can be used to control multiple
\texttt{if-else} statements.
While \texttt{maybe} is a powerful programming tool, it is important that it
be used sparingly. In the case where dependencies exist between the
alternatives expressed by separate \texttt{maybe} statements, each
\texttt{maybe} may expand the overall configuration space exponentially which
makes the resulting process of determining the best alternative much more
complicated. Compile-time analysis may be required to ensure that downstream
optimization remains feasible.
The most important guideline for when \textit{not} to use \texttt{maybe}
usage is when a decision is not app-specific, and should instead be
refactored into a library or service. As an example, \texttt{maybe} should
not be used to decide which networking interface to use to send a packet.
To the degree that
one app shares the same objectives as others---say, to minimize latency---a
service should be performing adaptation on behalf of all apps using the
merged network interfaces, possibly through the use of its own internal
\texttt{maybe} statements.
Finally, note that structured uncertainty is not randomness. The
\texttt{maybe} statement indicates that during any given execution one
alternative may be better than the others---even if the developer or system
are not sure which alternative to use.