- Timestamp:
- Apr 17, 2017, 4:55:53 PM (7 years ago)
- Branches:
- ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
- Children:
- eb79750
- Parents:
- 4ae83a4b
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/generic_types/generic_types.tex
r4ae83a4b r43a284c 948 948 Though \CFA provides significant added functionality over C, these features have a low runtime penalty. 949 949 In fact, \CFA's features for generic programming can enable faster runtime execution than idiomatic @void *@-based C code. 950 This claim is demonstrated through a set of generic-code-based micro-benchmarks in C, \CFA, and \CC (see s ource-code interfaces in Appendix~\ref{sec:BenchmarkInterfaces}).950 This claim is demonstrated through a set of generic-code-based micro-benchmarks in C, \CFA, and \CC (see stack implementations in Appendix~\ref{sec:BenchmarkStackImplementation}). 951 951 Since all these languages share a subset comprising standard C, maximal-performance benchmarks would show little runtime variance, other than in length and clarity of source code. 952 952 A more illustrative benchmark is to show the costs of idiomatic use of each language's features covering common usage. … … 964 964 \begin{figure} 965 965 \begin{lstlisting}[xleftmargin=3\parindentlnth,aboveskip=0pt,belowskip=0pt] 966 int main( int argc, char * argv[] ) {966 int main( int argc, char * argv[] ) { 967 967 FILE * out = fopen( "cfa-out.txt", "w" ); 968 968 int maxi = 0, vali = 42; … … 1039 1039 To quantify this, the ``redundant type annotations'' line in Table~\ref{tab:eval} counts the number of lines on which the type of a known variable is re-specified, either as a format specifier, explicit downcast, type-specific function, or by name in a @sizeof@, struct literal, or @new@ expression. 1040 1040 The \CC benchmark uses two redundant type annotations to create a new stack nodes, while the C and \CCV benchmarks have several such annotations spread throughout their code. 1041 The t hreeinstances in which the \CFA benchmark still uses redundant type specifiers are to cast the result of a polymorphic @malloc@ call (the @sizeof@ argument is inferred by the compiler).1042 These uses are similar to the @new@ expressions in \CC, though ongoing work onthe \CFA compiler's type resolver should shortly render even these type casts superfluous.1041 The two instances in which the \CFA benchmark still uses redundant type specifiers are to cast the result of a polymorphic @malloc@ call (the @sizeof@ argument is inferred by the compiler). 1042 These uses are similar to the @new@ expressions in \CC, though the \CFA compiler's type resolver should shortly render even these type casts superfluous. 1043 1043 1044 1044 … … 1143 1143 \appendix 1144 1144 1145 \section{Benchmark Interfaces}1146 \label{sec:Benchmark Interfaces}1145 \section{Benchmark Stack Implementation} 1146 \label{sec:BenchmarkStackImplementation} 1147 1147 1148 1148 \lstset{basicstyle=\linespread{0.9}\sf\small} 1149 1149 1150 \begin{comment} 1150 1151 \CFA 1151 1152 \begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt] … … 1212 1213 void print( FILE * out, const char * fmt, ... ); 1213 1214 \end{lstlisting} 1215 \end{comment} 1216 1217 Throughout, @/***/@ designates a counted redundant type annotation. 1218 1219 \medskip\noindent 1220 \CFA 1221 \begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt] 1222 forall(otype T) struct stack_node { 1223 T value; 1224 stack_node(T)* next; 1225 }; 1226 forall(otype T) void ?{}(stack(T)* s) { (&s->head){ 0 }; } 1227 forall(otype T) void ?{}(stack(T)* s, stack(T) t) { 1228 stack_node(T)** crnt = &s->head; 1229 for ( stack_node(T)* next = t.head; next; next = next->next ) { 1230 *crnt = ((stack_node(T)*)malloc()){ next->value }; /***/ 1231 stack_node(T)* acrnt = *crnt; 1232 crnt = &acrnt->next; 1233 } 1234 *crnt = 0; 1235 } 1236 forall(otype T) stack(T) ?=?(stack(T)* s, stack(T) t) { 1237 if ( s->head == t.head ) return *s; 1238 clear(s); 1239 s{ t }; 1240 return *s; 1241 } 1242 forall(otype T) void ^?{}(stack(T)* s) { clear(s); } 1243 forall(otype T) _Bool empty(const stack(T)* s) { return s->head == 0; } 1244 forall(otype T) void push(stack(T)* s, T value) { 1245 s->head = ((stack_node(T)*)malloc()){ value, s->head }; /***/ 1246 } 1247 forall(otype T) T pop(stack(T)* s) { 1248 stack_node(T)* n = s->head; 1249 s->head = n->next; 1250 T x = n->value; 1251 ^n{}; 1252 free(n); 1253 return x; 1254 } 1255 forall(otype T) void clear(stack(T)* s) { 1256 for ( stack_node(T)* next = s->head; next; ) { 1257 stack_node(T)* crnt = next; 1258 next = crnt->next; 1259 delete(crnt); 1260 } 1261 s->head = 0; 1262 } 1263 \end{lstlisting} 1264 1265 \medskip\noindent 1266 \CC 1267 \begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt] 1268 template<typename T> class stack { 1269 struct node { 1270 T value; 1271 node* next; 1272 node( const T& v, node* n = nullptr ) : value(v), next(n) {} 1273 }; 1274 node* head; 1275 void copy(const stack<T>& o) { 1276 node** crnt = &head; 1277 for ( node* next = o.head;; next; next = next->next ) { 1278 *crnt = new node{ next->value }; /***/ 1279 crnt = &(*crnt)->next; 1280 } 1281 *crnt = nullptr; 1282 } 1283 public: 1284 stack() : head(nullptr) {} 1285 stack(const stack<T>& o) { copy(o); } 1286 stack(stack<T>&& o) : head(o.head) { o.head = nullptr; } 1287 ~stack() { clear(); } 1288 stack& operator= (const stack<T>& o) { 1289 if ( this == &o ) return *this; 1290 clear(); 1291 copy(o); 1292 return *this; 1293 } 1294 stack& operator= (stack<T>&& o) { 1295 if ( this == &o ) return *this; 1296 head = o.head; 1297 o.head = nullptr; 1298 return *this; 1299 } 1300 bool empty() const { return head == nullptr; } 1301 void push(const T& value) { head = new node{ value, head }; /***/ } 1302 T pop() { 1303 node* n = head; 1304 head = n->next; 1305 T x = std::move(n->value); 1306 delete n; 1307 return x; 1308 } 1309 void clear() { 1310 for ( node* next = head; next; ) { 1311 node* crnt = next; 1312 next = crnt->next; 1313 delete crnt; 1314 } 1315 head = nullptr; 1316 } 1317 }; 1318 \end{lstlisting} 1319 1320 \medskip\noindent 1321 C 1322 \begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt] 1323 struct stack_node { 1324 void* value; 1325 struct stack_node* next; 1326 }; 1327 struct stack new_stack() { return (struct stack){ NULL }; /***/ } 1328 void copy_stack(struct stack* s, const struct stack* t, void* (*copy)(const void*)) { 1329 struct stack_node** crnt = &s->head; 1330 for ( struct stack_node* next = t->head; next; next = next->next ) { 1331 *crnt = malloc(sizeof(struct stack_node)); /***/ 1332 **crnt = (struct stack_node){ copy(next->value) }; /***/ 1333 crnt = &(*crnt)->next; 1334 } 1335 *crnt = 0; 1336 } 1337 _Bool stack_empty(const struct stack* s) { return s->head == NULL; } 1338 void push_stack(struct stack* s, void* value) { 1339 struct stack_node* n = malloc(sizeof(struct stack_node)); /***/ 1340 *n = (struct stack_node){ value, s->head }; /***/ 1341 s->head = n; 1342 } 1343 void* pop_stack(struct stack* s) { 1344 struct stack_node* n = s->head; 1345 s->head = n->next; 1346 void* x = n->value; 1347 free(n); 1348 return x; 1349 } 1350 void clear_stack(struct stack* s, void (*free_el)(void*)) { 1351 for ( struct stack_node* next = s->head; next; ) { 1352 struct stack_node* crnt = next; 1353 next = crnt->next; 1354 free_el(crnt->value); 1355 free(crnt); 1356 } 1357 s->head = NULL; 1358 } 1359 \end{lstlisting} 1360 1361 \medskip\noindent 1362 \CCV 1363 \begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt] 1364 stack::node::node( const object& v, node* n ) : value( v.new_copy() ), next( n ) {} 1365 void stack::copy(const stack& o) { 1366 node** crnt = &head; 1367 for ( node* next = o.head; next; next = next->next ) { 1368 *crnt = new node{ *next->value }; 1369 crnt = &(*crnt)->next; 1370 } 1371 *crnt = nullptr; 1372 } 1373 stack::stack() : head(nullptr) {} 1374 stack::stack(const stack& o) { copy(o); } 1375 stack::stack(stack&& o) : head(o.head) { o.head = nullptr; } 1376 stack::~stack() { clear(); } 1377 stack& stack::operator= (const stack& o) { 1378 if ( this == &o ) return *this; 1379 clear(); 1380 copy(o); 1381 return *this; 1382 } 1383 stack& stack::operator= (stack&& o) { 1384 if ( this == &o ) return *this; 1385 head = o.head; 1386 o.head = nullptr; 1387 return *this; 1388 } 1389 bool stack::empty() const { return head == nullptr; } 1390 void stack::push(const object& value) { head = new node{ value, head }; /***/ } 1391 ptr<object> stack::pop() { 1392 node* n = head; 1393 head = n->next; 1394 ptr<object> x = std::move(n->value); 1395 delete n; 1396 return x; 1397 } 1398 void stack::clear() { 1399 while ( node* next = head; next; ) { 1400 node* crnt = next; 1401 next = crnt->next; 1402 delete crnt; 1403 } 1404 head = nullptr; 1405 } 1406 \end{lstlisting} 1214 1407 1215 1408 1216 1409 \begin{comment} 1217 Throughout, @/***/@ designates a counted redundant type annotation.1218 1410 1219 1411 \subsubsection{bench.h}
Note: See TracChangeset
for help on using the changeset viewer.