Changeset 43a284c


Ignore:
Timestamp:
Apr 17, 2017, 4:55:53 PM (4 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, resolv-new, with_gc
Children:
eb79750
Parents:
4ae83a4b
Message:

add stack implementation

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/generic_types/generic_types.tex

    r4ae83a4b r43a284c  
    948948Though \CFA provides significant added functionality over C, these features have a low runtime penalty.
    949949In 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 source-code interfaces in Appendix~\ref{sec:BenchmarkInterfaces}).
     950This 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}).
    951951Since 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.
    952952A more illustrative benchmark is to show the costs of idiomatic use of each language's features covering common usage.
     
    964964\begin{figure}
    965965\begin{lstlisting}[xleftmargin=3\parindentlnth,aboveskip=0pt,belowskip=0pt]
    966 int main( int argc, char *argv[] ) {
     966int main( int argc, char * argv[] ) {
    967967        FILE * out = fopen( "cfa-out.txt", "w" );
    968968        int maxi = 0, vali = 42;
     
    10391039To 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.
    10401040The \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 three 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 ongoing work on the \CFA compiler's type resolver should shortly render even these type casts superfluous.
     1041The 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).
     1042These uses are similar to the @new@ expressions in \CC, though the \CFA compiler's type resolver should shortly render even these type casts superfluous.
    10431043
    10441044
     
    11431143\appendix
    11441144
    1145 \section{Benchmark Interfaces}
    1146 \label{sec:BenchmarkInterfaces}
     1145\section{Benchmark Stack Implementation}
     1146\label{sec:BenchmarkStackImplementation}
    11471147
    11481148\lstset{basicstyle=\linespread{0.9}\sf\small}
    11491149
     1150\begin{comment}
    11501151\CFA
    11511152\begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
     
    12121213void print( FILE * out, const char * fmt, ... );
    12131214\end{lstlisting}
     1215\end{comment}
     1216
     1217Throughout, @/***/@ designates a counted redundant type annotation.
     1218
     1219\medskip\noindent
     1220\CFA
     1221\begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
     1222forall(otype T) struct stack_node {
     1223        T value;
     1224        stack_node(T)* next;
     1225};
     1226forall(otype T) void ?{}(stack(T)* s) { (&s->head){ 0 }; }
     1227forall(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}
     1236forall(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}
     1242forall(otype T) void ^?{}(stack(T)* s) { clear(s); }
     1243forall(otype T) _Bool empty(const stack(T)* s) { return s->head == 0; }
     1244forall(otype T) void push(stack(T)* s, T value) {
     1245        s->head = ((stack_node(T)*)malloc()){ value, s->head }; /***/
     1246}
     1247forall(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}
     1255forall(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]
     1268template<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
     1321C
     1322\begin{lstlisting}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
     1323struct stack_node {
     1324        void* value;
     1325        struct stack_node* next;
     1326};
     1327struct stack new_stack() { return (struct stack){ NULL }; /***/ }
     1328void 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; }
     1338void 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}
     1343void* 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}
     1350void 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]
     1364stack::node::node( const object& v, node* n ) : value( v.new_copy() ), next( n ) {}
     1365void 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}
     1373stack::stack() : head(nullptr) {}
     1374stack::stack(const stack& o) { copy(o); }
     1375stack::stack(stack&& o) : head(o.head) { o.head = nullptr; }
     1376stack::~stack() { clear(); }
     1377stack& stack::operator= (const stack& o) {
     1378        if ( this == &o ) return *this;
     1379        clear();
     1380        copy(o);
     1381        return *this;
     1382}
     1383stack& stack::operator= (stack&& o) {
     1384        if ( this == &o ) return *this;
     1385        head = o.head;
     1386        o.head = nullptr;
     1387        return *this;
     1388}
     1389bool stack::empty() const { return head == nullptr; }
     1390void stack::push(const object& value) { head = new node{ value, head }; /***/ }
     1391ptr<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}
     1398void 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}
    12141407
    12151408
    12161409\begin{comment}
    1217 Throughout, @/***/@ designates a counted redundant type annotation.
    12181410
    12191411\subsubsection{bench.h}
Note: See TracChangeset for help on using the changeset viewer.