Changeset 9861ef2 for doc/theses/fangren_yu_MMath/performance.tex

Timestamp:

Dec 6, 2024, 10:02:01 AM (12 days ago)

Author:

Fangren Yu <f37yu@…>

Branches:

master

Children:

b4c6e10

Parents:

5b66938

Message:

add description of closed trait types

File:

• doc/theses/fangren_yu_MMath/performance.tex (modified) (1 diff)

doc/theses/fangren_yu_MMath/performance.tex

@@ -5 +5 @@
 \section{Closed trait types}
 
-\CFA as it currently is does not have any closed types, as new functions can be added at any time. It is also possible to locally declare a function\footnote{Local functions are not a standard feature in C but supported by mainstream C compilers such as gcc, and allowed in \CFA too.} or a function pointer to make a type satisfy a certain trait temporarily and be used as such in this limited scope. However, the lack of closed types in such a "duck typing" scheme proposes two problems. For library implementors, it is common to not want the defined set of operations to be overwritten and cause the behavior of polymorphic invocations to change. For the compiler, it means caching and reusing the result of resolution is not reliable as newly introduced declarations can participate in assertion resolution, making a previously invalid expression valid, or the other way around by introducing ambiguity in assertions. Sometimes those interfaces are fairly complicated, for example the I/O library traits \textbf{istream} and \textbf{ostream} each has over 20 operations. Without the ability to store and reuse assertion resolution results, each time the compiler encounters an I/O operation in the source code (mainly the pipe operator \textbf{?|?} used to represent stream operations in \CFA) it has to resolve the same set of assertions again, causing a lot of repetitive work. Previous experiments have shown that the I/O assertions often account for over half of the number of assertions resolved in a \CFA translation unit. Introducing a way to eliminate the need of doing such repetitive assertion resolutions that are very unlikely to change by new overloads can therefore provide significant improvement to the performance of the compiler.
+\CFA as it currently is does not have any closed types, as new functions can be added at any time. It is also possible to locally declare a function,\footnote{Local functions are not a standard feature in C but supported by mainstream C compilers such as gcc, and allowed in \CFA too.} or a function pointer variable to make a type satisfy a certain trait temporarily and be used as such in this limited scope. However, the lack of closed types in such a "duck typing" scheme proposes two problems. For library implementors, it is common to not want the defined set of operations to be overwritten and cause the behavior of polymorphic invocations to change. For the compiler, it means caching and reusing the result of resolution is not reliable as newly introduced declarations can participate in assertion resolution, making a previously invalid expression valid, or the other way around by introducing ambiguity in assertions. Sometimes those interfaces are fairly complicated, for example the I/O library traits \textbf{istream} and \textbf{ostream} each has over 20 operations. Without the ability to store and reuse assertion resolution results, each time the compiler encounters an I/O operation in the source code (mainly the pipe operator \textbf{?|?} used to represent stream operations in \CFA) it has to resolve the same set of assertions again, causing a lot of repetitive work. Previous experiments have shown that the I/O assertions often account for over half of the number of assertions resolved in a \CFA translation unit. Introducing a way to eliminate the need of doing such repetitive assertion resolutions that are very unlikely to change by new overloads can therefore provide significant improvement to the performance of the compiler.
+
+The output stream trait in \CFA looks like this:
+
+\begin{cfa}
+forall( ostype & )
+trait basic_ostream {
+        // private
+        bool sepPrt$\$$( ostype & );                                                    // get separator state (on/off)
+    
+        void sepReset$\$$( ostype & );                                                  // set separator state to default state
+        void sepReset$\$$( ostype &, bool );                                    // set separator and default state
+        const char * sepGetCur$\$$( ostype & );                         // get current separator string
+        void sepSetCur$\$$( ostype &, const char [] );                  // set current separator string
+        bool getNL$\$$( ostype & );                                                     // get newline
+        bool setNL$\$$( ostype &, bool );                                               // set newline
+        bool getANL$\$$( ostype & );                                                    // get auto newline (on/off)
+        bool setANL$\$$( ostype &, bool );                                              // set auto newline (on/off), and return previous state
+        bool getPrt$\$$( ostype & );                                                    // get fmt called in output cascade
+        bool setPrt$\$$( ostype &, bool );                                              // set fmt called in output cascade
+        // public
+        void nlOn( ostype & );                                                          // turn auto-newline state on
+        void nlOff( ostype & );                                                         // turn auto-newline state off
+
+        void sep( ostype & );                                                           // turn separator state on
+        void nosep( ostype & );                                                         // turn separator state off
+        bool sepOn( ostype & );                                                         // set default state to on, and return previous state
+        bool sepOff( ostype & );                                                        // set default state to off, and return previous state
+        const char * sepGet( ostype & );                                        // get separator string
+        void sepSet( ostype &, const char [] );                         // set separator to string (15 character maximum)
+        const char * sepGetTuple( ostype & );                           // get tuple separator string
+        void sepSetTuple( ostype &, const char [] );            // set tuple separator to string (15 character maximum)
+
+        void ends( ostype & );                                                          // end of output statement
+        int fmt( ostype &, const char format[], ... ) __attribute__(( format(printf, 2, 3) ));
+}; // basic_ostream
+
+\end{cfa}
+
+and the overloaded output operator is declared as
+
+\begin{cfa}
+forall( ostype & | basic_ostream( ostype ) ) ostype & ?|?( ostype &, int ); // also defined for all other basic types
+\end{cfa}
+
+The \CFA polymorphic calling convention makes the output operator take all the trait functions above as implicit arguments, and they are repeatedly resolved every time an output operator is called. This creates both compile-time and run-time overheads. \CFA compilation takes the most amount of time in resolving assertions, and it is not uncommon to see in the current codebase and test suite that the majority of time spent in compiling a program is due to a series of I/O statements, while resolving those assertions for I/O operators could have been a once and done job. Repeatedly pushing tens of arguments onto the stack to call these operators at run-time can also have some impact on performance, although in the I/O case it is not as significant, since these operations involve system calls which are already slow.
+
+An addition of closed trait type will make a \CFA trait behave similarly to a Haskell type class and require an explicit instance declaration as well. The syntax for closed trait is not settled yet, but it may look something like the following:
+
+\begin{cfa}
+    forall(ostype &)
+    closed trait basic_ostream{
+        // all the above declarations
+    };
+
+    struct ofstream {
+        // ... 
+    };
+
+    // implementation of trait functions for ofstream
+
+    __cfa_trait_instance(ofstream, basic_ostream);
+\end{cfa}
+
+At the point of instance declaration, all the required trait functions must be declared in scope, and they are inferred and specialized in the usual way. The list of inferred and specialized functions will then be saved into an array of function pointers, and polymorphic functions using the closed trait type can simply take the instance pointer, instead of a list of implicit parameters.
+
+\begin{cfa}
+    // original declaration
+    forall( ostype & | basic_ostream( ostype ) ) ostype & ?|?( ostype & os, int i); 
+
+    // translated code with closed trait
+    void* ?|?(void* os, int i, void* _instance_basic_ostream); 
+    // polymorphic pointer and reference types are erased
+
+    // call site
+    sout | 42;
+    
+    // generated code
+    ?|?(sout, 42, __cfa_instance_ofstream__basic_ostream /* generated by __cfa_trait_instance decl */);
+\end{cfa}
+
+Introducing closed trait types also comes with the additional benefit of the ability to achieve better encapsulation. In the above @basic_ostream@ example, the functions ending with dollar sign \$ are meant to be private (internal to the library) and the client code should not be able to see or call those functions directly. This is impossible with the current trait and assertion system, because the satisfying declarations must be visible at call site for the polymorphic call to resolve. With closed traits and instance types, it will be possible to forward declare a closed trait (which would not even make sense otherwise) and the instance pointer of a type implementing the trait without exposing any details to the client, since all the information necessary to call the trait functions are now captured in a single pointer to a table of functions built at compile time, and the type of that pointer is made opaque to the client.
+
+
+
 
 \section{Associated Types}