Changeset 231f01c for doc

Timestamp:

Mar 24, 2017, 4:31:07 PM (8 years ago)

Author:

Aaron Moss <a3moss@…>

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:

58d246a

Parents:

fe1b6a4

Message:

Further updates to paper

Location:

doc/generic_types

Files:

• generic_types.bib (modified) (1 diff)
• generic_types.tex (modified) (6 diffs)

doc/generic_types/generic_types.bib

@@ -8 +8 @@
     address     = {Waterloo, Ontario, Canada, N2L 3G1},
     note        = {\href{http://plg.uwaterloo.ca/theses/BilsonThesis.pdf}{http://\-plg.uwaterloo.ca/\-theses/\-BilsonThesis.pdf}},
+}
+
+@techreport{C11,
+    type = {International Standard},
+    keywords    = {ISO/IEC C 11},
+    contributer = {pabuhr@plg},
+    key         = {{ISO/IEC} 9889-2011},
+    title       = {American National Standard Information technology -- Programming Languages -- {C}},
+    institution = {International Standard Organization},
+    address     = {http://www.iso.org},
+    year        = 2012,
 }
 

doc/generic_types/generic_types.tex

@@ -20 +20 @@
         morekeywords={_Alignas,_Alignof,__alignof,__alignof__,asm,__asm,__asm__,_At,_Atomic,__attribute,__attribute__,auto,
                 _Bool,catch,catchResume,choose,_Complex,__complex,__complex__,__const,__const__,disable,dtype,enable,__extension__,
-                fallthrough,fallthru,finally,forall,ftype,_Generic,_Imaginary,inline,__label__,lvalue,_Noreturn,one_t,otype,restrict,sized,_Static_assert,
+                fallthrough,fallthru,finally,forall,ftype,_Generic,_Imaginary,inline,__label__,lvalue,_Noreturn,one_t,otype,restrict,size_t,sized,_Static_assert,
                 _Thread_local,throw,throwResume,trait,try,typeof,__typeof,__typeof__,zero_t},
 }%
@@ -280 +280 @@
 
 forall(otype T)
-T value( pair(const char*, T) *p ) { return p->second; }
+T value( pair(const char*, T) p ) { return p.second; }
 
 forall(dtype F, otype T)
@@ -286 +286 @@
 
 pair(const char*, int) p = { "magic", 42 };
-int magic = value( &p );
+int magic = value( p );
 
 pair(void*, int*) q = { 0, &p.second };
@@ -315 +315 @@
 Though \CFA{} implements concrete generic types efficiently, it also has a fully-general system for computing with dynamic generic types. As mentioned in Section~\ref{sec:poly-fns}, @otype@ function parameters (in fact all @sized@ polymorphic parameters) come with implicit size and alignment parameters provided by the caller. Dynamic generic structs also come with an \emph{offset array} which contains the offsets of each member of the struct\footnote{Dynamic generic unions need no such offset array, as all members are at offset 0.}. Access to members\footnote{The \lstinline@offsetof@ macro is implmented similarly.} of a dynamic generic struct is provided by adding the corresponding member of the offset array to the struct pointer at runtime, essentially moving a compile-time offset calculation to runtime where neccessary.
 
-\TODO{} Discuss caller-provided versus callee-provided offset arrays, layout functions.
+These offset arrays are staticly generated where possible. If a dynamic generic type is declared to be passed or returned by value from a polymorphic function, the compiler can safely assume that the generic type is complete (that is, has a known layout) at any call-site, and the offset array is passed from the caller; if the generic type is concrete at the call site this offset array can even be statically generated using the C @offsetof@ macro. As an example, @p.second@ in the @value@ function above is implemented as @*(p + _offsetof_pair[1])@, where @p@ is a @void*@, and @_offsetof_pair@ is the offset array passed in to @value@ for @pair(const char*, T)@. The offset array @_offsetof_pair@ is generated at the call site as @size_t _offsetof_pair[] = { offsetof(_pair_conc1, first), offsetof(_pair_conc1, second) };@.
+
+In some cases the offset arrays cannot be staticly generated. For instance, modularity is generally produced in C by including an opaque forward-declaration of a struct and associated accessor and mutator routines in a header file, with the actual implementations in a separately-compiled \texttt{.c} file. \CFA{} supports this pattern for generic types, and in tis instance the caller does not know the actual layout or size of the dynamic generic type, and only holds it by pointer. The \CFA{} compiler automatically generates \emph{layout functions} for cases where the size, alignment, and offset array of a generic struct cannot be passed in to a function from that function's caller. These layout functions take as arguments pointers to size and alignment variables and a caller-allocated array of member offsets, as well as the size and alignment of all @sized@ parameters to the generic struct (un-@sized@ parameters are forbidden from the language from being used in a context which affects layout). Results of these layout functions are cached so that they are only computed once per type per function.%, as in the example below for @pair@.
+% \begin{lstlisting}
+% static inline void _layoutof_pair(size_t* _szeof_pair, size_t* _alignof_pair, size_t* _offsetof_pair, 
+%               size_t _szeof_R, size_t _alignof_R, size_t _szeof_S, size_t _alignof_S) {
+%     *_szeof_pair = 0; // default values
+%     *_alignof_pair = 1;
+
+%       // add offset, size, and alignment of first field
+%     _offsetof_pair[0] = *_szeof_pair;
+%     *_szeof_pair += _szeof_R;
+%     if ( *_alignof_pair < _alignof_R ) *_alignof_pair = _alignof_R;
+        
+%       // padding, offset, size, and alignment of second field
+%     if ( *_szeof_pair & (_alignof_S - 1) )
+%               *_szeof_pair += (_alignof_S - ( *_szeof_pair & (_alignof_S - 1) ) );
+%     _offsetof_pair[1] = *_szeof_pair;
+%     *_szeof_pair += _szeof_S;
+%     if ( *_alignof_pair < _alignof_S ) *_alignof_pair = _alignof_S;
+
+%       // pad to struct alignment
+%     if ( *_szeof_pair & (*_alignof_pair - 1) )
+%               *_szeof_pair += ( *_alignof_pair - ( *_szeof_pair & (*_alignof_pair - 1) ) );
+% }
+% \end{lstlisting}
+
+Layout functions also allow generic types to be used in a function definition without reflecting them in the function signature. For instance, a function that strips duplicate values from an unsorted @vector(T)@ would likely have a pointer to the vector as its only explicit parameter, but internally may use some sort of @set(T)@ to test for duplicate values. This function could acquire the layout for @set(T)@ by calling its layout function with the layout of @T@ implicitly passed into the function.
 
 Whether a type is concrete, dtype-static, or dynamic is decided based solely on the type parameters and @forall@ clause on the struct declaration. This allows opaque forward declarations of generic types like @forall(otype T) struct Box;@ -- like in C, all uses of @Box(T)@ can be in a separately compiled translation unit, and callers from other translation units will know the proper calling conventions to use. If the definition of a struct type was included in the determination of dynamic or concrete, some further types may be recognized as dtype-static (\eg, @forall(otype T) struct unique_ptr { T* p };@ does not depend on @T@ for its layout, but the existence of an @otype@ parameter means that it \emph{could}.), but preserving separate compilation (and the associated C compatibility) in this way is judged to be an appropriate trade-off.
@@ -353 +380 @@
 \section{Tuples}
 
-\TODO{} Integrate Rob's work
+The @pair(R, S)@ generic type used as an example in the previous section can be considered a special case of a more general \emph{tuple} data structure. The authors have implemented tuples in \CFA{} as an extension to C. \TODO{}
 
 \TODO{} Check if we actually can use ttype parameters on generic types (if they set the complete flag, it should work, or nearly so).
@@ -365 +392 @@
 \section{Conclusion \& Future Work}
 
-\TODO{} Among future work, talk about ideas for selectively template-expanding code (on decls for specific types, or on calls for accessible decls).
+In conclusion, the authors' design for generic types and tuples imposes minimal runtime overhead while still supporting a full range of C features, including separately-compiled modules. There is ongoing work on a wide range of \CFA{} feature extensions, including reference types, exceptions, and concurent programming primitives. In addition to this work, there are some interesting future directions the polymorphism design could take. Notably, \CC{} template functions trade compile time and code bloat for optimal runtime of individual instantiations of polymorphic functions. \CFA{} polymorphic functions, by contrast, use an approach which is essentially dynamic virtual dispatch. The runtime overhead of this approach is low, but not as low as \CC{} template functions, and it may be beneficial to provide a mechanism for particularly performance-sensitive code to close this gap. Further research is needed, but two promising approaches are to allow an annotation on polymorphic function call sites that tells the compiler to create a template-specialization of the function (provided the code is visible in the current translation unit) or placing an annotation on polymorphic function definitions that instantiates a version of the polymorphic function specialized to some set of types. These approaches are not mutually exclusive, and would allow these performance optimizations to be applied only where most useful to increase performance, without suffering the code bloat or loss of generality of a template expansion approach where it is unneccessary.
 
 \bibliographystyle{ACM-Reference-Format}