Index: doc/theses/aaron_moss_PhD/phd/experiments.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/experiments.tex (revision 0e6a0bebb41b45cf615f928ea49e1295870c1fc7) +++ doc/theses/aaron_moss_PhD/phd/experiments.tex (revision 8d752592bd81177ff1ccdf30301e7555da9fcc43) @@ -9,8 +9,8 @@ The first is small, hand-written tests designed to test the expressive power and correctness of the prototype. These tests are valuable for regression testing, but not time-consuming enough to be useful performance tests. -The second sort of problem instances are procedurally generated according to a set of parameters (\eg{} distributions of polymorphic versus monomorphic functions, number of function arguments, number of types, \etc{}); the procedural problem generator can be used to explore the behaviour of an algorithm with respect to certain sorts of problem instances by varying the input parameters. +The second sort of problem instances are procedurally generated according to a set of parameters (distributions of polymorphic versus monomorphic functions, number of function arguments, number of types, \etc{}); the procedural problem generator can be used to explore the behaviour of an algorithm with respect to certain sorts of problem instances by varying the input parameters. I have implemented a flagged \CFACC{} pass which outputs information which can be used to initialize the procedural generator's parameters to realistic values. The final sort of problem instances are derived from actual \CFA{} code. -The prototype has a rich enough representation of \CFA{} that actual instances of expression resolution can be expressed with good fidelity, and I have implemented a compiler pass for \CFACC{} which can generate instances from actual code. +The prototype has a rich enough representation of \CFA{} that actual instances of expression resolution can be expressed with good fidelity, and I have implemented a compiler pass for \CFACC{} which can generate instances from \CFA{} code. Since at this juncture all development in \CFA{} is done by our research team, I have tested the prototype system on all \CFA{} code currently extant, primarily the standard library and compiler test suite. @@ -48,7 +48,23 @@ \section{Resolver Prototype Design} -% talk about GC here, associated visitor/AST design +As discussed above, the resolver prototype works over a simplified version of the \CFA{} type system, for speed of development. +The build system for the resolver prototype uses a number of conditional compilation flags to switch between algorithm variants while retaining maximal shared code. +A different executable name is also generated for each algorithmic variant so that distinct variants can be more easily tested against each other. -% talk about shared type representations +The primary architectural difference between the resolver prototype and \CFACC{} is that the prototype system uses a simple mark-and-sweep garbage collector for memory management, while \CFACC{} takes a manual memory management approach. +This decision was made for the purpose of faster development iteration, but has proved to be a significant performance benefit as well. +\CFACC{} frequently needs to make deep clones of significant object graphs to ensure memory ownership (followed by eventual deletion of these clones), an unnecessarily time-consuming process. +The prototype, on the other hand, only needs to clone modified nodes, and can share identical subsets of the object graph. +The key design decision enabling this is that all subnodes are held by !const! pointer, and thus cannot be mutated once they have been stored in a parent node. +With minimal programming discipline, it can thus be ensured that any expression is either mutable or shared, but never both; the Dotty research compiler for Scala takes a similar architectural approach\cit{}. % this citation would be "personal correspondence" +The tree mutator abstraction is designed to take advantage of this, only creating new nodes if a node must actually be mutated. +I attempted to port this garbage collector to \CFACC{}, but without success. +The GC could be used for memory management with few changes to the codebase, but without a substantial re-write to enforce the same ``!const! children'' discipline \CFACC{} could not take advantage of the potential to share sub-objects; without sharing of sub-objects the GC variant of \CFACC{} must do all the same allocations and deletions and garbage-collector overhead degraded performance unacceptably (though it did fix some known memory leaks intoduced by failures of the existing manual memory management scheme). + +Another minor architectural difference between \CFACC{} and the prototype system is that \CFACC{} makes extensive use of the pointer-chasing !std::list!, !std::set!, and !std::map! data structures, while the prototype uses the array-based !std::vector! and the hash-based !unordered_! variants of !set! and !map! instead. \TODO{investigate performance difference by testing a resolver prototype variant with List etc. redefined} + +The final difference between \CFACC{} and the resolver prototype is that, as an experiment in language usability, the prototype performs resolution-based rather than unification-based assertion satisfaction, as discussed in Section~\ref{resn-conclusion-sec}. +This enables coding patterns not available in \CFACC{}, \eg{} a more flexible approach to type assertion satisfaction and better handling of functions returning polymorphic type variables that do not exist in the parameter list. +\TODO{test performance; shouldn't be too hard to change \texttt{resolveAssertions} to use unification} \section{Experimental Results} Index: doc/theses/aaron_moss_PhD/phd/resolution-heuristics.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/resolution-heuristics.tex (revision 0e6a0bebb41b45cf615f928ea49e1295870c1fc7) +++ doc/theses/aaron_moss_PhD/phd/resolution-heuristics.tex (revision 8d752592bd81177ff1ccdf30301e7555da9fcc43) @@ -326,5 +326,5 @@ As such, I opted to continue Bilson's approach of designing a bespoke solver for \CFA{} assertion satisfaction, rather than attempting to re-express the problem in some more general formalism. -\section{Conclusion \& Future Work} +\section{Conclusion \& Future Work} \label{resn-conclusion-sec} I have experimented with using expression resolution rather than type unification to choose assertion resolutions; this path should be investigated further in future work.