maybe.tex
6.01 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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
\section{\texttt{\large maybe} Statement Semantics}
\label{sec-maybe}
\sloppypar{To begin, we provide a brief overview of the semantics of the
\texttt{maybe} statement, describing how it can express structured
uncertainty in variable values and runtime execution. We refer to each of the
values a \texttt{maybe} variable can take and each of the a paths a
\texttt{maybe} code block can execute 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);
choice = FAST;
} or {
ret = slowPowerEfficientAlgorithm(input);
choice = SLOW;
} analyze {
return { "repeat": false,
"score" : nanoTime() + powerDrain() }
}
// Cleanup may depend on which algorithm was used
if(choice == FAST){ cleanUpAfterFastAlg(ret); }
else { cleanUpAfterSlowAlg(ret); }
\end{minted}
\vspace*{-0.2in}
\caption{\textbf{More Examples of \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.
% Note that at present the \texttt{maybe}
% statement controlling code blocks described below does not include features
% required to coordinate multiple code blocks, and so if this functionality is
% required, multiple \texttt{if-else} statements branching on a
%\texttt{maybe}-derived variable can be used.
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''.
A s
\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 performs a post-mortem on 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{Programming With \texttt{\large maybe}}
We have yet to determine how well programmers will be able to use the new
\texttt{maybe} construct. At some level, \texttt{maybe} statements are
similar to the common \texttt{if-else} construct. At the bottom of the
statement, the programmer may not be sure which block was executed. Of
course, with \texttt{if-else} blocks it can be determined which block was
executed by examining the branch conditions. When working with the
\texttt{maybe} statement, the developer must set a variable inside each
\texttt{maybe} block if downstream code depends on which alternative was
chosen, as in Figure~\ref{fig-maybeexamples}. Alternatively, programmers may
use a \texttt{maybe} variable to select a policy, and employ the traditional
\texttt{if-else} construct to direct control flow based on the \texttt{maybe}
variable.
\subsection{When Not To Use \texttt{\large maybe}}
% 10/13 by OK:
% We don't discuss dependencies between maybe statements anywhere else, so I'm
% killing the ref here. It's still true that we're creating an exponential
% search space of possibilities; so the same text is getting re-purposed for
% that.
While \texttt{maybe} is a powerful programming tool, it is important that it
be used sparingly. In the case where no dependencies exist between the
alternatives expressed by separate \texttt{maybe} statements, each
\texttt{maybe} expands the overall configuration space exponentially and
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
made by 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.